51Nod 2059 上台阶 easy
目录
文章目录
1. 题目描述
1.1. Limit
Time Limit: 1000 ms
Memory Limit: 131072 kB
1.2. Problem Description
现在小瓜想通过台阶走上平台,最底层(小瓜所在的层)编号为1
,最顶层编号为 n。由于小瓜的腿比较短,他一次只能向上走1
级或者2
级台阶。小瓜想知道他有多少种方法走上平台,你能帮帮他吗?
1.3. Input
一个整数 n,其中 2≤n≤25。
1.4. Output
一行一个整数,表示小瓜上台阶的方案数
1.5. Sample Input
4
1.6. Sample Output
3
从台阶1
到台阶4
,可能方案有:
1→2→3→4
1→2→4
1→3→4
共3种。
1.7. Source
2. 解读
使初始值为 f(2)=1, f(3)=2,计算斐波那契数列 f(n)=f(n−1)+f(n−2), (n≥4)。
3. 代码
#include <iostream>
#include <string.h>
using namespace std;
// 存储数列
long long fabList[25];
// 计算斐波那契数列
long long fab(int n)
{
if (n == 2) {
return fabList[2];
} else if (n == 3) {
return fabList[3];
} else {
return fab(n - 1) + fab(n - 2);
}
}
int main()
{
long long n;
// 读入n
scanf("%lld", &n);
// 初始化
memset(fabList, 0, sizeof(fabList));
fabList[2] = 1;
fabList[3] = 2;
// 计算斐波那契数列
long long ans = fab(n);
// 输出
printf("%lld", ans);
}
联系邮箱:curren_wong@163.com
Github:https://github.com/CurrenWong
欢迎转载/Star/Fork,有问题欢迎通过邮箱交流。