汉诺塔算法

article/2025/9/18 1:44:02

2019独角兽企业重金招聘Python工程师标准>>> hot3.png

 

 

有A、B和C 3跟柱子，在A上从下往上按照从小到大的顺序放着64个圆盘，以B为中介，把盘子全部移动到C上。移动过程中，要求任意盘子的下面要么没有盘子，要么只能有比它大的盘子。

 

 * 思想：采用递归的方法来接

 *      1. 先将A上面的n-1个盘子，移到B柱上

 *      2. 然后把A上最大的一个盘子放到C上去

 *      3. 然后把B上面的n-1个盘子移到A上去

 *

 * 步骤：

 *      汉若塔用递归思考首先考虑一种临界状态,把n-1个上面的盘从A—B, 就是把n从A移动到C,最后把n-1个盘从B---C，

 *      （注意在考虑把n-1个盘从B---C的时候就出现递归调用，如果把A，B盘交换就又重复上面的流程了，最后到n = 1的时候就返回）

 *

 * 伪代码：

 *  public void run(int n, char a, char b, char c)

    {

        if(n==1)

        {

            move(n,a,c) //等于1的时候把盘从A移动到C

        }else

        {

            run(n-1,a,b,c);//递归调用把a上面的n-1个盘移动到B上，怎么表示移动？把柱子交换不就是移动了。

            move(n,a,c);

            run(n-1,b,a,c);//意图是把n-1个盘从B移动到A上。

        }

         

    }      

 *

package cglib;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Hashtable;  

 

public class StringNumber {
    public static void main(String args[]) throws Exception {
                int n;
                BufferedReader buf =
                         new BufferedReader(new InputStreamReader(System.in));
                System.out.print("请输入盘数：");
                n = Integer.parseInt(buf.readLine());
                StringNumber hanoi = new StringNumber();
                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);
                 }
             }
    
}
      


输出：

请输入盘数：5
盘 1 由 A 移至 C
盘 2 由 A 移至 B
盘 1 由 C 移至 B
盘 3 由 A 移至 C
盘 1 由 B 移至 A
盘 2 由 B 移至 C
盘 1 由 A 移至 C
盘 4 由 A 移至 B
盘 1 由 C 移至 B
盘 2 由 C 移至 A
盘 1 由 B 移至 A
盘 3 由 C 移至 B
盘 1 由 A 移至 C
盘 2 由 A 移至 B
盘 1 由 C 移至 B
盘 5 由 A 移至 C
盘 1 由 B 移至 A
盘 2 由 B 移至 C
盘 1 由 A 移至 C
盘 3 由 B 移至 A
盘 1 由 C 移至 B
盘 2 由 C 移至 A
盘 1 由 B 移至 A
盘 4 由 B 移至 C
盘 1 由 A 移至 C
盘 2 由 A 移至 B
盘 1 由 C 移至 B
盘 3 由 A 移至 C
盘 1 由 B 移至 A
盘 2 由 B 移至 C
盘 1 由 A 移至 C

 

 ①如果只能移动到相邻的  那么n个圆盘需要  
  f(n)=(3^n)-1 次
