精华内容
下载资源
问答
  • hanoi塔

    2017-09-15 14:20:07
    Hanoi塔思路简述+代码
    最近复习数据结构,看到了以前的一道期中考试题,hanoi塔问题。简述思路:

    假设有3个柱子a,b,c。同时只有3个盘子1、2、3,在柱子a上,现在想把盘子全部转移到柱子c上。(第一次发博客,不会排版)

    方法:一、把盘子1从柱子a放到柱子c上
               二、把盘子2从柱子a放到柱子b上
               三、把盘子1从柱子c放到柱子b上
               四、把盘子3从柱子1放到柱子c上
               五、把盘子1从柱子b放到柱子a上
               六、把盘子2从柱子b放到柱子c上
               七、把盘子1从柱子a放到柱子c上

    简化之后:一、把盘子1和2从柱子a放到柱子b上
                      二、把盘子3从柱子1放到柱子c上
                      三、把盘子1和2从柱子b放到柱子c上

    至此全部转移完成。

    (假设有n个盘子)思路:还是用递归的方法

    一、把n-1个盘子从柱子a移到柱子b上
    二、把第n个盘子从柱子a移到柱子
    三、把n-1个盘子从柱子b移到柱子c上
    n=0时结束代码
    public class MoveHanoi {
    	public static void main(String[] args) {
    		move('a', 'b', 'c', 3);  
    		
    	}
    	
    	
    	public static void move(char a, char b, char c, int n) {  
    		  if(n == 0) {
    			  return;
    		  }    
    		  move(a, c, b, n-1);  
    		  System.out.println("把盘子"+n+"从柱子"+a+"移到柱子"+c+"上");
    		  move(b, a, c, n-1);  
    	}  
    		    
    
    }

    结果:
    展开全文
  • Hanoi塔

    2019-03-05 08:39:00
    Hanoi塔问题是源于印度一个古老传说的益智玩具。设a,b,c是三个塔座,开始时,在塔座a上有一叠共n个圆盘,这些圆盘自上而下,由大到小叠在一起,各圆盘的编号为1,2,3,...,n。现要求将塔座a上的这一叠圆盘移动到塔座...

    Hanoi塔问题是源于印度一个古老传说的益智玩具。设a,b,c是三个塔座,开始时,在塔座a上有一叠共n个圆盘,这些圆盘自上而下,由大到小叠在一起,各圆盘的编号为1,2,3,...,n。现要求将塔座a上的这一叠圆盘移动到塔座b上,并仍按从到到小的顺序叠置。再移动圆盘时应该遵守以下移动规则:

    规则一:每次只能移动一个圆盘。

    规则二:不允许将较大的圆盘压在较小的圆盘上面。

    规则三:在满足规则一、规则二的情况下,可将圆盘移动到啊a,b,c中任一塔座上。

    如图为一Hanoi塔问题的移动步骤:

    a

    圆盘总数为n,当n=1时,只要将编号为1的圆盘从塔座a直接移动到塔座b。当n>1时,需要利用塔座c作为辅助,将n-1个较小的圆盘依照移动规则从塔座a移动至塔座c,然后将最大的圆盘从塔座a移动至塔座b,再将n-1个圆盘从塔座c移动至塔座b,T(n)=2^(n-1)-1。由于n-1个圆盘以同样的方式移动了两次,可以利用递归方法来解决。这个就是典型的Hanoi塔递归问题。

     public static void hanoi(int n,int a,int b,int c){
            if(n>0){
                hanoi(n-1,a,c,b);
                move(a,b);
                hanoi(n-1,c,b,a);
            }
        }

     

    如果将三个塔座a,b,c改为四个塔座a,b,c,d,利用分治法则和归纳法分成两个小规模问题。

    T(n)来表示最小步数,可以知道T(1)=1,T(2)=3,当n>=3时,假设已经输出T(1),T(2),…,T(n-1),则T(n)可以这样计算:

    for i=1;i<n;i++

    一:先从塔座a移动i个圆盘到塔座d(b,c),塔座b,c作为辅助,移动步数为T(i)。

    二:剩下的n-i个圆盘只可以在三个塔座之间移动,利用Hanoi函数将其由塔座a移动至塔座,塔座c作为辅助,移动步数为T(n-i)=2^(n-i)-1。

    三:再将塔座d中的i个圆盘移动至塔座b,塔座c,a作为辅助(与步一移动方式相同)移动步数为T(i)。

    public class Han {
    
        //创建一个静态数组用于存储移动的圆盘的最小步数
        static int[] a=new int [65];
    
        //创建一个静态数组用于存储先移动的圆盘的个数
        static int[] s=new int [65];
    
        public static void step() {
            a[0] = 0;
            a[1] = 1;
            a[2] = 3;
    
            //先移动圆盘个数的循环
            for (int n = 3; n <= 64; n++) {
                double min = 200000;
                double temp = 0;
                int temp2 = 0;
    
                //一个一个移动计算步数和圆盘个数
                for (int i = 1; i < n; i++) {
                    temp = 2 * a[i] + Math.pow(2, n - i) - 1;
                    if (temp < min) {
                        min = temp;//计算出移动总步数并赋值
                        temp2 = i;//计算出先移动圆盘数并赋值
                    }
                    a[n] = (int) temp;
                    s[n] = temp2;
                }
            }
        }

     

    public static void hanoi4(int n,int a,int b,int c,int d,int []s){
            if(n>=3){
                hanoi4(s[n],a,b,c,d,s);
                hanoi(n-s[n],a,c,b);
                hanoi4(s[n],d,a,b,c,s);
            }else{
                if(n==1){
                    move(a,b);
                }
                if(n==2){
                    hanoi(2,a,c,b);
                }
            }
        }

     

    示例:

    Hanoi塔问题中如果塔的个数变为a,b,c,d四个,现要将n个圆盘从a全部移动到d移动规则不变,编写移动步数最小的方案和具体的移动过程(只考虑n<=64),并演示当n=9时的情形。

    package jihe;
    
    /**
     * author Gsan
     */
    public class Han {
    
        //创建一个静态数组用于存储移动的圆盘的最小步数
        static int[] a=new int [65];
    
        //创建一个静态数组用于存储先移动的圆盘的个数
        static int[] s=new int [65];
    
        public static void step() {
            a[0] = 0;
            a[1] = 1;
            a[2] = 3;
    
            //先移动圆盘个数的循环
            for (int n = 3; n <= 64; n++) {
                double min = 200000;
                double temp = 0;
                int temp2 = 0;
    
                //一个一个移动计算步数和圆盘个数
                for (int i = 1; i < n; i++) {
                    temp = 2 * a[i] + Math.pow(2, n - i) - 1;
                    if (temp < min) {
                        min = temp;//计算出移动总步数并赋值
                        temp2 = i;//计算出先移动圆盘数并赋值
                    }
                    a[n] = (int) temp;
                    s[n] = temp2;
                }
            }
        }
    
        public static void hanoi(int n,int a,int b,int c){
            if(n>0){
                hanoi(n-1,a,c,b);
                move(a,b);
                hanoi(n-1,c,b,a);
            }
        }
    
        public static void move(int a,int b){
            System.out.println("move"+a+"to"+b);
        }
    
        public static void hanoi4(int n,int a,int b,int c,int d,int []s){
            if(n>=3){
                hanoi4(s[n],a,b,c,d,s);
                hanoi(n-s[n],a,c,b);
                hanoi4(s[n],d,a,b,c,s);
            }else{
                if(n==1){
                    move(a,b);
                }
                if(n==2){
                    hanoi(2,a,c,b);
                }
            }
        }
    
        public static void main(String[] args) {
    
            int n=9;
            step();
            hanoi4(n,1,2,3,4,s);
    
            System.out.println("9个圆盘移动的最小步数为:"+a[n]);
        }
    
    }

    运行结果:

     

    转载于:https://www.cnblogs.com/Gsan/p/10474366.html

    展开全文
  • hanoi塔问题.dochanoi塔问题.doc
  • hanoi

    2015-03-05 20:08:45
    n个盘子,移动次数是pow(2,n)-1;f(n)=f(n-1)*2+1; void hanoi(int n,char x,char y,char z) { if(n==1) { cout; return; }

    n个盘子,移动次数是pow(2,n)-1;f(n)=f(n-1)*2+1;

    void hanoi(int n,char x,char y,char z)
    {
        if(n==1)
            {
                cout<<"move disk "<<n<<"from"<<x<<"to"<<z<<endl;
                return;
            }
    
    
    
            hanoi(n-1,x,z,y);
           cout<<"move disk "<<n<<"from"<<x<<"to"<<z<<endl;
           hanoi(n-1,y,x,z);
    
    
    }
    


    展开全文
  • 今天,在学习C#的时候,遇到了一个很有意思很经典的问题--Hanoi塔(汉诺塔)问题。于是就研究了一下子,现在小小的总结一下。(1)问题的描述古代有一个梵塔,塔内有3个座,分别用A、B、C表示。开始时A座有N个盘子,盘子...

    今天,在学习C#的时候,遇到了一个很有意思很经典的问题--Hanoi塔(汉诺塔)问题。于是就研究了一下子,现在小小的总结一下。

    (1)问题的描述

    古代有一个梵塔,塔内有3个座,分别用A、B、C表示。开始时A座有N个盘子,盘子两两大小不等,大的在下,小的在上,盘子编号从上到下分别编号为1到N。B座,C座上面没有盘子。要求将这N个盘子从A移到C上,且在移动的过程中大盘不能压在小盘上。移动过程可以借助B盘中转。

    (2)问题的分析

    这是一个典型的递归问题,将A转移到C,可以分为下面的这些步骤:

    1.如果N=1,那么只需要将盘子从A移到C即可。所以,N=1也是递归终止条件。

    2.如果N>1,那么将N-1个盘子从A移到B,利用C做中转。再将第N个盘子从A移到C。

    3.接下来,就变成了一个N-1个盘子从B移到C的,A为中转的汉诺塔问题了,就可以直接递归了。

    (3)问题的实现

    那么,在实现的时候,我用了以前学习的Java和最近正在学习的C#语言来实现它,其实两种语言差不多,在实现这个问题的具体算法上,没有很大的不同。

    1.C#版本实现

    using System;

    using System.Collections.Generic;

    using System.Linq;

    using System.Text;

    using System.Threading.Tasks;

    namespace Hanoi

    {

    class Program

    {

    //总共搬动盘子的次数

    static int count = 0;

    /*

    *程序入口

    */

    static void Main(string[] args)

    {

    Console.Write("请输入Hanoi塔问题的盘子数目:");

    int n = int.Parse(Console.ReadLine());

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

    Console.WriteLine("移动结束,一共进行了{0}次移动",count);

    Console.ReadLine();

    }

    /*

    *输出一个移动步骤的方法

    */

    public static void PrintMove(char x, char y)

    {

    Console.WriteLine("{0}-->{1}", x, y);

    }

    /*

    Hanoi塔递归方法,n是盘子数,one,two,three是3个座

    */

    public static void Hanoi(int n,char one,char two,char three) {

    if (n == 1)

    {

    ++count;

    PrintMove(one, three);

    return;

    }

    else {

    ++count;

    //把N-1个盘子拿到中转座

    Hanoi(n-1,one,three,two);

    //将第N个盘子移到目标座

    PrintMove(one,three);

    //把中转座上的N-1个盘子移到目标座

    Hanoi(n-1,two,one,three);

    }

    }

    }

    }

    运行结果:

    101518174.jpg

    1.Java版本实现

    import java.util.Scanner;

    /**

    * 汉诺塔问题

    * xiangpin

    */

    public class Hanoi {

    //计算搬动盘数目

    public static int count=0;

    /**

    * 程序入口

    * @param args

    */

    public static void main(String[] args) {

    //从键盘读取数据

    System.out.println("请输入汉诺塔问题的盘子数目:");

    Scanner scan=new Scanner(System.in);

    int n=scan.nextInt();

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

    System.out.println("移动结束,一共移动了"+count+"次");

    }

    /**

    * 输出移动步骤的方法

    */

    public static void PrintMove(char x,char y){

    System.out.println("从"+x+"移动到"+y);

    }

    /**

    * 汉诺塔的递归方法,n是盘子数,one,two,three是3个座

    */

    public static void Hanoi(int n ,char A,char B,char C){

    //如果N=1,则直接从A搬到C

    if(n==1){

    ++count;

    PrintMove(A,C);

    }

    else{

    ++count;

    //如果n>1,则将n-1个盘子,从A搬到B,C作为中转

    Hanoi(n-1,A,C,B);

    //再将第n个盘子搬到C

    PrintMove(A,C);

    //现在问题变成n-1个盘子,从B到C,A为中转的问题了,运用递归

    Hanoi(n-1,B,A,C);

    }

    }

    }

    运行结果:

    101518175.jpg

    通过这个例子可以很容易的看出来,利用递归可以很快速且有效的得出结果。另外,我觉得将一种自己较为熟悉的语言和另外一种新学的结合起来学习,是一件很有趣的事情。

    展开全文
  • 1.2 Hanoi塔问题

    2020-09-19 16:17:24
    1.2 Hanoi塔问题问题描述分析代码 问题描述       Hanoi塔问题由3个竖立着的塔座和一组中间有孔的圆盘组成,圆盘中间有个孔以便沿塔座柱移动叠放,每个圆盘有不同的直径。Hanoi塔的...
  • hanoi塔问题解析(一) c++实现

    万次阅读 多人点赞 2016-10-14 19:10:39
    什么是hanoi塔? 汉诺塔问题:古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,...
  • hanoi塔问题

    2014-08-03 10:45:07
    hanoi塔问题
  • hanoi塔改进.rar

    2011-04-01 14:53:02
    hanoi塔改进.rar hanoi塔改进.rar
  • Hanoi塔问题

    2020-10-26 21:03:54
    对于有n个圆盘的Hanoi塔(从上至下编号为1~n), A塔===B塔===C塔 递推式: n = 1时只需将编号为1的圆盘直接从A塔移动到C塔 n > 1时,分为三个阶段 1.将A塔上的n-1个圆盘按照规定移动到B塔 2.将编号为n的圆盘由A...
  • Hanoi塔题解

    2020-02-23 09:53:36
    Hanoi塔 题目描述 问题的提出:Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图所示。 要求把a柱上n个圆盘按下述规则移到c柱上: 规则: (1)、一次只能移一个圆盘...
  • hanoi塔 java 图形 演示程序 hanoi塔 java 图形 演示程序 hanoi塔 java 图形 演示程序 hanoi塔 java 图形 演示程序
  • hanoi塔c语言

    2021-01-01 21:13:17
    hanoi塔描述: 有三根柱子,64个直径不等的空心碟子套在第一根柱子上,下面的碟子都比上面的碟子大。传说一些和尚要把这些碟子从第一根柱子移到第三根柱子,移动时必须遵循以下规则: (1)一次只能移动一个碟子 (2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,748
精华内容 4,299
关键字:

hanoi塔