详细题目如下题目
一千位斐波那契数
斐波那契数列是按如下递归关系定义的数列:
F1 = 1 F2 = 1
Fn = Fn−1 + Fn−2
因此斐波那契数列的前12项分别是:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
第一个有三位数字的项是第12项F12。
在斐波那契数列中,第一个有1000位数字的是第几项?
其实我们就需要解决两个问题
- 如何使用循环数组解决斐波那契数列问题
- 如何实现大整数相加
代码如下
/************************************************************************* > File Name: try.2.c > Author:Gin.TaMa > Mail:1137554811@qq.com > Created Time: 2019年01月06日 星期日 19时00分50秒 ************************************************************************/
#include<stdio.h>
#define max 1000
int Fib[2][max + 5] = {
0};
void add(int * a,int * b){
b[0] = b[0] > a[0] ? b[0]:a[0];
for(int i = 1;i <= b[0];i ++){
b[i] += a[i];
// 完成大整数的相加 处理进位
if(b[i] < 10)continue;
b[i + 1] += b[i] / 10;
b[i] %= 10;
}
if(b[b[0] + 1])b[0]++;
}
int main(){
int n = 0;
Fib[0][0] = Fib[1][0] = 1;
Fib[0][1] = 1;
while(Fib[(n+1) % 2][0] < 1000){
n ++;
add(Fib[n%2],Fib[(n + 1)%2]);
}
printf("%d\n",n);
}
大整数相加还是很好实现的,在相加的同时处理一下进位问题就OK了
这个问题的关键是在循环数组与n的对应关系上
就是这个题目最后是输出n还是n+1还是n+2
不要被% 2的运算迷惑了,本质上循环数组就用%运算模拟了一个完整的数组
只不过这个n取决与初始的定义
我是定义 n = 0时 对应的数列为值为F0的值 0
所以当循环结束的时候指向的就是第n项
没有对比就没有意思
这样
看另一份代码
int main(){
int n = 0;
Fib[0][0] = Fib[1][0] = 1;
Fib[0][1] = 1;
Fib[1][1] = 2;//修改部分
while(Fib[(n+1) % 2][0] < 1000){
n ++;
add(Fib[n%2],Fib[(n + 1)%2]);
}
printf("%d\n",n+3);//结果调整
}
我修改了定义 n=0的时候判断的F3
所以最后就输出n+3