Java编程挑战：递归河内塔 - 虚拟人物

这个挑战可以帮助你使用你的编程人才来编写一个Java程序，根据磁盘的数量，打印解决河内难题所需的步骤。

河内塔是一个经典的逻辑谜题，由三个垂直钉和许多不同直径的圆盘组成。每个磁盘的中心都有一个孔，可以让磁盘在磁盘上滑动。

拼图开始于其中一个钉上的所有磁盘，最底部的磁盘最大，顶部最小。谜题的目的是将一叠磁盘移动到另一个钉上，遵从两个简单的规则：（1）一次只能移动一个磁盘，（2）永远不能放置更大的磁盘小一个的顶部。

<！ - 1 - >

下图显示了三个磁盘堆栈的解决方案。如您所见，解决方案需要七步移动：

将磁盘1从挂钩1移至挂钩3.
将磁盘2从挂钩1移至挂钩2.
将磁盘1从挂钩3移至挂钩2。
将磁盘3从挂钩1移至挂钩3.
将磁盘1从挂钩2移至挂钩1.
将磁盘2从挂钩2移至挂钩3.
<！ - 2 - >
将磁盘1从挂钩1移动到挂钩3.

经过这七个步骤后，磁盘的堆栈将在挂钩3上。

解决方案为河内拼图三磁盘。

开始将磁盘添加到起始位置时，这个难题会变得很有趣。有了三个磁盘，这个谜题只需要7步就可以解决。使用四个磁盘时，需要15次移动。有了五个磁盘，你需要31个动作。六个磁盘需要64个移动。

如果你一直在数学中，解决这个难题所需要的移动次数随着磁盘数量的增加呈指数增长。具体来说，移动 n 磁盘所需的移动次数为2 999 999 n。例如，一个20个磁盘的堆栈将需要2 999 $ 20 999 - 1个移动;这是超过一百万的动作！ ^{一个有趣的传说与这个难题有关：在河内的一座寺庙里，僧人自创建地球以来一直在研究河内的一个谜题塔，共有64个圆盘。当他们完成后，世界将会结束。幸运的是，我们还有很长一段时间需要等待：如果僧侣每秒钟可以移动一个磁盘，那么在完成这个难题之前还需要5800亿年左右的时间。} 你的挑战很简单：编写一个Java程序，根据磁盘的数量，打印解决河内难题所需的步骤。程序应该首先提示用户输入磁盘的数量。然后它应该显示步骤，每行一个。每一步应该指出哪个挂钩移动磁盘，哪个挂钩移动磁盘。这些步骤也应该按顺序编号。 ^{一旦完成，程序应该重复，再次询问用户的磁盘数量。程序应该在用户输入0时结束。} 以下是程序应该生成的控制台输出示例：

多少个磁盘？（0到结束）

1：1到3 2：1到2 3：3到2 4：1到3 5：2到1 6：2到3 7：1到3多少个磁盘？（0到结束）

解决这个挑战的唯一的其他要求是你的解决方案必须使用递归编程。换句话说，你的解决方案必须包括一个方法来调用它来解决这个难题。 递归编程可能是具有挑战性的，所以下面是解决这个难题的一些提示： 这个谜题包含三个瑕疵。其中之一包含起始堆栈的磁盘;调用这个peg 源peg

。其余两个挂钩之一是你想要移动磁盘堆栈的挂钩;调用这个挂钩

目标挂钩

。您可以使用第三个挂钩作为中间挂钩在移动磁盘时临时存储磁盘。把这个挂钩叫做 spare peg 。递归方法应接受三个参数：要移动的磁盘数，源绑定和目标绑定。使用整数值1,2和3来表示钉。递归解决这个难题的基本思路是：要将一堆磁盘从一个源peg移动到一个目标peg，需要三个步骤：将除了底部磁盘之外的所有磁盘移动到备用挂钩。将原始堆栈中的最大磁盘移动到目标挂钩。
将您在步骤1中移动的堆栈从备用挂钩移至目标挂钩。
当然，谜题规则允许你一次只移动一个磁盘，所以你只需拾取堆栈并移动它，就不能完成这里给出的过程的第1步和第3步。这就是递归的地方。对于步骤1和步骤3，您递归地调用方法，每次指定要移动的磁盘数量较少，并且每次使用先前的目标挂钩作为备用挂钩。
1. 想知道为什么递归方法不需要接受备用挂钩作为参数？因为你可以很容易地计算出来，给定源和目标钉。由于只有三个挂钩，编号为1,2和3，所以三个挂钩的总和是6（1 + 2 + 3）。给定来源和目标挂钩，可以通过从6中扣除来源和目标挂钩来计算备用挂钩。例如，如果来源挂钩为1且目标挂钩为3，则备用挂钩必须为2，因为
2. 6 - 3 - 1 = 2.
3. 有关解决方法，请转至
Java全合一傻瓜版，
第4版产品页面的下载选项卡。祝你好运！