爬楼梯问题
问题描述：
假设你现在正在爬楼梯，楼梯有 n 级。每次你只能爬 1 级或者 2 级，那么你有多少种方法爬到楼梯的顶部？
输入格式
第一行输入一个整数 n(1≤n≤50)，代表楼梯的级数。
输出格式
输出爬到楼梯顶部的方法总数。
样例输入
5
样例输出
8
n级楼梯，每次只可以爬1-2级。这个问题相当于将n分解为1和2个数相加，有多少种分法，而每种分法中1、2又有几种不同的排法。假设n现在分为i个1与j个2相加，相当于在（i+j）个空中选取i个空排1，其他的全排2（或者选取j个空排2，其余的全排1）。这样这个问题就好解决了，代码如下：
#include<stdio.h>
/*排列组合函数*/
int cmn(int m, int n)
{
if (m - n < n) return cmn(m, m - n);
else if (n == 0) return 1;
else if (n == 1) return m;
else
return cmn(m - 1, n) + cmn(m - 1, n - 1);
}
int main()
{
long long int k, m = 0;
int i, j, n, s;
scanf("%d", &n);
/*i表示1的个数j表示2的个数，若n-i的余数可以被2整除即视为一种分法*/
for (i = 0; i <= n; i++)
{
s = n - i;
j = s / 2;
if (s % 2 == 0)
{
k = cmn(i + j, i);
/*计算每种分法的排列数k并求和*/
m = m + k;
}
}
printf("%ld", m);
return 0;
}但是经过测试后发现，当大于40后，运行就会超时。说明这个算法在n较大时就显得有些乏力。
那么换一种想法：
级数n每增加一级的总可能数f(n)，相当于从n-2级（可能数f（n-2））再走2级或者由n-1级（可能数f(n-1)）再走一级，这样既可得：
f（n）=f（n-1）+f（n-2）
由数组记忆每一级的运算结果就可以加快运算速度了。
代码如下：
#include<stdio.h>
int main()
{
int n, i;
scanf("%d", &n);
long long int a[n];
/*由于n-2大于0，需要先计算第一级与第二级的可能数*/
a[0] = 1;
a[1] = 2;
for (i = 2; i < n; i++)
{
/*第i+1级的结果*/
a[i] = a[i - 1] + a[i - 2];
}
printf("%ld", a[n - 1]);
return 0;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-05-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读