프로젝트 오일러 25

피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?

배열을 사용한 덧셈, 곱셈 함수는 계속 만들게 되는듯.
문제를 풀다 보니 약간의 요령이 생기게 되었다.

실행시간을 측정해 본다. 너무 길다 싶으면.. 답을 구하기에는 부적합한 알고리즘.
알고리즘을 짰으면, 작은 케이스의 값으로 검증을 몇 번 해본다. 한번에 맞춘다는게 쉬운게 아니니까..

/*
	 Problem 25 : FIND-digit Fibonacci number
*/

#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <string.h>

#include <ctime>

using namespace std;

void sum( int a[], int b[], int result[], int max)
{
	for(int i=0; i<max; i++)
	{
		int s = a[i] + b[i];

		result[i] += s;

		if( result[i] >= 10) {
			result[i+1] += result[i]/10;
			result[i] = result[i]%10; 
		}
	}
	cout << "sum=";
	for(int i=max-1; i>=0; i--)
	{
		cout << result[i];
	}
	cout << endl;
}

int digit( int arr[], int max)
{
	max++;
	for(int i=max-1; i>=0; i--)
	{
		if (arr[i] != 0){
			return i;
		}
	}
	return 0;
}

#define FIND 999 
#define BUFSIZE 1002 

int main(int argc, char** argv)
{
	int a[BUFSIZE] = {0,};
	int b[BUFSIZE] = {0,};
	int c[BUFSIZE] = {0,};

	a[0] = 1;
	b[0] = 2;

	clock_t begin = clock();

	int nth = 2;
	while( true)
	{
		nth++;
		int mod = nth%3;
		if (mod == 0){
			memset( c, 0, sizeof(c));
			sum(a, b, c, BUFSIZE);

			int d = digit(c, FIND);
			cout << "digit=" << d << endl;
			if (d >= FIND) break;
		} else if (mod == 1) {
			memset( a, 0, sizeof(a));
			sum( b, c, a, BUFSIZE);

			int d = digit(a, FIND);
			cout << "digit=" << d << endl;
			if (d >= FIND) break;
		} else {
			memset( b, 0, sizeof(b));
			sum( c, a, b, BUFSIZE); 

			int d = digit(b, FIND);
			cout << "digit=" << d << endl;
			if (d >= FIND) break;
		}
	}

	clock_t end = clock();
	cout << "nth=" << nth << endl;

	cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << endl;
	return 0;
}