ProjectEuler 2

2번문제

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로 시작하여 처음 10번째까지의 수열은 다음과 같다:

 

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

 

4백만이 넘지 않는 피보나치 수열이 있다고 가정할때 

짝수인 피보나치의 수열을 합을 구하여라

 

코드는 아래와 같다 

     public static void main(String []args){
        int sum = 0;
		int f1 = 1;
		int f2 = 1;
		while(f1<4000000){
			f1 = f1 + f2;
			f2 = f1 - f2;
			if(f1%2==0){
				sum=sum+f1;
			}
		}
		System.out.print(sum);
     }

문제가 물어보는 것은 피보나치 수열을 짤 수 있느냐를 물어보는 것 같다. 

 

int buf =0;
int f1 = 1;
int f2 = 1;
	while(true){
		buf = f2;
		f2 = f1+f2;
		f1 = buf;
	}

 

1번째 줄은 임시 변수

2번째 줄의 f1은 피보나치 첫번째 수열인 1
3번째 줄의 f2는 피보나치 두번째 수열인 1이고

 

나머지는 일반적으로 간단하게 생각할 수 있는 변수를 3개를 사용하여 계속해서 피보나치 수열을 만들어가는 방법이다

(코드는 돌리지 마시길.. 무한 루프임ㅋㅋ)

 

하지만 조금 생각해보면 만들어질 새운 피보나치 수열은 현재 변수 2개로 만든다!

 

int f1 = 1;
int f2 = 1;
	while(true){
		f1 = f1 + f2;
		f2 = f1 - f2;
	}

위 코드를 잘 보면

 

4번째 줄에서 하는 작업은 피보나치의 다음 수열을 현재 두개의 변수로 생성한다

 

이게 핵심인데 피보나치 수열을 이항하면 F[n-1] = F[n] - F[n-2]와 같은 식이 나오는데

피보나치의 다음수열에서 이전전 수열을 빼면 이전 수열이 나온다는 소리이다. 

 

4번째줄에서 f1변수는 F[n]을 저장하였고 f2변수는 F[n-2]를 저장하고 있기 때문에 둘이 빼면 F[n-1]을 얻을 수 있다!!!

 

말로 설명하니까 햇갈릴수도 있는데, 직접 수를 대입해서 몇번만 해보면 이해갈것이다. 

 

 

문제 조건이 짝수인 피보나치인 수를 더하는 것이기 때문에 mod operation으로

홀수를 걸러주면서 더해주면 답이 나온다!