[코딩문제]n번째 피보나치 나머지 구하기 - 1

#include <iostream>

using namespace std;

/*

피보나치 수열이란,

첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때,

이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.

예) 0, 1, 1, 2, 3, 5, 8, 13

피보나치 수열의 n번째 수를 4,294,967,291으로 나누었을 때의

나머지를 출력하는 프로그램을 작성하시오.

정수 n이 입력으로 주어진다. (1 <= n <= 10^100000)

*/

#define MAXNUM 4294967291 //unsigned int 최대인 4294967295 보다 4 작음

unsigned int Fibonacci(unsigned long long n)

{

if (n > 2)

{

unsigned int first = 0;

unsigned int second = 1;

unsigned int temp = 0;

unsigned long long count = n - 2;

for (unsigned long long i = 0; i < count; i++)

{

temp = first;

first = second;

if (MAXNUM - second < temp)

{

second = temp - (MAXNUM - second);

}

else

{

second += temp;

}

}

return second;

}

else if (n == 2) return 1;

else return 0; //if (n <= 1) 

}

void main()

{

unsigned long long n = 1000000000;

cout << Fibonacci(n) << endl;

getchar();

}

10^100000 까지 입력할 수 있는 방법을 무시하고

기본 자료형으로 최대치를 계산 할 수 있는 unsigned long long 을 사용하여 구하였다.

리턴될 수 있는 최대값는 unsigned int 보다 작기 때문에 unsigned int 을 사용하였다.

MAXNUM  < temp +  second 을 계산하여야 하나

temp +  second을 해버리면 자료형 맥스 값을 넘어가므로

값 하나를 넘겨 MAXNUM - second < temp 로 조건을 주었다.

마차나지로 temp + second - MAXNUM 을 해야 하나

temp + second은 맥스 값을 넘기게 되므로

자료형 맥스 값을 안넘기기 위해

temp - (MAXNUM - second)로 처리하였다.

위처럼 자료형의 최대치(맥스값)를 넘기지 않게 컨트롤 하지 않고

무작정 더해버리면 원하지 않는 결과가 나와버린다.

커다란 숫자를 컨트롤 해야 할 경우에는

자료형의 최대값(맥스값)을 항상 고려하면서 코딩을 해야 한다.

문제 출처 : 코딩도장

코딩 출처 : 내 머리, 내 손