Title：漢諾塔問題的遞歸實現(xiàn)
創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比汕尾網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式汕尾網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋汕尾地區(qū)。費用合理售后完善，十多年實體公司更值得信賴。
漢諾塔（又稱河內(nèi)塔）問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
一、漢諾塔（基本）
漢諾塔問題是典型的分治算法問題，首先我們來討論最基本的漢諾塔問題。假設(shè)有n個圓盤，三根柱子，a，b，c，需要把n個盤子（從下往上按照大小順序摞著）從a柱移動到c柱，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
1.1 打印路徑
采用分治法，分而治之，把大問題化解成小問題。故可以把n個盤子看成n-1個盤子，和第n個盤子，首先我們需要把n-1個盤子移動到b柱子上，然后把第n個盤子移動到c柱子上，最后把n-1個盤子移動到c柱子上，這樣就用最少的移動次數(shù)完成了任務(wù)。
c++實現(xiàn)：
#include
using namespace std;
void move(int n, char a, char b){
cout<"< 0) {
hanoi(n - 1, a, c, b);// 把n-1個盤子移動到c柱子上
move(n, a, b); // 把a移動到b
hanoi(n - 1, c, b, a); // 把第n-1個盤子從c柱子移動到b柱子上
}
}
int main()
{
int n;
while(cin>>n){
char a='a',b='b',c='c';
hanoi(n,a,c,b); //把n個盤子從a柱子移動到c柱子
}
return 0;
}
以上程序顯示全部步驟的移動方法。
1.2 計算移動次數(shù)
如果要計算一共移動了多少次，找出規(guī)律即可。
假設(shè)移動n個盤子需要移動f(n)次，所以把n-1個盤子移動到b柱子上，需要移動f(n-1)次，然后把第n個盤子移動到c柱子上，需要移動1次，最后把n-1個盤子移動到c柱子上，需要移動f(n-1)次，綜上所述，一共移動了
f(n) = 2 f(n-1) + 1
而：
f(1) = 1;
f(2) = 2*1+ 1;
f(3) = 2(2*1+ 1)+ 1;
.......
f(n) = 2^n -1
C++實現(xiàn)：
//基本漢諾塔移動次數(shù)，可以算小于64的所有盤子數(shù)
#include
using namespace std;
int main()
{
int n;
while(cin>>n){
if(n>63||n<1) {
cout<<"ERROR"<
二、漢諾塔（必須通過中間的柱子）
假設(shè)有n個圓盤，三根柱子，a，b，c，需要把n個盤子（上從下往上按照大小順序摞著）從a柱移動到c柱，不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到下盤的上面。
2.1 打印路徑
參考acm題目：http://acm.hdu.edu.cn/showproblem.php?pid=2064
這道題和之前不同，約束了必須通過中間的柱子才可以，這也難不倒我們，我們只需要在遞歸的時候改變一下策略就可以完成任務(wù)。
解決方法：
依然采用分治法，分而治之，把大問題化解成小問題。最開始在a柱子上有n個盤子，我們可以把n個盤子看成n-1個盤子，和第n個盤子。首先我們需要把n-1個盤子移動到c柱子上（n-1個盤子只能由a移動到c或者由c移動到a，否則就不是最少次數(shù)了），然后把第n個盤子移動到b柱子上（不能直接由a移動到c），最后把n-1個盤子移動到c柱子上，這樣就用最少的移動次數(shù)完成了任務(wù)。
c++實現(xiàn)：
#include
using namespace std;
void move(int n, char a, char b){
cout<"< 0) {
hanoi(n - 1, a, c, b);
move(n, a, b);
hanoi(n - 1, c, a, b);
move(n, b, c);
hanoi(n - 1, a, c, b);
}
}
int main()
{
char a='a',b='b',c='c';
hanoi(3,a,c,b);
return 0;
}
2.2 計算移動次數(shù)
如果要計算一共移動了多少次，找出規(guī)律即可。
假設(shè)移動n個盤子需要移動f(n)次，所以把n-1個盤子移動到c柱子上，需要移動f(n-1)次，然后把第n個盤子移動到b柱子上，需要移動1次，然后把n-1個盤子移動到a柱子上，需要移動f(n-1)次，第n個盤子移動到c柱子上，需要移動1次，最后把n-1個盤子移動到c柱子上，需要移動f(n-1)次，綜上所述，一共移動了
f(n) = 3 f(n-1) + 2
而：
f(1) = 2;
f(2) = 3*2+ 2;
f(3) = 3(3*2+ 2)+ 2;
.......
f(n) = 3^n -1
C++實現(xiàn)：
#include
using namespace std;
int main()
{
int n;
__int64 f[36];
f[1]=2;
for(int i=2;i<=35;i++) f[i]=3*f[i-1]+2;
while(cin>>n){
if(n>56||n<1){
cout<<"ERROR!"<三、漢諾塔（必須通過中間的柱子，允許大的放在最上面）
假設(shè)有n個圓盤，三根柱子，a，b，c，需要把n個盤子（上從下往上按照大小順序摞著）從a柱移動到c柱，不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到小盤的上面。如果我們允許大的盤子放到最上面會怎么樣呢？（只允許大的放在最上面）當然最后需要的結(jié)果是盤子從小到大排在最右邊。
3.1 打印路徑
參考acm題目：http://acm.hdu.edu.cn/showproblem.php?pid=2077
這道題和之前不同，約束了必須通過中間的柱子才可以，也放寬了對大盤子的限制，所以肯定比第二種漢諾塔移動次數(shù)少，我們也是只需要在遞歸的時候改變一下策略就可以完成任務(wù)。
解決方法：
依然采用分治法，分而治之，把大問題化解成小問題。最開始在a柱子上有n個盤子，我們可以把n個盤子看成n-2個盤子，和第n-1，以及第n個盤子。首先我們需要把n-2個盤子移動到c柱子上（利用第二種類型的算法），然后把第n-1和n個盤子依次移動到b柱子上，再把n-2個盤子移動到a柱子上，再把第n和第n-1個盤子移動到柱子c上，這樣就用最少的移動次數(shù)完成了任務(wù)。
C++實現(xiàn)：
#include
using namespace std;
void move(int n, char a, char b){
cout<"< 0) {
hanoi(n - 1, a, c, b);
move(n, a, b);
hanoi(n - 1, c, a, b);
move(n, b, c);
hanoi(n - 1, a, c, b);
}
}
void Hanoi_(int n, char a, char c, char b){
if(n > 0) {
hanoi(n - 2, a, c, b);
if(n > 1)
move(n - 1, a, b);
move(n, a, b);
hanoi(n - 2, c, a, b);
move(n, b, c);
if(n > 1)
move(n - 1, b, c);
hanoi(n - 2, a, c, b);
}
}
int main()
{
int n;
while(cin>>n) {
char a='a',b='b',c='c';
Hanoi_(n,a,c,b);
}
return 0;
}
3.2 計算移動次數(shù)
如果要計算一共移動了多少次，找出規(guī)律即可。
假設(shè)移動n個盤子需要移動F(n)次，用第二種算法把n-2個盤子移動到c柱子上（利用第二種類型的算法），需要f(n-2)次，然后把第n-1和n個盤子依次移動到b柱子上，需要2次，再把n-2個盤子移動到c柱子上，再把第n和第n-1個盤子移動到柱子c上，需要2次，綜上所述，一共移動了
f(n) = 3 f(n-2) + 4
而：
f(n-2) = 3^(n-2)-1
故，f(n)=3^(n-1)+1
C++實現(xiàn);
#include
using namespace std;
int main()
{
int T;
cin>>T;
while(T--){
int n;
cin>>n;
if(n>51||n<1) {
cout<<"ERROR"<四、漢諾塔（加一根柱子）
假設(shè)有n個圓盤，三根柱子，a，b，c，需要把n個盤子（上從下往上按照大小順序摞著）從a柱移動到c柱，再找來了一根一模一樣的柱子d，通過這個柱子來更快的把所有的盤子移到第三個柱子上。
4.1 計算移動次數(shù)
參考acm題目：http://acm.hdu.edu.cn/showproblem.php?pid=1207
這道題和之前都有很大的不同，加了一根柱子，意味著有的時候可用3根柱子，有的時候可用4根柱子，當把j個小盤子移動到d盤上時，有四根柱子可用，而當把n-j個盤子從a移動到c時，僅有三根柱子可用。這里我們就要找到j(luò)的值，使所有移動的次數(shù)和最小。
解決方法：
依然采用分治法。首先把j個盤子移動到d柱子上（通過四個柱子可用的算法），需要B[j]次移動，然后把n-j個盤子移動到c柱子上（通過三個柱子可用的算法），需要A[n-j]次移動，，然后把d中的j個盤子移動到c柱子上，需要B[j]次移動。我們可以用j的大小循環(huán)，找到移動次數(shù)最小的j。
首先我們先計算移動的次數(shù)，核心公式為下面代碼中的：flag = 2*B[ j ] + A[ i - j]; //j個盤子移動到第四個柱子，然后把剩下的i-j個在第四個不能用的情況下移到第三個
計算次數(shù)的c++實現(xiàn)：
#include
using namespace std;
int main()
{
int n;
double a[65],b[65]; //數(shù)組a代表沒加第四個柱子的結(jié)果，數(shù)組b代表加了第四個柱子的結(jié)果
a[1]=1;
for(int i=2;i<=64;i++) a[i]=2*a[i-1]+1;
b[1]=1;
b[2]=3;
for(int i=3;i<=64;i++){
double min=a[i],flag;
for(int j=1;jflag) min=flag;
}
b[i]=min;
}
while(cin>>n){
if(n>64||n<1){
cout<<"ERROR!"<4.2 打印路徑
利用上面的算法，我們可以很容易得出路徑
模擬移動步驟的C++實現(xiàn)：
#include
using namespace std;
void move(int n, char a, char b){
cout<"< 0) {
hanoi_basic_3(n - 1, a, c, b);// 把n-1個盤子移動到b柱子上
move(n, a, b); // 把a移動到b
hanoi_basic_3(n - 1, c, b, a); // 把第n個盤子移動到b柱子上
}
}
void hanoi(int n, char a, char c, char b, char d, int C[]){
int j=C[n]; //j個盤子使用四個柱子的移動方式
if(n > 0) {
hanoi(j, a, d, b, c, C);// 把j個盤子移動到d柱子上
hanoi_basic_3(n - j, a, c, b);// 把n-j個盤子移動到c柱子上（使用三個柱子的移動方式）
hanoi(j, d, c, a, b, C); // 把j個盤子移動到c柱子上
}
}
int main()
{
int n,flag_j;
double A[65]; //未加第四個柱子時候的移動次數(shù)情況
A[1]=1;
for(int i=2;i<65;i++) A[i]=2*A[i-1]+1;
double B[65],flag,min;
int C[65]; //把前 c[j]個元素用四個柱子的方法，后i-j 個元素用三個柱子的方法
C[1]=0;
C[2]=0;
for(int i=3;i<=64;i++){
min=A[i]; //數(shù)組A代表沒加第四個柱子的結(jié)果次數(shù)，數(shù)組b代表加了第四個柱子的結(jié)果次數(shù)
B[1]=1;
B[2]=3;
flag_j=0;
for(int j=1;jflag) {
min=flag;
flag_j=j;
}
B[i]=min;
C[i]=flag_j;
}
}
while(cin>>n){
char a='a',b='b',c='c',d='d';
hanoi(n,a,c,b,d,C); //把n個盤子從a柱子移動到c柱子
}
return 0;
}
@碼農(nóng)同學(xué)，版權(quán)所有。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
標題名稱：漢諾塔問題的遞歸實現(xiàn)（擴展）-創(chuàng)新互聯(lián)
URL地址：http://weahome.cn/article/pidgd.html
重慶分公司
重慶分公司
