※ 引述《hu610346 (狐狸)》之銘言：
: 三色河內塔的規則就是
: 有三個顏色的河內塔
: 要想辦法用河內塔的規則
: 把三個顏色互換
: 想要問一下
: 要用甚麼樣子才可以用最少的次數完成
: 像是這樣: http://ppt.cc/rXTj
: 然後我統計了一下數據
: 最後解出來
: An=2An-1 - An-2 + 36*2^(n-3)
: (An是當一個顏色有n個盤子,要用最少次完成的次數)
: 可以請板友幫我解他的一般項嗎
: 有人說是比一般的河內塔還要複雜一點點而已
: 但我始終想不出來
: 拜託各位板友了
A1=10, A2=38
首先 如果是你的式子:
An - An-1 = An-1 - An-2 + 18*2^(n-2)
兩邊從n=3~k求和
Ak - Ak-1 = 18*2^(k-1)-36 + A2-A1 = 18*2^(k-1) - 8
Ak = Ak-1 + 18*2^(k-1) - 8
兩邊從k=2~n求和
An = A1 + 18*2^n - 36 - 8n + 8 = 18*2^n - 8n - 18
即為一般式
另:
一般解法應該是假設bn, cn
bn為原始狀態到所有圓環集中到同一根柱上的最小步數
cn為所有圓環集中到同一根柱上移至所有圓環集中到另一根柱上的最小步數
簡單算法可知 b1=2, b2=10, c1=3, c2=9
另外 遞迴式:
bn = bn-1 + 2cn-1 + 2
cn = 2cn-1 + 3
所以可解出 cn = 3*2^n - 3 , bn = 6*2^n - 4n - 6
最後An至少要 2bn-1 + 8cn-1 + A1 步
所以 An= 18*2^n - 8n - 18
p.s. 詳細點還要證明這樣的分法一定可以使每種顏色配對到
即最後會同色圓環在同一跟柱上
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.40.198.54