피보나치 재귀를 사용하여 1에서 n까지 인쇄

Question

필자는 함수에서 피보나치 시리즈를 1에서 n으로 인쇄하고 싶습니다. 은 내가이 같이 N. 1을 인쇄하는 블록의에 정기적 피보나치를 작성하고 그것을 사용하여 그것을 할 수 있다는 사실을 알고 :

#include <iostream> 
using namespace std; 

int fibo(int); 

int main(){ 
    for (int i = 0; i < 5; i++) 
     cout << fibo(5); 
    system("pause"); 
    return 0; 
} 

int fibo(int n){ 
    if (n == 1 || n == 2) 
     return 1; 
    else 
     return fibo(n - 1) + fibo(n - 2); 
} 

하지만 내 problme 내가 대한없이 그것을 할 수 없다는 것입니다, 내 함수에서 내 말은 내가 재귀 알고리즘으로 인쇄 할 여기 내 코드는 지금까지의

#include <iostream> 
using namespace std; 

int fibo(int, bool); 

int main(){ 
    fibo(5, false); 
    system("pause"); 
    return 0; 
} 

int fibo(int n, bool IsPrinted){ 
    if (n == 1 || n == 2){ 
     if (!IsPrinted) 
      cout << 1 << endl; 
     return 1; 
    } 
    else{ 
     int temp = fibo(n - 1, IsPrinted) + fibo(n - 2, IsPrinted); 
     if (!IsPrinted){ 
      cout << temp << endl; 
      IsPrinted = true; 
     } 
     return temp; 
    } 
} 

Answer 1

long fibo(int N, bool print) { 
    long value = 0; 

    if(1 == N) 
     value = 1; 

    if(1 < N) 
     value = fibo(N-1, print) + fibo(N-2, false); 

    if(print) 
     std::cout << N << " => " << value << std::endl; 
    return value; 
} 

int main(){ 
    fibo(5, true); 
    return 0; 
} 

당신이 알아야하는 것은 fibo 함수에 대한 호출 트리를 만드는 것입니다. 트리 루트는 의 fibo(5, true)에 대한 호출입니다. 각 값을 한 번만 인쇄하기를 원할 때 솔루션은 해당 트리의 가장 왼쪽 분기에서만 함수 값을 인쇄하기로 결정하는 것입니다. 규칙은 간단하게 다음과 같습니다

• 오른쪽 지점 (fibo(N-2, false)
• 결코 부모가 인쇄되지 않은 경우 인쇄에 따라서 호출 할 때 (인쇄를 방지하기 위해 인쇄 결코 아이에 권리의 분기를 떠날 때 branch)

Answer 2

일반적인 솔루션을 사용하는 메모이 제이션입니다 :

int fibo(int n) 
{ 
    static std::map<int,int> memo; 
    auto it=memo.find(n); 
    if(it!=std::end(memo)) 
    { 
     return it->second; 
    } 

    int ret=1; 
    if (n > 2) 
    { 
     ret = fibo(n - 1) + fibo(n - 2); 
    } 
    memo[n]=ret; 
    return ret; 
} 

그런 다음 수 계속해서 또 다시 값을 재 계산하지 않고 입력 매개 변수를 통해 안전하게 루프 : 적어도 당신이 전화로이 인쇄 만 유리 아니라고

for(int i=0;i<20;++i) 
{ 
    std::cout<<i<<" "<<fibo(i)<<std::endl; 
} 

주뿐만 아니라 계산 자체 (대한 기능은 한 번 이상).

위의 경우 반환 유형으로 long 또는 double을 사용하는 것이 좋습니다. int이 더 빨리 오버플로됩니다.

---

편집 : 좋아, 편집 한 후 내 대답은 정확하게 질문에 맞는지 모르겠지만, 나는 어쨌든 좋은 충고 생각합니다.

그러나 여기가 가까워 다른 빠른 대안 같아요 :

int fibo(int n, bool first=true) 
{ 
    int ret=0; 
    if(n>2) 
    { 
     ret=fibo(n-1,false)+fibo(n-2,false); 
    } 
    else 
    { 
     ret=1; 
    } 

    if(first) 
    { 
     std::cout<<ret<<std::endl; 
    } 
    return ret;   
} 

DEMO