非递归方式：

我们计算n为4的情况：那么我们需要做如下的计算：     Fibonacci(4) = Fibonacci(3) + Fibonacci(2);     = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);     = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);  看看，多做了多少计算。2 计算了 2次，1 计算了5次，0计算了3次。正常来说我们计算4次就可以了吧。这样相当于多做了4次。

public static int fibnacci2(int n){
        if (n==0){
            return 0;
        }
        if (n==1 || n==2){
            return  1;
        }
        int f1=1;
        int f2=1;
        int count=3;
        while (count++<=n){
            int temp=f1;
            f1=f2;
            f2=temp+f2;
        }
        return f2;
    }

 4，C语言实现

我们设台阶数位N; 当N=1时，当然只有1种跳法； 当N=2时，青蛙可以跳2次1层和跳1次2层； 当N=3时，当有3层台阶时，青蛙可以选择先跳1层，剩下2层台阶，所以此时就是有2层台阶时的跳法，有2种；当青蛙选择第一次跳2层台阶时，剩下1层台阶，此时有1层台阶时的跳法，所以3层台阶时的方法是：2层台阶的方法 + 1层台阶的方法。 当N=4时，具体跳法为: 1、先跳1层 若先跳1层，则剩下3层，接下来就是3层台阶的跳法。 2、先跳2层 若先跳2层，则剩下2层，接下俩就是2层台阶的跳法，所以4层台阶的方法为：3层台阶的方法+2层台阶的方法。 以此类推，当N=n时，n层台阶的方法为: n-1层台阶的方法+ n-2 层台阶的方法。

#include<stdio.h>
int frog(int n)
{
   if(n == 1)
   {
      return 1;
   }
   if(n == 2)
   {
      return 2;
   }
   return frog(n-1) + frog(n-2);
}
int main()
{
   int n;
   scanf("%d",&amp;n);
   int ways = frog(n);
   PRintf("%dn",ways);
   return 0;
}

5，Java实现

递归方式：

public static int jump(int n){
        if (n==0)
            return 0;
        if (n==1)
            return 1;
        if (n==2)
            return 2;
        return jump(n-1)+jump(n-2);
    }

 非递归方式：

 public static int jump2(int n){
        if (n==0)
            return 0;
        if (n==1)
            return 1;
        if (n==2)
            return 2;
        int n1=1;
        int n2=2;
        int count=2;
        while (count++<=n){
            int tmp=n1;
            n1=n2;
            n2=tmp+n2;
        }
        return n2;
    }

三，汉诺塔问题

1，题目

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说益智游戏。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

2，图解

3，C语言实现

#include <stdio.h>
void hanoi(int n, char A, char B, char C)//n个圈圈在柱子A上，借助柱子B，移动到柱子C上
{
    if (n == 1)//如果A柱子上只有一个圈圈，直接移动到C上
        printf("%c --> %cn", A, C);
    else
    {
        hanoi(n - 1, A, C, B);//将A柱子上的n-1个圈圈，借助柱子C，移动到柱子B上
        printf("%c --> %cn", A, C);//将A柱子上的最后一个圈圈移动到柱子C上
        hanoi(n - 1, B, A, C);//将B柱子上的n-1个圈圈，借助柱子A，移动到柱子C上
    }
}

int main()
{
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

 4，Java实现

class Text{
    public static void move(char pos1,char pos2) {
        System.out.print(pos1+" -> "+pos2+" ");
    }

    public static void hanio(int n,char pos1,char pos2,char pos3) {
        if(n == 1) {
            move(pos1,pos3);
        }else {
            hanio(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            hanio(n-1,pos2,pos1,pos3);
        }
    }

    public static void main(String[] args) {
        hanio(1,'A','B','C');
        System.out.println();
        hanio(2,'A','B','C');
        System.out.println();
        hanio(3,'A','B','C');
        System.out.println();
    }
}