②如果不加上只能移动到相邻的限制的话     那么n个圆盘需要  

  f（n）=（2^n）-1次

  1. public class Hanoi {  
  2.   
  3.     /** 
  4.      * @count记录是第几次移动 
  5.      */  
  6.     private static int count = 0;  
  7.   
  8.     /** 
  9.      * @Describe_将塔座x上按直径大小自上而下编码为123...n个圆盘按规则一到塔座Z上_y做辅助塔座 
  10.      * @param n圆盘的格式 
  11.      * @param x起始圆盘的位置 
  12.      * @param y辅助塔座 
  13.      * @param z目标塔座 
  14.      */  
  15.     public static void hanoi(int n, char x, char y, char z) {  
  16.         if (n == 1) {  
  17.             move(x, 1, z);//  
  18.         } else {  
  19.             hanoi(n - 1, x, z, y);// 将前n-1个从x移动到y，z当辅助  
  20.             move(x, n, z);// 将变化为n的圆盘从x移动到z  
  21.             hanoi(n - 1, y, x, z);// 再将前n-1个圆盘从y移动到z，x当辅助  
  22.         }  
  23.     }  
  24.   
  25.     /** 
  26.      * @Describe_移动操作_将编号为n的圆盘从x移动到z 
  27.      * @param x 
  28.      * @param n 
  29.      * @param z 
  30.      */  
  31.     public static void move(char x, int n, char z) {  
  32.         System.out.println("第 " + (++count) + "次移动  ：" + n + "号圆盘，" + x + "-->"  
  33.                 + z);  
  34.     }  
  35.   
  36.     /** 
  37.      * @Describe_规则再次变化_再加上一个只能移动到相邻的限制条件 
  38.      * @param n 
  39.      * @param x 
  40.      * @param y 
  41.      * @param z 
  42.      */  
  43.     public static void hanoi2(int n, char x, char y, char z) {  
  44.         if (n == 1) {  
  45.             move(x, 1, y);//  
  46.             move(y, 1, z);//  
  47.         } else {  
  48.             hanoi2(n - 1, x, y, z);// 将前n-1个从x移动到z，y当辅助  
  49.             move(x, n, y);// 将变化为n的圆盘从x移动到y  
  50.             hanoi2(n - 1, z, y, x);// 再将前n-1个圆盘从z移动到x，y当辅助  
  51.             move(y, n, z);// 将变化为n的圆盘从y移动到z  
  52.             hanoi2(n - 1, x, y, z);// 将前n-1个从x移动到z，y当辅助  
  53.         }  
  54.     }  
  55.   
  56.     public static void main(String[] args) {  
  57. //      Hanoi.hanoi(4, 'x', 'y', 'z');//------可以移动到相邻的或者不相邻的  
  58. //      Hanoi.hanoi2(4, 'x', 'y', 'z');//-----只能移动到相邻的  
  59.     }  
  60. } 

用栈实现：

package cglib;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Stack;  

 

public class StringNumber {
     //塔  
    class Tower<E> {  
       //塔编号  
       private int number;  
       //塔名称  
       private String name;  
       //存放盘子的栈  
       private Stack<E> stack = new Stack<E>();  
         
       public Tower(int number,String name) {  
           this.number = number;  
           this.name = name;  
       }  
                
       public int getNumber() {  
           return number;  
       }  
   
       public String getName() {  
           return name;  
       }  
   
       public Stack<E> getStack() {  
           return stack;  
       }  
         
    }  
      
    //盘子  
    class Tray {  
       //盘子编号  
       private int number;  
       //盘子名称  
       private String name;  
         
       public Tray(int number,String name) {  
           this.number = number;  
           this.name = name;  
       }  
         
       public int getNumber() {  
           return number;  
       }  
         
       public String getName() {  
           return name;  
       }  
         
       public String toString() {  
           return name;  
       }  
    }  
      
    public <T> void hanoi(int num,Tower<T> from,Tower<T> middle,  
           Tower<T> to) {  
       if(num == 1) {  
           move(from,middle,to);  
       } else {  
           //将num-1个盘子从from塔上移到middle塔上  
           hanoi(num-1,from,to,middle);  
           //将第num个盘子移到to塔上  
           move(from,middle,to);  
           //将num-1个盘子从middle塔上移到to塔上  
           hanoi(num-1,middle,from,to);  
       }  
    }  
      
    private <E> void move(Tower<E> from,Tower<E> middle ,Tower<E> to) {  
       E tray = from.getStack().pop();  
       to.getStack().push(tray);  
       StringBuilder sb = new StringBuilder();  
       sb.append("=====================Hanoi.move()======================\n")  
       .append(" Move tray : ").append(((Tray)tray).getName())  
       .append(" from ").append(from.getName()).append(" to ")  
       .append(to.getName()).append("\n ")  
       .append(from.getName()).append(":").append(format(from)).append(",")  
       .append(middle.getName()).append(":").append(format(middle)).append(",")  
       .append(to.getName()).append(":").append(format(to));  
       System.out.println(sb.toString());  
    }  
    
