批处理之家 - Powered by Discuz! Board

标题: [原创代码] 无忧公主项数定律 [打印本页]

作者: happy886rr 时间: 2016-4-9 17:50 标题: 无忧公主项数定律

本帖最后由 happy886rr 于 2016-4-10 21:13 编辑

　　关注无忧公主微信号之后，看到许多奇妙问题。有几个都是关于斐波那契数列的。这个数列到底有多奇妙？百度一下才知道：斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...，即后一项等于之前两项之和。也没感觉有多奇妙，就是个普通加法，而且它的定义很怪，第0项是0，第1项是第一个1。

　　但是无忧公主说了斐波那契数列第 12 项为 144，是第一个包含 3 个数字的斐波那契数。那第一个包含 1000 个数字的斐波那契数，它的项数是几？我们不妨把它叫做无忧公主项数。还是编程挑战题，限于自己只会批处理，bat模拟大数又太累，字符串也不能超过1024个，无奈跑到python自学网充了下电。

　　Cool!，原来python这么好用啊！一个len就能表示字符串位数，这下有解了。斐波那契数我只要一个劲的加，每次判断它的位数是不是等于1000，答案不就出来了。于是按照批处理的思路写了一个python，不管它语法规范不规范了，自己也不晓得。

# Python 解无忧公主的编程挑战004：第一个1000位的斐波那契数的项数是
F1=0;F2=1;n=1;l=1
while l<1000:
	Fn=F1+F2;F1=F2;F2=Fn;n+=1
	l=len(str(Fn))
print(n)
# 偶然发现使用 while F2<10**999: 来中断循环用时最省.
复制代码

　　运行结果是4782，到底对不对，于是又拼了一个python用来打印斐波那契数列和它的项数、位数。

# 斐波那契数项数与位数打印
print("斐波那契数Fn  项数n  位数")
F1=0;F2=1;n=1
while n<1000:
	Fn=F1+F2;F1=F2;F2=Fn;n+=1
	print(Fn,"(",n,",",len(str(Fn)),")")
复制代码

　　把结果保存到了txt，当我打开txt，Cool!，这些数字末端堆积的形状怎么看怎么像一条斜线。形状这么规则，不由得一惊。数字末端的位置不就是数字的长度吗，行号不就是项数吗。形状像条斜线，难不成是线性关系，无奈不会python绘图线性拟合，拿批处理线性拟合了一下，得到了一个近似关系：无忧公主项数=4.78*位数-2.39

　　只是近似线性关系，用这个近似公式每次求出来的结果和正确值比对不是差1就是差0，看来用数学无法描述它的准确关系。百度到python中int就可以取整，恍然大悟，用int就可以把小数部分引起的扰动过滤掉，这样就不会老是差1或不差。思路来了，最终用python结合特征根将这个线性扰动拟合描述出来了，发现网上没有任何资料介绍过这个奇妙关系。干脆起个名算了就叫 ”斐波那契-无忧公主项数定律“吧。

　　第一个L位的斐波那契数的项数N是：

# 斐波那契-无忧公主项数定律
N=int((L-1+0.5*math.log10(5))/math.log10((1+5**0.5)/2))+1

# 斐波那契位数估值式
L=int((N*math.log10((1+5**0.5)/2))-math.log10(5**0.5))+1
复制代码

　　这下就跳过了不断的加加+...，就有了最优解法，几乎不需时间。

# 线性拟合一行流
import math;L=1000;N=int((L-1+0.5*math.log10(5))/math.log10((1+5**0.5)/2)+1);print(N)
复制代码

作者: codegay 时间: 2016-4-9 23:21

本帖最后由 codegay 于 2016-4-10 00:32 编辑

这个题是欧拉计划，第25题。
注册后可以提交答案。

https://projecteuler.net/problem=25

python代码风格指南：pep8 中文翻译
http://my.oschina.net/u/1433482/blog/464444?p=1

作者: happy886rr 时间: 2016-4-9 23:41

回复 2# codegay
难道是无忧公主剽窃了欧拉计划的题目，我还以为是无忧公主出的题目。不过python确实太好用，感觉批处理智能化太低。

作者: CrLf 时间: 2016-4-9 23:41

XD

作者: codegay 时间: 2016-4-10 00:01

回复 3# happy886rr

-_-!她的题目来源应该是某些书上，
她好像有参加算法赛，应该也有算法赛的题目。

除了欧拉计划这类网站，还有一类是编程考试或者程序算法类的练习网站。

不过她的解题思路视频或者语音都是自己录的。

作者: happy886rr 时间: 2016-4-10 00:32

回复 5# codegay
听声音像是个小女孩，不知是不是女孩，还是幕后有个团队在运作。

作者: codegay 时间: 2016-4-10 00:36

回复 6# happy886rr

