本文目錄一覽：
用C語言編寫汗諾塔的代碼誰知道哪裡有?
/********hanoi.c*********/
#include graphics.h
struct H
{
int data[15];/*存放每個盤的代號*/
int top;/*每個塔的具體高度*/
}num[3];/*三個塔*/
void move(char x,char y,struct H num[3]);/*移動的具體過程*/
void hanoi(char x,char y,char z,int n,struct H num[3]);/*遞歸*/
void Init(void);/*初始化*/
void Close(void);/*圖形關閉*/
int computer=1;/*自動控制與手動控制的標誌*/
int speed=0;/*全局變數speed主要是演示過程的速度*/
void main(void)
{
Init();/*初始狀態*/
Close();/*圖形關閉*/
exit(0);
}
void Init(void)/*初始化*/
{
int gd=DETECT,gm;
int i,n,color;
clrscr();
printf(“please input n(n=10): “);/*輸入要演示的盤子數*/
scanf(“%d”,n);
printf(“Please input 1 or 2:\n1.computer 2.people\n”);
scanf(“%d”,i);
if(i==2)/*選擇手動控制標誌為0*/
computer=0;
if(n1||n10)
n=10;/*越界的話n當10處理*/
if(computer)/*如果是自動控制的話輸入速度*/
{
printf(“please input speed: “);/*輸入速度*/
scanf(“%d”,speed);
}
initgraph(gd,gm,”c:\\tc”);
cleardevice();
for(i=0;i3;i++)
num[i].top=-1;/*三個地方的高度開始都為-1*/
for(i=0;in;i++)/*畫一開始的塔座A上的盤子*/
{
num[0].top++;/*棧的高度加1*/
num[0].data[num[0].top]=i; /*最大的盤子代號為0，依次為1，2，…n-1*/
color=num[0].data[num[0].top]+1;/*盤子的顏色代碼為棧頂盤子代號加1*/
setfillstyle(SOLID_FILL,color);
bar(100-(33-3*num[0].data[num[0].top]),400-20*i-8,100+
(33-3*num[0].data[num[0].top]),400-20*i+8); /*畫矩形*/
}
setcolor(YELLOW);
outtextxy(180,450,”any key to continue”);
settextstyle(0,0,2);
outtextxy(90,420,”A”); /*塔座標誌*/
outtextxy(240,420,”B”);
outtextxy(390,420,”C”);
getch();/*接收字元後就執行遞歸操作*/
hanoi(‘a’,’b’,’c’,n,num);
}
void move(char x,char y,struct H num[3])/*移動的具體過程*/
{
int i;
char num1[3],num2[3];
sprintf(num1,”%c”,x-32);/*將小寫變成大寫，並轉換成字元串輸出*/
sprintf(num2,”%c”,y-32);
setfillstyle(SOLID_FILL,BLACK);/*把原來的地方移去塗黑*/
bar(0,0,640,60);
setcolor(RED);
outtextxy(150,30,num1);/*輸出移動過程*/
outtextxy(200,30,”—“);
outtextxy(310,30,num2);
settextstyle(0,0,2);
setfillstyle(SOLID_FILL,BLACK);/*把原來的地方移去塗黑*/
bar(100+150*(x-97)-(33-3*num[x-97].data[num[x-97].top]),
400-20*num[x-97].top-8,100+150*(x-97)+(33-3*
num[x-97].data[num[x-97].top]),400-20*num[x-97].top+8);
num[y-97].top++;/*入棧，目標點的top加1*/
num[y-97].data[num[y-97].top]=num[x-97].data[num[x-97].top];/*在目標點盤子的代號與源點盤子的代號相同*/
num[x-97].top–;/*出棧，原來地方的top減1*/
setfillstyle(SOLID_FILL,num[y-97].data[num[y-97].top]+1);/*盤子顏色代碼是棧頂盤子代號加1*/
bar(100+150*(y-97)-(33-3*num[y-97].data[num[y-97].top]),
400-20*num[y-97].top-8,100+150*(y-97)+
(33-3*num[y-97].data[num[y-97].top]),400-20*num[y-97].top+8);
if(computer)/*自動控制就用delay*/
delay(speed);/*延時函數*/
else
getch();/*手動控制的話就自己按鍵盤來控制*/
}
void hanoi(char one,char two,char three,int n,struct H num[3])/*遞歸n為盤子數，num為堆棧*/
{
if(n==1)
move(one,three,num);/*如果盤子為1，將這個盤子從塔座A移動到塔座C*/
else
{
hanoi(one,three,two,n-1,num);/*將塔座A的前n-1個盤子移到塔座B*/
move(one,three,num);/*將塔座A的第n個盤子移到塔座C*/
hanoi(two,one,three,n-1,num); /*將塔座B的n-1個盤子移到塔座C*/
}
}
void Close(void)/*圖形關閉*/
{
getch();
closegraph();
}
遞歸 漢諾塔 問題 快點來個人吧 急死了 出事了
引用譚書第一版。
函數的遞歸調用
一個函數在它的函數體內調用它自身稱為遞歸調用。 這種函數稱為遞歸函數。C語言允許函數的遞歸調用。在遞歸調用中， 主調函數又是被調函數。執行遞歸函數將反覆調用其自身。 每調用一次就進入新的一層。例如有函數f如下：
int f (int x)
{
int y;
z=f(y);
return z;
}
這個函數是一個遞歸函數。 但是運行該函數將無休止地調用其自身，這當然是不正確的。為了防止遞歸調用無終止地進行， 必須在函數內有終止遞歸調用的手段。常用的辦法是加條件判斷， 滿足某種條件後就不再作遞歸調用，然後逐層返回。 下面舉例說明遞歸調用的執行過程。
你這裡的條件是if(n==1)，就是A針上只有一個盤子，才結束調用函數，返回到上一個函數里，依次倒推。
Hanoi塔問題
一塊板上有三根針，A，B，C。A針上套有64個大小不等的圓盤， 大的在下，小的在上。如圖5.4所示。要把這64個圓盤從A針移動C針上，每次只能移動一個圓盤，移動可以藉助B針進行。但在任何時候，任何針上的圓盤都必須保持大盤在下，小盤在上。求移動的步驟。
本題演算法分析如下，設A上有n個盤子。
如果n=1，則將圓盤從A直接移動到C。
如果n=2，則：
1.將A上的n-1(等於1)個圓盤移到B上；
2.再將A上的一個圓盤移到C上；
3.最後將B上的n-1(等於1)個圓盤移到C上。
如果n=3，則：
A. 將A上的n-1(等於2，令其為n`)個圓盤移到B(藉助於C)，
步驟如下：
(1)將A上的n`-1(等於1)個圓盤移到C上，見圖5.5(b)。
(2)將A上的一個圓盤移到B，見圖5.5(c)
(3)將C上的n`-1(等於1)個圓盤移到B，見圖5.5(d)
B. 將A上的一個圓盤移到C，見圖5.5(e)
C. 將B上的n-1(等於2，令其為n`)個圓盤移到C(藉助A)，
步驟如下：
(1)將B上的n`-1(等於1)個圓盤移到A，見圖5.5(f)
(2)將B上的一個盤子移到C，見圖5.5(g)
(3)將A上的n`-1(等於1)個圓盤移到C，見圖5.5(h)。
到此，完成了三個圓盤的移動過程。
從上面分析可以看出，當n大於等於2時， 移動的過程可分解為
三個步驟：
第一步 把A上的n-1個圓盤移到B上；
第二步 把A上的一個圓盤移到C上；
第三步 把B上的n-1個圓盤移到C上；其中第一步和第三步是類同的。
當n=3時，第一步和第三步又分解為類同的三步，即把n`-1個圓盤從一個針移到另一個針上，這裡的n`=n-1。 顯然這是一個遞歸過
程，據此演算法可編程如下：
move(int n,int x,int y,int z)
{
if(n==1)
printf(“%c–%c\n”,x,z);
else
{
move(n-1,x,z,y);
printf(“%c–%c\n”,x,z);
move(n-1,y,x,z);
}
}
main()
{
int h;
printf(“\ninput number:\n”);
scanf(“%d”,h);
printf(“the step to moving %2d diskes:\n”,h);
move(h,’a’,’b’,’c’);
}
move(int n,int x,int y,int z)
{
if(n==1)
printf(“%–%c\n”,x,z);
else
{
move(n-1,x,z,y);
printf(“%c–%c\n”,x,z);
move(n-1,y,x,z);
}
}
main()
{ ……
move(h,’a’,’b’,’c’);
}
從程序中可以看出,move函數是一個遞歸函數，它有四個形參n,x,y,z。n表示圓盤數，x,y,z分別表示三根針。move 函數的功能是把x上的n個圓盤移動到z 上。當n==1時，直接把x上的圓盤移至z上，輸出x→z。如n!=1則分為三步：遞歸調用move函數，把n-1個圓盤從x移到y；輸出x→z；遞歸調用move函數，把n-1個圓盤從y移到z。在遞歸調用過程中n=n-1，故n的值逐次遞減，最後n=1時，終止遞歸，逐層返回。當n=4 時程序運行的結果為
input number:
4
the step to moving 4 diskes:
a→b
a→c
b→c
a→b
c→a
c→b
a→b
a→c
b→c
b→a
c→a
b→c
a→b
a→c
b→c
如何推導漢諾塔的公式
求汗諾塔N個盤子須幾次移動時得到了下面的遞推公式：
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
請教通項公式？
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
可得a[i]= 2^i-1;
證明，採用數學歸納法：
1、猜想a[i]= 2^i-1
2、當i=1時，顯然成立。
3、假設i=k時成立，即 a[k] = 2^k – 1;則：
由a[n] = a[n-1] * 2 – 1;得
a[k+1] = a[k] * 2 – 1
= 2^k * 2 – 1
= 2^(k-1) – 1
故得證。
同時：：
漢諾塔問題（又稱河內塔問題）是根據一個傳說形成的一個問題：
有三根杆子A，B，C。A桿上有N個(N1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至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”挪動到”yendl;
}
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 */
#includestdio.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次
原創文章，作者：YWCW，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/146021.html
微信掃一掃 
支付寶掃一掃 