請你設計一程式﹐利用遞迴函數的技巧﹐計算出般運N個圓環之河內塔所需要的全部移動次數。
--------
條件限制
1.使用者輸入一個正整數N(N<64)
2.輸出移動N個圓環所需要的全部移動次數。
--------
輸入格式
無檔案輸入,由鍵盤輸入資料(正整數N,N<=64)。
--------
輸出格式
無檔案輸出,由營幕輸出資料(移動次數)。
--------
輸入範例
Please input positive integerN(N<=64)
N=3
--------
輸出範例
N=3,Total moves=7
----------
/*
1.簡單的想法
將N個環分成上面的[N-1個]及[最下面的環],假設柱子編號為A,B,C
將所有環由A移到C。
1.1 先將[N-1個環]由 A 暫移到 B
1.2 再將[最下面的環]由 A 移到 C
1.3 最後再將[N-1個環]由 B 移到 C
假設移動N個環所需的次數為F(N),則由1.1~1.3可知:
F(N)=F(N-1)+1+F(N-1)=2*F(N-1)+1
*/
int hanoi-total-moves(int n){
if(n==1)
return 1;
else
return 2*hanoi-total-moves(n-1)+1;
}
/*
2.進階問題
如果要把移動的過程順便顯示出來,則需要改寫以上的函數:
*/
/* N個環,由 from柱 移到 to柱, 中間透過 tmp柱 */
void hanoi-moving-steps(int n,char from,char to,char tmp){
// 移動前 N-1 個環,由 from 到 tmp,透過 to
if(n==1)
printf("move ring %d from pillar %c to pillar %c\n",n,from,to);
else{
hanoi-moving-steps(n-1,from,tmp,to);
// 移動第 N 個環
printf("move ring %d from pillar %c to pillar %c",n,from,to);
// 移動前 N-1 個環,由 tmp 到 to,透過 from
hanoi-moving-steps(n-1,tmp,to,from);
}
}
/* 呼叫函數例: 移動三個環,由A柱到C柱,中間透過B柱*/
hanoi-moving-steps(3,'A','C','B')