算法之路----漢諾塔

漢諾塔是很簡單也很經典的算法之一。 漢諾塔是根據一個傳說形成的數學問題: 有三根桿子A,B,C 。A桿上有N個(N>1)穿孔圓盤,盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿:

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

提示:可將圓盤臨時置于B桿,也可以將A桿移除的圓盤重新移動回A桿,但都必須遵循上述兩條規則。 問:如何移?最少要移動多少次?

3個圓盤的漢諾塔移動

4個圓盤的漢諾塔移動

傳說

最早發明這個問題的人是法國數學家愛德華*盧卡斯。 傳說印度某間寺院有三根柱子,上串64個金盤。寺院里的僧侶依照一個古老的預言,以上述規則移動這些盤子;預言說當這些盤子移動完畢,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說,還是他受他人啟發。 若傳說屬實,僧侶們需要264- 1步才能完成這個任務;若他們每秒可完成一個盤子的移動,就需要5849億年才能完成。整個宇宙現在也不過137億年。 這個傳說有若干變體:寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位于越南的河內,所以被命名為“河內塔”。另外亦有“金盤是創世時所造”、“僧侶們每天移動一盤”之類的背景設定。 佛教中確實有“浮屠”(塔)這種建筑;有些浮屠亦遵守上述規則而建?！昂觾人币幻赡苁怯芍心习雿u在殖民時期傳入歐洲的。

解答

如取N=64,最少需移動264- 1次。即如果一秒鐘能移動一塊圓盤,仍將需5849.42億年。目前按照宇宙大爆炸理論的推測,宇宙的年齡僅為137億年。 在真實玩具中,一般N=8;最少需移動255次。如果N=10,最少需移動1023次。如果N=15,最少需移動32767次;這就是說,如果一個人從3歲到99歲,每天移動一塊圓盤,他最多僅能移動15塊。如果N=20,最少需移動1048575次,即超過了一百萬次。

解法

解法的基本思想是遞歸。假設有A、B、C 三個塔,A塔有N塊盤,目標是把這些盤全部移動到C塔。那么先把塔頂部的N-1塊盤移動到B塔,再把A塔剩下的大盤移動到C,最后把B塔的N-1塊盤移動到C。 每次移動多于一塊盤時,則再次使用上述算法來移動。

怎么來理解呢? 我們可以倒著理解,要將A塔上的所有圓盤移動到C塔,且所有圓盤是下大上小。那么必定有一個過程是最大的圓盤(也就是第N個圓盤)從A移動到C。那么必須保證上面的N-1個圓盤全在B塔,且圓盤滿足上面小,下面大。當第N個圓盤從A移動到C之后,又得把N-1個圓盤從B塔移動到C塔,這樣工作就完成了。 但是怎么把A塔上的N-1個圓盤移動到B塔呢? 這里需要一點想象力,可以想象成只有N-1個圓盤,從A塔移動到B塔(此時的B塔其實就相當于上面的C塔),我們稱A塔為A1塔,B塔為C1塔,C塔為B1塔,那么問題就變成了如何將N-1個盤從A1塔移動到C1塔? 同樣的需要將上面的N-2個圓盤從A1塔移動到B1塔,然后將第N-1個圓盤從A1塔移動到C1塔,然后再將B1塔上的N-2個圓盤移動到C1塔。 同理,遞推第N-2個塔.....。

將 B塔上的 N-1個盤,移動到C塔的過程與上面原理一樣。

遞歸解

以Objective-C語言實現:

- (void)viewDidLoad {    [super viewDidLoad];    // Do any additional setup after loading the view from its nib.    int n = 9;    [self hannoi:n from:@"A" buffer:@"B" to:@"C"];    NSLog(@"一共 %d 步",count);}- (void)hannoi:(int)n from:(NSString *)from buffer:(NSString *)buffer to:(NSString *)to{    if (n == 1) {        NSLog(@"Move disk %d from %@ to %@", n, from, to);    } else {        [self hannoi:n-1 from:from buffer:to to:buffer];        NSLog(@"Move disk %d from %@ to %@", n, from, to);        [self hannoi:n-1 from:buffer buffer:from to:to];    }}console : 一共 511 步

以C++語言實現:

using namespace std;#include <iostream>#include <cstdio>void hannoi (int n, char from, char buffer, char to){    if (n == 1) {        cout << "Move disk " << n << " from " << from << " to " << to << endl;    } else {        hannoi (n-1, from, to, buffer);        cout << "Move disk " << n << " from " << from << " to " << to << endl;        hannoi (n-1, buffer, from, to);    }}int main(){    int n;    cin >> n;    hannoi (n, 'A', 'B', 'C');    return 0;}

通過以上遞歸過程可知hannoi(n) = 2 * hannoi(n-1) + 1 ,hannoi(n) = 2n-1 + 2n-2 + 2n-3+ ...... + 22 + 2 +1。 對等比數列求和得出hannoi(n) = 2n -1。