?

[定理1] 標準Fibonacci序列（即第0項為0，第1項為1的序列）當N大于1時，一定有f(N)和f(N-1)互質

其實，結合“互質”的定義，和一個很經典的算法就可以輕松證明?
對，就是輾轉相除法?
互質的定義就是最大公約數為1

數學歸納法是很有用的證明方法，我們接下來這個定理用數學歸納法就很好證明：?
[定理2]若i為奇數， f(i)*f(i)=f(i-1)*f(i+1)+1，否則f(i)*f(i)=f(i-1)*f(i+1)-1?
對，這個定理用數學歸納法可以輕松證明，大家有興趣可以自己嘗試

[定理3] f(n)=f(i)*f(n-i-1)+f(i+1)*f(n-i)

f(n)=f(1)*f(n-2)+ f(2)*f(n-1)?
??? =f(2)*f(n-3)+ f(3)*f(n-2)?
??? =f(3)*f(n-4)+ f(4)*f(n-3)?
看來沒有錯，證明方法就是這樣

這個公式也可以用來計算較大的fibonacci數除以某個數的余數

設i=n/2 不過，為了保證計算能延續下去 需要每次保留三個值?
這樣，下一次計算就可以利用這三個值來求出兩個值，再相加就可以得到第三個值?
譬如，計算出f(5),f(6),f(7)，可以計算出f(11)、f(12)，然后推出f(13)?
就是剛才洛奇的悲鳴(364738334)所提到的矩陣方法?
我們知道我們若要簡單計算f(n)，有一種方法就是先保存?
a=f(0),b=f(1)，然后每次設：?
a'=b b'=a+b

并用新的a'和b'來繼續這一運算

如果大家熟悉利用“矩陣”這一工具的話，就知道，如果把a、b寫成一個向量[a,b]，完成上述操作相當于乘以矩陣
0 1?
1 1?
也就是說，如果我們要求第100個fibonacci數，只需要將矩陣?
[0,1]乘上?
0 1?
1 1?
的一百次方，再取出第一項

因為我們知道，矩陣運算滿足結合律，一次次右乘那個矩陣完全可以用乘上那個矩陣的N次方代替，更進一步，那個矩陣的N次方就是這樣的形式：?
f(n-1) f(n)?
f(n) f(n+1)

而求矩陣的N次方，由于矩陣乘法滿足結合律，所以我們可以用log(N)的算法求出——這個算法大家都會么？?
一個是二分，一個是基于二進制的求冪

二分的原理：要求矩陣的N次方A(N)，設i=N/2若N%2==1， 則 A(N)=A(i)*A(i)*A(1)若N%2==0， 則 A(N)=A(i)*A(i)

基于二進制的原理：將N拆為二進制數，譬如13=1101那么 A^13= A^8 * A^4 * A^1 （這里^表示冪運算）

也就是說，由A^1開始，自乘得到A^2，然后自乘得到A^4，如果N對應位為1，則將這個結果乘到目標上去

這樣的話，將所有乘法改為模乘，就可以得到一個較大Fibonacci數除以M的余數

若不用遞歸，其實類似

http://acm.pku.edu.cn/JudgeOnline/problem?id=3070?
這里用的fib矩陣略有不同，是?
f(n+1) f(n)?
f(n) f(n-1)?
但實際上可以驗證效果是一樣的

這題是要求求F(n)的最后四位數，所有乘法過程增加一個模10000的步驟即可，大家可以收藏稍候AC

關于矩陣我們告一段落，等下會回來繼續探討利用矩陣來解決復雜些的Fibonacci問題

http://acm.hdu.edu.cn/showproblem.php?pid=1568?
我們來看這題，這題要求求出Fibonacci某項的前四位

當然，用矩陣也可以解決這道題——只要將乘法改為乘并保留前四位

我們采用double 保留整數部分四位 這題最好還是double吧

不過顯然有更好的解法——如果我們知道Fibonacci序列的通項公式

F(n) = (((1+Sqrt(5))/2)^n - ((1-Sqrt(5))/2)^n)*1/Sqrt(5)

不過組合數學里也有這一公式的推導方法 叫做“線性齊次遞推式”

這個解法的核心是，通解是某個數的冪 將f(n)=x^n代入遞推方程，可以解出三個通解 0和 (1+sqrt(5))/2

通常把“0”稱作平凡解，那么特解就是通解的某個線性組合

再代入f(0)=0 f(1)=1，就可以得出我們剛才的公式

不過通常情況下，我們只需要記住那個公式就可以了

提醒大家，記憶公式的時候千萬別忘記了系數1/sqrt(5)

因為(1-sqrt(5))/2的絕對值小于1

所以當i較大的時候，往往可以忽略掉這一項?
f(i)≈((1+Sqrt(5))/2)^n/sqrt(5);

所以，剛才列舉出的HDOJ的1568，可以很簡單的30以內直接求解，30以上采用這個公式，還是用log(N)求冪的算法求解?
恩，就是公式的前半部分

http://acm.hdu.edu.cn/showproblem.php?pid=1021?
或? http://acm.zju.edu.cn/show_problem.php?pid=2060?
Fibonacci某項是否被3整除

[定理5] 標準Fibonacci序列對任意大于2的正整數的余數序列，必然是以“0 1”為循環節開頭的序列

顯然0、1是序列開頭，也就是說序列開頭就是循環節開頭

