재귀함수 어려워요~)피보나치 수열 반복문으로 구현(1/2)

재귀함수 공부하면서 나오는 단골 문제가 있습니다

그런 바로 피보나치 수열입니다

어릴떄 수학공부하면서 한번은 들어보셨슬겁니다..

(사실 전 기억이 안났습니다.)

써보자면  // 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 36

앞에 두 숫자를 더해서 나온 값과 그 앞에 숫자를 더하는 과정을 계속 반복하는거죠

식으로 보자면

x + y = z -> y + z = z 이런식으로 말입니다..

 

재귀함수떄보다 이 피보나치 수열이 정말 어려웠습니다..

하나하나 그려서 보니까 위에 규칙이 보이더라구요

하지만 아..어떻게 구현할지 막막했습니다..

 

결론을 말씀드리면 네..전 풀지 못하였고 남의 코드를 보며 이해를 했습니다

 

코드를 보니 제 생각이 반은 근접했더군요

근데 역시 계속 생각한다고 해서 풀었을꺼 같지는 않았습니다..

 

이렇게 생각하는 과정이 정말 중요하다고 생각합니다

다들 코딩하다보면 느끼실겁니다

머리속으론 이렇게 하면 되겠다 라는 생각을 하는데

막상 그 생각을 코드로 구현하는게 안된다고

네..저는 지금도 안됩니다..ㅋㅋ

 

이러한 문제점를 해결하는 방법은

코드를 많이 사용해보고 문제를 풀어봐야 된다고 많이 하더라구요

어려운 문제를 혼자풀면 결국 자신의 생각들을 계속 코딩해봐야됩니다

이러한 과정이 결국은 생각을 코드화하는 단련법이라는 겁니다

 

그렇다고 저처럼 고민하다 안됬을떄 남의 코드를 보는게 문제냐..

사실 전 그렇게 생각하지 않습니다

 

충분히 고민했는데 답이 안나오면 남의 코드를 보고 공부하는것도 방법이라고 생각합니다..

사실 이제 공부하는 새내기라 이게 정답인지는 모르겠지만

이렇게 저렇게 저만의 스타일을 찾아가며 공부하다보면 결국 발전하는게 아닐까 싶네요..

 

말이 이상하게 길어 졌는데 결국 피보나치 수열..어떻게 공부했는지 써보겠습니다

 

제가 재귀함수로 구현하는건 반복문으로 구현이 가능하다고 했었는데

피보나치를 반복문으로 구현한것봐 재귀함수로 구현한걸 보여 드리겠습니다

 

    //피보나치 반복문으로 구현
int Ss(int num)
{

    int x = 0;
    int y = 1;
    int z = 0;

    if (num == 0)
    {
        return 0;
    }
    else if (num == 1)
    {
        return 1;
    }

    for (int i = 0; i < num- 2; ++i) 
    { 
        z = x + y; 
        x = y; 
        y = z; 
    } 
    return z;
}
int main()
{
    cout << Ss(7) << endl;
    return 0;
}

여기서 num 변수는 몇번쨰 피보나치값을 출력할껀지 선택하는겁니다

 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 36 중 7번쨰니까 출력값은 8입니다

 

피보나치수열을 구현하기 위해선

x + y = z  / 첫 x + y값을 정해줘야합니다  

보통 0 + 1 = 1하거나 1 + 1 = 2을 하는데 자기가 하고싶은데로 하면 됩니다

위에 식은 x와 y값이   0+1인 상태로 시작합니다

 

만약 1+1을 하고 싶으시면 세가지를 바꿔주시면 됩니다

int x를 0이 아닌 1로 바꿔주시고

조건문을 if (num == 1 || num == 2) { return 1; } 

 

자 이제 코드를 하나하나 보면

첫번쨰 두번쨰 조건문은 브레이크입니다

num이 0일떈 0, 1일떄 1을 반환해 줍니다

이유는 num이 몇번쨰 피보나치인지 선택하는 거라고 했죠??

0과 1도 몇번쨰 피보나치인지 말해주는 겁니다

1번쨰 피보나치는 앞에 더할 숫자가 없죠 그래서 0

2번쨰 피보나치도 앞에 더할 숫자가 없습니다..그래서 1

 

이제 3번쨰부턴 x + y = z식이 성립됩니다..

피보나치 수열의 규칙이 있었죠??

처음은 값을 지정해준다

예) 1 + 2 = 3

그 다음부턴 y값과 z값이 앞으로 떙겨지고 계산한다

예) 2 + 3 = 5

 

이걸 생각하면 위치를 바꿔줘야 하는구나 생각이 듭니다..

저는 여기서 생각은 했는데 방법이 안떠올랐습니다..

 

그렇지만 이 기능은 앞에서 배워보신적이 있을겁니다..

네..로또구현하기에서 사용한 셔플을 사용하면 구현이 되죠

그렇게 해서 구현한

        z = x + y;  
        x = y;  
        y = z;   

자 이제 포문을 해석해 보면

0 < num -2 만큼 반복한다 즉 7이면 6이죠 5번 반복한다..

자 왜 그런지 아시겠나요?? 이 부분도 처음엔 진짜 이해 안갔습니다..ㅋㅋ

 

처음에 제가 첫번쨰 값은 정해줘야 한다고 했었죠?

x+y 즉 첫번쨰와 두번쨰 자리 값을 제가 정해준겁니다.

조건문으로 정해줘서 계산을할 필요없습니다.

그럼 제가 구하려는 값의 -2를 해주시면 됩니다

 

이걸 보면 좀 더 이해하기 편할겁니다.

 

        //1+1일떄
        // 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 36
        // 3번쨰를 구하려면 1번 연산을 하죠 왜냐 3번쨰 값은 2고 2가 나오려면 1+1 = 2를 해야합니다
        // 그럼 4번쨰를 구하려면 2번 연산을 합니다 1번(1+1=2),  2번(1+2=3)

        //0+1일떄
        // 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 36
        // 3번쨰를 구하려면 1번 반복함 0+1 = 1
        // 4번쨰를 구하려면 2번 반복함 0+1=1 1+1=2

 

이해가 되시나요?? 제가 만약 7번쨰를 구한다고 하면

첫번쨰와 두번쨰값은 이미 제가 정해줘서 연산을 할 필요가 없으니 제외하고 

계산하시면 됩니다 그럼 당연히 7에서 -2를 한 5번쨰 값이 나오게됩니다.

 

자 이렇게 피보나치수열을 재귀함수가 아닌 반복문으로 구현을 해봤습니다.

왜 재귀함수가 아닌 반복문으로 구현했냐면

 

저처럼 그 기능을 어떻게 구현할지 모를떈

처음부터 그 기능으로 구현하지말고 더 쉬운 방법으로 구현하시는게 좋습니다

 

왜냐면 어떻게 구현할지도 모르는데 생각한다고 방법이 나오진 않습니다

그렇다면 더 쉬운 방법으로 구현을 해본뒤 여기서 어떻게 

재귀함수로 바꿀 수 있을까를 생각하는게 생각하시기 더 편할겁니다

 

이미 어쩄든 이미 구현은 했으니

원리를 어느정도 이해를 하셨기에 여기서 조금만 더 생각하시면 답이 나옵니다

 

다음은 재귀함수로 피보나치를 구현하는 방법을 써보겠습니다.