题目来源2008年华中科技大学计算机保研机试真题题目描述N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）输入说明输入包括一个整数N,(1<=N<90)。输出说明可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。样例展示输入：4复制输出：5问题分析这个问题就是一个典型的递推问题。若我们把N分别等于1，2，3...的答案依次排列成一个数列，我们即需求这个数列每一个数的值。我们定义f[n]为数列中的第n个数字，同时F[n]为台阶总数为n时的上台阶方式总数。首先，我们必须确定数列之间的递推关系。当n大于2时，我们考虑每一种上台阶方式的最后一步，由于只有两种行走的方法，因此它只可能是从n-1阶经过一步走到n阶，或者从n-2阶经过2步走到n阶。我们分别考虑这两种走法，即我们将此时所有的上台阶方式按照最后一步走法的不同分为两类，分别确定这两类的上台阶数目。这样我们就确定达到n阶楼梯总的上楼方式个数为F[n-1]和F[n-2]的和，即F[n]=F[n-1]+F[n-2]。这就是我们这个数列的递归关系。由初始值F[1]=1,F[2]=2,我们就能得到所有F[n]的值。C++代码#include<iostream>using namespace std;typedef long long ll;ll F[100];int main() {    F[1]=1;    F[2]=2;    for(int i=3;i<=90;i++) {        F[i]=F[i-1]+F[i-2];    }    int n;    while(scanf("%d",&n)!=EOF) {        printf("%lld\n",F[n]);    }    return 0;}不容易系列之一题目描述大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语考试的时候，竟然把 40 个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。不幸的是，这种小概率事件又发生了，而且就在我们身边：事情是这样的——HDU 有个网名叫做 8006 的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给 n 个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！现在的问题是：请大家帮可怜的 8006 同学计算一下，一共有多少种可能的错误方式呢？输入说明输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数 n（1<n<=20），n 表示 8006 的网友的人数。输出说明对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。样例说明样例输入：23样例输出：12问题分析同样的，在该例子中我们也容易得到规模较小时的错装方式数量。如n为1时，数量为0;n为2时数量为1.我们按照n的取值顺序将所有的错装方式数量排列为一个数列，同样F[n]表示数列里第n个数的取值，F[n]同时代表n个信封的错装方式总数。接下来我们确定该数列的递推关系。当n大于3时候，我们考虑n封信全部装错的情况。将信封按照顺序由1到n编号。在任意一种封装方案中，假设n号信封里面装的是k号信封的信，而n号信封里的信则封装在m号信封里。我们按照k和m的相等与否将总的装错方式分为两类。若k不等于m，交换n号信封和m号信封的信后，n号信封里装的恰好是对应的信，而m号信封中错装k号信封的信，即除n号信封外其余n-1个信封装错，其装错方式为F[n-1]，又由于m的n-1个可能取值，这类错装总数为（n-1）F[n-1]。也可以理解为，在n-1个信封错装的F[n-1]的基础上，将n号信封所装的信与n-1个信封中任意一个信封交换后，得到所有信封的全部装错的方式数。另一种情况，若k等于m,交换n号信封和m号信封后，n和信封和m号信封里面装的恰好是对应的信，这样除她们之外剩余的n-2个信封全部错装，其错装方式为F[n-2]，又由于m的n-1个取值，这类错装方式总数为（n-1）* F[n-2]。也可以理解为，在n-2个信封全部错装的基础上，交换最后两个信封中的信（n号信封和1到n-1号信封中任意一个）共有n-1种选择，使得所有的信封全部错装的方式数。综上所述：F[n]=(n-1) * F[n-1] + (n-1) * F[n-2]C++代码#include<iostream>using namespace std;typedef long long ll;ll F[21];int main() {    F[1]=0;    F[2]=1;    for(int i=3;i<=20;i++) {        F[i]=(i-1)*F[i-1]+(i-1)*F[i-2];    }    int n;    while(scanf("%d",&n)!=EOF) {        printf("%lld\n",F[n]); //输出    }    return 0;}吃糖果https://www.nowcoder.com/questionTerminal/72015680c32b449899e81f1470836097C++代码//话说这应该是和爬楼梯一样吧#include<iostream>using namespace std;typedef long long ll;ll dp[21];int main() {    dp[1]=1;    dp[2]=2;    for(int i=3;i<=20;i++) {        dp[i]=dp[i-1]+dp[i-2];    }    int n;    while(scanf("%d",&n)!=EOF) {        printf("%d\n",dp[n]);    }    return 0;}