是小学生。大量的视频和录音都是她一个人。
而且英语很好.

教育条件很好，智商也很高。

作者: codegay 时间: 2016-4-10 03:04

#=
julia解欧拉计划025 1000-digit Fibonacci number.jl
2016年4月9日 15:33:05 codegay
两个方法解法一样，一个是比较字符数量，一个是比较数字大小。
=#

counter=1
a=big(0)
b=big(1)

while length(string(b))<1000
    a,b=b,a+b
    counter=counter+1
end
println(counter)
#=
4782
[Finished in 3.7s]
=#

function ff2()
    f1=big(0)
    f2=big(1)
    counter=1
    while f2<big(10)^999
        f1,f2=f2,f1+f2
        counter+=1
    end
    println(counter)
end

@time ff2()
#=
4782
  0.050925 seconds (90.95 k allocations: 4.712 MB, 54.44% gc time)
[Finished in 4.4s]
=#
复制代码

作者: happy886rr 时间: 2016-4-10 12:13

回复 8# codegay
批处理花了3分钟才算出来。进行了5000次数百位大数加法。

REM 解无忧公主的编程挑战004：第一个1000位的斐波那契数的项数是
@echo off&setlocal enabledelayedexpansion
set "Fa[1]=00000001"
set "Fb[1]=00000001"
for /l %%i in (2 1 125) do (
	set "Fa[%%i]=00000000"
	set "Fb[%%i]=00000000"
)
for /l %%n in (3 1 5000) do (
	set add=0
	for /l %%i in (1 1 125) do (
		set/a Fn[%%i]=1!Fa[%%i]!+1!Fb[%%i]!
		set/a tmp=Fn[%%i]+add
		set Fa[%%i]=!Fb[%%i]!
		set Fb[%%i]=!tmp:~1!
		if !tmp! geq 300000000 (set add=1) else (set add=0)
	)
	if not "!Fb[125]:~0,1!"=="0" (set/p =%%n&exit)
)
复制代码

作者: codegay 时间: 2016-4-10 12:21

回复 9# happy886rr

你们能拿批处理做大数运算的都太强。

作者: CrLf 时间: 2016-4-10 12:29

本帖最后由 CrLf 于 2016-4-10 12:52 编辑

回复 9# happy886rr

咳咳咳...还有更快的批处理吗？

@echo off&setlocal enabledelayedexpansion
set /a len=9,n[0]=1,n[1]=2
for /l %%n in (4 1 5000) do (
	set /a n[0]=n[1],n[1]+=!n[0]!
	if !n[1]! gtr 999999999 (
		set /a len+=1,n[0]/=10,n[1]/=10
		if !len!==1000 (set/p =%%n&exit)
	)
)
复制代码

怪异代码风采大赛参赛作品：

@echo off&setlocal enabledelayedexpansion
set /a len=9,n[0]=1,n[1]=2
(for /l %%n in (4 1 5000) do (
	set /a "n[0]=n[1],n[1]+=!n[0]!,1/^!((n[1]=last+n[0])/1000000000)"||(
		set /a "1/(1000-(len+=1)),n[0]/=10,n[1]/=10"||set/p =%%n&&exit
	)
))2>nul
复制代码

参赛作品2：

@echo off&setlocal enabledelayedexpansion
set /a len=9,n[0]=1,n[1]=2
(for /l %%n in (4 1 5000) do (
	set /a "n[0]=n[1],n[1]+=!n[0]!,1/((n[1]=last+n[0])/1000000000),len+=1,n[0]/=10,n[1]/=10"&&(
		if !len!==1000 set/p =%%n&&exit
	)
))2>nul
复制代码

作者: happy886rr 时间: 2016-4-10 12:52

回复 11# CrLf
斐波那契数列中的本福特定律：
以1为首位数字的数的出现机率约为总数的三成，接近期望值1/9的3倍。推广来说，越大的数，以它为首几位的数出现的就越低。
大师眼力非凡，一下就看到了捷径。这个方法应该是最佳方案，无需安装语言。速度居然还超过了python好几倍。

作者: CrLf 时间: 2016-4-10 14:05

本帖最后由 CrLf 于 2016-4-10 14:08 编辑

回复 12# happy886rr

本福特定律是顶楼方案，我这是只对头部相加，避开大数运算

作者: happy886rr 时间: 2016-4-10 14:32

本帖最后由 happy886rr 于 2016-4-10 14:35 编辑

回复 13# CrLf
大师这是用的失传已久的抛出错误。顶楼方案不是本福特，用的线性拟合。外加特征根推导出是黄金分割律的对数式。
您的只加头部基于的原理正好是本福特定律。因为开头的数字是5到9的可能性小。

作者: codegay 时间: 2016-4-10 14:44

不明觉厉

欢迎光临批处理之家 (http://www.bathome.net/)