黑马程序员技术交流社区

标题: 一个递归的而经典问题----汉诺塔 [打印本页]
作者: 苟苟    时间: 2015-5-5 00:39
标题: 一个递归的而经典问题----汉诺塔
问题描述:
从左到右 X  Y Z 柱 大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱, 期间只有一个原则: 大盘子只能在小盘子的下面.
如果有3个盘子, 大中小号, 越小的越在上面, 从上面给盘子按顺序编号 1(小),2(中),3(大), 后面的原理解析引用这里的编号.

分析,这个是一个经典的递归问题.我们现在可做如下设想
1,递归结束条件,当X上有一个盘子的时候,直接将盘子拿到Z就ok
2,如果盘子有n个,那么将n-1个盘子借助Z从X移动到Y.hanoi(n-1,X,Y,Z)
   那么将X上剩下的最大盘子移动到Z
   接下来将n-1个盘子从Y借助Z移动到X

PS:那么会有一个疑问, 移动的n-1个盘子怎么移动呢? 呵呵,使用递归.
这样n个规模的问题分解n-1和一个, n-1继续分解, 那么一直分解到最小问题或者有解,这样大问题的解也就出来了

汉诺塔代码如下:
  1. /**
  2. * <p>Title: HanoiRecursion.java</p>
  3. * <p>Description: </p>
  4. * <p>Copyright: Copyright (c) 2015</p>
  5. * @author possible
  6. * @date 2015年5月4日
  7. * @version 1.0
  8. */
  9. package com.dl.recursion;

  11. public class HanoiRecursion {
  12.         public static void hanoi(int counter, String src, String helper, String des) {
  13.                 if (counter == 1) {//递归结束条件
  14.                         move(counter, src, des);
  15.                 } else {
  16.                         //将counter-1个盘子从src借助des移动到helper
  17.                         hanoi(counter - 1, src, des, helper);
  18.                     //将最大的从src移动到des
  19.                         move(counter, src, des);
  20.                         //将counter-1个盘子从helper借助des移动到src
  21.                         hanoi(counter - 1, helper, src, des);
  22.                 }

  24.         }

  26.         private static void move(int name, String src, String des) {
  27.                 System.out.println("将 " + name + "从" + src + "  移动到   " + des);
  28.         }
  29. }
复制代码



测试代码:
  1. public static void main(String[] args) {
  2.                 HanoiRecursion.hanoi(4, "X", "Y", "Z");
  3.         }
复制代码


PS:移动的不要太大, 如果是64,呵呵, PC一天两天也递归不完.......
作者: Ray丶少年    时间: 2015-5-5 10:04
太聪明了，受教了，谢谢
作者: jing3133920    时间: 2015-5-5 10:48
学习学习



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2