Project Euler

Project Euler 문제풀이를 통해 문제해결 능력과 프로그래밍 기법 향상

Project Euler Project Euler 문제풀이를 통해 문제해결 능력과 프로그래밍 기법 향상
본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

#2. Even Fibonacci numbers

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;

댓글

댓글 본문
버전 관리
학생
현재 버전
선택 버전
graphittie 자세히 보기