漢諾塔是一個非常經典的問題，其背后是一個傳說故事：
在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針，印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔，不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面，僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡，
抽象為數學問題就是：
有三根相鄰的柱子，標號為a,b,c，a柱子上從下到上按金字塔狀疊放著n個不同大小的圓盤，要把所有盤子一個一個移動到柱子c上，并且每次移動同一根柱子上都不能出現大盤子在小盤子上方，請問至少需要多少次移動，設移動次數為H(n)，
那么如何用C語言編程解決這個問題呢？
不難想到，通過遞回來實作代碼，將這個復雜的問題轉化為簡單的問題，其思想是先將a柱上的n-1個盤子借助c柱移到b柱上，然后把a柱上第n個盤子移到c柱上，最后將b柱上的n-1個盤子借助a柱移到c柱上，
#include <stdio.h>
void move(char x, char y)//把盤子從x柱移到y柱
{
static int i = 0;//記錄移動的次數
i++;
printf("第%d次把盤子從%c柱移到%c柱\n", i, x, y);
}
void Hanoi(int n, char A, char B, char C)//把n個盤子從A柱借助B柱移到C柱
{
if (n == 1)//遞回限制條件（達到該條件則不再遞回）：A柱上最后一個盤子從A柱移動到C柱
{
move(A, C);
}
else if(n > 1)
{
Hanoi(n - 1, A, C, B);//把A柱上n-1個盤子借助C柱移到B柱
move(A, C);//A柱上n-1個盤子移到B上之后將A柱上第n個盤子移到C柱
Hanoi(n - 1, B, A, C);//將B柱上n-1個盤子借助A柱移到C柱
}
}
int main()
{
int n = 0;
printf("input n:\n");
scanf("%d", &n);
char x = 'a';
char y = 'b';
char z = 'c';
Hanoi(n, x, y, z);
return 0;
}
以3個盤子為例，來看看解決方案：
這就是漢諾塔問題的C語言實作，希望各位能夠點個贊~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277756.html
標籤：其他
上一篇：淺談我涉及到的編程語言