C语言王道练习题第六周一题

递归---走台阶

Description

假如有n个台阶，一次只能上1个台阶或2个台阶，请问走到第n个台阶有几种走法？

为便于读者理解题意，这里举例说明如下：假如有3个台阶，那么总计就有3种走法：

第一种为每次上1个台阶，上3次：

第二种为先上2个台阶，再上1个台阶；

第三种为先上1个台阶，再上2个台阶。

输入为n，输出为走到第n个台阶有几种走法？

Input

比如输入是3

Output

如果输入是3,走到第3个台阶的走法总计有3种,1,1,1 和 1,2 和2,1,输出

思想：

递归问题提炼公式，结束条件

代码：

#include<stdio.h>


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

int main() {
    int n;
    scanf("%d",&n);
    printf("%d",step(n));
    return 0;
}

分析：

? ? ? ? 一次只能走1个或者2个台阶，所以n个台阶，第n-1前个台阶，是一种方案，第n-2前个台阶是一种方案。

注意：

????????当走到第n-2个台阶，再向前走1个台阶，则与第一种方案重复。