코세라 강의  중에 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  = 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)  값을 구해서 반환하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int get_fibonacci_val( long long n)
{
 
  int a = 0;
  int b = 1;
  int remain = 0;
 
  forint i = 2 ; i <= n; i++)
  {
   
    remain = (a + b )%10;
    a = b;
  b =  remain;
   }
 
   return remain; 
 
}
 
cs


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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
 
using namespace std;
 
int get_fibonacci_val( long long n)
{
 
  int a = 0;
  int b = 1;
 
  int remain = 0;
 
  forint i = 2 ; i <= n; i++)
  { 
 
    //합구하기      
     remain = (a + b )%10;
     a = b;
     b =  remain;
   }
 
   return remain; 
 
}

int main()
{
   int n = 0;
   
   std::cin >> n; 
   int val = get_fibonacci_val(n);
   std::cout << val << std::endl
 
   return 0;
 
}
cs




저작자 표시
신고

'Study > 알고리즘' 카테고리의 다른 글

Binary Search with example  (0) 2016.11.19
Linear Search 1  (0) 2016.11.19
분할과 정복 알고리즘 도입  (0) 2016.11.19
피보나치 수열 값에서 마지막 숫자 구하기  (0) 2016.10.08
[week 1] Find Max Pairwise and multiply it  (0) 2016.09.19

WRITTEN BY
Profile
비타오백
Enjoy your stage!

받은 트랙백이 없고 , 댓글이 없습니다.
secret

명심해야 될 점!

  1. Implement a program for a given computational problem.
  2. Find out that it is slow: on large datasets, it takes too long to run.
  3. Implement a more efficient program that is able to process even large datasets in less than a second.
  4. Use stress testing to locate and fix a bug in the program.



문제는 최대값을 2개 찾아서 곱하는 것입니다. 하지만, 같은 번지의 숫자를 사용할 수 없습니다.









코드 구현은 사용할 수 있는 언어로 하면 됩니다..

정답은 첨부파일로 넣었습니다.  답을 알면, 생각하는 힘이 떨어져요..






max_pairwise_product.cpp
max_pairwise_product.py
MaxPairwiserProduct.java








저작자 표시
신고

'Study > 알고리즘' 카테고리의 다른 글

Binary Search with example  (0) 2016.11.19
Linear Search 1  (0) 2016.11.19
분할과 정복 알고리즘 도입  (0) 2016.11.19
피보나치 수열 값에서 마지막 숫자 구하기  (0) 2016.10.08
[week 1] Find Max Pairwise and multiply it  (0) 2016.09.19

WRITTEN BY
Profile
비타오백
Enjoy your stage!

받은 트랙백이 없고 , 댓글이 없습니다.
secret

코드를 컴파일 할때 보면 디버그 모드에서 잘되다가 릴리즈 모드에서 잘 않되는 경우가 있습니다.

저도 MFC 프로그래밍 할 때 디버그 모드에서 잘 되다가 릴리즈 모드에서 기능이 잘 안되곤 했습니다.

왜 그럴 까요?

 

컴파일 최적화를 살펴봐야 합니다..

 

연산자 

최적화 --> 의존성

 

 

 

'의존성' 을 변수를 기준으로 합니다.

 

변수 ==> 자료

 

연산 --> 변수 (의존성)

 



최적화

특정 변수(자료)에 대해 의존성이 존재하는 연산들을 구별 할 수 있어야 한다.


변수가 많은 것 , 적은 것  중에 좋은 것은 뭘까요??


변수는 메모리를 많이 쓰니깐, 많으면 않좋은 거 아닐까요??

변수는 적은 것이 좋다.

 

변수가 늘어나면 늘어날 수록 논리적 구조가 복잡 할 수 있다.

최적화 하기 어렵습니다..



최적화 된 코드를 작성하기 위한 방법

1) 컴파일러가 최적화 하기 좋게 작성해야 한다.

 최적화는 기계적이고, Low 레벨..


최적화 방해요소는??

1) 변수가 많은 경우 --> 최대한 변수의 개수를 줄여라..

2) 포인터 사용 주의 (자제)

 

 


저작자 표시
신고

'Study > C lang' 카테고리의 다른 글

코드 최적화 하기  (0) 2016.09.17
포인터와 메모리 핵심정리  (1) 2016.08.31
버블정렬 [Bubble Sort]  (2) 2016.08.09

WRITTEN BY
Profile
비타오백
Enjoy your stage!

받은 트랙백이 없고 , 댓글이 없습니다.
secret