1

例如，在下面的汉诺塔算法中：

input   Number of disk   
output  Print: disk moved successfully  
complexity  O(n).  

Tower(n , beg , aux , end)  
1.  If (n=1) then   
Beg = end;  
Return;  
2.  Call Tower(n-1 , beg ,end , aug );  
3.  Call Tower (1 ,beg ,aux ,end );  
4.  Call Tower (n-1,aux ,beg ,end);

辅助假设代表什么？

4

2 回答 2

3

河内塔问题中有三个主轴：一个起始主轴（塔开始的地方），一个结束主轴（塔应该结束的地方）和一个辅助主轴（三个中的另一个）。辅助主轴用作临时存储空间，用于在将整体塔从起始主轴到结束主轴的过程中移动磁盘和塔。

希望这可以帮助！

于 2013-10-07T18:34:05.527 回答
1

如果只有两个钉子，就不可能移动多个磁盘。要将包含多个磁盘的组从例如 peg 1 移动到 peg 2，有必要将除底部磁盘之外的所有磁盘移动到既不是该组的起点也不是终点的 peg。另一个挂钩被称为“辅助”。算法的一些表示明确指定了辅助挂钩（在这种情况下，挂钩的编号是 0-1-2、1-2-3 还是 11-47-93 无关紧要），而另一些则要求这三个挂钩具有三个特定的数字（例如 0-1-2），并假设未给出的任何值都是辅助数字（例如通过计算 (aux = 3-src-dest)）。

顺便说一句，拼图的 3 钉版本被如此普遍地用作示例，这几乎是一种耻辱，以至于没有努力探索更多钉的变化。100 多年前的益智书籍中探索了这种变化，但我没有看到任何现代教科书提到它们，尽管我认为它们更有趣。

于 2013-10-07T18:43:39.053 回答