漢諾塔傳說：漢諾塔問題，是源于印度一個古老的益智玩具；大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，
數學抽象：如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數；
遞回問題：遞回是函式呼叫函式自身；如果一個大型復雜的問題能蹭蹭轉化為一個與原問題相似的規模較小的問題，那么就能用遞回來進行求解；一般來說遞回需要有邊界條件、遞回前進端（子問題）和遞回回傳段（遞回出口）；當邊界條件不滿足時，遞回前進；當邊界條件滿足時，遞回回傳，
遞回函式設計技巧：
- 遞回主題；
- 遞回函式引數；
- 遞回函式出口；
- 遞回問題分析順序：從大問題分析小問題，每次利用減治思想減少規模；
遞回演算法解決問題的種類：
- 資料的定義是按照遞回定義的；（Fibonacci 函式）
- 問題的解法是按照遞回演算法進行實作；（漢諾塔問題）
- 資料的結構的形式是按照遞回定義的；（二叉樹，圖問題，線性表：DFS搜索，歸并排序，快速排序等）
漢諾塔問題遞回分析：
假設一共有n個圓盤，則漢諾塔問題，以遞回角度進行分析為：
- 把n-1個盤子由A移動到B；(借助輔助塔C)
- 把第n個盤子，由A移動到C;
- 把n-1個盤子由B移動到C; (借助輔助塔A)
游戲解法：游戲要求從A->C移動；手動操作時：首先確定層數n, 如果層數是奇數，最上層由A->C; 如果層數為偶數，最上層A->B;
程式解法：
#include <iostream> using namespace std; int m = 0; // 移動次數 void move(int disk, char from, char to){ cout << "移動次數:" << (++m) <<" 把塊:" << disk << " 按照如下移動：" << from << " --> " << to << endl; } // 遞回求解漢諾塔 void hanoi(int disks, char from, char to, char assist){ if (disks == 1) // 遞回出口； { move(disks, from, to); return; } //遞回子問題； hanoi(disks-1, from, assist, to); // n-1個盤子，由A移動到B, 借助輔助塔C； move(disks, from, to); // 把第n個盤子，由A移動到C； hanoi(disks-1, assist, to, from); // 把n-1個盤子，由B移動到C, 借助輔助塔A； } int main(){ cout << "漢諾塔問題：" << endl; int n = 3; cout << "漢諾塔圓盤個數：" << n << endl; // 創建三個塔； char A = 'A'; char B = 'B'; char C = 'C'; // 遞回求解漢諾塔，輸出移動步驟； // n 個盤 從 A 塔移動到 C塔， 借助輔助塔B； hanoi(n, A, C, B); // 漢諾塔遞回求解； return 0; }漢諾塔程式模板
bash-3.2$ c++ 漢諾塔問題.cc; ./a.out 漢諾塔問題： 漢諾塔圓盤個數：1 移動次數:1 把塊:1 按照如下移動：A --> C bash-3.2$ c++ 漢諾塔問題.cc; ./a.out 漢諾塔問題： 漢諾塔圓盤個數：2 移動次數:1 把塊:1 按照如下移動：A --> B 移動次數:2 把塊:2 按照如下移動：A --> C 移動次數:3 把塊:1 按照如下移動：B --> C bash-3.2$ c++ 漢諾塔問題.cc; ./a.out 漢諾塔問題： 漢諾塔圓盤個數：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漢諾塔輸出樣例
通過運行結果可以發現：總的移動次數為：2^n-1次；n為圓盤個數；
程式地址：https://github.com/yaowenxu/codes/blob/master/遞回/漢諾塔問題.cc
保持更新，轉載請注明出處；更多內容請關注cnblogs.com/xuyaowen;
參考鏈接：*文中圖來自于參考鏈接，如侵權請私信我更換；
漢諾塔的圖解 如何理解漢諾塔的遞回？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65476.html
標籤：其他
下一篇：求一個序列中的主元素