面接問題9(変形):変態階段
2090 ワード
タイトルリンク:http://ac.jobdu.com/problem.php?pid=1389
考え方:カエルが1つのn段の階段を跳ぶのは全部でFn種類の跳び方があって、しかもF 0=1、F 1=1、n段の階段の最後の一歩を跳ぶことを考慮します
1、0段の階段からn歩跳ぶ
2、1段階段からn-1歩跳ぶ
......
n、n-1段階段から一歩跳ぶ
繰返し式は、Fn=F 0+F 1+…+Fn-1=2^(n-1)
code:
考え方:カエルが1つのn段の階段を跳ぶのは全部でFn種類の跳び方があって、しかもF 0=1、F 1=1、n段の階段の最後の一歩を跳ぶことを考慮します
1、0段の階段からn歩跳ぶ
2、1段階段からn-1歩跳ぶ
......
n、n-1段階段から一歩跳ぶ
繰返し式は、Fn=F 0+F 1+…+Fn-1=2^(n-1)
code:
1 #include <cstdio>
2 using namespace std;
3 typedef long long LL;
4 int main()
5 {
6 int n;
7 while (scanf("%d", &n) != EOF)
8 {
9 LL ans = (LL)1 << (n - 1);
10 printf("%lld
", ans);
11 }
12 return 0;
13 }