漢諾塔（Tower of Hanoi）是一個源于印度古老傳說的益智玩具，基本規則很簡單，有三個立柱，然后在最左邊放著n個盤子疊成的“塔”，要求把所有盤子移到最右邊的柱子，一次只能移動一個盤子，并且不能從中間抽出盤子，即只能拿最上面的盤子，并且移動盤子程序中需始終遵循大盤子在小盤子下面的原則，
程式要求：已知三根柱子從左到右依次標號A、B、C，輸入一個正整數n，表示最左邊的柱子一開始盤子的個數，盤子初始狀態也遵循大盤子在小盤子下面的原則，并且盤子從小到大依次標號為1、2、…、n，要求列印出每次對盤子的操作，并且每次操作單獨占一行，比如：把柱子A最上面的標號為i的盤子移動到柱子B上，即列印“Move plate i from A to B."，操作結束后，要求列印操作的次數，
思路：
本文用遞回實作操作程序，因此要思考遞回實作問題的基本思路：大問題化小問題，遞回是一種經典的分治演算法思想，將大問題化為若干小問題解決，因此我們想到，如果要把A柱的n層塔移動到C柱，必須要把編號為n的盤子從A移動到C，而要移動編號為n的盤子，必須把標號為1到n-1的盤子移開，不然n號盤我們動不了，而且1號到n-1號盤子都必須在B柱，因為我們的n號盤要放在C柱的最底下，又因為盤子的疊放要遵循大盤子始終在小盤子下面的原則，因此這n-1個盤子均疊放在B柱并且是從小到大疊放的，即我們把一個n-1階的漢諾塔從A柱移動到了B柱，
看到這里可能有些讀者已經明白了這個演算法的實作程序，我們把三根柱子分成出發柱、程序柱、目的柱，比如我們的初始問題，把n階漢諾塔從A柱移動到C柱，那么A柱就是出發柱，C柱就是目的柱，B柱就是我們的程序柱，我們要借助這個程序柱實作我們的搬運程序，我們要實作n階漢諾塔的移動，就得先把n-1階的漢諾塔從A柱移動到B柱，然后把第n號盤從A柱移動到C柱，再把n-1階的漢諾塔移動到C柱，
而對于n-1階漢諾塔從A到B的移動，出發柱還是A，但是目的柱變成了B，程序柱變成了C，即利用C把盤堆從A移動到B，后來把n-1階漢諾塔從B到C的移動，出發柱成了B，目的柱變成了C，程序柱變成了A，而n-1階漢諾塔的移動又變成了n階漢諾塔的移動，只是這個n變成了n-1，所以我們在編程中要給遞回函式出發柱、程序柱、目的柱描述此時的程序，因此思路是這樣，下面上代碼：
#include<stdio.h>
int cont=0;//用來記錄操作次數，此處使用全域變數
void Hanoi(int n,char start,char end,char process)//此處識別符號的使用是為了便于讀者理解，實際使用時可以適當簡化
{
cont++;
if(n==1)//只剩最后一個盤子（即1號盤）時，直接移動即可
{
printf("Move plate 1 from %c to %c.\n",start,end);
return;
}
else
{//此大括號內的目的、程序、出發都是對本次函式體內的移動程序而言，即對此時n個盤子的移動程序而言
Hanoi(n-1,start,process,end);//將n-1階漢諾塔從出發柱移動到程序柱，通過目的柱
printf("Move plate %d from %c to %c\n",n,start,end);//將最下面的大盤子從出發柱直接移動到目的柱
Hanoi(n-1,process,end,start);//將n-1階漢諾塔從程序柱移動到目的柱，通過出發柱
}
}
int main(){
char a='A',b='B',c='C';
int n;
printf("Now tell me how much plates you want to move?\n")
scanf("%d",&n);
Hanoi(n,a,c,b);//把n個盤子從A柱移動到C柱，借助B柱
printf("There are %d moves in total.\n",cont);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/254960.html
標籤：其他
上一篇：javascript繼承