汉诺塔，递归的典型例子，自己认真做，做出来加分了。...

汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。

汉诺塔问题

提示

这个问题在盘子比较多的情况下，很难直接写出移动步骤。我们可以先分析盘子比较少的情况。假定盘子从大向小依次为：盘子1，盘子2，...，盘子64。

如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。

如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。

如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。

如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。

上述的思路可以一直扩展到64个盘子的情况：可以借助空座C将盘子1上的63个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的63个盘子移动到C。

韦念欣 · 韦念欣

嘿嘿，这道题对于上过算法的同学来说，还是相对简单的。

蒙武辉 · 蒙武辉

这个是课本上的例子，哈哈

丁二跃 · 丁二跃

public class Test {
public static void main(String[] args) throws FileNotFoundException {
int num=18; //盘子数量
String a = "A"; //初始盘子存放位置
String b = "B"; //盘子移动目标位置
String c = "C"; //另外一个中介
System.setOut(new PrintStream("d:/log.txt")); //太长了看不到结果可以输出到文件
move(num, a, c, b);
}
//该方法实现盘子移动将 n 个盘子从 a 借助 c 移动到 b
static void move(int n,String a ,String c,String b){
if(n==1){
System.out.println(a +"--1-->"+b );
return ;
}
if(n==2){
System.out.println(a+"--1-->"+c);
System.out.println(a+"--2-->"+b);
System.out.println(c+"--1-->"+b);
return;
}
move(n-1, a, b, c); //要想把最下面的 n 号盘子移动到 b ，首先要把前面n-1 个盘子由 a 移动到 c
System.out.println(a+"--"+n+"-->"+b);//将n 号盘子移动到 b 现在有n-1 个盘子在c
move(n-2, c, b, a); //现在想把第 n-1 个盘子由 c 移动到 b ，首先应该把 n-2 个盘子移动到 a
System.out.println(c+"--"+(n-1)+"-->"+b);//将 n-1 号盘子移动到b
// 注意现在有 n-2 个盘子在a 问题是不是又回到最初只不过盘子数量已经 -2 继续调用就哦了
move(n-2, a, c, b);
}
}

复制代码

:'( 想了好久…………
最后发现从整体去想好像容易些：想移动下面的，就要把上面的全移到另外的盘子…………这样一次减少一个盘子的递归调用…………具体看程序，里面有注释。不知道对不对？……

5555…………递归真慢，数小还好……64 好半天没出来。

位雪 · 位雪

public class HanoiW {
public static void main(String args[]){
HanoiW han = new HanoiW();
han.hanoi(3,'A','B','C');
}
public void hanoi(int num,char a,char b,char c){
if(num == 0) return;
this.hanoi(num-1,a,c,b);
System.out.println("move plate p" + num +
" from " + a + " to " + c);
this.hanoi(num-1,b,a,c);
}
}

复制代码

王冰 · 王冰

本帖最后由王冰于 2012-7-13 20:52 编辑

class Hanoi
{
      public static void main(String[] args)
      {
            hanoiMove(3,'a','b','c');
      }

      public static void  hanoiMove(int n,char a,char b,char c)//将塔x上的盘子按直径由小到大
      //自上而下从1 ~ n编号，按规则从塔a移到塔c，b用作辅助塔，调用时，n可以为任意正整数
      {
            if(n ==1)
                     sop(n+"号盘子从"+a+"-->"+c);
            else
            {
                     hanoiMove(n-1,a,c,b);//将a塔上编号为1 ~ n-1的移动到b塔，c作辅助塔
                     sop(n+"号盘子从"+a+"-->"+c);    //将编号为n的直接从a塔移到c塔
                     hanoiMove(n-1,b,a,c);//将b塔上编号为1 ~ n-1的移动到c塔，a作辅助塔
            }
      }

      public static void sop(Object obj)
      {
         System.out.println(obj);
      }
}

何旭栋 · 何旭栋

// num为汉诺塔的层数，返回int为需要移动的次数
public static int HanoiBy(int num){
// 一层的塔只需要移动一次就可以了
if (num == 1)
return 1;
// 假如2层的塔需要移动3次，那么3层他就可以先把上面2层她移动到B，需要3次（移2层塔需要3次），接着把
// 地下一层移到C盘，再从B移一次2层塔到C，又需要3次，一共是3+1+3=7次
return (HanoiBy(num-1)*2+1)；
}
递归试试

