我最近在河内解决问题的塔。 我用了一个“分而治之”的策略来解决这个问题。 我分的主要问题为三个较小的子问题，从而产生以下复发。
T（N）= 2T（N-1）+1
解决这导致
O（2 ^ N）[指数时间]
然后我试图使用记忆化技术来解决这个问题，但这里太空间复杂度呈指数和堆空间很快用尽的问题仍然无法解决对于更大的n。
有没有解决小于指数时间问题的方法吗？ 什么是它的问题是可以解决的最佳时机？
Answer 1:
这取决于你所说的“解决”的意思。 汉诺塔的问题，3个突和n磁盘会占用2**n - 1移动来解决，所以如果你想枚举动作，你显然不能做到优于O(2**n)因为枚举k东西是O(k) 。
在另一方面，如果你只是想知道的需要（不枚举它们）的移动次数，计算2**n - 1是一个更快的操作。
还值得注意的是，所述移动的枚举可以迭代与完成O(n)空间复杂性如下（ disk1是最小的磁盘）：
while true:
if n is even:
move disk1 one peg left (first peg wraps around to last peg)
else:
move disk1 one peg right (last peg wraps around to first peg)
if done:
break
else:
make the only legal move not involving disk1
Answer 2:
你能解决复发并获得封闭形式。
T（N）= 2 * T（N-1）+ 1
T（N）= 2 *（2 * T（N-2）+ 1）+ 1
T（N）=（2 ^ 2）* T（N-2）+ 2 ^ 1 + 2 ^ 0
T（N）=（2 ^ k）的* T（NK）+ 2 ^（K-1）+ 2 ^（K-2）+ ... + 2 ^ 0
解决这个从封闭出来是
T（N）=（2 ^ N） - 1 T（0）= 0
现在，通过使用平方幂。
Answer 3:
Unfortunantly这是不可能在较短的时间来解决这个问题，因为需要改变所有汉诺塔的位置移动数是指数。 因此，最好的解决方案根据的步骤O（T）的数目为线性，因此，在尾巴溶液数量是指数O（2 ^ n）的
Answer 4:
正好有2 ^ n-1个动作，所以把它们列出所有我们不能做的比O（2 ^ n）的时间复杂度更好。
必要动作枚举是O（1）（好了，O（log n）的，如果你把一个任意大小的整数）的空间可能：
(define (fbs n i) (if (even? n) (fbs (/ n 2) (+ i 1)) i))
(define (fb n) (fbs n 1))
(define (hanois n i m)
(
cond
((= i m) "DONE")
(else
(define k (fb i))
(print "move disk " k " " (if (even? (+ n k)) "left" "right"))
(hanois n (+ 1 i) m))))
(define (hanoi n) (hanois n 1 (expt 2 n)))
[方案]
请注意，该算法具有日志的n由于算法的开销（和算法fb找到最显著设置位的位置）。 任何涉及任何一种递增/递减的柜台上天真的解决方案将具有相同的开销。
Answer 5:
这取决于你接受什么样的表示了一下。 想象一下以下方面的代表：
OneMove
from : integral
to : integral
Solution
step_one : optional reference to Solution
step_two : OneMove
step_three : optional reference to Solution
这样的表示可以实际上线性复杂性被创建，因为这牵涉到大量的重复。
我刚刚试了一下，构建适合身高64这样的解决方案只用了不到一毫秒。 当然，通过它步进仍然需要2 n -1 个步骤。
您没有指定的语言，但如果你在C ++代码想，掉线。
文章来源: Complexity for towers of Hanoi?
