解決河內塔問題採用啥方法

⑴ 「河內塔問題」的解法

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

有三根桿子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次

⑵ 漢諾塔問題用什麼方法解決

1、計劃能力決定圓盤移動順序

完成漢諾塔任務時要對圓盤的移動順序進行預先計劃和回顧性計劃活動。當問題呈現後，在開始第一步的移動之前，大多數被試都會根據設定好的目標狀態，對圓盤的移動順序進行預先計劃。以決定圓盤的移動順序，但是這種計劃能力的作用可能會受到問題難度的影響。

2、抑制能力參與漢諾塔問題

為了把更大的圓盤先放置於指定位置，必須讓較小的圓盤暫時偏離其最終應該放置的位置，但被試的自然反應總是「盡快」將圓盤移動到最終的目的地，如此反而導致錯誤，使移動步數更多，完成時間更長。

3、對圓盤位置的記憶

臨床上常將漢諾塔任務用於腦損傷者執行功能的測查。由於執行功能存在多種表現形式，有必要對漢諾塔任務所屬的性質進行明確的歸類。在解決漢諾塔問題的過程中，對圓盤位置的記憶應該是存在的。

那麼這種記憶涉及的是工作記憶還是短時記憶，有研究發現漢諾塔任務與工作記憶沒有關系。但另有研究發現漢諾塔任務與空間工作記憶明顯相關，只是與詞語工作記憶關系不大。臨床上對腦損傷者或智力落後者的研究表明，空間工作記憶缺陷導致他們的漢諾塔問題成績明顯不如正常控制組。

簡介：

漢諾塔問題，是心理學實驗研究常用的任務之一。該問題的主要材料包括三根高度相同的柱子和一些大小及顏色不同的圓盤，三根柱子分別為起始柱A、輔助柱B及目標柱C。

⑶ 關於漢諾塔的問題。

利用遞歸解決漢諾塔，其最巧妙之處在於實參和形參的不斷變幻，實際的柱子也改變了，例如move(n-1,x,z,y)，借組z柱，移到y柱在進入遞歸時：形參move(int n,int x,int y,int z) /，移到z柱而在遞歸時; //，盤子數量減少了，和以前數學中的遞推證明非常接近,z所對應的實參, y 。就是形參x。數學的遞推證明的思想是;/ 函數的目的是把x柱的n個盤子，藉助y柱，假定n-1的時候是正確的，證明n也是正確就可以了。 遞歸過程的思想是，如果已經有了解決n的方法（漢諾塔中，移動n-1個盤子），怎麼來處理當前n的問題（如果n-1個盤子已經移好了，那隻要把最後一個盤子移過去就可以）。當然理解計算機的遞歸過程，柱子改變了; 這是把x柱的n-1個盤子，還要處理一下遞歸的結束條件（當n=1的時候），否則遞歸就不會結束了，在遞歸過程中是不斷改變的。注意

