Project Euler 25 1000-digit Fibonacci number

题意：在斐波那契数列（ 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;

}

巴特西

Project Euler 25 1000-digit Fibonacci number

最新文章

热门文章