首页 > ACM题库 > 九度OJ > 剑指offer(16)-变态跳台阶[递推]
2014
02-13

剑指offer(16)-变态跳台阶[递推]

题目来自九度剑指offer系列:九度-1389-变态跳台阶

题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
输入:
输入可能包含多个测试样例,对于每个测试案例,输入包括一个整数n(1<=n<=50)。

输出:
对应每个测试案例,输出该青蛙跳上一个n级的台阶总共有多少种跳法。

样例输入:
6
样例输出:
32

当台阶数为n时,可以分为以下步骤来完成:
设第一次跳的台阶数为s,跳台阶方式数为T,则:
(1)s=1时,T(n) = T(n-1)
(2)s=2时,T(n) = T(n-2)
.
.
.
(n)s=n时,T(n) = T(0) = 1
所以总的跳台阶方式数T可以表示为:
T(n) = T(0) + T(1) + T(2) + … + T(n-1)
由于T(0) = T(1) = 1,所以T(n) = 2^(n-1)

#include<iostream>
#include<math.h>
using namespace std;
int main()
{int n;
while(cin>>n)
{long long result=(long long)pow(2,n-1);
cout<<result<<endl;
}
return 0;
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.