用栈来求解汉诺塔问题

【题目】

汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有N层的时候,打印最优移动过程和最优移动总步数。

例如,当塔数为两层时,最上层的塔记为1,最下层的塔记为

2,则打印：

请点击此处输入图片描述

注意:关于汉诺塔游戏的更多讨论,将在本书递归与动态规划的章节中继续。

【要求】

用以下两种方法解决。

方法一:递归的方法；

方法二:非递归的方法,用栈来模拟汉诺塔的三个塔；

本文将讲述方法一：

【解答】

方法一:递归的方法。

首先,如果只剩最上层的塔需要移动,则有如下处理

1.如果希望从“左”移到“中”,打印“Move1 from left to mid”。

2.如果希望从“中”移到“左”,打印“Move1 from mid to left”。

3.如果希望从“中”移到“右”,打印“Move1 from mid to right”。

4.如果希望从“右”移到“中”,打印“Mve1 from right to mid”。

5.如果希望从“左”移到“右”,打印"Move1 from left to mid”和"Move1 from mid to right"。

6.如果希望从“右”移到“左”,打印“Move1 from right to mid"和“Move1 from mid to left”。

以上过程就是递归的终止条件,也就是只剩上层塔时的打印过程。

接下来,我们分析剩下多层塔的情况。

如果剩下N层塔,从最上到最下依次为1~N,则有如下判断：

1.如果剩下的N层塔都在“左”,希望全部移到“中”,则有三个步骤。

1)将1~N-1层塔先全部从“左”移到“右”,明显交给递归过程。

2)将第N层塔从“左”移到“中”。

3)再将1~N-1层塔全部从“右”移到“中”,明显交给递归过程。

2.如果把剩下的N层塔从“中”移到“左”,从“中”移到“右”,从“右”移到“中”,过程与情况1同理,一样是分解为三步，在此不再详述。

3.如果剩下的N层塔都在“左”,希望全部移到“右”,则有五个步骤。

1)将1~N-1层塔先全部从“左”移到“右”,明显交给递归过程。

2)将第N层塔从“左”移到“中”。

3)将1~N-1层塔全部从“右”移到明显交给递归过程。

4)将第N层塔从“中”移到“右”。

5)最后将1~N-1层塔全部从“左”移到“右”,明显交给递归过程。

4.如果剩下的N层塔都在“右”,希望全部移到“左”,过程与情况3同理,一样是分解为五步,在此不再详述。

以上递归过程经过逻辑化简之后的代码请参看如下代码中的hanoi Problem1方法。

请点击此处输入图片描述

欢迎一起来交流代码那点事：https://mp.csdn.net/postedit/80325970?utm_source=zwqt

请点击此处输入图片描述