周刚 · 周刚

本帖最后由周刚于 2012-7-13 22:25 编辑

/*
* 汉诺塔问题是递归的一个经典问题。他很好地展示的递归的精髓！将一个复杂的问题简单化，关键要找出
* 求解这个问题，要先解决什么问题！先拿一个简单的阶乘来说：要求n!要得要求出(n-1)!然后乘以n;
*
* 假设有A、B、C三个柱子，要将A柱子上的圆盘放到C柱上，其中B柱子为中转。
*
* 汉诺塔问题也是这个原理，找出问题的精髓：
* 1、要解决 n层的汉诺塔，首先要解决n-1层的汉诺塔。先假设将上面
*             的n-1层已经按从小到大放到B柱子上，第n个还在A柱子上。
* 2、将A柱上的第n层放到C柱子上。
* 3、将B柱上的n-1层全部放到C柱子上。
*
*/

public class Hannuota

{
      private static int sum = 0;
      public void hannuo(int n, String a, String b, String c)// a----->c,b为中转

      {
            if (n == 1)// 一层塔
            {
                     move(1, a, c);// 直接a----->c
            } else
            {
                     hannuo(n - 1, a, c, b); // a--->b 先把上面n-1个搬到b
                     move(n, a, c); // a--->c 再把最下面的一个搬到c 输出一条移动语句
                     hannuo(n - 1, b, a, c); // b--->c 再把b上面的n-1个搬到c
            }
      }

      public static void move(int n, String a, String b)

      {
            System.out.println("第" + n + "层：" + a + "---->" + b);
            sum++;
      }

      public static void main(String args[])

      {
            new Hannuota().hannuo(Integer.parseInt(args[0]), "柱1", "中转", "柱2");
            System.out.println("共移动了" + sum + "次。");
      }
}

输入参数:3 (表示从小到大，一共有三个盘子叠在一起)
输出结果：
第1层：柱1---->柱2
第2层：柱1---->中转
第1层：柱2---->中转
第3层：柱1---->柱2
第1层：中转---->柱1
第2层：中转---->柱2
第1层：柱1---->柱2
共移动了7次。

刘俊佳 · 刘俊佳

用C实现的代码如下：
void Move(char sour, char dest){
printf("\nMove the top plate of %c to %c",sour, dest);
}
Hanoi(int n, char A, char B, char C)
{
if(n==1) /*盘子数量为1，打印结果后，不再继续进行递归*/
Move(A,C);
else/*盘子数量大于1，继续进行递归过程*/
{
Hanoi(n-1,chA,chC,chB);
Movech(A,chC);
Hanoi(n-1,chB,chA,chC);
}
}
main()
{
int n;
printf("\n:请输入盘子的个数: ");
scanf("%d",&n);
printf("\n移动 %d 盘子从A到C:",n);

Hanoi(n,'A','B','C');
}

彭超华 · 彭超华

package Test_02;

/*
* 首先,假设只有一个圆盘,那么很好办,直接将圆盘从x移动到y就可以了.但是如果不止一个盘子呢?

*假设有n个圆盘,解决问题的最后一步应该是,将第n个盘从x移动到y,然后将在z上的其他n-1个圆盘移动到y.那么在这一步之前就是将n-1个盘从x移动到z然后将前面的(n-1)-1个盘从y移动到z.
*在移动时,总是将最大的一个从x移动到y或者是z,而将之前的从y或z上移动到x,那么怎么来确定最大的盘到底是从x移动到y还是z呢?

*如果y上面已经放了一个按顺序放置的序列,而z为空时,就应该将盘子放在z上,反之,z上有这样的序列就放在y上.

*那么这个递归到什么时候结束呢?那就是x上只剩下最后一个盘子了,那么就直接把盘子移动到y.

*/

public class hannosiTest {

public static void main(String[] args) {
move(3, "a", "b", "c");

}

public static void move(int n, String x, String y, String z) {
// x上只剩下最后一个盘子,退出递归
if (n == 1) {
System.out.println("盘子" + n + "从" + x + "到" + y);
} else {

move(n - 1, x, z, y);
System.out.println("盘子" + n + "从" + x + "到" + y);
move(n - 1, z, y, x);
}

}

}

