[理工] 離散 遞迴 5-16

[ouskit (ouskit)]

題目的第c小題
http://i.imgur.com/UL0AK4i.jpg

解答
http://i.imgur.com/xMSz3j8.jpg

最少步驟的移動方式為 3^n - 1 那邊我都懂
但解答結論說的「每一種排列的可能都會出現」是什麼意思？

-----
Sent from JPTT on my Samsung SM-G970F.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.16.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1566553663.A.942.html
→ JKLee: 總共有3^n種可能的state.最小的盤子可能出現在A,B or MID
→ JKLee: 第二小的盤子可能出現在A,B or MID.
→ JKLee: 每個盤子都有三種可能
我知道總共3^n，這跟這小題答案有關係嗎？
→ JKLee: 所以總共是3^n種可能的state
※ 編輯: ouskit (220.135.16.216 臺灣), 08/23/2019 19:10:17
→ Ricestone: 移動次數有3^n-1，每次移動都是新的排列，所以都用掉了
→ Ricestone: 如果移動中有重複的排列，代表就不是最短的移動