Fibonacci级数

Question

我试着用斐波纳契系列来做一个练习。我必须用递归函数来实现Fibonacci的素数n的继承，并在相同的函数中打印它们。问题是我的函数也打印中间号。例如，对于n = 6，结果应该是：1 1 2 3 5 8。有什么解决办法吗？

谢谢

#include<iostream>
using namespace std;
int rec(int n)
{
    int a, b;
    if (n == 0 || n == 1)
    {
        return n;
    }
    else
    {
        a = rec(n - 1);
        b = rec(n - 2);
        cout << a + b << endl;
        return a + b;
    }

}
int main()
{ 
    int n = 6;
    rec(n);
    return 0;
}

Answer 1

你可以用这个：

#include<iostream>
using namespace std;
#define MAXN 100
int visited[MAXN];
int rec(int n)
{
    if(visited[n])
    {
        return visited[n];
    }
    int a, b;
    if (n == 0|| n==1)
    {
        return n;
    }
    else
    {
        a = rec(n - 1);
        b = rec(n - 2);
        cout << " " <<a + b;
        return visited[n] = a + b;
    }

}
int main()
{
    int n = 6;
    cout<< "1";
    rec(n);
    cout<<endl;
    return 0;
}

该实现使用动态编程。因此，它减少了计算时间:)

Answer 2

我接受了static int的帮助。那是你想要的效果。

void rec(int n)
{
    static int a=0,b=1,sum;
    if(n>0)
    {
         sum = a+b;
         a=b;
         b= sum;
         cout<<sum<<" ";
         rec(n-1);
    }
}

尽管您必须在main()中自己打印第一个斐波纳契数字。

cout<<"0 ";
rec(n);

Answer 3

因为您是在rec中打印，所以它的多次打印是因为递归。不需要在递归函数中打印。相反，在main中打印结果

#include<iostream>
using namespace std;
int rec(int n)
{
    int a, b;
    if (n == 0 || n == 1)
    {
        return n;
    }
    else
    {
        a = rec(n - 1);
        b = rec(n - 2);
        //cout << a + b << endl;
        return a + b;
    }
}

int main()
{
    int n = 6;

    for (int i = 1; i <= n; i++)
    {
        cout << rec(i) << endl;
    }

    system("pause");
    return 0;
}