目錄

一，寫在前面

二，求解青蛙跳臺階

1，題目

2，圖解

3，斐波那契數列回顧

4，C語言實作

5，Java實作

三，漢諾塔問題

1，題目

2，圖解

3，C語言實作

4，Java實作

一，寫在前面

青蛙跳臺階和漢諾塔都是比較經典的題目，我覺得作為一個合格的程式員，應該要很好的掌握它，

如何你覺的本章博客寫的不錯的話，求收藏，求點贊，求評論，您的三連是我進步最大的動力，廢話不多說，讓我們學起來吧！！！

二，求解青蛙跳臺階

1，題目

一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果），

2，圖解

1. 如果n=1，只有一種跳法，那就是1

2. 如果n=2，那么有兩種跳法，2，[1,1]

3. 如果n=3，那么有三種跳法，[1,1,1],,[1,2],[2,1]

4. 如果n=4，那么有五種跳法，[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]

看到這里我們可能想到的斐波那契數列，先來回顧一下斐波那契數列，

3，斐波那契數列回顧

斐波那契數列含義（百度百科）：指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞回的方法定義：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

遞回方式：

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

非遞回方式：

我們計算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",&n);
   int ways = frog(n);
   printf("%d\n",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 --> %c\n", A, C);
    else
    {
        hanoi(n - 1, A, C, B);//將A柱子上的n-1個圈圈，借助柱子C，移動到柱子B上
        printf("%c --> %c\n", 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();
    }
}