黑马程序员技术交流社区

标题: 递归和汉诺塔攻略 [打印本页]
作者: niuapp    时间: 2015-5-19 21:40
标题: 递归和汉诺塔攻略
本帖最后由 niuapp 于 2015-5-22 23:16 编辑

据说 A柱子上如果有64个盘子，把它们都移动到C柱子上时，世界就会毁灭百度百科：http://baike.baidu.com/link?url=MWuajZIEWJRoU8ndGAlDTI9OYQd_kOIaBfKDrfT2AmCrrgFJp1PRwmJwchURQXsQU72p_rHlloPjOqHZeErWn_

输出例子：---------------------------------------------
输入A柱子上盘子个数 n = 4
把编号为1的盘子从A柱子移动到B柱子
把编号为2的盘子从A柱子移动到C柱子
把编号为1的盘子从B柱子移动到C柱子
把编号为3的盘子从A柱子移动到B柱子
把编号为1的盘子从C柱子移动到A柱子
把编号为2的盘子从C柱子移动到B柱子
把编号为1的盘子从A柱子移动到B柱子
把编号为4的盘子从A柱子移动到C柱子
把编号为1的盘子从B柱子移动到C柱子
把编号为2的盘子从B柱子移动到A柱子
把编号为1的盘子从C柱子移动到A柱子
把编号为3的盘子从B柱子移动到C柱子
把编号为1的盘子从A柱子移动到B柱子
把编号为2的盘子从A柱子移动到C柱子
把编号为1的盘子从B柱子移动到C柱子
请按任意键继续. . .

---------------------------------------------


  1. /*
  2.         需求：汉诺塔，有三个柱子，A柱子上从小到大有n个盘子，要借用B柱子把A柱子上的盘子移动到C柱子，大的在下边，小的在上边

  4.         步骤：        1.先创建三个柱子
  5.                         2.输入A柱子上的盘子个数n
  6.                         3.创建一个移动盘子的方法，接受三个柱子和盘子
  7.                         4.递归
  8.                                 如果A柱子上有n个盘子，则先把 n-1 个盘子移动到B柱子，把A柱子上剩下的 第n个盘子移动到C柱子
  9.                                 B柱子上有的 n-1 个盘子，把 (n-1)-1 个盘子移动到A柱子，把B柱子上剩下的 第n-1个盘子移动到C柱子
  10.                                 ......直到A或B柱子上 只剩1个盘子，直接把它移动到C柱子，完成

  12.         总结：把大规模的东西分成两个部分，规模递减，直到把大规模的问题变成可以直接解决的问题
  13.         
  14. */

  16. import java.util.Scanner;

  18. class HanNuoTa {
  19.         public static void main(String[] args) {
  20.                 //先创建三个柱子
  21.                 char a = 'A';
  22.                 char b = 'B';
  23.                 char c = 'C';
  24.                 int n;
  25.                 Scanner sc = new Scanner(System.in);
  26.                 System.out.print("输入A柱子上盘子个数 n = ");
  27.                 n = sc.nextInt();

  29.                 move(n, a, b, c);
  30.         }

  32.         //接收  a/b/c 三个柱子（小写）目的是把a柱子上的盘子 借助b柱子 移动到c柱子
  33.         public static void move(int n, char a, char b, char c){
  34.                
  35.                 if(n==1){        //如果A柱子上只剩一个盘子，就直接把它移动到C柱子
  36.                         System.out.println("把编号为"+n+"的盘子从"+a+"柱子移动到"+c+"柱子");
  37.                 }else{
  38.                         move(n-1, a, c, b);//规模递减 先把A柱子上的 n-1 个盘子借助C移动到B
  39.                         System.out.println("把编号为"+n+"的盘子从"+a+"柱子移动到"+c+"柱子");//上边语句过后A柱子上只剩1个盘子,直接把它移动到C柱子
  40.                         move(n-1, b, a, c);//继续，把B柱子当做原先的A柱子，把B柱子上的 n-1 个盘子借助A移动到C
  41.                 }
  42.                 return;
  43.         }
  44. }
复制代码


汉诺塔.jpg (117.5 KB, 下载次数: 8)

图

图
作者: LoveMyself    时间: 2015-5-20 12:33
还有这样的题，长见识了
作者: hsx500    时间: 2015-5-20 13:52
求问递归在编程上有什么实际应用？
作者: niuapp    时间: 2015-5-20 19:49
hsx500 发表于 2015-5-20 13:52
求问递归在编程上有什么实际应用？

有时候可以用那种规模递减的方法吧复杂的问题精细的问题变得稍简单和整洁？我是新人不太懂
作者: 谷歌    时间: 2015-5-21 00:35
收藏学习！
作者: 汤姆大叔    时间: 2015-5-22 22:18
有一点，还是有点看不提啊明白。。
作者: 马鹏涛    时间: 2015-5-22 22:21
不是很明白!长知识了
作者: 远上寒山    时间: 2015-6-14 11:14
为什么世界会毁灭？
作者: 海角秋风    时间: 2015-6-14 11:30
先收藏，学习一下。。。
作者: meng12    时间: 2015-6-14 11:50
赞赞赞，顶一下
作者: mouwengang    时间: 2015-6-14 12:03
谢谢分享！
作者: 13569403973    时间: 2015-6-14 13:57
看着好复杂奥！
作者: 冷雨敲窗被未温    时间: 2015-6-14 14:31
啧啧！这个
作者: 文伟伟    时间: 2015-6-14 14:36
很好，但是界面是怎么出来的了？



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