佑佑的語言

題目:河內塔

這題的規則大家都知道才點進來看吧(￣(エ)￣)

不過我還是簡單介紹一下規則…….. (･A･)

柱子1號已經排好盤子由大到小,接著把所有盤子一道3號柱子

1. 每次只能從最上面移動一個盤子
2. 任何盤子可以從任何柱子搬到其他柱子
3. 小盤子永遠必須放在大盤子之上

假設當有3個盤子

每個步驟左邊的數字是他的總移動次數

如果你在嘗試4個盤子的話可以發現規律(・。・)

移動次數=2ⁿ-1次

[步驟1] 將n-1個盤子,從柱子1移動到柱子2

[步驟2] 將n個最大盤子,從柱子1移動到柱子3

[步驟3] 將n-1個盤子,從柱子2移動到柱子3

這時假設a_n為移動次數,a₁=1

a_n  = 2_n-1+1

_{這式子經由一連串的推導後}

所以結論就是n個盤子所需移動次數為2^n-1次ヾ(*´∀｀*)ﾉ

那當然用遞回寫最好啦(*≧∇≦*)

ß-------------------------------我是分隔線-------------------------------------à

只有3根柱子的情況下

輸入:請輸入n個盤子

輸出:請把移動過程印出,在印總移動次數

話不多說,咱門開始吧(｡･ˇ_ˇ･｡)

1. #include <iostream>  
2.  
3. #include <cmath>  
4.   
5. using namespace std;  
6.   
7. void array(int n,int p1,int p2,int p3);  
8.   
9.   
10.   
11. int main()  
12.   
13. {  
14.   
15.    int n;  
16.   
17.    cin >>n;  
18.   
19.    array(n,1,2,3);//有三根柱子p1,p2,p3,要印位置用  
20.   
21.    cout << "總共移動:"<< pow(2,n)-1<<endl; //標頭檔#include <cmath>  
22.   
23. }  
24.   
25. void array(int n,int p1,int p2,int p3)  
26.   
27. {  
28.   
29.     if(n==1)  
30.   
31.         cout << "盤子從"<<p1<<"移到"<<p3<<endl;  
32.   
33.     else  
34.   
35.     {  
36.   
37.         array(n-1,p1,p3,p2);  
38.   
39.         cout << "盤子從"<<p1<<"移到"<<p3<<endl;  
40.   
41.         array(n-1,p2,p1,p3);//把盤子弄到剩一個  
42.   
43.     }  
44.   
45. }

可能大家對array裡的else有點困惑

由剛上面的3大步驟來看( . .)

[步驟1] 將n-1個盤子,從柱子1移動到柱子2

[步驟2] 將n個最大盤子,從柱子1移動到柱子3

[步驟3] 將n-1個盤子,從柱子2移動到柱子3

這是其中一回合,1柱子是來源,2柱子是目的,3柱子是暫存區

其中的步驟1和3又會套回這個流程執行,直到盤子剩一個的時候,在搬移,也就是跑回n=1

End ʅ（´◔౪◔）ʃ