许瑞航老师 · 许瑞航老师

class HanRuoTa {
static long s=0;
public static void main(String args[]) {

int n =3;
System.out.println("汉诺塔层数为" + n);
System.out.println("移动方案为：" );
hanoi(n, 'a', 'b', 'c');
System.out.println("需要移动次数："+s);

}

static void hanoi(int n, char a, char b, char c) {

if (n > 0) {

hanoi(n - 1, a, c, b);
move(a, b);
hanoi(n - 1, c, b, a);
s++;

}
}

static void move(char x, char y) {

System.out.println(x + "->" + y + "\t");

}
}

温少邦 · 温少邦

public class Hanoi{
private static char[] ch=new char[]{'A','B','C'};
public static void move(int i,int src,int des){ //i号盘子，从src座，到des座
int another=des+1>2?0:des+1; //算出另一座
if(another==src)
another=another+1>2?0:another+1;
if(i==0)
System.out.println(i+"号盘子从"+ch[src]+"座到"+ch[des]+"座");
else{
move(i-1,src,another); //先把i号上面的全挪到另一座
System.out.println(i+"号盘子从"+ch[src]+"座到"+ch[des]+"座"); //再把i号从src挪到des
move(i-1,another,des); //再把i号上面的从另一座挪到des
}
}
public Hanoi(int i){
move(i,0,2);
}
public static void main(String[] args){
new Hanoi(3);
}
}

复制代码

李金龙 · 李金龙

