递归问题求C++代码(用递归做)
发布网友
发布时间：2024-05-28 14:08
共2个回答
热心网友
时间：2024-05-30 00:53
我们考虑一个数x，当x大于2时，它可以减1或减2，方法数是两种可能之和。不断地从n分而治之，直到x小于1即可。
首先，我们考虑暴力枚举：
#include <iostream>
using namespace std;
unsigned long long getWays(int n)
{
if (n < 2)
return 1;
else
return getWays(n - 1) + getWays(n - 2);
}
int main()
{
int n;
cin >> n;
cout << getWays(n) << endl;
return 0;
}
暴力枚举的代码可以正确地给出结果，但是当n较大时（比如说40，甚至400，400000），时间较长，原因是有多次重复的计算。为此，我们可以采用“记忆化搜索”的编程方法，记录每一次计算的结果，减少重复计算的次数，从而达到提高程序性能的目的：
#include <iostream>
#define MAXN 50
using namespace std;
long long mem[MAXN]; // 记忆化搜索数组
unsigned long long getWays(int n)
{
if (mem[n])
return mem[n];
else
{
if (n < 2)
return mem[n] = 1;
else
return mem[n] = getWays(n - 1) + getWays(n - 2);
}
}
int main()
{
int n;
cin >> n;
cout << getWays(n) << endl;
return 0;
}
热心网友
时间：2024-05-30 00:53
没安装c环境，用python写了一下，很容易看懂，用c重写一下即可。
还是用c写一下把：