    private <E> String format(Tower<E> tower) {  
       Iterator<E> i = tower.getStack().iterator();  
       if (! i.hasNext())  
           return "[]";  
       StringBuilder sb = new StringBuilder();  
       sb.append('[');  
       while(i.hasNext()) {  
           sb.append(i.next().toString()).append(",");  
       }  
       sb.replace(sb.length()-1, sb.length(), "]");  
       return sb.toString();  
    }  
 
    public static void main(String[] args) {  
        StringNumber hanoi = new StringNumber();  
       Tower<Tray> from = hanoi.new Tower<Tray>(1, "1号塔");  
       Tower<Tray> middle = hanoi.new Tower<Tray>(2, "2号塔");  
       Tower<Tray> to = hanoi.new Tower<Tray>(3, "3号塔");  
       int num = 4;  
       for (int i = num; i >0; i--) {  
           Tray tray = hanoi.new Tray(i,i+"号盘子");  
           from.getStack().push(tray);  
       }  
       hanoi.hanoi(num, from, middle, to);  
    }
    
}
      


输出：

=====================Hanoi.move()======================
 Move tray : 1号盘子 from 1号塔 to 2号塔
 1号塔:[4号盘子,3号盘子,2号盘子],3号塔:[],2号塔:[1号盘子]
=====================Hanoi.move()======================
 Move tray : 2号盘子 from 1号塔 to 3号塔
 1号塔:[4号盘子,3号盘子],2号塔:[1号盘子],3号塔:[2号盘子]
=====================Hanoi.move()======================
 Move tray : 1号盘子 from 2号塔 to 3号塔
 2号塔:[],1号塔:[4号盘子,3号盘子],3号塔:[2号盘子,1号盘子]
=====================Hanoi.move()======================
 Move tray : 3号盘子 from 1号塔 to 2号塔
 1号塔:[4号盘子],3号塔:[2号盘子,1号盘子],2号塔:[3号盘子]
=====================Hanoi.move()======================
 Move tray : 1号盘子 from 3号塔 to 1号塔
 3号塔:[2号盘子],2号塔:[3号盘子],1号塔:[4号盘子,1号盘子]
=====================Hanoi.move()======================
 Move tray : 2号盘子 from 3号塔 to 2号塔
 3号塔:[],1号塔:[4号盘子,1号盘子],2号塔:[3号盘子,2号盘子]
=====================Hanoi.move()======================
 Move tray : 1号盘子 from 1号塔 to 2号塔
 1号塔:[4号盘子],3号塔:[],2号塔:[3号盘子,2号盘子,1号盘子]
=====================Hanoi.move()======================
 Move tray : 4号盘子 from 1号塔 to 3号塔
 1号塔:[],2号塔:[3号盘子,2号盘子,1号盘子],3号塔:[4号盘子]
=====================Hanoi.move()======================
 Move tray : 1号盘子 from 2号塔 to 3号塔
 2号塔:[3号盘子,2号盘子],1号塔:[],3号塔:[4号盘子,1号盘子]
=====================Hanoi.move()======================
 Move tray : 2号盘子 from 2号塔 to 1号塔
 2号塔:[3号盘子],3号塔:[4号盘子,1号盘子],1号塔:[2号盘子]
=====================Hanoi.move()======================
 Move tray : 1号盘子 from 3号塔 to 1号塔
 3号塔:[4号盘子],2号塔:[3号盘子],1号塔:[2号盘子,1号盘子]
=====================Hanoi.move()======================
 Move tray : 3号盘子 from 2号塔 to 3号塔
 2号塔:[],1号塔:[2号盘子,1号盘子],3号塔:[4号盘子,3号盘子]
