漢諾塔：（Hanoi)是1種玩具，如圖：
從左到右 A B C 柱 大盤子在下, 小盤子在上, 借助B柱將所有盤子從A柱移動到C柱, 期間只有1個原則: 大盤子只能在小盤子的下面.
問題理解與描寫：
1．問題的理解與描寫
問題的情勢化表示為：
輸入：圓盤數(shù)n，3根細(xì)桿―― 源桿A、過渡桿B和目標(biāo)桿C。
輸出：圓盤從源桿移動到目標(biāo)桿進(jìn)程的最少步驟序列。
2.算法的偽代碼：
HANOI(n, A, B, C)
1 if n=1
2 then print A,"?", C
3 return
4 HANOI(n-1,A, C, B)
5 print A,"?", C
6 HANOI(n-1,B, A, C)3.算法的運行時間：
對盤數(shù)n，HANOI進(jìn)程的運行時間
4 算法理解：
理解1：（參考：http://blog.csdn.net/yafei450225664/article/details/8647908）
案例 1 - 假定只有1個盤子的時候, 盤子數(shù)量 N=1
只有1個步驟 將第1個盤子從A移動到C, 為了對照方便我這樣來描寫這個步驟：
步驟 盤子編號 從柱子移動 移動到柱子
1 1 A C
案例 2 - 如果有兩個盤子, 盤子數(shù)量 N = 2
步驟 盤子編號 從柱子移動 移動到柱子
1 1 A B
2 2 A C
3 1 B C
案例 3 - 如果有3個盤子, 盤子數(shù)量 N = 3
步驟 盤子編號 從柱子移動 移動到柱子
1 1 A C
2 2 A B
3 1 C B
4 3 A C
5 1 B A
6 2 B C
7 1 A C
如何找出盤子移動的規(guī)律 ？
我們要做的最重要的1件事情就是永久要把最底下的1個盤子從 A 移動到 C
看看上面從1個盤子的移動到3個盤子的移動, 在移動記錄中,當(dāng)盤子的編號和盤子數(shù)量相同的時候他們的步驟都是從A移動到C (看加粗的部份),其它的步驟對等.
再視察第3個案例中的第 1⑶ 步 和 第 5⑺步
第 1⑶ 步 目的是從 A 移動到 B 如果我們把 B 當(dāng)作終點, 那末這里的第 1⑶ 步理解起來和 第2個案例的3個步驟完全相同, 都是通過1個柱子來移動,和第2個案例比起來在后面加括號來表示
1 1 A C ( A -> B)
2 2 A B ( A -> C)
3 1 C B ( B -> C)
總結(jié)：將盤子B變成C便可.
第 5⑺ 步 目的是從 B 移動到 C 如果我們把 C 當(dāng)作終點, 那末這里的 5⑺ 步理解起來和上面也是1樣的, 和第2個案例的3個步驟也完全相同.和第2個案例比起來就是:
5 1 B A ( A -> B)
6 2 B C ( A- > C)
7 1 A C ( B -> C)
總結(jié): 將盤子B變成A便可
根據(jù)這個演示可以明確幾點規(guī)律:
1. 當(dāng)盤子只有1個的時候,只有1個動作 從 A 移動到 C 即結(jié)束.
2. 當(dāng)有N個盤子的時候, 中間的動作都是從 A 移動到 C, 那末表示最下面的第N個盤子移動終了
3. 中間動作之上都可以認(rèn)為是: 從 A 移動到 B
4. 中間動作之下都可以認(rèn)為是: 從 B 移動到 C
2，3，4 可以表示為
1 1 A B
2 2 A C
3 1 B C
理解2：（參考：http://blog.csdn.net/leo115/article/details/7991734）
美國的1位學(xué)者發(fā)現(xiàn)1種出人意料的簡單的算法，只要輪番兩步操作既可以實現(xiàn)：首先，把3張桌子按順序首尾相接的排列，構(gòu)成1個環(huán)，然后對A上的盤子開始移動，順時針擺放成 A B C的順序：
若n為奇數(shù)，圓盤的移動順序是 A->C->B->A->C->B->A……… 即 間隔兩個步長移動 。此處的n代表盤子位的層數(shù)，比如說 3 層漢諾塔就是從下往上數(shù)第1、3 個盤子移動的順序。
若n為偶數(shù)，圓盤移動的順序為A->B->C->A->B->C->A……….即 間隔1個步長移動。對n的解釋同上 第2個盤子移動 A->B->C。
5.代碼實現(xiàn)（c）：
/*************hanoi.c********************/
#include<stdlib.h>
#include <stdio.h>
#include "hanoi.h"
/*************找x桿頂部盤的編號**********
輸入?yún)?shù)：current[i]記錄第i號盤所在的桿號
x;桿的編號
輸出參數(shù)：x桿頂部盤的編號
****************************************/
int pickTopDisk(char* current,char x)
{
int i = 0;
while (current[i] != x)
i++;
return i;
}
/*************漢諾塔**********
輸入?yún)?shù)：current[i]記錄第i號盤所在的桿號
n:盤的數(shù)量
A,B,C:桿的編號
****************************************/
void hanoi(char* current, int n, char A, char B, char C)
{
static int cout = 0; //static類型變量會在函數(shù)屢次調(diào)用時保存改變的值，并且初始化操作僅做1次
int i = 0;
if (n==1)
{
i = pickTopDisk(current, A);
current[i] = C;
cout++;
printf("move %d disk %d: %c->%c
", cout, i + 1, A, C);
return;
}
hanoi(current, n - 1, A, C, B);
current[n- 1] = C;
cout++;
printf("move %d disk %d: %c->%c
", cout, n, A, C);
hanoi(current, n - 1, B, A, C);
}/****************hanio.h************/
#ifndef _HANOI_H
#define _HANOI_H
#ifdef __cplusplus
extern "C" {
#endif // __cplusplus
int pickTopDisk(char* current, char x);
void hanoi(char* current, int n, char A, char B, char C);
#ifdef __cplusplus
}
#endif
#endif/**************main.c************************/
#include <stdlib.h>
#include "hanoi.h"
int main(int argc, char** argv)
{
char current[] = { 'A', 'A', 'A', 'A' };
char A = 'A', B = 'B', C = 'C';
hanoi(current, 4, A, B, C);
system("pause");
return EXIT_SUCCESS;
}6運行結(jié)果：
參考：《算法設(shè)計、分析與實現(xiàn)：C、C++和Java》 徐子珊
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
