漢諾塔問題演算法分析

① 漢諾塔演算法問題

怎麼我看起來亂七八糟的呢?
至少 C語言裡面 main()函數是不可以被其他函數調用的,你那樣定義main()函數個人覺得是不正確的,main()函數怎麼能有返回值呢?

② 漢諾塔問題

TMD 連個問題都沒

③ 漢諾塔問題演算法

用遞歸實現：

#include <iostream.h>

void Towers(int n, char fromPeg, char auxPeg, char toPeg)
{
if (1 == n) //遞歸出口
{
cout << "Move Disk 1 from Peg " << fromPeg << " to Peg " << toPeg << endl;
return;
}

//把n-1個盤子從fromPeg藉助toPeg移動到auxPeg
Towers(n - 1, fromPeg, toPeg, auxPeg);

//把盤子n由fromPeg直接移動到toPeg
cout << "Move Disk " << n << " from Peg " << fromPeg << " to Peg " << toPeg << endl;

//把n-1個盤子從auxPeg藉助fromPeg移動到toPeg
Towers(n - 1, auxPeg, fromPeg, toPeg);
}

int main()
{
int n = 0;
cout << "Pleae input disk number:";
cin >> n;
Towers(n, 'A', 'B', 'C');

return 0;
}

④ 漢諾塔演算法步驟解析

這是一個遞歸的過程,你要自己搞個簡單例子擺一擺,再看看我的解釋就明白了

hanoi(n-1, A, C, B);//將n-1個盤通過c從a移到b
printf("Move sheet %d from %c to %c\n", n, A, C);//將第n個盤從a移到c
hanoi(n-1, B, A, C);//將n-1個盤通過a從b移到c

⑤ 漢諾塔問題的遞歸演算法流程圖

關鍵是第一步移法，奇數層的說，3層在第一柱，後兩根柱數數：123。所以，第一塊應放在第二根柱，4層，第一塊放第三柱。...........奇數層第一塊放第二柱，偶數層第一塊放第三柱。

⑥ 漢諾塔遞歸演算法分析

我之前回答過的，http://..com/question/499530116.html?oldq=1&from=evaluateTo#reply-box-1259261416

⑦ 漢諾塔問題公式是什麼

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

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

⑧ 漢諾塔問題演算法詳細解答

#include <stdio.h>
void hanio(int n,char a,char b,char c)
{
if(n>=1)
{hanio(n-1,a,c,b);//可以理解為把a上的n-1個盤子通過c移動到b上
printf("%c--> %c\n",a,c);//然後再把a上剩下的一個盤子移動到c上
hanio(n-1,b,a,c);//再把b上的n-1個盤子通過a移動到c上，搞定，遞歸程序，看起來簡單，理解起來稍微有點難度，調試也不容易，你用多了就明白了
}
}
int main ()
{
int n ;
printf("please input the num:\n");
scanf("%d",&n) ;
//盤子數為n，三個柱子分別為ABC
hanio ( n, 'A' , 'B' , 'C' ) ;
return 0;
}

⑨ 怎麼用歸納法證明漢諾塔問題 演算法設計與分析的課後習題

如果柱子標為ABC，要由A搬至C，在只有一個盤子時，就將它直接搬至C，當有兩個盤子，就將B當作輔助柱。
如果盤數超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A->B、A ->C、B->C這三個步驟，而被遮住的部份，其實就是進入程式的遞回處理。
事實上，若有n個盤子，則移動完畢所需之次數為2^n - 1

演演算法Procere HANOI(n, A, B, C) [
IF(n == 1) [
PRINT("Move sheet " n " from " A " to " C);
]
ELSE [
HANOI(n-1, A, C, B);
PRINT("Move sheet " n " from " A " to " C);
HANOI(n-1, B, A, C);
]
]

⑩ 漢諾塔問題的遞歸求解演算法,並分析演算法的時間復雜性

void Hanoi(int n, char a, char b, char c)
{
if(n==1) //只有一個盤子，直接移動
printf("move %c to %c\n", a, c);
else
{
Hanoi(n-1, a, c, b); //將n-1個盤子從a柱移動到b柱
printf("move %c to %c\n", a, c); //將最後一個盤子從a柱移動到c柱
Hanoi(n-1, b, a, c); //將n-1個盤子從b柱移動到c柱
}
}時間復雜度下限是O(2n)