=====================Hanoi.move()======================
 Move tray : 1号盘子 from 1号塔 to 2号塔
 1号塔:[2号盘子],3号塔:[4号盘子,3号盘子],2号塔:[1号盘子]
=====================Hanoi.move()======================
 Move tray : 2号盘子 from 1号塔 to 3号塔
 1号塔:[],2号塔:[1号盘子],3号塔:[4号盘子,3号盘子,2号盘子]
=====================Hanoi.move()======================
 Move tray : 1号盘子 from 2号塔 to 3号塔
 2号塔:[],1号塔:[],3号塔:[4号盘子,3号盘子,2号盘子,1号盘子]

或者：

  1. import java.util.Stack;  
  2.   
  3. public class Demo {  
  4.   
  5.       public static void main(String[] args) {  
  6.              // TODO Auto-generated method stub  
  7.              int n=3;  
  8.              int disks=5;  
  9.             Tower[] towers= new Tower[ n];  
  10.              for( int i=0; i< n; i++){  
  11.                    towers[ i]= new Tower( i);  
  12.             }  
  13.               
  14.              for( int i= disks; i>=0; i--){  
  15.                    towers[0].add( i);  
  16.             }  
  17.              towers[0].moveDisks( disks, towers[2], towers[1]);  
  18.       }  
  19. }  
  20.   
  21. class Tower{  
  22.       public  Stack<Integer> disks;  
  23.       public int index;  
  24.         
  25.       public Tower(int index){  
  26.              disks= new Stack<Integer>();  
  27.              this. index= index;  
  28.       }  
  29.         
  30.       public int getIndex(){  
  31.              return this. index;  
  32.       }  
  33.         
  34.       public void add(int d){  
  35.              if(! disks.isEmpty()&& disks.peek()<= d)  
  36.                   System. out.println( "Error placing disk"+d);  
  37.              else  
  38.                    disks.push( d);  
  39.       }  
  40.         
  41.       //将orgin顶端的盘子移到destination  
  42.       public void movetoTop(Tower t){  
  43.              int top= disks.pop();  
  44.              t.add( top);  
  45.             System. out.println( "Move disk "+ top+ " from "+this.getIndex()+" to "+t.getIndex());  
  46.       }  
  47.         
  48.   
  49.       public void moveDisks( int n,Tower destination,Tower buffer){  
  50.              if( n>0){  
  51.                    //将顶端n-1个盘子从origin移到buffer  
  52.                   moveDisks( n-1, buffer, destination);  
  53.                    this.movetoTop( destination);  
  54.                    //将顶部n-1个盘子从buffer移到destination，将origin用作缓冲区  
  55.                    buffer.moveDisks( n-1, destination, this);  
  56.             }  
  57.       }  
  58. }

转载于:https://my.oschina.net/u/2822116/blog/789451


http://chatgpt.dhexx.cn/article/X2N6K1YN.shtml

相关文章

汉诺塔算法的理解

汉诺塔算法的理解

2019独角兽企业重金招聘Python工程师标准>>> 当盘子数为两个时&#xff0c;移动图如下&#xff1a; 移动规律为&#xff1a; 步骤盘子编号源柱子目标柱子11AB22AC31BC 当盘子数为3个时&#xff1a; 移动规律为&#xff1a; 步骤盘子编号源柱子目标柱子11AC22AB31CB4…
阅读更多...
汉诺塔递归算法

汉诺塔递归算法

