漢諾塔問題（分治+源碼+動畫演示）

漢諾塔問題源自印度一個古老的傳說，印度教的“創造之神”梵天創造世界時做了 3 根金剛石柱，其中的一根柱子上按照從小到大的順序摞著 64 個黃金圓盤。梵天命令一個叫婆羅門的門徒將所有的圓盤移動到另一個柱子上，移動過程中必須遵守以下規則：

每次只能移動柱子最頂端的一個圓盤；

每個柱子上，小圓盤永遠要位于大圓盤之上；

圖 1 給您展示了包含 3 個圓盤的漢諾塔問題：

圖 1 漢諾塔問題

一根柱子上摞著 3 個不同大小的圓盤，那么在不違反規則的前提下，如何將它們移動到另一個柱子上呢？圖 2 給大家提供了一種實現方案：

圖 2 漢諾塔問題的解決方案

漢諾塔問題中，3 個圓盤至少需要移動 7 次，移動 n 的圓盤至少需要操作 2n-1 次。

在漢諾塔問題中，當圓盤個數不大于 3 時，多數人都可以輕松想到移動方案，隨著圓盤數量的增多，漢諾塔問題會越來越難。也就是說，圓盤的個數直接決定了漢諾塔問題的難度，解決這樣的問題可以嘗試用分治算法，將移動多個圓盤的問題分解成多個移動少量圓盤的小問題，這些小問題很容易解決，從而可以找到整個問題的解決方案。

分治算法解決漢諾塔問題

為了方便講解，我們將 3 個柱子分別命名為起始柱、目標柱和輔助柱。實際上，解決漢諾塔問題是有規律可循的：

當起始柱上只有 1 個圓盤時，我們可以很輕易地將它移動到目標柱上；

當起始柱上有 2 個圓盤時，移動過程如下圖所示：

圖 3 移動兩個圓盤

移動過程是：先將起始柱上的 1 個圓盤移動到輔助柱上，然后將起始柱上遺留的圓盤移動到目標柱上，最后將輔助柱上的圓盤移動到目標柱上。

當起始柱上有 3 個圓盤時，移動過程如圖 2 所示，仔細觀察會發現，移動過程和 2 個圓盤的情況類似：先將起始柱上的 2 個圓盤移動到輔助柱上，然后將起始柱上遺留的圓盤移動到目標柱上，最后將輔助柱上的圓盤移動到目標柱上。

通過分析以上 3 種情況的移動思路，可以總結出一個規律：對于 n 個圓盤的漢諾塔問題，移動圓盤的過程是：

將起始柱上的 n-1 個圓盤移動到輔助柱上；

將起始柱上遺留的 1 個圓盤移動到目標柱上；

將輔助柱上的所有圓盤移動到目標柱上。

由此，n 個圓盤的漢諾塔問題就簡化成了 n-1 個圓盤的漢諾塔問題。按照同樣的思路，n-1 個圓盤的漢諾塔問題還可以繼續簡化，直至簡化為移動 3 個甚至更少圓盤的漢諾塔問題。

如下為分治算法解決漢諾塔問題的偽代碼：

// num 表示移動圓盤的數量，source、target、auxiliary 分別表示起始柱、目標柱和輔助柱 hanoi(num ,
source , target , auxiliary):
if num == 1: // 如果圓盤數量僅有 1 個，則直接從起始柱移動到目標柱
print(從 source 移動到 target)
else:
// 遞歸調用 hanoi 函數，將 num-1 個圓盤從起始柱移動到輔助柱上，整個過程的實現可以借助目標柱
hanoi(num-1 , source , auxiliary , target)
// 將起始柱上剩余的最后一個大圓盤移動到目標柱上
print(從 source 移動到 target)
// 遞歸調用 hanoi 函數，將輔助柱上的 num-1 圓盤移動到目標柱上，整個過程的實現可以借助起始柱
hanoi(n-1 , auxiliary , target , source)

漢諾塔問題的代碼實現

根據偽代碼，我們為大家編寫好了相應的 C 語言、Java 以及 Python 程序。

如下是解決漢諾塔問題的 C 語言程序：

#include <stdio.h> void hanoi(int num, char sou, char tar,char aux) {//統計移動次數static int i = 1;//如果圓盤數量僅有 1 個，則直接從起始柱移動到目標柱if (num == 1) {printf("第%d次:從 %c 移動至 %c\n", i, sou, tar);i++;}else {//遞歸調用 hanoi() 函數，將 num-1 個圓盤從起始柱移動到輔助柱上hanoi(num - 1, sou, aux, tar);//將起始柱上剩余的最后一個大圓盤移動到目標柱上printf("第%d次:從 %c 移動至 %c\n", i, sou, tar);i++;//遞歸調用 hanoi() 函數，將輔助柱上的 num-1 圓盤移動到目標柱上hanoi(num - 1, aux, tar, sou);} } int main() {//以移動 3 個圓盤為例，起始柱、目標柱、輔助柱分別用 A、B、C 表示hanoi(3, 'A', 'B', 'C');return 0; }

如下是解決漢諾塔問題的 Java 程序：

public class Demo {// 統計移動次數public static int i = 1;public static void hanoi(int num, char sou, char tar, char sux) {// 如果圓盤數量僅有 1 個，則直接從起始柱移動到目標柱if (num == 1) {System.out.println("第" + i + "次:從" + sou + "移動到" + tar);i++;} else {// 遞歸調用 hanoi() 函數，將 num-1 個圓盤從起始柱移動到輔助柱上hanoi(num - 1, sou, sux, tar);// 將起始柱上剩余的最后一個大圓盤移動到目標柱上System.out.println("第" + i + "次:從" + sou + "移動到" + tar);i++;// 遞歸調用 hanoi() 函數，將輔助柱上的 num-1 圓盤移動到目標柱上hanoi(num - 1, sux, tar, sou);}}public static void main(String[] args) {// 以移動 3 個圓盤為例，起始柱、目標柱、輔助柱分別用 A、B、C 表示hanoi(3, 'A', 'B', 'C');} }

如下是解決漢諾塔問題的 Python 程序：

#記錄移動次數 i = 1 def hanoi(num,sou,tar,aux):global iif num==1:print("第%d次:從 %c 移動至 %c" % (i, sou, tar))i=i+1else:#遞歸調用 hanoi() 函數，將 num-1 個圓盤從起始柱移動到輔助柱上hanoi(num - 1, sou, aux, tar)#將起始柱上剩余的最后一個大圓盤移動到目標柱上print("第%d次:從 %c 移動至 %c" % (i, sou, tar))i=i+1#遞歸調用 hanoi() 函數，將輔助柱上的 num-1 圓盤移動到目標柱上hanoi(num - 1, aux, tar, sou) #以移動 3 個圓盤為例，起始柱、目標柱、輔助柱分別用 A、B、C 表示 hanoi(3, 'A', 'B', 'C');

以上程序的執行結果均為：

第1次:從 A 移動至 B
第2次:從 A 移動至 C
第3次:從 B 移動至 C
第4次:從 A 移動至 B
第5次:從 C 移動至 A
第6次:從 C 移動至 B
第7次:從 A 移動至 B

總結

以上是生活随笔為你收集整理的汉诺塔问题（分治+源码+动画演示）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。