조띵의지극히개인적인공간


피보나치 수열의 새 항은 이전의 두 항의 합으로 만들어집니다. 1과 2로 시작한 10개의 항은 아래와 같습니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

피보나치 수열의 4백만을 초과하지 않는 항 중 짝수를 모두 더한 값은 얼마인가요?





내맘대로 해설 : 
피보나치 수열은 3번 주기로 짝수가 된다.
F(n) 에서 n이 5보다 크면
F(n) = F(n-1)+F(n-2)          // 각각의 항을 풀면
       = F(n-2)+F(n-3) + F(n-3) + F(n-4)   // 첫번쨰 F(n-2)만 풀면
       = F(n-3) + F(n-4) + F(n-3) + F(n-3) + F(n-4)  // 정리하면
       = F(n-3) * 3 + F(n-4) * 2


다음과 같은 식을 얻을 수 있다.
F(n)*3 + F(n-1)*2 = F(n+3)



int _tmain(int argc, _TCHAR* argv[])
{
unsigned int Sum=2;
int n=2, n_1=1;

for (int i=5; Sum<4000000; i+=3)
{
int oldn = n;
int oldn_1= n_1;
Sum+=oldn*3+oldn_1*2;

n=oldn*3+oldn_1*2;
n_1 = n - (oldn + oldn_1);
}

printf("Sum=%d", Sum);

return 0;
}



Posted by 조띵


티스토리 툴바