推 vvbird:河內塔(Tower of Hanoi), 你可以查查看 02/24 23:24
> -------------------------------------------------------------------------- <
作者: waterworld0 () 看板: tutor
標題: Re: [問題] 請教..數學...
時間: Fri Feb 24 23:24:12 2006
※ 引述《Zuyi (祖儀)》之銘言：
: 有A B C三根柱子 , A柱中有n個大小不同的圓盤由大而小上堆疊
: 若要由A柱全部搬到B柱 , 每次只能搬動一圓盤 ,
: 且大盤不可放在小盤上 , 假設最少要搬動An次
: 若An = P * A(n-1) + k , 求數對(p,k)= ?
: ---------------------------------------
: 我連題意是怎樣都不太懂@@
: 請問這題要怎麼算呢
這應該是Hanoi tower吧, 這個題意應該不難懂啦, 跟著模擬一次就好了.
妳這個式子, 應該是照著recursive的方法來做的.
---- ---- ----
A B C
假設A上面有 n個 disk 然後要搬到C
雖然我不知道怎麼搬n個 但是我可以假裝我已經知道怎麼搬n-1個了
所以我就問編號n-1的人應該要怎麼做
(如果不知道也無妨, 他可以一直往下問
總有一天會問到一個知道怎麼做的(也就是搬一個))
因此假設我知道怎麼搬n-1個 我可以把A上面的n-1個放到B
然後再把剩下的一個放到C 最後再把B上面的n-1個放到C上面 整個步驟就完成了
因此 搬n個的方法 等於是搬兩次n-1(A->B B->C) 以及把A的底盤放到C
所以一共花了 2*An-1 + 1 因此 放n個的方法(An) 就會等於 2An-1 + 1
這樣懂了哩?
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.58.70.170
> -------------------------------------------------------------------------- <
作者: towish (好人是什麼?可以吃嗎?!) 看板: tutor
標題: Re: [問題] 請教..數學...
時間: Fri Feb 24 23:36:16 2006
(P,K)=(2,1)
由A1=1,A2=3,A3=7,A4=15可輕易找出P,K
若欲證明之
1.先假設若A柱中有n個大小不同的圓盤由大而小上堆疊
若要由A柱全部搬到B柱，最少要搬動An次
2.現在有(n+1)個圓盤,先將上面n個搬到C柱,由1可知需An次
3.將最下面一個搬到B柱,需1次
4.將C柱的n個圓盤再搬到B,亦須An次,到此已全完成
then A(n+1) = An + 1 + An =2 * An + 1
找出(P,K)=(2,1)
第一次解題有錯請包涵
※ 引述《Zuyi (祖儀)》之銘言：
: 有A B C三根柱子 , A柱中有n個大小不同的圓盤由大而小上堆疊
: 若要由A柱全部搬到B柱 , 每次只能搬動一圓盤 ,
: 且大盤不可放在小盤上 , 假設最少要搬動An次
: 若An = P * A(n-1) + k , 求數對(p,k)= ?
: ---------------------------------------
: 我連題意是怎樣都不太懂@@
: 請問這題要怎麼算呢
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.125.69
有A B C三根柱子 , A柱中有n個大小不同的圓盤由大而小上堆疊
若要由A柱全部搬到B柱 , 每次只能搬動一圓盤 ,
且大盤不可放在小盤上 , 假設最少要搬動An次
若An = P * A(n-1) + k , 求數對(p,k)= ?
---------------------------------------
我連題意是怎樣都不太懂@@
請問這題要怎麼算呢
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.91.107.203