文档介绍：神奇的斐波那契数列----------------------------精品word文档值得下载值得拥有----------------------------------------------?神奇的斐波那契数列?----------------------------精品word文档值得下载值得拥有--------------------------------------------------------------------------精品word文档值得下载值得拥有----------------------------------------------斐波那契数列指的是这样一个数列:1、1、2、3、5、8、13、21、……这个数列从第三项开始~每一项都等于前两项之和。它的通项公式为:(1/?5)*{[(1+?5)/2]^n-[(1-?5)/2]^n},又叫“比内公式”~是用无理数表示有理数的一个范例。,,?5表示根号5,有趣的是:这样一个完全是自然数的数列~通项公式居然是用无理数来表达的。----------------------------精品word文档值得下载值得拥有--------------------------------------------------------------------------精品word文档值得下载值得拥有----------------------------------------------【奇妙的属性】随着数列项数的增加~……从第二项开始~每个奇数项的平方都比前后两项之积多1~每个偶数项的平方都比前后两项之积少1。,注:奇数项和偶数项是指项数的奇偶~而并不是指----------------------------精品word文档值得下载值得拥有--------------------------------------------------------------------------精品word文档值得下载值得拥有----------------------------------------------数列的数字本身的奇偶~比如第五项的平方比前后两项之积多1~第四项的平方比前后两项之积少1,如果你看到有这样一个题目:某人把一个8*8的方格切成四块~拼成一个5*13的长方形~故作惊讶地问你:为什么64,65,其实就是利用了斐波那契数列的这个性质:5、8、13正是数列中相邻的三项~事实上前后两块的面积确实差1~只不过后面那个图中有一条细长的狭缝~一般人不容易注意到。斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。----------------------------精品word文档值得下载值得拥有--------------------------------------------------------------------------精品word文档值得下载值得拥有----------------------------------------------斐波那契数列,f(n)~f(0)=0~f(1)=1~f(2)=1~f(3)=2……,的其他性质:(0)+f(1)+f(2)+…+f(n)=f(n+2)-(1)+f(3)+f(5)+…+f(2n-1)=f(2n)-(0)+f(2)+f(4)+…+f(2n)=f(2n+1)-14.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)?f(n+1)----------------------------精品word文档值得下载值得拥有--------------------------------------------------------------------------精品word文档值得下载值得拥有----------------------------------------------(0)-f(1)+f(2)-…+(-1)^n?f(n)=(-1)^n?[f(n+1)-f(n)]+(m+n)=f(m-1)?f(n-1)+f(m)?f(n)利用这一点~可以用程序编出时间复杂度仅为O,logn,的程序。7.[f(n)]^2=(-1)^(n-1)+f(n-1)?f(n+1)(2n-1)=[f(n)]^2-[f(n-2)]^(n)=f(n+2)+f(n-2)(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m)[n〉m?-1,且n?1]--------------------