[C++] 河內塔問題

whitefox

河內塔問題很適合用來練習遞迴技巧(Recursion)跟分治法的演算法技巧(Divide and Conquer)
這個程式碼輸入要放幾個盤子，執行過程也可以顯示要搬移第幾個盤子從哪個柱子到哪個住子

1. #include <iOStream>
   
2. #include <cstdlib>
   
3. 
   
4. using namespace std;
   
5. 
   
6. long int times;
   
7. 
   
8. void Hanoi(int disks, int src, int dst, int No)
   
9. {
   
10.     if ( disks == 1 )
    
11.     {
    
12.         cout << ++times << ": Move Disk." << No << " (" << src << ") → (" << dst << ")" << endl;
    
13.         return;
    
14.     }
    
15.    
    
16.     // 棒子編號 1 2 3 編號總和 6
    
17.     int aux = 6 - src - dst;
    
18.    
    
19.     Hanoi((disks-1), src, aux, (No-1));
    
20.     Hanoi(1, src, dst, No);
    
21.     Hanoi((disks-1), aux, dst, (No-1));
    
22. }
    
23. 
    
24. int main(void)
    
25. {
    
26.     int count;
    
27.    
    
28.     cout << "輸入盤子數：";
    
29.     cin >> count;
    
30.    
    
31.     times = 0;
    
32.     Hanoi(count, 1, 2, count);
    
33.    
    
34.     cout << "------------" << endl;
    
35.     cout << "移動" << count << "個盤子，需要移動" << times << "次";
    
36.    
    
37.     system("pause");
    
38. }

複製代碼