코세라 강의  중에 Algorithmic Toolbox Course 강의를 듣고 있는 데,  그 중에 피보나치 문제를 숙제로 내주었다.

생각하는 법이 익숙하지 않은 나는 문제를 풀려고 도전했지만 쉽지가 않았다. 

피보나치 수열은 뭔지 아나요??

0,  1,  1,  2,  3,  5,  8  .....

앞에 두 개의 수는 두고 2번째 원소부터  이전 원소의 값을 더하며 증가하는 수열입니다..

그림으로 보면 이렇습니다..

피보나치 문제 나갑니다!.. 

Problem Introduction

The Fibonacci numbers are defined as follows: F(0) = 0, F(1) = 1, and 
F(i) = F(i−1) + F(i−2) for i ≥ 2.

Problem Description

Task: Given an integer n, find the last digit of the nth Fibonacci number F(n) (that is, F(n) mod 10).
Input Format: The input consists of a single integer n.
Constraints: 0 ≤ n ≤ 10 ^7.
Output Format: Output the last digit of F(n) .

Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec,

                      Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb.

Sample 1

Input:
3
Output:
2

Sample 2

Input:
327305
Output:
5

What To Do

Recall that Fibonacci numbers grow exponentially fast. For example, the 200th Fibonacci number equals 280571172992510140037611932413038677189525. Therefore, a solution like

F[0]=0
F[1]=1
for i=2 to n:
    F[i]=F[i-1]+F[i-2]
print(F[n] mod 10)

먼저 규칙을 찾아봅시다..

0  + 1  = 1

1   + 1  = 2     

1  + 2  = 3

1) 처음에 시작하는 수는 0  과 1  입니다.   

2) 마지막 자릿수를 구하려면 10으로 나눠야 합니다.. 

3) 기본 자리는 10의 자리라고 생각했습니다.

4)  합을 구할 때 보면 F(1) + F(2) = F(3) 입니다. 

F(0) + F(1) = F(2)

F(1) + F(2) = F(3)

첫번째 위치와 두번쨰 위치를 바꿔치기를 해야 겠지요..    간단한 수식으로 해봅시다..

저는 코드를 잘 못짜서 이방법으로 접근해보렵니다..

1)  for loop 만들기

2)  규칙을 이용하여 수식화

3)  값을 구해서 반환하기

위 코드는 제 생각대로 만든 코드 입니다..  규칙을 찾고 했더니 이해가 되네요.

main()  함수와 합쳐 보겠습니다.