使用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
      递归等式如下：

代码实现如下（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);
}
赞 (0)

相关推荐

  • C++求阶乘的两种方法

    1.使用静态局部变量static静态局部变量在函数调用结束之后不消失而保留原值,即其占用的存储单元不释放,在下一次该函数调用时,该变量保留上一次函数调用结束时的值. 静态局部变量赋初值实在编译时进行的,即只赋初值一次,在程序运行时它已有初值. code: 复制代码 代码如下: #include<iostream>using namespace std;int fac(int n){ static int f=1; f=f*n; return f;}int main(){ int i; for(

  • C++使用递归方法求n阶勒让德多项式完整实例

    C++使用递归方法求n阶勒让德多项式完整实例

    本文实例讲述了C++使用递归方法求n阶勒让德多项式的实现方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 24 日 * 版 本 号:v1.0 * 输入描述: * 问题描述: 用递归方法求n阶勒让德多项式的值.. * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std; int main() { double p(double,double); double s

  • C++求四个正整数最大公约数的方法

    C++求四个正整数最大公约数的方法

    本文实例讲述了C++求四个正整数最大公约数的方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 输入四个正整数,输出其最大公约数. * 问题描述: * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std; int f(int,int); int g(int,int,int,int); int main()

  • C语言解3元1次方程组 用初中学的最基本的联合消元法

    C语言解3元1次方程组 用初中学的最基本的联合消元法

    没学过线性代数,但是很多算法都和矩阵相关,所以就硬着头皮学.最近就想自己能不能先写个算线性方程组的程序呢?后来就想了这么个方法,暂时只能算3元的,任意元的接下来继续想.有太多硬编码,希望有兴趣的读者可以给点修改建议! 复制代码 代码如下: #include "stdafx.h"//VS2010需要#include "stdio.h"#include "stdlib.h"#include "math.h"double x[3];

  • C++通过自定义函数求一元二次方程的根

    C++通过自定义函数求一元二次方程的根

    本文实例讲述了C++通过自定义函数求一元二次方程的根.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 24 日 * 版 本 号:v1.0 * 输入描述: * 问题描述: 求一元二次方程的根.定义函数 * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> #include<cmath> using namespace std; double x,x1,x2,t; //定义全局变量 void

  • C++短路求值（逻辑与、逻辑或）实例

    C++短路求值（逻辑与、逻辑或）实例

    本文实例讲述了C++短路求值(逻辑与.逻辑或),分享给大家供大家参考.具体方法分析如下: 1.逻辑或的短路 首先看如下代码: #include <iostream> using namespace std; int main() { int a = 1; cout << "a = " << a <<endl; true || (a=0); cout << "a = " << a <<

  • C语言解线性方程的四种方法

    发了好几天编了个解线性方程组的小程序,可第一次实战就大败而归.经过半天的调试,仍找不出纠正的方法.因为并不是算法的问题,而是因为自己对编译器处理 浮点函数的方法不是很理解.明明D=0的方阵解出来不等于0了,跟踪调试发现,计算过程程序对数据进行了舍去处理,导致最终结果不对.不过如果没有浮点型 的话,这个程序应该算不错了 . 复制代码 代码如下: #include<stdio.h>#include<math.h>#include<mem.h>#define NUM 100v

  • c#实现一元二次方程求解器示例分享

    复制代码 代码如下: using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Windows.Forms;namespace WindowsFormsApplication4{public partial class Form1 :

  • 在线一元二次方程计算器实例(方程计算器在线计算)

    复制代码 代码如下: <html><head><meta http-equiv="Content-Type" content="text/html" charset="utf-8"><title>在线一元二次方程式计算器</title></head><body><form name="fquad">    <p align=&

  • C++求Fib数列

    1. 第一版本程序 int fib(int pos) { int elem = 1; int n1 = 1, n2 = 1; for (int i = 3; i <= pos; i++) { elem = n2 + n1; n1 = n2; n2 = elem; } return elem; } 2. 第二版本 bool fib(int pos, int &elem) { if(pos < 0 || pos > 1024) { elem = 0; return false; }

  • C++利用链栈实现表达式求值

    本文实例为大家分享了C++利用链栈实现表达式求值的具体代码,供大家参考,具体内容如下 #include<iostream.h> typedef int Status; typedef char Cstack; #define OK 1 #define ERROR 0 typedef struct StackNode { Cstack data; struct StackNode *next; }StackNode,*LinkStack; Status InitStack(LinkStack &

随机推荐