Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?
--------------------------초기조건--------------------------
f(2) = 2;
f(5) = 8;
------------------------------------------------------------
f(3n+2) --> f(8) 부터 계산
초기조건을 활용하기 위해서는
f(3n+2) --> f(3(n-1)+2) 와 f(3(n-2)+2)로 일반적인 조건을 구하도록 한다.
f(3n+2) --> a*f(3n-1) + b*(3n-4)로 구한다.
f(3n+2)
= f(3n+1) + f(3n)
= f(3n) + f(3n-1) + f(3n)
= f(3n-1) + f(3n-2) + f(3n-1) + f(3n)
= 3*f(3n-1) + 2*f(3n-2)
= 3*f(3n-1) + f(3n-3) + f(3n-4) + f(3n-2)
= 3*f(3n-1) + f(3n-3) + f(3n-2) + f(3n-4)
= 4*f(3n-1) + f(3n-4)
따라서 a = 4, b = 1
명명
3n-4 -> first
3n-1 -> second
C / C++
const int MAX_NUM = 4000000;
int f_sequence_first = 2;
int f_sequence_second = 8;
int f_sequence = 0;
int f_result = 10;
while ( ( f_sequence = f_sequence_first + (4*f_sequence_second) ) <= MAX_NUM )
// 수열을 구하고 4백만 보다 작은지 체크
{
f_result += f_sequence; // 결과에 더함
f_sequence_first = f_sequence_second; // 다음 수열을 위한 셋팅
f_sequence_second = f_sequence; // 다음 수열을 위한 셋팅
}
cout << "Question 2 : " << f_result << endl;
