一.漢諾塔問題
漢諾塔是一種古印度游戲，該游戲的實質就是在一塊木板上有三根固定的柱子
而在左邊的柱子上有著n個大小不同的圓盤，我們需要做就是把左邊所有的盤子全部移到右邊的柱子上，操作規則：1.圓盤在柱子上必須按照從大到小（大圓盤在下）依次排列，2.每次只能移動圓柱最上面的圓盤，
問題分析：先假設三根柱子分別為“A”"B""C",A柱有著所有的初始盤，我們的目的就是把A柱上的所有盤子全部移到C柱上，
n=1時，直接把圓盤從A柱移動到C柱就可，
n=2時，A-->B,A-->C,B-->C，（在這操作中B為中轉柱）
n=3時，A-->C,A-->B,C-->B,①A-->C,B-->A,B-->C,A-->C，對n=3這種情況進行分析：在①之前圓盤所在圓柱的情況有兩種：
1.是所有圓盤在A,B,C三個圓柱中都有一個圓盤，
2.是A，C上有圓盤而B上沒有圓盤，
由此可知在①前B柱是中轉柱；在①之后也有兩種情況：
1.只有B,C上有圓盤，
2.A,B,C上都有一個圓盤，
并且我們的游戲目標從一開始的把A上所有圓盤移到C柱（A-->C）,變成了把B上所有圓盤移到C柱上（B-->C）,而在這時中轉柱是A柱，
......
直到A上有n個圓盤時,現在對n這種情況進行分析：想要把n個圓盤從A柱移到C柱上有三大步驟：
①將A上n-1個圓柱全部移到C柱上（中轉柱B柱），
②將A上的一個圓盤移到C柱上，
③將B上n-1個圓盤全部移到C柱上（中轉柱A柱），
在這要穿插一下遞回的主要思想就是大事化小，現在將①步驟分為三個小步驟：
①將A上n-2個圓盤全部移到C柱上（中轉柱B柱），
②將A上第n-1個圓盤移到B柱上，
③將C上n-2個圓盤移到A柱上（中轉柱A柱），
然后將第二個①化為更小的三個步驟......就這樣一步步大事化小，
代碼實作：
#include<stdio.h>
void hanoi(int n, char post_1, char post_2, char post_3)
{
if (n == 1)
{
printf("%c --> %c\n", post_1, post_3);
}
else
{
hanoi(n - 1, post_1, post_3, post_2);
printf("%c --> %c\n", post_1, post_3);
hanoi(n - 1, post_2, post_1, post_3);
}
}
int main()
{
int n = 0;
char a = 'A', b = 'B', c = 'C';
scanf("%d", &n);
hanoi(n, a, b, c);
return 0;
}二.青蛙跳臺階問題
一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階，求該青蛙跳上一個n級臺階有多少種跳法？（實質就是斐波那契數列的變種）
問題分析：
我們不妨列舉一下n比較少的情況時的跳法：
①n=1時，1種跳法， ②n=2時，有2種跳法，
③n=3時，有3種跳法， ④n=4時，有5種跳法，
⑤n=5時，有8種跳法，
......
很明顯，同過觀察上面列舉的情況可以發現：
n=3時所有的跳法等于n=1時和n=2時的所有跳法之和；
n=4時的所有跳法等于n=2和n=3時的所有跳法之和；
......
以此類推可以得出f(n)=f(n-1)+f(n-2) (n>2)，（f(n)為跳法數量）
代碼實作：
#include<stdio.h>
int frogjump(int n)
{
if (n == 1)
{
return 1;
}
else if (n == 2)
{
return 2;
}
else
{
return frogjump(n - 1) + frogjump(n - 2);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
printf("%d", frogjump(n));
return 0;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/355415.html
標籤：其他
上一篇：步步為營，拿下三子棋
下一篇：掃雷（C語言版）