【汉诺塔问题】汉诺塔问题怎么解决啊

【汉诺塔问题】汉诺塔问题怎么解决啊

【答案】 1问题描述 问题提出：有三个塔(分别为A号，B号和C号)。开始时．有 n个圆形盘以从下到上、从大到小的次序叠置在A塔上。现要将A 塔上的所有圆形盘，借助B搭，全部移动到C搭上。且仍按照原来 的次序叠置。 移动的规则如下：这些圆形盘只能在3个塔问进行移动．一 次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比 它小的盘子的上面。 要求如下：从键盘输入初始圆形盘子个数n．用JAVA实现n 个盘子最佳移动的全过程。 2算法分析 此题的目的是设计一个盘子移动的方案．使得A号塔上的所 有盘子借助于B号塔按照原来的次序移动到C号塔上，并且．要 给出完整的最佳的盘子移动的方案。 我们从实际的、具体的盘子的移动过程来分析．找出问题内 在的规律。经分析无论盘子的个数有多少．是1、2、3..或n个． 也不管我们怎么去移动盘子(当然是按规则来移动)．但在移动的 过程中，将始终会出现这样的状态情况：(n一1)个盘子将会以从下 到上、从大到下的次序叠置在B塔上，这时，A塔上第n个盘子就 能被轻而易举叠放到c塔上；接着，我们再把B塔上的其fn一1)十 盘子移动到C塔上，问靼好像已经解决 但，B塔上fn—1)个盘子怎么移动到C塔上呢?这是我们要解 决的第二个问题。同样，不管我们怎么移动，也将会出现这样的状态情况：(n一2)个盘子将会以从上到下、从大到小的次序叠置在A 塔上，这时。B塔上第(n一1)个盘子就能被轻而易举放到C塔上；接 着，我们把A塔上的共(n一2)个盘子移动到C塔上。 这样，不断深入，不断细小化，最终，将到达仅有一个盘的情 形。这时，递归也就终止了，问题也得到了解决。通过以上分析．这 里有很明显递归关系 由此，想到了采用递归算法来解决该问题。因为递归算法有这 样特征描述：为了求解出规模力N的问题的解．我们先设法将它分 解成一些规模较小的问题，然后从这些较小问题的解能方便地构 造出大问题的解，并且这些规模较小的问题也能采用同样的方法 分解，分解成规模更小的问题，并能从这些更小的问题的解构造出规模稍大问题的解。特别地是，当规模N-I时，能直接得到解。 现在，严格按照递归算法来解决问题。先定义递归方法Hanio (int N，char A，char B，char C)，按如下步骤进行解题(设初始盘子个 数为N)：若A塔上仅仅只有一个盘子(N=1)，则直接从A移动到 C，问题完全解决。若A塔上有一个以上的盘子(N>1)，则需要考虑以下三个步骤。 第一步：把 一1)个盘子从A塔经过移动，叠放到B塔上。在 不违反规则情况下，所有fN一1)个盘子不能作为一个整体一起移 动，而是要符合要求地从一个塔移到另一个塔上。用Hanio(N—1．A， C，B)调用递归方法，注意：这里是借助于C塔，将(N一1)个盘子从A 塔移动到B塔，A是源塔，B是目标塔。 第二步：将剩下的第N个盘子(也就是最底下的一个)直接从A塔 叠放到空着的C塔上。 第三步 用第一步的方法，再次将B塔上的所有盘子叠放到 C塔上。同样，这一步实际上也是由一系列更小的符合规则的移动 盘子的操作组成的。用Hanio(N一1，B，A，C)调用递归方法，注意：这 里是借助于A塔，将(N—1)个盘子从B塔移动到C塔，B是源塔，℃ 是目标塔。 这个算法达到了预期的目标．即在C塔上按正确的次序叠放 了所有的圆形盘子。有了前面问题算j去分析的基础，继而，我们可 以用JAVA来实现算法。 3 JAVA实现 3．1说明如下 (1)n为A塔初始盘子个数； (2)A塔上盘子从上到下、从小到大编号依次为l，2，3. . ： (3)Hanio0方法采用递归算法，实现盘子移动的最佳方案： (5)InputnO方法实现盘子个数n的键盘输入(输入必须为阿 拉伯数字)。 3．2编程如下 import java．io． ；，／引用java包的io子包的所有公有类 public class Hanio／／Hanio类的声明 {static int n； public static void main(Strin乱J args)throws IOException I System．out．print(”请输入盘子的个数lI=”)； n=Integer．parselnt(Inputn0)； System．out．prindn(”盘子的整个移动过程如下．I ； Hanio(n， A ， B ， C )；，／调用Hanio方法l #HanioO方法采用递归算法 public static void Hanio(int N，char A，char B，char C) {if(N==1) System．out．prlntln(”Dish l from”+A+”to”+C)； else · {Hanio(N—l，A，C，B)；／／把A上的N一1个盘子借助于C叠放刘 B上 System．out．println(”Dish”+N+”from”+A+”to“+C)： Hanio(N一1，B，A，C)；／／再把B上的N—1个盘子借助于A叠放到 C上 ll ，，读从键盘输入的数据流的方法 public static String InputnO throws IOException {String str； BuferedReader Input=new BuferedReader fnew InputStream． Reader(System．in11； str=Input．readLine0； retum str；}l 3．3编译、解释运行iava程序 上面的代码可以使用记事本录入，保存文件名为Hanio．java。 在运行iava程序前首先使用编译程序iavac进行编译，通过后再 使用java运行即可。具体的命令操作如下。 (1)编译程序 C：＼j 追问： 能不能把c语言解决的程序发过来？谢了 追答： 在运行iava程序前首先使用编译程序iavac进行编译，通过后再 使用java运行即可。具体的命令操作如下。 (1)编译程序 C：＼java>javac Hanio．java 编译成功后生成类文件Hanio．class (2)运行程序 C：＼java>java Hanio 注：编写iava程序的运行环境必须安装JDK工具包，并进行 配置．可以从WWW．java．com下载。 4总结 其实。递归算法的执行过程分为递推和回归两个阶段。在递推阶段，把较为复杂的问题(如规模为N)的求解推到比原问题简 单一些的问题(规模小于N)的求解。’例如上面分析过程中，为求 解Hanio(N，A，B，C)，推到计算Hanio(N一1，A。C。B)。 在回归阶段，当获得最简单情况的解后，逐级返回。依次获得 稍复杂问题的解。在这里的“汉诺塔”问题中，有它的特别的地方， 回归的过程当中．还要涉及到递推。 另外．在编写递归方法时要注意是：每次调用递归方法，方法 中的参数只是局限于当前调用层的，当递推进入“简单问题”层 时，原来层次上的参数便被隐藏起来。在一系列“简单问题”层，它 们各有自己的参数。 ． 最后．通过经典“汉诺塔”问题移动过程的分析、解决以及最 后JAVA编程实现，使我们能够掌握解决此类问题的方法，也使 我们对递归算法能有个更加深刻的理解。分享到： 追问： 不能用java的，我们刚开始学程序，要用c 追答： hanoi(m,'A','B','C');这个算法的目的就是将m个积木块，从'A‘柱经过'B'柱移到'C‘柱上给你照着代码讲吧。void hanoi(int n,char one ,char two,char three) {void move(char x,char y);//声明打印函数if(n==1) //如果只有一个积木块，直接将这个积木块从A移到Cmove(one,three); //打印A->Celse //如果大于一个积木块，{hanoi(n-1,one,three,two); //首先将n-1个从A经过C移到B上，此时A上剩最大的一个积木move(one,three) //将最大的积木从A移到C上，打印A->Chanoi(n-1,two,one,three); //之后将n-1个从B经过A移到C上，完成。}}整个递归的过程你可以用n=2，n=3在脑力里过一遍就应该没有问题了。他就是循环调用hanoi这个方法，直到n==1 追问： 你的回答完美的解决了我的问题，谢谢！

这个解释是对的