Question

楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，用C++或lua语言编一程序计算共有多少种不同的走法

楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，用C++或lua语言编一程序计算共有多少种不同的走法。分别用递归、迭代二种方式， 写出详细的代码

Answer 1

    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 <= 2)
return n;
return recursive(n - 1) + recursive(n - 2);
}

int iterative(int n)
{
int f1 = 1, f2 = 2, f;
for (int i = 3; i <= n; ++i)
{
f = f2 + f1;
f1 = f2;
f2 = f;
}
return f;
}

Answer 2

#include<stdio.h>
#define maxn 50
int arr[maxn];
int main(void)
{
    arr[0] = arr[1] = 1;
    int i;
    for(i = 2; i < maxn; i++)
        arr[i] = arr[i - 1] + arr[i - 2];
    return 0;
}

追问

这是迭代的方法？还有递归的方法是该这样吗：
int f(int n)
{
if (n <= 0)

return 0;

else if (n == 1)

return 1;

else if (n == 2)

return 2;

else

return f(n-1)+f(n-2);

}

追答

是。

Answer 3

int get(int a)
{
if (a <=2)
return a;
else
return get(a - 1) + get(a - 2);
}
int main()
{
int a;
while (EOF)
{
scanf_s("%d", &a,1);
a = get(a);
printf("%d\n", a);
}
return 0;
}

Answer 4

C语言版本：
#include<stdio.h>
int jiecheng(int x,int ci)
{
int i=0,p=1;
while(i++<ci)
p*=x--;
return p;
}
int main()
{
int i,n,sum=0;
printf("请输入台阶数量n:");
scanf("%d",&n);
for(i=1;i<=n/2;i++)
sum+=jiecheng(n-i,i)/jiecheng(i,i);
printf("总共有%d种方案\n",sum+1);
return 0;
}