2019独角兽企业重金招聘Python工程师标准>>> import java.util.Scanner;/*** 汉诺塔* * author JayChang* */ public class HanoiResolve {/*** 移动位置* * param positionA* param positionB*/public static void move(String positionA, String positionB) {Syst…
阅读更多...
数据结构——树和二叉树 6-1 求二叉树高度 (20 分)

数据结构——树和二叉树 6-1 求二叉树高度 (20 分)

本题要求给定二叉树的高度。 函数接口定义&#xff1a; int GetHeight( BinTree BT ); 其中BinTree结构定义如下&#xff1a; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ElementType Data;BinTree Left;BinTree Right; }; 要求函数返回给定…
阅读更多...
PTA 函数题 求二叉树高度（C语言）

PTA 函数题 求二叉树高度（C语言）

本题要求给定二叉树的高度。 函数接口定义&#xff1a; int GetHeight( BinTree BT ); 其中BinTree结构定义如下&#xff1a; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ElementType Data;BinTree Left;BinTree Right; }; 要求函数返回给定…
阅读更多...
6-1 求二叉树高度

6-1 求二叉树高度

6-1 求二叉树高度 (15 分) 本题要求给定二叉树的高度。 函数接口定义&#xff1a; int GetHeight( BinTree BT );其中BinTree结构定义如下&#xff1a; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ElementType Data;BinTree Left;BinTree Rig…
阅读更多...
二叉树的构造及求解二叉树高度

二叉树的构造及求解二叉树高度

题目描述 1、参考题目解释构造一棵二叉树&#xff1b; 2、求解二叉树的高度 3、有余力同学尝试打印这棵二叉树&#xff08;以树的形态&#xff0c;非必须&#xff09; 输入 A(B(E,C(D(F(,G),),) 输出 二叉树高度为: 6 代码实现 #include <iostream> //#include &l…
阅读更多...
二叉树4：二叉树求树高度(超级详细)

二叉树4：二叉树求树高度(超级详细)

一、思路 什么是树高&#xff1f; 树的高度(或深度)就是树中结点的最大层数。 在这里使用后序遍历的递归算法。 对每一个结点都进行如下操作&#xff1a; 后序遍历其左子树求树高后序遍历其右子树求树高对这个结点进行下面操作&#xff1a; 比较其左右子树的高度大小若左&g…
阅读更多...
二叉树的高度和深度

二叉树的高度和深度

二叉树的高度和深度定义 &#xff08;对某个节点来说&#xff09; 深度是指从根节点到该节点的最长简单路径边的条数&#xff1b; 高度是指从最下面的叶子节点到该节点的最长简单路径边的条数&#xff1b; &#xff08;对二叉树&#xff09; 深度是从根节点数到它的叶节点&…
阅读更多...
关于360提示发现木马—HEUR/QVM.Malware.Gen

关于360提示发现木马—HEUR/QVM.Malware.Gen

今天用Visual Studio写的关于三层架构的程序 在启动运行时&#xff0c;弹出了360关于"检测到木马程序"的提示框&#xff1a; 虽然知道自己写的是正规程序&#xff0c;但初看时还是被吓了一跳&#xff0c;于是立马上网查阅相关资料和解答&#xff0c;结论是&#xff…
阅读更多...
WebRTC 之 RTX

WebRTC 之 RTX

AbstractWebRTC RTX 笔记AuthorsWalter FanCategorylearning noteStatusv1.0Updated2020-08-28LicenseCC-BY-NC-ND 4.0 什么是 RTX RTX 就是重传 Retransmission, 将丢失的包重新由发送方传给接收方。 Webrtc 默认开启 RTX (重传)&#xff0c;它一般采用不同的 SSRC 进行传输&a…
阅读更多...
红与蓝：现代Webshell检测引擎免杀对抗与实践

红与蓝：现代Webshell检测引擎免杀对抗与实践

上半年Webshell话题很火，业界举办了数场对抗挑战赛，也发布了多篇站在安全产品侧，着重查杀思路的精彩文章，但鲜有看到以蓝军视角为主的paper。 作为多场挑战赛的参赛者及内部红蓝对抗的参与者，笔者试着站在蓝军角度，聊聊现代Webshell对抗的一些思路，也以PHP Webshell为例…
阅读更多...
堪比熊猫烧香！中国新型蠕虫病毒大爆发！电脑瞬间报废

堪比熊猫烧香！中国新型蠕虫病毒大爆发！电脑瞬间报废

堪比熊猫烧香&#xff01;中国新型蠕虫病毒大爆发&#xff01;电脑瞬间报废 近日&#xff0c;深信服安全团队监测到一种名为incaseformat的病毒&#xff0c;全国各个区域都出现了被incaseformat病毒删除文件的用户。 经调查&#xff0c;该蠕虫正常情况下表现为文件夹蠕虫&#…
阅读更多...
Dreh zelle acht hoch

Dreh zelle acht hoch

Android6.0权限和SharedPreferences存储 static class MyTask extends AsyncTask<String,String,String> { Override protected String doInBackground(String... strings) { FileOutputStream outnull; InputStream inputStreamnull;//网络连接的输入流 HttpURLConnecti…
阅读更多...
json.cp37-win32.pyd HEUR/QVM30.2.223F.Malware...

json.cp37-win32.pyd HEUR/QVM30.2.223F.Malware...

问题 使用pyinstaller导出exe,运行时候会被360杀毒报木马. 病毒类型是HEUR/QVM30.2.223F.Malware.Gen 木马文件是 pandas库下的一个文件 \Python\Python37-32\Lib\site-packages\pandas\_libs\json.cp37-win32.pyd 原因 32位的pandas文件是 json.cp37-win32.pyd (32位的,3…
阅读更多...
Herm Chart

Herm Chart

参考链接 https://blog.csdn.net/QianLiStudent/article/details/111872100 https://www.jianshu.com/p/4bd853a8068b 1 概念 1.1 Helm 1.1.1 Helm是什么&#xff1f; Helm 是 Kubernetes 的包管理器。包管理器类似于我们在 Ubuntu 中使用的apt、Centos中使用的yum 或者Pyt…
阅读更多...
关于桌面程序被安全软件误判为HEUR:Trojan.Win32.Generic的解决方案

关于桌面程序被安全软件误判为HEUR:Trojan.Win32.Generic的解决方案

最近写了一个桌面程序&#xff0c;里面用了些读取系统环境变量、提取文件图标、启动外部程序之类的操作。 然后…………卡巴斯基就把它识别成了HEUR:Trojan.Win32.Generic………… 咱遵纪守法好程序&#xff0c;怎么说是木马就是木马了呢&#xff1f;&#xff1f;&#xff1f; …
阅读更多...
从0到1学会使用SpringBoot 搭建mock Server

从0到1学会使用SpringBoot 搭建mock Server

做过接口测试的同学一定听说过mock Server&#xff0c;大家会觉得其很神秘&#xff0c;很高大上&#xff01;mock Server出现的原因是现今的业务系统很少有孤立存在的&#xff0c;它们或多或少需要使用兄弟团队或是其他公司提供的服务&#xff0c;这给我们的联调和测试造成了麻…
阅读更多...
Postman mockserver详细教程

Postman mockserver详细教程

转自&#xff1a; https://blog.csdn.net/testdeveloper/article/details/80559538 模客API接口链接&#xff1a;http://mock-api.com/ http://mock-api.com/ http://mock-api.com/ http://mock-api.com/ 1.发送一个request 发送请求之后在History标签下保存了请求的数据&a…
阅读更多...
postman如何使用mockserver？

postman如何使用mockserver？

mock服务&#xff0c;实现创建一个url&#xff0c;设定response Body&#xff0c;通过访问这个假的url&#xff0c;就能得到想要的返回结果。 应用于&#xff0c;当后端接口如A没有开发完成&#xff0c;但是当前测试又依赖于接口A时&#xff0c;就可以用mock服务&#xff0c;访…
阅读更多...
Postman接口Mock Server服务器设置

Postman接口Mock Server服务器设置

目录 一、适用场景 二、设置步骤 2.1.创建一个mock server 2.2.配置mock server 2.3.Mock Servers创建成功一个新的mock地址 2.4.环境变量Environments&#xff1a;生成一个mock server新的环境变量 2.5.项目集Collections&#xff1a;生成一个mock server新的项目集&am…
阅读更多...
推荐文章

Copyright @ 2022~2023