斐波那契数列（Fibonacci sequence），又称黄金分割数列，因意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89..，这个数列从第3项开始，每一项都等于前两项之和。
在数学上，斐波那契数列以如下递推的方法定义：
F(0)=0，F(1)=1, F(n)=F(n – 1)+F(n – 2)（n ≥ 2，n ∈ N*）。
其通项公式为F(n)=
当所求的n值较大时，可以构造一个矩阵，利用矩阵乘法完成斐波那契数列递推的运算。如下所示。
【例1】斐波那契数列
问题描述
斐波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数是多少。
输入
每个测试用例由单行中的一个整数n组成，其中0≤n≤50.输入以-1终止。
输出
每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第n个数的大小。
输入样例
3
4
5
-1
输出样例
2
3
5
（1）编程思路。
由于题目只涉及到斐波那契数列的前50项，因此可以定义一个数组long long f[51]，直接采用递推的办法将数列前50项的值求出来并保存。
（2）源程序。
#include int main(){ long long f[51]={0,1}; for (int i=2;i<=50;i++) f[i]=f[i-1]+f[i-2]; int n; while (scanf("%d",&n) && n!=-1) { printf("%lld\n",f[n]); } return 0;}
将上面的源程序提价给HDU 题库HDU 2070 Fibbonacci Number （http://acm.hdu.edu.cn/showproblem.php?pid=2070），可以Accepted。
【例2】还是斐波那契数列
问题描述
大家都知道，斐波那契数列是满足如下性质的一个数列：
F(n)=1 (n≤2)
F(n)=F(n−1)+F(n−2) (n≥3)
请你求出 F(n) mod 109 +7 的值。
输入
一行一个正整数n(1≤n<263)
输出
输出一行一个整数表示答案。
输入样例
5
输出样例
5
（1）编程思路。
由于n值最大可到263，因此直接用递推的方式效率太低。构造一个矩阵，采用矩阵快速幂运算进行求解。
（2）源程序。
#include #define MODNUM 1000000007struct Matrix { long long s11 , s12 , s21 , s22 ;};typedef struct Matrix matrix;matrix f(matrix a,matrix b){ matrix p ; p.s11 = (a.s11*b.s11 + a.s12*b.s21)%MODNUM; p.s12 = (a.s11*b.s12 + a.s12*b.s22)%MODNUM; p.s21 = (a.s21*b.s11 + a.s22*b.s21)%MODNUM; p.s22 = (a.s21*b.s12 + a.s22*b.s22)%MODNUM; return p ;}matrix quickpow(matrix p,long long n) // 采用递归的方法实现矩阵快速幂运算{ matrix q ; q.s11 = q.s22 = 1 ; // 初始化为单位矩阵 q.s12 = q.s21 = 0 ; if (n == 0) return q ; q = quickpow(p,n/2); q = f(q,q); if (n%2) q = f(q,p); return q ;}int main(){ long long n ; matrix p ; scanf("%lld", &n); p.s11 = p.s12 = p.s21 = 1 ; p.s22 = 0 ; p = quickpow(p,n); printf("%lld\n", p.s12); return 0;}
将上面的源程序提价给洛谷题库P1962 斐波那契数列 （https://www.luogu.com.cn/problem/P1962），可以Accepted。
【例3】Fibonacci的数字
问题描述
经过一年的努力，数学神童zouyu终于把0到100000000的Fibonacci数列
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，zouyu就要把答案说出来，不过有的数字太长了。所以规定超过8位的只要说出前4位和后4位就可以了。
输入
输入若干数字n(0 <= n <= 100000000)，每个数字一行。读到文件尾。
输出
输出f[n]的前4个数字和后4个数字（若不超过8个数字，就全部输出）。
输入样例
0
1
35
39
40
65
输出样例
0
1
9227465
63245986
1023…4155
1716…7565
（1）编程思路。
通过输入输出样例可知，当n的值超过39时，斐波那契数列的位数不超过8位。因此先定义一个数组int f[41]，通过递推的方法直接将n<40时f[n]的值求出并保存，若输入的n值小于40，直接输出求得的f[n]值。
当n值较大时，f[n]的位数超过了8位。求后4位比较容易，采用求10000的模即可，使用矩阵快速幂运算来完成，参见上面的例2。
前4位不同于后4位，要考虑进位问题，不能直接取模。将每个f[n]求出来，无论时间复杂度还是空间复杂度都要求太高。
我们知道，斐波那契数列第n项F[n]的通项公式是
将公式两端取对数可得
其中第三部分非常小，当n很大时趋近于0，可以忽略掉。
再由求得的log10(F[n])求出其高4位。具体方法以f[40]为例说明。
f[40]=102334155
log10(102334155)=log10(1.02334155*108)=log10(1.02334155)+8，
取其小数部分 log10(1.02334155)=0.0100206078，
10^0.0100206078=1.02334155，结果乘以1000取整，即为高4位1023。
（2）源程序。
#include #include typedef struct{ int s11 , s12 , s21 , s22 ;}Matrix;Matrix f(Matrix a,Matrix b){ Matrix p ; p.s11 = (a.s11*b.s11 + a.s12*b.s21)%10000; p.s12 = (a.s11*b.s12 + a.s12*b.s22)%10000; p.s21 = (a.s21*b.s11 + a.s22*b.s21)%10000; p.s22 = (a.s21*b.s12 + a.s22*b.s22)%10000; return p ;}Matrix quickpow(Matrix p,int n) // 采用递归的方法实现矩阵快速幂运算{ Matrix q ; q.s11 = q.s22 = 1 ; // 初始化为单位矩阵 q.s12 = q.s21 = 0 ; if (n == 0) return q ; q = quickpow(p,n/2); q = f(q,q); if (n%2) q = f(q,p); return q ;}int main(){ int f[51]={0,1,1},i; for (i=3;i<=40;i++) { f[i]=f[i-1]+f[i-2]; } int n; while (scanf("%d",&n)!=EOF) { if (n<=39) printf("%d\n", f[n]); else { Matrix p ; p.s11 = p.s12 = p.s21 = 1 ; p.s22 = 0 ; p = quickpow(p,n); double s = log10(1.0 / sqrt(5.0)) + n * log10((1 + sqrt(5.0)) / 2); s -= (int)(s); s = pow(10, s); while (s < 1000) s *= 10; printf("%d...%04d\n", (int)(s),p.s12); } } return 0;}
将上面的源程序提价给HDU题库HDU 3117Fibonacci Numbers （http://acm.hdu.edu.cn/showproblem.php?pid=3117），可以Accepted。
HDU题库中的 HDU 1568 Fibonacci （http://acm.hdu.edu.cn/showproblem.php?pid=1568）只要求求出f[n]的高4位，将上面的程序进行简化如下，提交后同样可以Accepted。
#include #include int main(){ int f[41]={0,1,1},i,len; for (i=3;i<=40;i++) { f[i]=f[i-1]+f[i-2]; } int n; while (scanf("%d",&n)!=EOF) { if (n<=20) printf("%d\n", f[n]); else { double s = log10(1.0 / sqrt(5.0)) + n * log10((1 + sqrt(5.0)) / 2); s -= (int)(s); s = pow(10, s); while (s < 1000) s *= 10; printf("%d\n", (int)(s)); } } return 0;}
【例4】有多少个斐波那契数
问题描述
输入两个整数a和b，求这两个数中间有多少个斐波那契数。
输入
输入包含几个测试用例。每个测试用例由两个非负整数a和b组成。输入以a=b=0终止。a<=b<=10100。数字a和b没有多余的前导零。
输出
对于每个测试用例，用单独一行输出Fibonacci数fi（a<=fi<=b）的数量。
输入样例
10 100
1234567890 9876543210
0 0
输出样例
5
4
（1）编程思路1。
先预先计算一下，斐波那契数列第480项的数字位数将达到100位，因此可以用字符串数组将斐波那契数列中前480项的数计算出来并保存下来。计算时采用高精度加法运算即可。显然这个字符串数组是按数字升序排列的。对于输入的字符串a和b，可以通过二分查找得到一个区间[left,right]使得第left个斐波那契数刚好大于a，第right+1个斐波那契数刚好大于b，这样left~right间斐波那契数的个数就是所求，注意第right个数刚好等于b时需要加1个。
（2）源程序1。
#include #include <string.h>#define MAXLEN 110#define LAST MAXLEN-2char fib[481][MAXLEN]; // 存储480个斐波那契数void bigNumAdd(char a[],char b[],char c[]){ int i,j,n1,n2,n; int num1[MAXLEN]={0},num2[MAXLEN]={0}; // 将a和b中存储的字符串形式的整数转换到num1和num2中去， // num1[0]对应于个位、num1[1]对应于十位、…… n1 = strlen(a); j = 0; for (i = n1 - 1;i >= 0 ; i --) num1[j++] = a[i] - '0'; n2 = strlen(b); j = 0; for (i = n2 - 1;i >= 0 ; i --) num2[j++] = b[i] - '0'; n=n1>n2?n1:n2; for (i = 0;i < n ; i ++ ) { num1[i] += num2[i]; // 逐位相加 if (num1[i] >= 10 ) // 处理进位 { num1[i] -= 10; num1[i+1] ++; } } j=0; if (num1[n]!=0) c[j++]=num1[n]+'0'; for(i=n-1; i>=0; i--) c[j++]=num1[i]+'0'; c[j]='\0';}int compare(char *a, char *b){ int lenA = strlen(a); int lenB = strlen(b); if (lenA == lenB) { return strcmp(a, b); } return lenA>lenB ? 1 : -1;}int binSearch(char *num, int *flag){ int left,right,mid,res; left = 1; right= 480; while (left <= right) { mid = (left + right)/2; res = compare(num, fib[mid]); if (res == 0) { *flag = 1; return mid; } else if (res < 0) { right = mid - 1; } else { left = mid + 1; } } return left;}int main(){ int i; strcpy(fib[0], "1"); strcpy(fib[1], "1"); strcpy(fib[2], "2"); for (i = 3; i <485; i++) { bigNumAdd(fib[i-2],fib[i-1],fib[i]); } char a[MAXLEN], b[MAXLEN]; while (1) { scanf("%s%s",a,b); if (strcmp(a, "0") == 0 && strcmp(b, "0") == 0) break; int flagLeft = 0; int flagRight = 0; //分别找出a和b在斐波那契数中的位置 //当查找的数不是斐波那契数时，二分查找返回的位置是第一个比它大的斐波那契数的位置 int left = binSearch(a, &flagLeft); int right = binSearch(b, &flagRight); //当b也是斐波那契数时，要把两位置的差值加1 if (flagRight) { printf("%d\n", right - left + 1); } else { printf("%d\n", right - left); } } return 0;}
（3）编程思路2。
上面的源程序1是采用字符串数组来保存各斐波那契数。也可以用整数数组来保存斐波那契数。每个数组元素保留一个斐波那契数中的8位数字。定义一个结构体
struct BigNumber来表示大整数。然后编写大整数的高精度加法运算程序即可。
（4）源程序2。
#include #include <string.h>#define MOD 100000000struct BigNumber{ int len; int num[15];};struct BigNumber change(char s[]){ struct BigNumber res; memset(res.num,0,sizeof(res.num)); int i,len=0,k=0,p=1,num=0; for (i=strlen(s)-1;i>=0;i--) { num=num+(s[i]-'0')*p; p=p*10; k++; if (k%8==0) { res.num[len++]=num; num=0; p=1; } } if (strlen(s)%8!=0) res.num[len++]=num; res.len=len; return res;}int cmp(struct BigNumber a,struct BigNumber b) // 比较a,b大小，若a>b返回1，a=b返回0,a<b返回-1{ if (a.len!=b.len) { if (a.len<b.len) return -1; else return 1; } int i; for (i=a.len-1;i>=0;i--) if (a.num[i]!=b.num[i]) { if (a.num[i]<b.num[i]) return -1; else return 1; } return 0;}int main(){ struct BigNumber f[481]; memset(f[1].num,0,sizeof(f[1].num)); memset(f[2].num,0,sizeof(f[2].num)); f[1].len=f[2].len=1; f[1].num[0]=1; f[2].num[0]=2; int i,j; for (i=3;i<=480;i++) { memset(f[i].num,0,sizeof(f[i].num)); f[i].len = f[i-1].len; int cf=0; for (j=0;j<f[i].len;j++) { int num=f[i-1].num[j]+f[i-2].num[j]+cf; f[i].num[j]=num%MOD; cf=num/MOD; } if (cf!=0) f[i].num[f[i].len++]=cf; } char a[105],b[105]; while (scanf("%s%s",a,b) && (a[0]!='0' || b[0]!='0')) { struct BigNumber x,y; x=change(a); y=change(b); int left,right,t; for (i=1;i<=480;i++) { t=cmp(x,f[i]); if (t<=0) { left=i-1; break; } } for (i=left-1;i<=480;i++) { t=cmp(y,f[i]); if (t!=-1) right=i+1; } printf("%d\n",right-left-1); } return 0;}
将上面的两个源程序分别提交给HDU题库 HDU 1316 How Many Fibs? （http://acm.hdu.edu.cn/showproblem.php?pid=1316）或北大POJ题库POJ 2413 How many Fibs? （http://poj.org/problem?id=2413），均可以Accepted。
【例5】斐波那契的拆分
问题描述
已知任意一个正整数都可以拆分为若干个斐波纳契数，现在，让你求出n的拆分方法。
输入
一个数t，表示有t组数据
接下来t行，每行一个正整数n（1<=n<=10^9）。
输出
t行，每行一个字符串，表示拆分方法（格式:n=a1+a2+a3+..+an），要求从小到大输出。若有多组数据，以个数最小的为准，若仍有多组，输出右边尽量大的一组
输入样例
1
10
输出样例
10=2+8
（1）编程思路。
将前45项斐波那契数计算并保存在数组fib中。之后拆分n时，从数组的最后一个元素fib[45]开始试探直到fib[1]，若n大于或等于某个fib[i]，则fib[i]肯定会出现在拆分式中，保存fib[i]，并从n中减去fib[i]。
（2）源程序。
#include int main(){ int i; int fib[46]={0,1,1},a[51]; for (i=3;i<46;i++) fib[i]=fib[i-1]+fib[i-2]; int t; scanf("%d",&t); while (t--) { int n; scanf("%d",&n); printf("%d=",n); int len=0; for (i=45;i>=1;i--) { if (fib[i]=0) { n-=fib[i]; a[len++]=fib[i]; } } printf("%d",a[len-1]); for (i=len-2;i>=0;i--) { printf("+%d",a[i]); } printf("\n"); } return 0;}
将上面的源程序提交给洛谷题库P1755 斐波那契的拆分 （https://www.luogu.com.cn/problem/P1755），可以Accepted.
在HDU题库中下列几道题目就与斐波那契数列有关，可以作为练习做一做。
【练习1】HDU 1021 Fibonacci Again （http://acm.hdu.edu.cn/showproblem.php?pid=1021）。
#include #include int main(){ int a[8]={1,2,0,2,2,1,0,1}; int n; while (scanf("%d",&n)!=EOF) { if (a[n%8]!=0) printf("no\n"); else printf("yes\n"); } return 0;}
参考程序
【练习2】HDU 1250 Hat’s Fibonacci （http://acm.hdu.edu.cn/showproblem.php?pid=1250）。
#include #include <string.h>#define MOD 100000000struct BigNumber{ int len; int a[281];};struct BigNumber add(struct BigNumber x,struct BigNumber y){ struct BigNumber z; memset(z.a,0,sizeof(z.a)); z.len=x.len>y.len?x.len:y.len; int i,cf=0; for (i=0;i<z.len;i++) { z.a[i]=x.a[i]+y.a[i]+cf; cf=z.a[i]/MOD; z.a[i]=z.a[i]%MOD; } if (cf!=0) z.a[z.len++]=cf; return z;}void print(struct BigNumber x){ int i; printf("%d",x.a[x.len-1]); for (i=x.len-2;i>=0;i--) printf("%08d",x.a[i]); printf("\n");}struct BigNumber f[7505]={0};int main(){ struct BigNumber t; memset(f[1].a,0,sizeof(f[1].a)); memset(f[2].a,0,sizeof(f[2].a)); memset(f[3].a,0,sizeof(f[3].a)); memset(f[4].a,0,sizeof(f[4].a)); f[1].len=f[1].a[0]=1; f[2].len=f[2].a[0]=1; f[3].len=f[3].a[0]=1; f[4].len=f[4].a[0]=1; int i; for (i=5;i<=7500;i++) { t=add(f[i-4],f[i-3]); t=add(t,f[i-2]); t=add(t,f[i-1]); f[i]=t; } int n; while (scanf("%d",&n)!=EOF) { print(f[n]); } return 0;}
参考程序
【练习3】HDU 1708 Fibonacci String （http://acm.hdu.edu.cn/showproblem.php?pid=1708）。
#include #include <string.h>int main(){ int t; scanf("%d",&t); while (t--) { long long a1[27],a2[27],temp[27]; memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2)); char s0[31],s1[31]; int n; scanf("%s%s%d",s0,s1,&n); int i,j; for (i=0;s0[i]!='\0';i++) a1[s0[i]-'a']++; for (i=0;s1[i]!='\0';i++) a2[s1[i]-'a']++; for (i=2;i<=n;i++) { for (j=0;j<26;j++) { temp[j]=a2[j]; a2[j]+=a1[j]; a1[j]=temp[j]; } } if(n==0) { for (i=0;i<26;i++) a2[i]=a1[i]; } for(i=0;i<26;i++) { printf("%c:%lld\n",i+'a',a2[i]); } printf("\n"); } return 0;}
参考程序
【练习4】HDU 3306 Another kind of Fibonacci （http://acm.hdu.edu.cn/showproblem.php?pid=3306）。
#include #include <string.h>#define MOD 10007struct Matrix{ int mat[5][5]; // 存储矩阵中各元素};Matrix matMul(Matrix a ,Matrix b,int n){ Matrix c; memset(c.mat,0,sizeof(c.mat)); int i,j,k; for (k = 1; k<=n ; k++) for (i=1 ;i<=n ; i++) if (a.mat[i][k]!=0) for (j = 1 ;j<=n ;j++) c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD; return c;}Matrix quickMatPow(Matrix a ,int n,int b) // n阶矩阵a快速b次幂{ Matrix c; memset(c.mat ,0 ,sizeof(c.mat)); int i; for (i = 1 ;i <= n ;i++) c.mat[i][i] = 1; while (b!=0) { if (b & 1) c = matMul(c ,a ,n); // c=c*a; a = matMul(a ,a ,n); // a=a*a b /= 2; } return c;}int main(){ int n,x,y,ans; Matrix p; while(scanf("%d%d%d" ,&n ,&x ,&y)!=EOF) { x = x%MOD; y = y%MOD ; if (n==2) printf("%d\n" ,(x*x%MOD+y*y%MOD+2*x*y%MOD+2)%MOD) ; else { memset(p.mat,0,sizeof(p.mat)); p.mat[1][1]=p.mat[3][2]=1; p.mat[1][2]=p.mat[2][2]=(x*x)%MOD; p.mat[1][3]=p.mat[2][3]=(y*y)%MOD; p.mat[1][4]=p.mat[2][4]=(2*x*y)%MOD; p.mat[4][2]=x; p.mat[4][4]=y; p = quickMatPow(p,4,n-1); ans=(p.mat[1][1]*2%MOD+p.mat[1][2]+p.mat[1][3]+p.mat[1][4])%MOD; printf("%d\n" ,ans); } } return 0; }
参考程序
【练习5】HDU 5018 Revenge of Fibonacci （http://acm.hdu.edu.cn/showproblem.php?pid=5018）。
#include int main(){ int t; scanf("%d",&t); while (t--) { long long a,b,c,x; scanf("%lld%lld%lld",&a,&b,&x); if (x==a || x==b) { printf("Yes\n"); continue; } while (1) { c=a+b; if (c>=x) break; a=b; b=c; } if (c==x) printf("Yes\n"); else printf("No\n"); } return 0;}
参考程序