亲宝软件园·资讯

展开

C++解跳台阶问题 使用C++递归求解跳台阶问题

Zhang_H 人气:0
想了解使用C++递归求解跳台阶问题的相关内容吗,Zhang_H在本文为您仔细讲解C++解跳台阶问题的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++,跳台阶,算法,递归,下面大家一起来学习吧。

题目:

一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级。求总共有多少总跳法?

分析:

也是比较基础的题目,通过递归可以方便的求解。
用Fib(n)表示青蛙跳上n阶台阶的跳法数,青蛙一次性跳上n阶台阶的跳法数1(n阶跳),设定Fib(0) = 1;
       当n = 1 时, 只有一种跳法,即1阶跳:Fib(1) = 1;
       当n = 2 时, 有两种跳的方式,一阶跳和二阶跳:Fib(2) = Fib(1) + Fib(0) = 2;
       当n = 3 时,有三种跳的方式,第一次跳出一阶后,后面还有Fib(3-1)中跳法; 第一次跳出二阶后,后面还有Fib(3-2)中跳法;第一次跳出三阶后,后面还有Fib(3-3)中跳法
        Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;
       当n = n 时,共有n种跳的方式,第一次跳出一阶后,后面还有Fib(n-1)中跳法; 第一次跳出二阶后,后面还有Fib(n-2)中跳法..........................第一次跳出n阶后,后面还有 Fib(n-n)中跳法.
       Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)
      又因为Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)
      两式相减得:Fib(n)-Fib(n-1)=Fib(n-1)         =====》  Fib(n) = 2*Fib(n-1)     n >= 2
      递归等式如下:

2016215164218510.png (464×172)

代码实现如下(GCC编译通过):

#include "stdio.h"
#include "stdlib.h"
 
int function(int n);
 
int main(void)
{
  int tmp;
   
  tmp = function(5);
  printf("%3d\n",tmp);
 
  return 0;
}
 
int function(int n)
{
  if(n == 1)
    return 1;
  else if(n == 2)
    return 2;
  else  
    return function(n-1) + function(n-2);
}

加载全部内容

相关教程
猜你喜欢
用户评论