上圖來源:師範大學 某網站 |
n為河內塔總數,在書上看到河內塔的簡介要寫程式來表現時,只覺得頭腦不夠用...需要整個寫出來才能思考...和發現規律(我自己是找不太出來規律...看別人講解和自己話圖才:哇!天阿!,雖然書中也有步驟,可是還是看不太懂別人怎麼歸納出來的想法跟程序的轉換...(雖然我畫了n=4的河內塔,可是還是想不出來解法...只能按照正常情況一一寫出的移動步驟並裡解程式它的寫法 ...與感嘆別人的腦子
n=1
1.n1.A->C
n=2
| 1.n1.A->B (把1~1(1~n-1))的盤子從A搬到B)
2.n2.A->C (把第n(2)的盤子 從A搬到 C)
| 3.n1 B->C (把1~1(1~n-1))的盤子從B搬到C)
n=3
| 1.n1.A->C 2.n2.A->B 3.n1.C->B (把1~2(1~n-1))的盤子從A搬到B)
上方可以拆解為 n=2時的情況,只是B與C互換
4.n3.A->C (把第n=3的盤子 從A搬到 C)
| 5.n1.B->A 6.n2.B->C 7.n1.A->C (把1~2(1~n-1))的盤子從B搬到C)
上方可以拆解為n=2,A與B互換
n=4 從A經B到C
{ 1~n-1從A藉由C到B 從A經C到B
| { (1~n-2)從A藉由B搬到C,要讓n-1(3)可以放到B 從A經B到C
| | { (1~n-3)從A搬到B,要讓n-2(2)可以放到C 從A經C到B
| | | 1.n1.A->B n1 從A到B
| | }
| | 2.n2.A->C n2 從A到C
| | { (1~n-3)從B搬到C,要讓n-1(3)可以放到B 從B經A到C
| | | 3.n1.B->C n1 從B到C
| }
| 4.n3.A->B n3 從A到B
| { (1~n-2)從C搬到B,要讓n(4)可以放到C 從C經A到B
| | { (1~n-3)從C搬到A,要讓n(3)可以放到B 從C經B到A
| | | 5.n1.C->A n1 從C到A
| | }
| | 6.n2.C->B n2 從C到B
| | { (1~n-3)從A搬到B,要讓n(4)可以放到C 從A經C到B
| | | 7.n1.A->B n1 從A到B
| | }
| }
}
8.n4.A->C n4 從A到C
下方就不再多用 { }表示...不然太長 下方是把1~n-1從B經A到C的過程,可以看縮排來得知在哪層
| | | 9.n1.B->C n1
| | 10.n2.B->A n2
| | | 11.n1.C->A n1
| 12.n3.B->C n3
| | | 14.n1.A->B n1
| | 15.n2.A->C n2
| | | 16.n1.B->C n1
總共是可以分為三個步驟
1.把(1~n-1)的盤子從A搬到B (從A藉由C到B)
2.把第n的盤子 從A搬到 C (從A到C)
3.(1~n-1)的盤子從B搬到C (從B藉由A到C)
void Honi(int n,char from,char by,char to)
{
if(n>0){
Honi(n-1,from,to,by);
printf("no %d move from %c to %c",n,from,to);
Honi(n-1,by,from,to);
}
}
沒有留言:
張貼留言