# 用遞迴（recurrence）解決河內塔（Hanoi Tower）問題（使用c++）

演算法divide-and-conquer實作

Hanoi Tower是非常經典的題型，大致的題意為有三跟柱子編號為A、Ｂ、Ｃ，而A柱子上有N個環，而環由下到上排列依序為大到小(越下面的環越大)。


目的：將全部的環移從A移到C

條件
1. 大環不能壓在小環上面
2. 一次只能移動一個環

解決方法：這個問題可以使用遞迴解決，
先找到遞迴的公式

base case：

n==1 move disk from src to des

reccursive case：

han(n-1,src,spare,des)
han(n-1,spare,des,src)

---

# 程式實作

#include <iostream>
using namespace std;
void han(int n,char x,char y, char z){
    if(n==1){
        //han(n,src,des,spare)
        cout <<"盤子從"<<x<<"移到"<<z<<endl;
    }    
    else{
        //han(n-1,src,spare,des)
        han(n-1,x,z,y);
        cout <<"盤子從"<<x<<"移到"<<z<<endl;
        //han(n-1,spare,des,src)
        han(n-1,y,x,z);
        
    }    

}
int main(){
    int n;
    cout << "請輸入有n個盤子 n=" << endl;
    cin >> n;
    han(n,'a','b','c');
}

運行結果

參考資料：[https://ithelp.ithome.com.tw/articles/10281346](https://ithelp.ithome.com.tw/articles/10281346)
###### tags: #演算法 #河內塔 #遞迴 #c++