题意:在斐波那契数列( 1 ,1,2,3,5 ...... )中,第一个有1000位数字的是第几项?
思路:****滚动数组 + 大数加法
/*************************************************************************
> File Name: euler025.c
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年06月25日 星期日 11时24分33秒
************************************************************************/
#include <stdio.h>
#include <inttypes.h>
int32_t main() {
int32_t fib[3][1100] = {0}; // fib[][0] 记录该数组所代表数字的最大位数
fib[1][0] = fib[1][1] = 1;
fib[2][0] = fib[2][1] = 1;
int32_t number = 2 , idx1 , idx2 , idx3;
while( fib[ number % 3 ][0] < 1000 ) {
number++;
idx1 = (number - 2) % 3; // 依靠取模运算进行“滚动”,fib[idx1] < fib[idx2] < fib[idx3]
idx2 = (number - 1) % 3;
idx3 = number % 3;
for(int32_t i = 1 ; i <= fib[idx2][0] ; i++)
fib[idx3][i] = fib[idx2][i] + fib[idx1][i];
fib[idx3][0] = fib[idx2][0];
for(int32_t i = 1 ; i <= fib[idx3][0] ; i++) {
if( fib[idx3][i] >= 10 ){
fib[idx3][i+1] += fib[idx3][i] / 10;
fib[idx3][i] %= 10;
if( fib[idx3][0] < i + 1 ) fib[idx3][0] = i + 1;
}
}
}
printf("%d\n",number);
return 0;
}