public class Hanoi{
private static final String DISK_B="diskB";
private static final String DISK_C="diskC";
private static final String DISK_A="diskA";
static String from=DISK_A;
static String to=DISK_C;
static String mid=DISK_B;.
public static void main(String[]args){
String input=JOptionPane.showInputDialog("请输入盘子的个数");
int num=Integer.parseInt(input);
move(num,from,mid,to);
}
private static void move(int num,String from2,String mid2,String to2){
if(num==1){ //当num是1的时候，跳出递归。
System.out.println("move disk 1 from"+from2+"to"+to2);
}
else{ //当num不是1时，是n，则我们先挪动上面n-1块disk,等
//上面挪完，即递归返回的时候，我们挪动最底下的disk
move(num-1,from2,to2,mid2);
System.out.println("move disk"+num+"from"+from2+"to+to2);
move(num-1,mid2,from2,to2);
}
}

李思静 · 李思静

public class TowerOfHanoi{
public static void main(String args[]){
int dishes;
try{
dishes=System.in.readInt(); //输入盘子数目
}catch(Exception e);
hanoi("A","B","C",dishes); //调用hanoi()方法显示移动盘子的过程
}
private static void hanoi(String start,String temp,String goal,int dishes){
if(dishes==0)
return; //初始情况，直接返回
hanoi(start,goal,temp,dishes-1)
//递归调用hanoi()方法，将(dishes-1)个盘子从最左边移到中间
System.out.println("Move disk from "+start+" to "+goal):
//将最底层的盘子移至最右边，并将此操作打印出来
hanoi(temp,start,goal,dishes-1);
//递归调用hanoi()方法，将(dishes-1)个盘子从中间移至最右边
}
}

复制代码

周恺 · 周恺

class HanoiTest
{
public static void main(String args[])
{
   int n=2;
   String a="A盘";
   String b="B盘";
   String c="C盘";
hanoi(n,a,b,c);
}
public static void hanoi(int n,String a,String b,String c)
{
if (n==1)
{
System.out.println("将第"+n+"个盘子从"+a+"移动到"+c);
}
else
{
hanoi(n-1,a,c,b);
System.out.println("将第"+n+"个盘子从"+a+"移动到"+c);
hanoi(n-1,b,a,c);
}
}
}

王宝康 · 王宝康

递归问题，先从简单的情况入手：假设A、B、C三个柱子，A柱有两个盘子，从下到上（从大到小）依次为盘子1，2，要从A移动到B，C为辅助柱子，移动开始：
1、盘子2移动到C  A--C
2、盘子1移动到B  A--B
3、盘子2移动到B  C--B
结论：可以借助第三根柱子把两个盘子从A柱移动到B柱。
三个盘子时，先只看上面的两个盘子，可以借助第三根柱子把上面的两个盘子移动到C柱，剩下的那个盘子移动到B柱，此时把B柱和盘子1看为一个整体，运用上面的结论，可以借助第三根柱子把剩下的两个盘子移动到A柱或者B柱。
结论：可以借助第三根柱子把三个盘子从A柱移动到B柱。
可以借助第三根柱子把n个盘子从A柱移动到B柱，会先将n-1个盘子移动到C柱，然后再把盘子1移动到柱B，然后再移动这n-1个盘子

package iterator;
/*
* 演示汉诺塔的移动操作
* 其中有A,B,C三个柱子，A柱有三个盘子，先要把盘子从A柱子移动到B柱子，C柱子为辅助柱子
* */
class Hanoi {
public static void main(String args[]) {
hanoi(3, 'a', 'b', 'c');
}
public static void hanoi(int n, char a, char b, char c) {
if (n > 0) {
hanoi(n - 1, a, c, b);
sop("从"+a+"移动到"+b);
hanoi(n - 1, c, b, a);
}
}
public static void sop(Object obj) {
System.out.println(obj);
}
}

复制代码

其实感觉说那么多还是直接代码比较明了！

侯茂绵 · 侯茂绵

public class Test06 {
public static String x = "柱1";
public static String y = "柱2";
public static String z = "柱3";
public Test06() {
}
public void Test06(int n, String x, String y, String z) {
if (n == 1)       //假如只有1个棋子，那么将棋子直接从x移到z
move(x, 1, z);    // 移动操纵move（x,n,z）可定义为将编号为n的柱子从x移动到z
else {
               //有多于1个的n个棋子　　　/*首先，将上面n-1个棋子按照汉诺塔规则从x移到y
               //然后，将最下面一个，也就是第n个棋子从x移到z

Test06(n - 1, x, z, y);
move(x, n, z);       //最后，将现在位于y柱子上的n-1个棋子按照汉诺塔规则从y移到z
Test06(n - 1, y, x, z);
}
}
public static void main(String[] args) {
Test06 game = new Test06();
game.Test06(5, x, y, z);
}
public void move(String x, int n, String z) {
System.out.println("将编号为" + n + "的棋子从" + x + "移到" + z);
}
}
自己运行下

程潇 · 程潇

本帖最后由 jeffreyno1 于 2012-7-16 00:19 编辑

public class HanoiTowers {
public static void main(String args[]){
      HanoiTowers hanoi = new HanoiTowers();
      hanoi.move(64, 'A', 'B', 'C');
}

public void move(int n, char a, char b, char c) {
      if(n == 1)
         System.out.println("plate " + n + " from " + a + " to " + c); //如果只有1个盘子，直接将盘子从A移到C
      else {
         move(n - 1, a, c, b); //如果大于1个盘子（共n个盘子），通过递归，以B为中转，先将最上面的n-1个盘子从A移到B
         System.out.println("plate " + n + " from " + a + " to " + c); //再将A上最下面的那个盘子，直接从A移到C
         move(n - 1, b, a, c);  //最后还是通过递归，将B上的n-1个盘子移动到C
      }
}
}

黄昆 · 黄昆

package cn.itcast.day1;

class HanoiTest
{
public static void main(String args[])
      {
               int n=2;
            String a="A盘";
            String b="B盘";
            String c="C盘";
            hanoi(64,a,b,c);
      }
      public static void hanoi(int n,String a,String b,String c)
      {
            if (n==1)//最后一步是将第一个盘子从A盘移到C盘
            {
                     System.out.println("将第1个盘子从"+a+"移动到"+c);
            }
            else
            {
                     hanoi(n-1,a,c,b);//递归调用hanoi()方法，将(n-1)个盘子从A盘移到B盘
                     System.out.println("将第"+n+"个盘子从"+a+"移动到"+c);
                     hanoi(n-1,b,a,c);//递归调用hanoi()方法，将(n-1)个盘子从B盘移到C盘
            }
      }
}

滔哥 · 滔哥

韦念欣发表于 2012-7-13 19:04
嘿嘿，这道题对于上过算法的同学来说，还是相对简单的。

你们加分放松点吧，很多新手有难度

帐号		自动登录	找回密码
密码			加入黑马

汉诺塔，递归的典型例子，自己认真做，做出来加分了。...

27 个回复

点评

点评

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

黑马骑士勋章