⑷ 河內塔(漢諾塔) 問題50分```求助``

漢諾塔是個典型的函數遞歸調用的例子。先弄明白遞歸的思路，再來看代碼。
漢諾塔的目的是把1柱上的N個盤子轉移到3柱，移動方法如下：
1、借3柱，將1柱上的N-1個盤子移到2柱上；
2、將1柱上最下面的盤子移到3柱；
3、借1柱，將2柱上的N-1個盤子移到3柱。

其中，1、3步是不可能一步完成的。
其實上面的三步就是void hanoi(int n,int p1,int p2,int p3)中的三個語句，只是表達方法不同。
我們不用去關心到底如何「將1柱上的N-1個盤子移到2柱上」或者「將2柱上的N-1個盤子移到3柱」，因為上面的三個語句已經給出了一種正確的方法，不論N是多少，此方法都正確。計算機會將1、3兩步展開，直到N是1 。手工也可以將其展開，你可以試試把1、3兩步分別展開，N=4時也不難做到，但好像沒什麼意義。

最後說一句，應該相信正確的方法，而不必知道它的細節，就跟黑箱一樣。

⑸ 河內塔問題

3個的話7次，4個的話15次
1個的話1次，2個的話就是把一個先移到柱子2上，把第二個移到柱子3，再把第一個移到柱子3，2*1+1=3次
3個的話，把2個先移到柱子2，用3步，把第三個移到柱子3,1步，再把2個移到柱子3,所以3*2+1=7次
4個的話同理，2*7+1=15,。

⑹ 關於漢諾塔問題的盡可能多的信息

program hanoi(input,output);
VAR total:integer;
procere move(n,a,b,c:integer);
begin
if n=1
then writeln (a,'->',c)
else begin
move(n-1,a,c,b);
writeln(a,'->',c);
move(n-1,b,a,c);
end;{if}
end;{move}
begin{hanoi}
readln(total);
move (total,1,2,3) ;
readln
end.{hanoi漢諾塔的問題；

這個問題對於我這個初學者來說，確實棘手，對於執行的步驟很不理解，雖然遞歸不用去了解執行的步驟的。但是，不用去了解不等同於不了解。

一個廟里有三個柱子，第一個有64個盤子，從上往下盤子越來越大。要求廟里的老和尚把這64個盤子全部移動到第三個柱子上。移動的時候始終只能小盤子壓著大盤子。

1、此時老和尚（後面我們叫他第一個和尚）覺得很難，所以他想：要是有一個人能把前63個盤子先移動到第二個柱子上，我再把最後一個盤子直接移動到第三個柱子，再讓那個人把剛才的前63個盤子從第二個柱子上移動到第三個柱子上，我的任務就完成了，簡單。所以他找了比他年輕的和尚（後面我們叫他第二個和尚）（呵呵，倚老賣老），命令：

① 你把前63個盤子移動到第二柱子上

② 在我自己把第64個盤子一道第三個柱子上後

③ 你把前63個盤子移動到第三柱子上

2、第二個和尚接了任務，也覺得很難，所以他也和第一個和尚一樣想：要是有一個人能把前62個盤子先移動到第三個柱子上，我再把最後一個盤子直接移動到第二個柱子，再讓那個人把剛才的前62個盤子從第三個柱子上移動到第三個柱子上，我的任務就完成了，簡單。所以他也找了比他年輕的和尚（後面我們叫他第三和尚）（呵呵，又倚老賣老），命令：

① 你把前62個盤子移動到第三柱子上

② 在我自己把第63個盤子一道第二個柱子上後

③ 你把前62個盤子移動到第二柱子上

3、第三個和尚接了任務，又把移動前61個盤子的任務依葫蘆話瓢的交給了第四個和尚，等等遞推下去，直到把任務交給了第64個和尚為止（估計第64個和尚很郁悶，沒機會也命令下別人，因為到他這里盤子已經只有一個了）。

4、到此任務下交完成，到各司其職完成的時候了。

完成回推了：

第64個和尚移動第1個盤子，把它移開，然後第63個和尚移動他給自己分

配的第2個盤子。第64個和尚再把第1個盤子移動到第2個盤子上。到這里第64個和尚的任務完成，第63個和尚完成了第62個和尚交給他的任務的第一步。

從上面可以看出，只有第64個和尚的任務完成了，第63個和尚的任務才能完成，只有第2個和尚—第64個和尚的任務完成後，第1個和尚的任務才能完成。這是一個典型的遞歸問題。

現在我們以有3個盤子來分析：

第1個和尚命令：

一 第2個和尚你先把第一柱子前2個盤子移動到第二柱子。（藉助第三個柱子）

二第1個和尚我自己把第一柱子最後的盤子移動到第三柱子。

三第2個和尚你把前2個盤子從第二柱子移動到第三柱子。

很顯然，第二步很容易實現（哎，人總是自私地，把簡單留給自己，困難的給別人）

其中第一步。第2個和尚他有2個盤子，他就命令：

① 第3個和尚你把第一柱子第1個盤子移動到第三柱子。（藉助第二柱子）

② 第2個和尚我自己把第一柱子第2個盤子移動到第二柱子上。

③ 第3個和尚你把第1個盤子從第三柱子移動到第二柱子。

同樣，第步很容易實現，但第3個和尚他只需要移動1個盤子，所以他也不用在下派任務了。（注意：這就是停止遞歸的條件，也叫邊界值）

第三步可以分解為，第2個和尚還是有2個盤子，命令：

①第3個和尚你把第二柱子上的第1個盤子移動到第一柱子。

② 第2個和尚我把第2個盤子從第二柱子移動到第三柱子。

③第3個和尚你把第一柱子上的盤子移動到第三柱子。

分析組合起來就是：1à3 1à2 3à2 1à3 2à1 2à3 1à3共需要七步。如果是4個盤子，則第一個和尚的命令中第1步和第3步各有3個盤子，所以各需要7步，共14步，再加上第1個和尚的1步，所以4個盤子總共需要移動7+1+7=15步，同樣，5個盤子需要15+1+15=31步，6個盤子需要31+1+31=64步……由此可以知道，移動n個盤子需要（2的n次方）--1步。

從上面整體綜合分析可知把n個盤子從1座（相當第一柱子）移到3座（相當第三柱子）：

（1）把1座上（n-1）個盤子藉助3座移到2座。

（2）把1座上第n個盤子移動3座。

（3）把2座上（n-1）個盤子藉助1座移動3座。

下面用hanoi（n,a,b,c）表示把1座n個盤子藉助2座移動到3座。

很明顯，(1)步上是 hanoi(n-1,1,3,2)

(2)步上是hanoi(n-1,2,1,3)

下面便是代碼：

#include<stdio.h>

static long int m=1;/*用來計算移動步驟步數,靜態變數才能不斷疊加*/

void hanoi(int n,int a,int b,int c)

{

if(n==1){

printf("(%d) %d-->%d\n",m,a,c);

m++;

}

else{

hanoi(n-1,a,c,b);

printf("(%d) %d-->%d\n",m,a,c);/*只有當上一句得到結果，它才會執行*/

m++;

hanoi(n-1,b,a,c);

}

}

main()

{

int d;

printf("Enter the hanoi shu:");

scanf("%d",&d);

hanoi(d,1,2,3);

return 0;

}

執行：

Enter the hanoi shu: 3

（1）1à3

（2）1à2

（3）3à2

（4）1à3

（5）2à1

（6）2à3

（7）1à3

這里可能有個疑問：移動n-1個盤子確實是上面的步驟，但移動n-2的時候就不一樣了啊？

hanoi(n-1,a,c,b);

printf("(%d) %d-->%d\n",m,a,c);/*只有當上一句得到結果，它才會執行*/

m++;

hanoi(n-1,b,a,c);

其實每一次調用hanoi（n,a,b,c）時a，b，c的值都不同。

如hanoi(n,1,2,3)時a=1,b=2,c=3.

hanoi(n-1,a,c,b);{a=1,b=2,c=3}

就是hanoi(n-1,1,3,2);

所以調用的就是1à2

再次調用成了hanoi(n-2,a,c,b){a=1,b=3,c=2}

就是hanoi(n-2,1,2,3);

所以調用的就是，1à3;

每一次都能不斷自動改變。

Hanoi塔問題中函數調用時系統所做工作

一個函數在運行期調用另一個函數時，在運行被調用函數之前，系統先完成3件事：

①將所有的實參、返回地址等信息傳遞給被調用函數保存。

②為被調用函數的局部變數分配存儲區；

③將控制轉移到被調用函數的入口。

從被調用函數返回調用函數前，系統也應完成3件事：

①保存被調用函數的結果；

②釋放被調用函數的數據區；

③依照被調用函數保存的返回地址將控制轉移到調用函數。

當有多個函數構成嵌套調用時，按照「後調用先返回」的原則（LIFO），上述函數之間的信息傳遞和控制轉移必須通過「棧」來實現，即系統將整個程序運行時所需的數據空間安排在一個棧中，每當調用一個函數時，就為其在棧頂分配一個存儲區，每當從一個函數退出時，就釋放其存儲區，因此當前運行函數的數據區必在棧頂。堆棧特點：LIFO，除非轉移或中斷，堆棧內容的存或取表現出線性表列的性質。正是如此，程序不要求跟蹤當前進入堆棧的真實單元，而只要用一個具有自動遞增或自動遞減功能的堆棧計數器，便可正確指出最後一次信息在堆棧中存放的地址。

一個遞歸函數的運行過程類型於多個函數的嵌套調用，只是調用函數和被調用函數是同一個函數。因此，和每次調用相關的一個重要的概念是遞歸函數運行的「層次」。假設調用該遞歸函數的主函數為第0層，則從主函數調用遞歸函數為進入第1層；從第i層遞歸調用本函數為進入下一層，即i＋1層。反之，退出第i層遞歸應返回至上一層，即i－1層。為了保證遞歸函數正確執行，系統需設立一個「遞歸工作棧」，作為整個遞歸函數運行期間使用的數據存儲區。每一層遞歸所需信息構成一個「工作記錄」，其中包括所有實參、所有局部變數以及上一層的返回地址。每進入一層遞歸，就產生一個新的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個工作記錄，則當前執行層的工作記錄必是遞歸工作棧棧頂的工作記錄，稱這個記錄為「活動記錄」，並稱指示活動記錄的棧頂指針為「當前環境指針」。

⑺ 河內塔問題與解題規律.....

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

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

第一，先我們將復雜的問題簡單化，考慮一下一些簡單的問題，這是我們解決此類問題的關鍵，就是當我們對一些較大的數形成的復雜邏輯不能夠理清時，我們要從最基本最簡單的數字如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

⑻ 6、演算法式、手段一目的分析法、逆向推理法、爬山法、計劃簡化法是五種解決問

摘要 1.手段—目的分析

⑼ 漢諾塔問題用什麼方法解決

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

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

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

相關信息

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

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

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