循環長度的計算貌似是個比較難的問題，我一時還沒有想到有效解法，不過，要說明的是，計算復雜度時，這個循環節長度應該按復雜度O(N^2)計算

恩，證明方法是利用同余定理、反證法，還有我們之前證明過的相鄰項一定互質的定理，留給大家家庭作業

http://acm.hdu.edu.cn/showproblem.php?pid=1588?
這是前天比賽關于Fibonacci的一道題，大家先看看題。?
Description看后半部分就行了

現在告訴大家一種正確解法，然后大家就可以去搞定這道題向別人炫耀了

首先，我們將問題整理一下，就是對等差數列 ai=k*i+b，求所有的f(ai)之和除以M的余數

當0<=i<N

大家有沒有想到，因為ai是等差數列，倘若f(ai)也是個等什么序列，那說不定就有公式求了

f(ai)顯然不是等差數列，直接看上去也不是等比數列

但是如果把f(ai)換成我們剛才所說的Fibonacci矩陣呢？

是的，可是我們對矩陣是直接求冪即可，由于矩陣加法的性質，我們要求A^ai的右上角元素之和，只要求A^ai之和的右上角元素

就矩陣這個東西來說，完全可以看作一個等比數列，?
首項是：A^b?
公比是：A^k?
項數是：N

呵呵，我們可以把問題進一步簡化

因為矩陣的加法對乘法也符合分配律，我們提出一個A^b來，形成這樣的式子：?
A^b*( I + A^k + (A^k)^2 + .... + (A^k)^(N-1) )

A^b 和 A^k 顯然都可以用我們之前說過的方法計算出來，這剩下一部分累加怎么解決呢

簡單起見，設A^k=B?
要求 G(N)=I + ... + B^(N-1)，設i=N/2?
若N為偶數，G(N)=G(i)+G(i)*B^i?
若N為奇數，G(N)=I+ G(i)*B + G(i) * (B^(i+1))

呵呵，這個方法就是比賽當時ACRush用的?
而農夫用的則是更精妙的方法，大家可想知道

我們來設置這樣一個矩陣?
B I?
O I?
其中O是零矩陣，I是單位矩陣

將它乘方，得到?
B^2 I+B?
O?? I?
乘三方，得到?
B^3 I+B+B^2?
O?? I?
乘四方，得到?
B^4 I+B+B^2+B^3?
O?? I

既然已經轉換成矩陣的冪了，繼續用我們的二分或者二進制法，直接求出冪就可以了

http://online-judge.uva.es/p/v110/11089.html?
大家來讀讀這一題

Fibinary數是指沒有相鄰的兩個1的二進制數。給N，求出第N大的Fibinary數

相對于二進制中每一位的值是2的冪，十進制中每一位的值是十的冪，?
Fibonacci進制是每一位的值是對應Fibonacci數的一種計數系統。?
???? 8 5 3 2 1?
1?????1?
2?????1 0?
3?????1 0 0?
4?????1 0 1?
5?????1 0 0 0?
6?????1 0 0 1?
7?????1 0 1 0?
8???? 1 0 0 0 0?
9???? 1 0 0 0 1?
10?? 1 0 0 1 0?
11?? 1 0 1 0 0?
12?? 1 0 1 0 1?
以上是前12個數字對應的十進制到Fibonacci進制的表格

Fibonacci的運算方法很奇怪。首先，它每一位上非0即1，而且不同于二進制的逢二進一或者十進制的逢十進一，它的進位方法是逢連續兩個1，則進1

譬如?
1010110==> 1011000 ==> 1100000==>10000000

在最低位有個特殊情況，最低位既可以逢2進1，也可以和次低位一起逢相鄰進1?
這種奇怪的進位方法，換句話描述就是，不存在兩個連續的1?
因為Fibonacci數其實也增長很快，int范圍內好像只有46個，本題只需要用最簡單的辦法轉換成Fibonacii進制即可?
其中一題是?
http://www.mydrs.org/program/down/?ahoi2004da?y1.pdf?
中的第二題，叫做數字迷陣?
還有一題是PKU上的很出名?的取石子問題?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1067

這題相當復雜，大家可以自己思考，往Fibonacci上想，也可以閱讀這里的論文：?
http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/index.html?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2967

另外這題 可以利用Fibonacci判斷數據范圍進行優化設計。不過貌似可以水過去，僅僅給大家提供個思路罷

關于Fibonacci和黃金分割，還有很多更高明的結論和定理，希望大家也繼續討論，將自己的知識和他人共享?
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/index.html?
中例3詳細講述了用生成函數來計算Fibonacci數公式的運算過程。 http://acm.hdu.edu.cn/showproblem.php?pid=1568?
Fibonacci 求fibonacci前4位

http://acm.hdu.edu.cn/showproblem.php?pid=1588?
Gauss Fibonacci?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1067?
取石子問題?
http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/index.html? 是報告?
http://acm.pku.edu.cn/JudgeOnline/problem?id=3070?
Fibonacci矩陣?
http://acm.hdu.edu.cn/showproblem.php?pid=1021?
或?
http://acm.zju.edu.cn/show_problem.php?pid=2060?
Fibonacci某項是否被3整除?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2116?
Fibonacci進制計算?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2967?
利用Fibonacci判斷數據范圍進行優化設計。?
http://online-judge.uva.es/p/v110/11089.html?
Fi-binary numbers，Fibonacci進制。?
http://www.mydrs.org/program/down/ahoi2004day1.pdf?
第二題 數字迷陣?? 這些，是今天涉及到的資料和網頁