楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,用C++或lua语言编一程序计算共有多少种不同的走法.分别用递归、迭代二种方式, 写出详细的代码
问题描述:
楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,用C++或lua语言编一程序计算共有多少种不同的走法.分别用递归、迭代二种方式, 写出详细的代码
答
int recursive(int n)
{
if (n <= 2)
return n;
return recursive(n - 1) + 2 * recursive(n - 2);
}
int iterative(int n)
{
int f1 = 1, f2 = 2, f;
for (int i = 3; i <= n; ++i)
{
f = f2 + 2 * f1;
f1 = f2;
f2 = f;
}
return f;
}2 * recursive(n - 2);
这里为什么要乘2?好像不用吧,直接return f(n-1)+f(n-2)就行了吧是不用乘2,你理解是对的。我想偏了。
更改为:
int recursive(int n)
{
if (n return n;
return recursive(n - 1) + recursive(n - 2);
}
int iterative(int n)
{
int f1 = 1, f2 = 2, f;
for (int i = 3; i {
f = f2 + f1;
f1 = f2;
f2 = f;
}
return f;
}