斐波那契函数的应用

　　题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙上一次n级的台阶总共有多少种跳法？

分析：首先考虑最简单的额情况。如果只有1级台阶，那显然只有一种跳法；如果有2级台阶，那就有两种跳法；跳一级再跳一级；一次性跳到第2级；

　　接下来讨论一般情况，把n级台阶时的跳法看成是n的函数；记作f（n）。当n > 2时，第一次跳的时候有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的数目；即为f（n-1）；另一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级数台阶数目，即为f（n-2）；因此n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2).

分析到这里，不难看出这实际就是斐波那契数列了；

 1 long long Fibonacci(unsigned n)
 2 {
 3     int result[2] = {0, 1};
 4     if(n<2)
 5     {
 6         return result[n];
 7     }
 8
 9     long long fibNMinusOne = 0;
10     long long fibNMinusTwo = 1;
11
12     long long fibN = 0;
13     for(unsigned int i=2;i<=n;++i)
14     {
15         fibN = fibNMinusOne + fibNMinusTwo;
16         fibNMinusTwo = fibNMinusOne;
17         fibNMinusOne = fibN;
18     }
19     return fibN;
20 }
21 ~

时间： 2024-09-20 04:20:09

斐波那契函数的应用的相关文章

Reverse反转算法＋斐波那契数列递归＋Reverse反转单链表算法－－C++实现

Reverse反转算法 1 #include <iostream> 2 3 using namespace std; 4 //交换的函数 5 void replaced(int &a,int &b){ 6 int t = a; 7 a = b; 8 b = t; 9 } 10 //反转 11 void reversed(int a[],int length){ 12 int left = 0; 13 int right = length - 1; 14 while (left

UVa 10229 Modular Fibonacci：矩阵快速幂求斐波那契

10229 - Modular Fibonacci Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1170 The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defin

UVa 10236 The Fibonacci Primes：斐波那契素数

10236 - The Fibonacci Primes Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1177 注意此题的描述和维基百科上Fibonacci Prime的描述不同. 上面加着重符的文字说明:可以用类似素数筛的方式筛出Fibonacci Pr

斐波那契数列和反向计算问题

反向计算:编写一个函数将一个整型转换为二进制形式反向计算问题,递归比循环更简单分析:需要理解,奇数的二进制最后一位是1,偶数的二进制最后一位一定是0,联想记忆,这个和整型的奇偶性是一致的,1本身就是奇数,0本身是偶数. 十进制整数转换为二进制整数采用"除2取余,逆序排列"法. 具体做法是:用2整除十进制整数,可以得到一个商和余数,再用2去除商,又会得到一个商和余数,如此进行,直到商为0时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,

内存管理-根据题目，编这个程序怎么会联想到用斐波那契数列?

问题描述根据题目,编这个程序怎么会联想到用斐波那契数列? 4．编写-个函数,它返回函数自身被调用的次数,并在一个循环中测试之. #include int Fibonacci(int n); int count; int main(void) { int n; printf("input the max term of Fibonacci:"); while( scanf("%d",&n) == 1 ) { count = 0; Fibonacci(n);

斐波那契数列(Fabonacci)兔子练习题

Java练习题:兔子问题此问题又叫斐波那契数列(Fabonacci),是最先研究这个数列的人是比萨的列奥那多(又名费波那契),他描述兔子生长的数目时用上了这数列. 第一个月有一对刚诞生的兔子第二个月之后它们可以生育每月每对可生育的兔子会诞生下一对新兔子兔子永不死去假设在 n 月有新生及可生育的兔子总共 a 对,n+1 月就总共有 b 对.在 n+2 月必定总共有 a+b 对: 因为在 n+2 月的时候,所有在 n 月就已存在的 a 对兔子皆已可以生育并诞下 a

递归-如何使用汇编斐波那契数列第N个数

问题描述如何使用汇编斐波那契数列第N个数要求使用递归方法 #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int n, r; if (argc < 2) { printf("Usage: %s number(<40)n", argv[0]); return -1; } n = atoi(argv[1]); __asm { // FILL YOU

求解斐波那契数列 python 的两个方法比较

Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个. 这次在,python中也不例外,最基本的那种递归(如下fib1)效率太低了,只要n数字大了运算时间就会很长:而通过将计算的指保存到一个dict中,后面计算时直接拿来使用,这种方式成为备忘(memo),如下面的fib2函数所示,则会发现效率大大提高. 在n=10以内时,fib1和fab2运行时间都很短看不出差异,但当n=40时,就太明显了,fib1运行花了35秒,fab2运行只花费了0.00001秒. n=

求斐波那契(Fibonacci)数列通项的七种实现方法_C 语言

一:递归实现使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1.二:数组实现空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快.三:vector<int>实现时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源.四:queue<int>实现当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了,