解決河內塔問題的方法

『壹』 漢諾塔問題用什麼方法解決

漢諾塔（又稱河內塔）問題是印度的一個古老的傳說。開天闢地的神勃拉瑪在一個廟里留下了三根金剛石的棒。

第一根上面套著64個圓的金片，最大的一個在底下，其餘一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。

面對龐大的數字(移動圓片的次數)18446744073709551615(2^64-1)，看來，眾僧們耗盡畢生精力也不可能完成金片的移動。

相關信息

法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。

印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。

僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。

『貳』 河內塔問題與解題規律.....

解析：對於此題，我們一遇到此類題是不是有點讓人煩惱！為什麼要來回移動呢？一下整體搬過去不就好了嗎？

所以在遇到此類題時，一定要冷靜，不要急於做，而要思考，看看我們有什麼方法找到一種能夠比較簡單的規律。

第一，先我們將復雜的問題簡單化，考慮一下一些簡單的問題，這是我們解決此類問題的關鍵，就是當我們對一些較大的數形成的復雜邏輯不能夠理清時，我們要從最基本最簡單的數字如1，2，3，開始。如下：

假如只有1個穿孔圓盤，就需要移動1次。 A→C 1 次

假如只有2個穿孔圓盤，就需要移動3次。A→B， A→C，B→C 3次

假如只有3個穿孔圓盤，這時我們可以將上面的2個圓盤看做是一個整體，也就是將3分解成1+2.來考慮。如我們將最大的第三個圓盤，取消，只剩2個圓盤，這時藉助C柱，移動3次可以讓2個圓盤到從A到B柱。再考慮最大的圓盤，移動最大的第三個圓盤到C柱。這時藉助A柱，移動3次可以讓2個圓盤從B到C柱。就需要移動7次。

第二，從移動的次數中，尋找可以被我們利用的規律。

這7次中，前有3次是為了將上面的2個圓盤從A到B柱，中間1次是最大的圓盤A→C移動，後3次是為了將上面的2個圓盤從B到C柱移動。

從上面的兩個3次的移動看，兩個圓盤的移動必須經過3次方可成功。這也就是是2個圓盤必須經過3次移動才能從一個柱子到另一柱子。同理我們從這一步的7次移動來看，這也就是是3個圓盤必須經過7次移動才能從一個柱子到另一柱子

另外我們從移動次數的結果數據：1，3，7，這樣的數據分析，就得出這樣一個規律：

每增加1個圓盤的次數就是在前面既原來的次數的兩倍的基礎上，再加1次。

於是我們就可以根據上面的規律得出以下的結論：

有4個穿孔圓盤，最少的次數，15次。（是否正確，可以自己驗證一下）

有5個穿孔圓盤，最少的次數，31次。

有6個穿孔圓盤，最少的次數，63次。

我們將次數寫出一個數列，就得到如下數列：

1，3，7，15，31，63，……

這時我們就會發現它和我們知道它和我們上一講講到的一個如下數列非常相似。

2，4，8，16，32，64，128 ……

而上面的移動次數與數列有一個配合的規律，這時我們馬上就明白了，這道題的答案：
—1

『叄』 「河內塔問題」的解法

漢諾塔問題（又稱河內塔問題）是根據一個傳說形成的一個問題：

有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：

1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。

提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須尊循上述兩條規則。

問：如何移？最少要移動多少次？
一般取N=64。這樣，最少需移動264-1次。即如果一秒鍾能移動一塊圓盤，仍將需5845.54億年。目前按照宇宙大爆炸理論的推測，宇宙的年齡僅為137億年。

在真實玩具中，一般N=8；這將需移動255次。如果N=10，需移動1023次。如果N=15，需移動32767次；這就是說，如果一個人從3歲到99歲，每天移動一塊圓盤，他僅能移動15塊。如果N=20，需移動1048575次，即超過了一百萬次。
先看hanoi(1, one, two, three)的情況。這時直接將one柱上的一個盤子搬到three柱上。注意，這里one柱或three柱到底是A、B還是C並不重要，要記住的是函數第二個參數代表的柱上的一個盤被搬到第四個參數代表的柱上。為方便，將這個動作記為：
one =》three

再看hanoi(2, one, two, three)的情況。考慮到hanoi(1)的情況已經分析過了，可知這時實際上將產生三個動作，分別是：
one =》two
one =》three
two =》three
很顯然，這實際上相當於將one柱上的兩個盤直接搬到three柱上。

再看hanoi(3, one, two, three)的情況。分析
hanoi(2, one , three, two)
one =》three
hanoi(2, two, one, three)
即：先將one柱上的兩個盤搬到two柱上，再將one柱上的一個盤搬到three柱上，最後再將two柱上的兩個盤搬到three柱上。這不就等於將one柱上的三個盤直接搬到three柱上嗎？

運用歸納法可知，對任意n，
hanoi(n-1, one , three, two)
one =》three
hanoi(n-1, two, one, three)
就是先將one柱上的n-1個盤搬到two柱上，再將one柱上的一個盤搬到three柱上，最後再將two柱上的n-1個盤搬到three柱上。這就是我們所需要的結果！
回答者：wuchenghua121 - 經理 四級 12-5 11:51
漢諾塔
漢諾塔（又稱河內塔）問題是印度的一個古老的傳說。開天闢地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其餘一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。解答結果請自己運行計算，程序見尾部。面對龐大的數字(移動圓片的次數)18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動。

後來，這個傳說就演變為漢諾塔游戲:

1.有三根桿子A,B,C。A桿上有若干碟子
2.每次移動一塊碟子,小的只能疊在大的上面
3.把所有碟子從A桿全部移到C桿上

經過研究發現，漢諾塔的破解很簡單，就是按照移動規則向一個方向移動金片：
如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C

此外，漢諾塔問題也是程序設計中的經典遞歸問題。

補充：漢諾塔的演算法實現（c++）
#include <fstream>
#include <iostream>
using namespace std;

ofstream fout("out.txt");

void Move(int n,char x,char y)
{
fout<<"把"<<n<<"號從"<<x<<"挪動到"<<y<<endl;
}

void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}

int main()
{
fout<<"以下是7層漢諾塔的解法:"<<endl;
Hannoi(7,'a','b','c');
fout.close();
cout<<"輸出完畢！"<<endl;
return 0;
}

C語言精簡演算法
/* Copyrighter by SS7E */
#include<stdio.h> /* Copyrighter by SS7E */
void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("請輸入數字n以解決n階漢諾塔問題：\n");
scanf("%d",&n);
hanoi(n,'A','B','C');
}/* Copyrighter by SS7E */
回答者： Vanquisher_ - 舉人 五級 12-5 13:57
parcel::::::::::
program hanoi;
functionhanoi(x:integer):longint;
begin
if x=1 then hanoi:=1;
if x=2 then hanoi:=3;
else
begin
hanoi:=2*hanoi(x-1)+1;
end;
end;

begin
read(x){第幾個數 }
write(hanoi(x));
end.

思想就是：第N個就等於第n-1個乘以2+1次