admin管理员组

文章数量:1794759

阶乘

目录

问题描述

解答

代码（C语言）

问题描述

假设现有n个台阶，你从第一个台阶开始，每次只能迈一个台阶或两个台阶，问到达第n个台阶总共有几种走法 ？

设从第一个台阶到第n个台阶总共有x种走法，通过列举我们可以知道部分n、x的对应关系如下：

通过观察可以得出到第n个台阶的走法刚好是到第n-1和第n-2个台阶的走法之和（n>=3）。

那么问题就是：这是为什么呢？难道是巧合吗？

解答

其实这个题的思路是：假设你已经到达了第n个台阶，那么前一步你在哪呢？只有两种可能：你要么在第n-1个台阶，要么在第n-2个台阶，所以你最后一步到达第n个台阶就可以分为两种情况，也就是说到达第n个台阶的所有可能的走法就可以一次为依据分成两个部分：一部分是到达第n-1个台阶的所有可能的走法，另一部分是到达第n-2个台阶的所有可能的走法。

注：为什么最后一步不用考虑，也就是为什么不给这两部分分别+1？

因为一旦确定了你最后一步之前是在第n-1个台阶还是第n-2个台阶，那么你的最后一步就是确定的了，在第n-1个台阶那你最后一步就只能迈1个台阶，在第n-2个台阶那你最后一步就只能迈2个台阶，没有别的组合，所以相当于给前面的走法数量再乘以1。

代码（C语言）

#include <stdio.h>int step(int n)
{if (n<=2)return n;return step(n-1)+step(n-2);
}int main()
{int n, s;scanf("%d", &n);s = step(n);printf("%d\n", s);return 0;
}

本文标签： 阶乘