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

汉诺（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。

陈少文 · 陈少文

import javax.swing.JOptionPane;

/*
递归原理：调用自身实现递归

移动次数f(n)
f(1)=1;
f(2)=3;
f(3)=7;
==>f(k+1)=2*f(k)+1;
==>f(n) = 2^n-1;
*/
public class Hanoi
{
      private static final String b = "diskB";
      private static final String c = "diskC";
      private static final String a = "diskA";
      static String from=a;
      static String to=c;
      static String mid=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
            {
                     //调用自身方法
                     move(num-1,from2,to2,mid2);
                     System.out.println("move disk "+num+" from "+from2+" to "+to2);
                     move(num-1,mid2,from2,to2);

            }
      }

}

陈世涛 · 陈世涛

public class Hanoi {

      static void hanoi(int n, String startpeg, String middlepeg, String endpeg) {
            if (n == 1)
                     System.out.println( "move " + startpeg + " to " + endpeg);
            else {
                     hanoi(n - 1, startpeg, endpeg, middlepeg);
                     System.out.println( "move " + startpeg + " to " + endpeg);
                     hanoi(n - 1, middlepeg, startpeg, endpeg);
            }
      }

      public static void main(String[] args) {
            int n = 3;
            String startpeg = "start ";
            String middlepeg = "middle ";
            String endpeg = "end ";
            System.out.println( "The solution for n = " + n);

            hanoi(n, startpeg, middlepeg, endpeg);
      }
}

高欢欢 · 高欢欢

import java.io.*;

public class Hanoi {
public static void main(String args[]) throws IOException {
      int n;
      BufferedReader buf;
      buf = new BufferedReader(new InputStreamReader(System.in));

      System.out.print("请输入盘数：");
      n = Integer.parseInt(buf.readLine());

      Hanoi hanoi = new Hanoi();
      hanoi.move(n, 'A', 'B', 'C');
}

public void move(int n, char a, char b, char c) {
      if(n == 1)
         System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
      else {
         move(n - 1, a, c, b);
         System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
         move(n - 1, b, a, c);
      }
}
}

想法不难！

马林康 · 马林康

public class Hanio {
public static void main(String[] args){
int i=3;
char a ='A',b='B',c='C';
hanio(i,a,b,c);
}
public static void hanio(int n,char a,char b,char c){
if(n==1)
System.out.println("移动"+n+"号盘子从"+a+"到"+c);
else{
hanio(n-1,a,c,b);//把上面n-1个盘子从a借助b搬到c
System.out.println("移动"+n+"号盘子从"+a+"到"+c);//紧接着直接把n搬动c
hanio(n-1,b,a,c);//再把b上的n-1个盘子借助a搬到c
}
}
}

复制代码

我也来写一个

薄炳鑫 · 薄炳鑫

public class Hnt
{

/**
* @param args
*/
public static void main(String[] args)
{

// TODO Auto-generated method stub
new Hnt().hanoi(4, "a", "b", "c");

}

// num是盘子个数，A是起始柱子，B是目标柱子，C是临时柱子
//用四个盘子进行解释的。
private void hanoi(int num, String A, String B, String C)
{

if (num > 0)
{
hanoi(num - 1, A, C, B);//将上面三个放到目标柱子上
System.out.println(A + "---->" + B);//将最下面一下移动到目标柱子
hanoi(num - 1, C, B, A);//将临时柱子的三个移动的目标柱子上
}
}

}

韩伟 · 韩伟

这么多人都写出来了，那我也要试试,下面是我的程序：
class HanoiTower {
      public static void mover(int n,char a,char b,char c)
      {
               if(n ==1)
         {
                     System.out.println("把"+1 + "号盘子从" + a + "移到" + c);
               }
      else
      {
                     mover(n-1, a, c, b);
                     System.out.println("把"+n + "号盘子从" + a + "移到" + c);
                     mover(n-1, b, a, c);
               }
      }

   public static void main(String[] args)
   {

            int num = 10;
            mover(num, 'A', 'B', 'C');

      }
}
结果太长，就不在这里显示图片了。

黑马刘涛 · 黑马刘涛

本帖最后由黑马刘涛于 2012-7-16 18:07 编辑

