分析算法 - 遞推方程（河內塔）

我看到了這個遞歸算法來解決維基百科的河內塔。有人能向我解釋我如何得到這個算法的遞推方程嗎？分析算法 - 遞推方程（河內塔）

遞歸溶液

標籤栓A，B，C - 這些標籤可以在不同的步驟移動

令n爲光盤的總數量從1

號盤（最小的，最上面的）至n（最大，最底部）

從栓A移動ñ光盤釘住C：

移動從A n-1個光盤到B.這使得盤ñ單獨對從A PEG甲

移動盤N端至C

移動n-1個盤從B到C，使他們坐在盤n

以上是遞歸算法，執行步驟1和3，再次對n-1應用相同的算法。整個過程是有限數量的步驟，因爲在某些時候，對於n = 1，該算法將是必需的。將單個盤從掛鉤A移動到掛鉤B的這一步驟是微不足道的。

來源

2013-10-31 U23r

T（n）=三個步驟的總和......請展示一些努力。 –

前三個步驟可以以線性的時間內完成，第二個三個步驟是遞歸的一部分，那麼，只是簡單的遞歸形式寫的東西是寫在純文本格式：

T(n,A,C) = T(n-1,A,B) + 1 + T(n-1,B,C).

在另一方面，因爲標籤不重要，T（n，A，B）= T（n，B，C）= T（n，A，C）= ...，我們可以去除標籤，所以等式會是？

來源

2013-10-31 11:43:48

分析算法 - 遞推方程（河內塔）

回答

相關問題