| | 漢諾塔（又稱河內塔）問題是印度的一個古老的傳說。開天闢地的神勃拉瑪在一個廟裏留下了三根金剛石的棒，第一根上面套着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,a,c);
}
else
{
hanoi(n-1,a,c,b); /* copyrighter by ss7e */
printf("move disk %d from %c to %c
",n,a,c);
hanoi(n-1,b,a,c); /* copyrighter by ss7e */
}
}
main() /* copyrighter by ss7e */
{
int n;
printf("請輸入數字n以解决n階漢諾塔問題：
");
scanf("%d",&n);
hanoi(n,'a','b','c');
}/* copyrighter by ss7e */ | | 漢諾塔的由來
漢諾塔是源自印度神話裏的玩具。
上帝創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上安大小順序摞着64片黃金圓盤。
上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次衹能移動一個圓盤。
有預言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今還在一刻不停地搬動着圓盤。
漢諾塔與宇宙壽命
如果移動一個圓盤需要1秒鐘的話，等到64個圓盤全部重新落在一起，宇宙被毀滅是什麽時候呢？
讓我們來考慮一下64個圓盤重新摞好需要移動多少次吧。1個的時候當然是1次，2個的時候是3次，3個的時候就用了7次......這實在是太纍了
因此讓我們邏輯性的思考一下吧。
4個的時候能夠移動最大的4盤時如圖所示。
到此為止用了7次。
接下來如下圖時用1次，在上面再放上3個圓盤時還要用7次（把3個圓盤重新放在一起需要的次數）。
因此，4個的時候是
“3個圓盤重新摞在一起的次數”+1次+“3個圓盤重新摞在一起需要的次數”
=2x“3個圓盤重新摞在一起的次數”+1次
=15次。
那麽，n個的時候是
2x“（n-1）個圓盤重新摞在一起的次數”+1次。
由於1 個的時候是1次，結果n個的時候為（2的n次方減1）次。
1個圓盤的時候 2的1次方減1
2個圓盤的時候 2的2次方減1
3個圓盤的時候 2的3次方減1
4個圓盤的時候 2的4次方減1
5個圓盤的時候 2的5次方減1
........
n個圓盤的時候 2的n次方減1
也就是說，n=64的時候是（2的64次方減1）次。
因此，如果移動一個圓盤需要1秒的話，
宇宙的壽命=2的64次方減1（秒）
用一年=60秒x60分x24小時x365天來算的話，大約有5800億年吧。
據說，現在的宇宙年齡大約是150億年，還差得遠呢。
漢諾塔問題在數學界有很高的研究價值，
而且至今還在被一些數學家們所研究，
也是我們所喜歡玩的一種益智遊戲，
它可以幫助開發智力，激發我們的思維。
漢諾塔的C語言實現
#include"stdio.h"
void move(char x,char y)
{
printf("%c-->%cn",x,y);
}
void hanoi(int n,char one ,char two,char three)
{
if(n==1) move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main()
{
int m;
printf("input the number of disks:");
scanf("%d",&m);
printf("the step to moving %3d diskes:n",m);
hanoi(m,'A','B','C');
}
====================================華麗的分割綫==================================
concreteHAM：
現在有三根相鄰的柱子，標號為A,B,C，A柱子上從下到上按金字塔狀疊放着n個不同大小的圓盤，現在把所有盤子一個一個移動到柱子B上，並且每次移動同一根柱子上都不能出現大盤子在小盤子上方，請問至少需要多少次移動，設移動次數為H(n)。
首先我們肯定是把上面n-1個盤子移動到柱子C上，然後把最大的一塊放在B上，最後把C上的所有盤子移動到B上，由此我們得出表達式：
H(1) = 1
H(n) = 2*H(n-1)+1 (n>1)
那麽我們很快就能得到H(n)的一般式：
H(n) = 2^n - 1 (n>0)
並且這種方法的確是最少次數的，證明非常簡單，可以嘗試從2個盤子的移動開始證，你可以試試。
進一步加深問題(解法原創*_*)：
假如現在每種大小的盤子都有兩個，並且是相鄰的，設盤子個數為2n，問：(1)假如不考慮相同大小盤子的上下要多少次移動，設移動次數為J(n)；(2)衹要保證到最後B上的相同大小盤子順序與A上時相同，需要多少次移動，設移動次數為K(n)。
(1)中的移動相當於是把前一個問題中的每個盤子多移動一次，也就是：
J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2
在分析(2)之前，我們來說明一個現象，假如A柱子上有兩個大小相同的盤子，上面一個是黑色的，下面一個是白色的，我們把兩個盤子移動到B上，需要兩次，盤子順序將變成黑的在下，白的在上，然後再把B上的盤子移動到C上，需要兩次，盤子順序將與A上時相同，由此我們歸納出當相鄰兩個盤子都移動偶數次時，盤子順序將不變，否則上下顛倒。
現在回到最開始的問題，n個盤子移動，上方的n-1個盤子總移動次數為2*H(n-1)，所以上方n-1個盤子的移動次數必定為偶數次，最後一個盤子移動次數為1次。
討論問題(2)，綜上兩點，可以得出，要把A上2n個盤子移動到B上，首先可以得出上方的2n-2個盤子必定移動偶數次，所以順序不變，移動次數為：
J(n-1) = 2^n-2
然後再移動倒數第二個盤子，移動次數為2*J(n-1)+1 = 2^(n+1)-3，
最後移動最底下一個盤子，所以總的移動次數為：
K(n) = 2*(2*J(n-1)+1)+1 = 2*(2^(n+1)-3)+1 = 2^(n+2)-5 |
|
|