ProjectEuler 문제 풀이

 projecteuler.net/ 

25번 째 문제....직접풀었음.ㅎ

<problem>

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

<Solution>
#include <iostream> #define MAXDIGIT 5000 using namespace std; void longsum(int* F1,int* F2,int* sum) { int surplus[MAXDIGIT]; memset(surplus,0,sizeof(surplus)); for(int i=0; i<MAXDIGIT; i++) { if(F1[i]+F2[i]+surplus[i]>=10) { surplus[i+1]=1; } } for(int j=0; j<MAXDIGIT; j++) { sum[j]=(F1[j]+F2[j]+surplus[j])%10; } } void longcopy(int* source, int* target) { for(int i=0; i<MAXDIGIT; i++) { target[i]=source[i]; } } bool check(int limit,int* target) { bool results=true; for(int i=limit; i<MAXDIGIT; i++) { if (target[i]!=0) { results=false; break; } } return results; } void main(void) { int a[MAXDIGIT]; int b[MAXDIGIT]; int F[MAXDIGIT]; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(F,0,sizeof(F)); int index = 2; b[0]=1; F[0]=1; while(check(999,F)) { longcopy(b,a); longcopy(F,b); longsum(a,b,F); index++; } printf("Answer is %d",index); }
그래서 답은..........4782 번째~!