【剑指offer】变态跳台阶

it2025-09-30  52

转载请注明出处:http://blog.csdn.net/ns_code/article/details/25367797

    斐波那契序列的变种,简单题,在九度OJ上測试通过。

时间限制:1 秒

内存限制:32 兆

题目描写叙述:

一仅仅青蛙一次能够跳上1级台阶,也能够跳上2级……它也能够跳上n级。求该青蛙跳上一个n级的台阶总共同拥有多少种跳法。

输入:

输入可能包括多个測试例子,对于每一个測试案例,

输入包括一个整数n(1<=n<=50)。

输出:

相应每一个測试案例,

输出该青蛙跳上一个n级的台阶总共同拥有多少种跳法。

例子输入: 6 例子输出: 32

    思路:

    先大致分析下,如果跳上第n个台阶有f(n)种方法,则f(1)=1,f(2)=2,f(3)=4,f(4)=8,我们隐约感觉到f(n)=2^(n-1)。可是须要证明下,相同依据我们依据上篇文章中跳台阶的思路,能够得到f(n)=f(n-1)+f(n-2)+....+f(1)+1,而f(n-1)=f(n-2)+....+f(1)+1,两个式子相减,得到f(n) = 2f(n-1),非常明显能够得到f(n)=2^(n-1)。

    AC代码例如以下:

#include<stdio.h> long long Fibonacci(unsigned int n) { if(n <= 0) return 0; if(n==1) return 1; long long FibN = 1; unsigned int i; for(i=2;i<=n;i++) { FibN *= 2; } return FibN; } int main() { unsigned int n; while(scanf("%d",&n) != EOF) printf("%lld\n",Fibonacci(n)); return 0; } /**************************************************************      Problem: 1389      User: mmc_maodun      Language: C      Result: Accepted      Time:0 ms      Memory:912 kb ****************************************************************/

转载于:https://www.cnblogs.com/bhlsheji/p/3835709.html

相关资源:数据结构—成绩单生成器
最新回复(0)