class HanoiDemo
{
public static void main(String[] args)
{
Hanoi h = new Hanoi();
h.hanoi(5,'A','B','C');
}
}
class Hanoi
{
private static int count = 0;//计数器
//将塔座a上按直径由小到大且自上而下编号为1到n的n个
//圆盘搬到塔座c上，b可用于辅助塔座
public void hanoi(int n,char a,char b,char c)
{
if(n == 1)
move(a,1,c);//将编号为1的圆盘从塔座a搬到塔座c上
else
{
//将塔座a上编号为1到n-1的圆盘搬到塔座b,c作为辅助塔
hanoi(n-1,a,c,b);
//将塔座a上编号为n的圆盘搬到塔座c上
move(a,n,c);
//将塔座b上编号为1到n-1的圆盘搬到塔座c上，a作为辅助塔
hanoi(n-1,b,a,c);
}
}
//搬动操作
public void move(char a,int n,char c)
{
System.out.println("第"+(count++)+"次搬运："+"将塔座"+a+"上的圆盘"+n+"搬到塔座"+c);
}
}

复制代码

数据结构课程中关于栈降到的递归问题

黄丽慧 · 黄丽慧

本帖最后由黄丽慧于 2012-7-16 17:48 编辑

package com.lianxi;
import java.util.*;
public class Hanoi {

      /**
      * @huanglihui
      需求：假设A塔上有64个盘子，要挪到C塔上，B为辅助塔，要求每次只能挪一个，
      而且小盘只能在大盘上面。
      分析：盘子数          步骤
               1    A--C
               2    A--B,A--C,B--C
               3    A--C,A--B,C--B,A--C,B--A,B--C,A--C
               ......
               从上面可以看出来，三个盘子时，需要把上面两个盘子移动到B塔，此时，B塔变成目标塔，
               而C塔变成辅助塔。
            定义一个函数move(int num,String orig,String dest,String help) ,接受的参数为四个--盘子数，原始塔，目标体，辅助塔，每个移动盘子的
            步骤由打印表示。
            如果只有一个盘子，则直接打印；
         如果不止一个盘子，则调用递归函数  move(num-1,orig,help,dest); --此时需要把第N个盘子上面的N-1个盘子全部移到辅助塔上，辅助塔就变成了目标塔，而目标塔变成辅助塔。把第N个盘子移动到目标塔之后，N-1个盘子全部在辅助塔上面，就可以调用递归函数 move(num-1,help,dest,orig)--此时因为盘子全在辅助塔上，所以辅助塔就变成了原始塔，而原始塔空下来就变成辅助塔了。
      */
      public static void main(String[] args) {
            System.out.println("请输入要移动的盘子数：");
            Scanner s=new Scanner(System.in);
            int num=s.nextInt();
            move(num,"A","C","B");

      }
      public static void move(int num,String orig,String dest,String help)
      {
            if(num==1)
                     System.out.println("第1盘子"+"从"+orig+"移动到"+help);
            else
            {
                     move(num-1,orig,help,dest);
                     System.out.println("第"+num+"盘子"+"从"+orig+"移动到"+dest);
                     move(num-1,help,dest,orig);
            }

      }

}
运行的结果为：

请输入要移动的盘子数：
3
第1盘子从A移动到C
第2盘子从A移动到B
第1盘子从C移动到B
第3盘子从A移动到C
第1盘子从B移动到A
第2盘子从B移动到C
第1盘子从A移动到C

滔哥 · 滔哥

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

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

黄昆 · 黄昆

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盘
            }
      }
}

程潇 · 程潇

本帖最后由 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
      }
}
}

侯茂绵 · 侯茂绵

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);
}
}
自己运行下

王宝康 · 王宝康

递归问题，先从简单的情况入手：假设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);
}
}

复制代码

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

周恺 · 周恺

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);
}
}
}

李思静 · 李思静

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)个盘子从中间移至最右边
}
}

复制代码

李金龙 · 李金龙

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 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);
}
}

复制代码

许瑞航老师 · 许瑞航老师

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");

}
}

彭超华 · 彭超华

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);
}

}

}

刘俊佳 · 刘俊佳

用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');
}

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

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

27 个回复

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

黑马骑士勋章