1、漢諾塔問題
問題背景：
相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲，該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤(如下圖)，游戲的目標:把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好，操作規則:每次只能移動一個盤子，并且在移動程序中三根桿上都始終保持大盤在下，小盤在上，操作程序中盤子可以置于A、B、C任一桿上，
（來自360百科）
A B C
首先分析一下問題：
題目中我們有一個十分重要的限制條件，就是在我們移動銅板的時候，一定要小的銅板在大的銅板上面
依據這個，我們可以簡單的有影像來展現我們的想法（圖有點丑，各位見諒哈）：
1、從A將最小塊移動到C上
2、從A將中間塊移動到B上
3、從C將最小塊移動到B上
4、從A將最大塊移動到C上
5、從B將最小快移動到A上面
6、從B 將中塊移動到C上
7、從A將最小快移動到C上
透過方法對其中的演算法進行分析 ：
通過圖解我們可以知道，在前三步中我們所做就是將最上面的兩塊移動到另外兩個柱子中的一個，在第四步中將最大塊移動到另外一個柱子上面，在后三步中將另外上面的兩塊移動到大塊的上面，
通過上面分析，我們可以再進一步抽象成數學模型來更加深入了解一下
前三步我們可以理解為是將上面兩塊進行一個漢諾塔問題的運作，然后中間一步是將大塊移動到另外一塊上面，然后最后三步是將另外兩塊再做一次漢諾塔問題的運作，這樣就完成了三塊的漢諾塔問題運作，
進而我們可以把三塊推廣到更為普遍的n塊來分析
簡單的理解就是先將上面n-1塊進行漢諾塔的運作，然后將最下面的第n塊放到另外一個柱子上面，最后將上面n-1塊再次漢諾塔運作放在最大快的上面，
至此我們對其中的演算法已經分析完畢，建立起了數學模型，接下來我們探討一下，再進行漢諾塔問題是n塊的操作步數的計算分析：
我們可以設n塊時候的操作步數為f(x);
f(x)=f(x-1)+1+f(x-1)=2f(x-1)+1
當x=0；f(x)=0;
當x=1；f(x)=1;
當x=2；f(x)=3;
當x=3；f(x)=7;
.......................
通過適當分析可知，[f(x)-1]是2的指數式增長，據此我們可以抽象出其中的數學模型為
x>=1 f(x)=2^x-1
x=0 f(x)=0
到此我們的分析已經全部結束了，接下來就是我們代碼實作的程序了
void move(char from , char to)
{
printf("將%c柱子最上面的圓盤->放到%c柱子上面\n", from, to);
}
void hanoi(char A,char B,char C,int n) //函式目的將n個圓盤按照漢諾塔規則從A柱子移動到C柱子上面(函式默認最開始都在A上最后移動到B上面)
{
if (n == 1)
{
move(A, C);
}
else
{
hanoi(A,C,B,n - 1);
move(A, C);
hanoi(B, A, C, n - 1);
}
}
int main()
{
char A = 'A';
char B = 'B';
char C = 'C'; //ABC分別表示三個柱子
int n = 0;
printf("請輸入漢諾塔的圓盤個數:\n");
scanf("%d", &n); //n為有幾個圓盤
hanoi(A,B,C,n); //呼叫漢諾塔函式函式給出步驟
}
2、斐波那契數列
背景介紹：
該數列提出者意大利數學家列昂納多·斐波那契（Leonardo Fibonacci）提出的，該數列又稱為黃金分割數列，其基本排列為：
1，1，2，3，5，8，13.......(j簡而言之就是從第三個開始該數是前兩個數之和)
（來自360百科）
演算法分析：
首先我們分析可知第n個數為前兩個數之和那么用數學語言表達就是
fib(n)=fib(n-1)+fib(n-2) [這里的n>2]
其實這里這里的遞回思維就已經產生了，我們可以將求第n個數轉化成求n-1和n-2,并無限的這樣下分下去直到第一個第二個數，這樣我們的數學模型就建立出來了，下面就是代碼實作了
1、遞回的方法求斐波那契數列
int fib(m)
{
int a = 1;
int b = 1;
if (m > 2)
return fib(m - 1) + fib(m - 2);
else
return 1;
}
int main()
{
int m = 0;
scanf("%d", &m);
int ret=fib(m);
printf("%d", ret);
return 0;
}
備注： 在這里雖然遞回方法可以解決斐波那契數列問題，不過隨著數字越來越靠后，運行次數將幾何倍數增加，嚴重拖慢運行速度，因此個人認為在這道題有非遞回解決可能更方便，不過由于這里介紹遞回經典例題我就不詳細講這種方法了，代碼奉上給各位有問題我們可以私信或者評論區探討
int fib(int m)
{
int ret = 1;
int a;
int b=1;
while (m > 2)
{
m -= 1;
a = b;
b = ret;
ret = a + b;
}
return ret;
}
int main()
{
int m = 0;
scanf("%d", &m);
int ret = fib(m);
printf("%d", ret);
return 0;
}3、青蛙跳臺階問題
問題背景：
一只青蛙一次可以跳上1級臺階，也可以跳上2 級，，此時該青蛙跳上一個n級的臺階總共有多少種跳法
演算法分析：
當只有一級臺階時候，那么就只有跳上去一個方法，因此跳法就是1；
當只有兩級臺階時候，那么我們可以先跳一級再跳一級或者直接跳兩個，因此跳法就是2；
當有三級及三級以上臺階的時候，我們可以分析一下，題目說一次只能跳一級或者兩級臺階，因此那豈不是我們要是求出了跳n-1個臺階跳法和跳n-2個臺階跳法，然后跳n-1個的就只有跳一個的一種方法因此乘以1，同理n-2個的乘以2，就可以求出跳n級的方法，
因此用數學語言表達：
jump(n)=jump(n-1)+jump(n-2)*2
這就對了嗎？
答：錯
不知道各位在我的分析程序中不知道有沒有發現一個漏洞，在我們算n-2個臺階時候，連續跳兩次的這個程序與我們算n-1個臺階的時候重復了，因此在這里應該把重復的那次扣除，也就是n-2那次不用乘以2即可
jump(n)=jump(n-1)+jump(n-2)
到這里我們的分析就算全部分析完了，下面就是代碼實作了
備注：同斐波那契數列一樣這里用遞回的話數字一大，計算機運算時間過慢，各位可以根據上面提供的另一種方法寫出這個的另一種方法
歡迎各位評論區留下意見~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294565.html
標籤：其他
上一篇：C++實作打飛機與彈球游戲
下一篇：童年回憶《三子棋》