[其他] 河內塔

看板Math作者 (冷氣團團長)時間14年前 (2011/10/03 08:34), 編輯推噓3(3推 0噓 15→)
留言18則, 4人參與, 最新討論串1/1
第一題 A.B.C 3個柱子 A能到B B能到C A不能到C 有N個DISK 求最少次數!! 拜託大家幫忙囉 想破頭想不出來XD -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 163.22.18.74 ※ 編輯: a606155123 來自: 163.22.18.74 (10/03 08:44)
→
10/03 11:50, , 1F
遞迴數列
10/03 11:50, 1F
→
10/03 11:54, , 2F
A(n) = 2A(n-1) + 1 , A(n)為n個disk最少次數
10/03 11:54, 2F
→
10/03 11:57, , 3F
確認2個問題：
10/03 11:57, 3F
→
10/03 11:57, , 4F
1.移動過程一樣要尊守大的在小的之下?
10/03 11:57, 4F
→
10/03 11:58, , 5F
2.A不能到C的意思是 以1個為例 A要到C是 A->B,B->C ?
10/03 11:58, 5F
→
10/03 11:59, , 6F
如果是這樣 那會複雜很多
10/03 11:59, 6F
推
10/03 12:15, , 7F
剛剛想一下其實也還好
10/03 12:15, 7F
→
10/03 12:16, , 8F
反正就是 要移動第n+1個時 要先把上面n個移到最右邊
10/03 12:16, 8F
→
10/03 12:16, , 9F
然後把第n+1個移到中間，再把前n個移到最左邊
10/03 12:16, 9F
→
10/03 12:17, , 10F
接著把第n+1個移到最右邊，最後把前n個也移到右邊
10/03 12:17, 10F
→
10/03 12:17, , 11F
所以只是遞迴變成 A(n+1) = 3An + 2
10/03 12:17, 11F
→
10/03 12:17, , 12F
其中A1 = 2 這樣
10/03 12:17, 12F
回一下c大 1.對要遵守大小 2.沒錯!! 意思就是a不能直接到c 要透過b 我自己算一下好像是3的n次方之後在-1(不是次方-1)!! ※ 編輯: a606155123 來自: 163.22.18.74 (10/03 12:43)
推
10/03 14:27, , 13F
(3^n)-1 無誤 數學歸納法可以證明 XD
10/03 14:27, 13F
推
10/03 14:38, , 14F
馬後炮一下 遞迴中的A1 = 2, A(n+1) = 3An+2可寫成
10/03 14:38, 14F
→
10/03 14:38, , 15F
A(n+1) = 3An+2 = 3(An+1)-1
10/03 14:38, 15F
→
10/03 14:39, , 16F
所以A1=2時 An是 3^n-1
10/03 14:39, 16F
→
10/03 14:53, , 17F
程式設計會有初始狀態是亂擺的練習(但是大在小下)
10/03 14:53, 17F
→
10/03 14:54, , 18F
想法跟原始版也是一樣就是了
10/03 14:54, 18F
‣ 更多 a606155123 的文章
文章代碼(AID): #1EYGCAHZ (Math)