Java与C++分别用递归实现汉诺塔详解

目录
  • 1.汉诺塔介绍
  • 2.解塔步骤
  • 3.C++实现（递归结果及显示步骤）
    • (1)递归结果
    • (2)显示步骤
  • 4.Java实现（递归结果及显示步骤）
    • (1)递归结果
    • (2)显示步骤

1.汉诺塔介绍

汉诺塔规则

1.有三根杆子A,B,C。A杆上有若干碟子

2.每次移动一块碟子,小的只能叠在大的上面

3.把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片： 如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

2.解塔步骤

圆盘：12345 柱子：ABC

1→C，2→B，1→B，3→C，1→A，2→C，1→C，4→B； 1→B，2→A，1→A，3→B，1→C，2→B，1→B，5→C； 1→A，2→C，1→C，4→A，1→B，2→A，1→A，4→C； 1→C，2→B，1→B，3→C，1→A，2→C，1→C，完成！

3.C++实现（递归结果及显示步骤）

(1)递归结果

#include<iostream>
using namespace std;
int H_tower(int num);
int main()
{
	int num;
	cout<<"请输入需要移动的盘子数"<<endl;
	cin>>num;
	cout<<H_tower(num)<<endl;
 }
 int H_tower(int num)
 {
 	if(num<1)
	 {
	 	cout<<"请输入大于等于一的数"<<endl;
		 exit(-1); //输入不合法，退出程序
	  }
	if(num==1)
	{
		return 1;
	}
	return (2*H_tower(num-1)+1);//规律递归
 }

(2)显示步骤

#include<iostream>
using namespace std;
 void hannuo(int num);
 void Move(int &sum,int num,char A,char B,char C);
 int main()
 {
 		int num;
	cout<<"请输入需要移动的盘子数"<<endl;
	cin>>num;
	hannuo(3);
 }
 void hannuo(int num)
 {
 	if(num<1)
 	{
 			cout<<"请输入大于等于一的数"<<endl;
		 exit(-1); //输入不合法，退出程序
	 }
	 int sum=0;
	 Move(sum,num,'A','B','C');
 }
 void Move(int &sum,int num,char A,char B,char C)
 {
 	if(num==1)
 	{
 		sum++;
 		//圆盘只有一个时，只需将其从A塔移到C塔
		cout << "第 "<<sum<<" 次move " << num << " from " << A << " to " << C << endl;
	 }
	else
	{
		Move(sum,num - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
		sum++;
		cout << "第 "<<sum<<" 次move " << num << " from " << A << " to " << C << endl;//把A塔上编号为n的圆盘移到C上
		Move(sum,num - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
	}
  }

4.Java实现（递归结果及显示步骤）

(1)递归结果

hannuo.java

import java.util.Scanner;
public class hannuo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num;
        System.out.println("请输入需要移动的盘子数");
        num= sc.nextInt();
        tower t=new tower();
        System.out.println("需要移动的次数 = "+t.H_tower(num));
    }
}

tower.java

public class tower {
    public int H_tower(int num) {
        if (num < 1) {
            System.out.println("请输入大于等于一的数" );
        }
        if (num == 1) {
            return 1;
        }
        return (2 * H_tower(num - 1) + 1);//规律递归
    }
}

(2)显示步骤

hannuo.java

import java.util.Scanner;
public class hannuo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num;
        System.out.println("请输入需要移动的盘子数");
        num= sc.nextInt();
        tower t=new tower();
        t.hannuo(num);
    }
}

tower.java

public class tower {
    public void hannuo(int num)
    {
        if(num<1)
        {
            System.out.println("请输入大于等于一的数");
        }
        int sum[]={0};
        Move(num,'A','B','C');
    }
    public void Move(int num,char A,char B,char C)
    {
        if(num==1)
        {
            //圆盘只有一个时，只需将其从A塔移到C塔
            System.out.println(" move " + num + " from " + A + " to " + C );
        }
        else
        {
            Move(num - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
            System.out.println(" move " + num + " from " + A + " to " + C );//把A塔上编号为n的圆盘移到C上
            Move(num - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
        }
    }
}

到此这篇关于Java与C++分别用递归实现汉诺塔详解的文章就介绍到这了,更多相关Java汉诺塔内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java SE求解汉诺塔问题的示例代码

    Java SE求解汉诺塔问题的示例代码

    目录 1.问题描述 2.画图分析 3.问题讲解 4.代码实现 1.问题描述 汉诺塔问题是一个经典的问题.汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说. 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上. 并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘. 问应该如何操作? 2.画图分析 一个圆盘的情况:移动前 移动后 1个盘子:A直

  • Java 实现一个汉诺塔实战练习

    Java 实现一个汉诺塔实战练习

    汉诺塔简介: 我们想要实现的是 让 A柱上的盘子,移动到C柱上 1层汉诺塔 2层汉诺塔 3层汉诺塔详解图 第一步 第二步 第三步 第四步 第五步 第六步 第七步 经过上面的图解,相比大家一定在一定程度了解到汉诺塔的游戏规则,以及怎么去玩. 总之 最终C柱上第一个盘子,是最大,最顶的是最小的,而且在操作过程中,前几步就是为了让三个柱子中最大的盘子移动到C柱上, 然后不断,将它两个柱子中最大盘子往上累加,(盘子从大到小,从下往上摆放) 而且盘子一多,你就会发现过程中间,除了最大的盘子,其余的盘子都会

  • 手把手带你用java搞定汉诺塔

    手把手带你用java搞定汉诺塔

    目录 什么是汉诺塔 问题剖析 n=1 n=2 n=3 小结 Java代码实现 代码讲解 move函数 hanoiTower函数 附:C语言实现汉诺塔 总结 什么是汉诺塔 汉诺塔问题是一个经典的问题.汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说. 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移

  • Java用递归方法解决汉诺塔问题详解

    Java用递归方法解决汉诺塔问题详解

    目录 前言 一.问题描述 二.问题分析 三.解决方案 四.示例 前言 博主之前有写过关于递归问题的思维模式: 递归的思路 下面将用这种思维模式来求解经典汉诺塔问题. 一.问题描述 汉诺塔(又称河内塔)问题是源于印度一个古老传说.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上. 并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 问应该如何操作? 玩法如下: 1.有三

  • Java通过递归算法解决迷宫与汉诺塔及八皇后问题

    Java通过递归算法解决迷宫与汉诺塔及八皇后问题

    目录 1.递归的重要规则 2.递归的三个案例 1.老鼠出迷宫 2.汉诺塔 3.八皇后 1.递归的重要规则 在执行一个方法时,就创建一个新的受保护的独立空间(栈空间). 方法的局部变量时独立的,不会相互影响. 如果方法中使用的是应用类型变量(比如数组,对象),就会共享该引用类型的数据. 递归必须向退出递归的条件逼近,否则就是无限递归. 当一个方法执行完毕,或者遇到return,就会返回,遵循谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕. 2.递归的三个案例 1.老鼠出

  • Java递归来实现汉诺塔游戏,注释详细

    Java递归来实现汉诺塔游戏,注释详细

    我们很容易能想到,可以用递归来实现汉诺塔游戏.因为要将n(n>1)个盘子从"源"柱子移到"目标"柱子,我们要先把n-1个盘子从"源"柱子移到"辅助"柱子上,然后把最底下那一个盘子移到目标柱子上,最后把"辅助柱"上的n-1个盘子移动到目标柱子上.n==1时直接移到目标柱上,也是递归的出口. 有了以上思路的铺垫,就可以开始实现代码了. public class HanoiDemo { public sta

  • Java 数据结构与算法系列精讲之汉诺塔

    Java 数据结构与算法系列精讲之汉诺塔

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 汉诺塔 汉诺塔 (Tower of Hanoi) 是一个源于印度的古老益智玩具. 汉诺塔由三根柱子和若干大小不同的圆盘组成. 目标是把圆盘从最左边的柱子移到最右边的柱子上. 如图: 递归 递归 (Recursion) 指的是在函数中调用自身. 递归可以帮助我们简化问题, 使用更少的代码达成目标. 汉诺塔实现 public class 汉诺塔 { // 汉诺塔实现 private static void hanoi(i

  • java递归实现汉诺塔步骤介绍

    java递归实现汉诺塔步骤介绍

    汉诺塔的规则是:一共三根柱子,一根柱子从上到下套着有小到大的若干个圆盘,要将所有圆盘按照这个排放顺序移动到第三根柱子上,并且每次只能移动一个圆盘. 可以将整个过程分为三个步骤来看: 第一步:将除最大圆盘外的n-1个圆盘移动辅助柱子上 第二步:将最大的圆盘移动到目标柱子 第三步:将n-1个圆盘从辅助柱子移动到目标柱子 其中第一步又可以拆成一模一样的三步,可以看成一个n-1层的塔要移动到目标柱子,只不过目标柱子换了一个: 第三步也可以拆分成一模一样的三步: 多拆几次就会发现规律:第一步和第三步无论如

  • Java 细致图解带你分析汉诺塔

    Java 细致图解带你分析汉诺塔

    目录 一.汉诺塔问题来源 二.问题分析 从简单问题开始 三.解决问题 整体思路 四.婆罗门能否完成大梵天的任务 移动 64 个盘子需要多长时间 计算机移动64个盘子需要多长时间 ? 一.汉诺塔问题来源 汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只

  • Java与C++分别用递归实现汉诺塔详解

    Java与C++分别用递归实现汉诺塔详解

    目录 1.汉诺塔介绍 2.解塔步骤 3.C++实现(递归结果及显示步骤) (1)递归结果 (2)显示步骤 4.Java实现(递归结果及显示步骤) (1)递归结果 (2)显示步骤 1.汉诺塔介绍 汉诺塔规则 1.有三根杆子A,B,C.A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上 经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片: 如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C 2.解塔步骤 圆盘:1

  • java 实现汉诺塔详解及实现代码

    java 实现汉诺塔详解及实现代码 汉诺塔问题:有三根柱子A,B,C,其中A上面有n个圆盘,从上至下圆盘逐渐增大,每次只能移动一个圆盘,并且规定大的圆盘不能叠放在小的圆盘上面,现在想要把A上面的n个圆盘全部都移动到C上面,输出移动的总步数以及移动的过程 分析: //先求出移动的总步数 1,假设g(n)表示n个圆盘时的移动总的步数,当n=1时,g(1)=1; 2.现在可以把g(n)进行细分为三步: 1>先将n-1个圆盘从A通过C移动到B上面,相当于将n-1个圆盘从A移动到C,因此需要g(n-1)步

  • java 汉诺塔详解及实现代码

    java 汉诺塔详解及实现代码

    java 汉诺塔详解及实现代码 实现效果图 打印的方法在 moveTheTopOne() 方法中被调用,调用该方法前打印出移动的方向--从X号塔往Y号塔 汉诺塔要求:将第一座塔上的所有盘子,借助第二座塔,全部搬运到第三座塔上. 规则:一次只能搬运一个盘子,不准将大盘子落在小盘子上.  汉诺塔实现代码: public class NewHanoi { public static int tiers = 4; // tiers 层数 private static List<String> pago

  • C语言递归思想实现汉诺塔详解

    C语言递归思想实现汉诺塔详解

    目录 1.递归思想简介 2.汉诺塔问题 3.汉诺塔递归的c语言实现 总结 1.递归思想简介 在c语言中,程序调用自身的编程技巧称为递归( recursion). 递归的定义看上去似乎很抽象,使用代码描述能够让人容易理解,下面是一个函数递归的例子. /* 递归求n的阶乘 */ int factorial(int n) //定义一个求阶乘的函数叫做factorial(),需要一个整形参数,返回一个整形值 { if (n <= 1) //递归结束的条件 { return 1; } else { ret

  • PHP递归实现汉诺塔问题的方法示例

    本文实例讲述了PHP递归实现汉诺塔问题的方法.分享给大家供大家参考,具体如下: 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘.简而言之,有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子B上,

  • Python递归实现汉诺塔算法示例

    本文实例讲述了Python递归实现汉诺塔算法.分享给大家供大家参考,具体如下: 最近面试题,面试官让我5分钟实现汉诺塔算法(已然忘记汉诺塔是啥). 痛定思痛,回来查了一下汉诺塔的题目和算法.题干与实现如下: A基座有64个盘子,大在下小在上,每次移动一个盘子,每次都需要大在下小在上,全部移动到B基座,C基座为辅助基座. # -*- coding:utf-8 -*- # 汉诺塔回溯递归实现 # 假设参数中初始杆为a,借助杆为c,阶段终止杆为b # 第一步,a状态借助b移动到c # 第二步,a移动到

  • C语言递归之汉诺塔和青蛙跳台阶问题

    C语言递归之汉诺塔和青蛙跳台阶问题

    递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题.汉诺塔问题等,在研究递归问题时我们要注意三点: 1.递归的结束条件 2.递归在每次进行过程中,都得离条件越来越近 3.相邻两次递归调用之间的关联关系 汉诺塔问题: 有三根杆子A, B, C.A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆: 1.每次只能移动一个圆盘: 2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆,

  • C语言运用函数的递归实现汉诺塔

    C语言运用函数的递归实现汉诺塔

    目录 1.汉诺塔是如何实现的 2.汉诺塔问题画图详解 3.汉诺塔问题代码解释 总结 1.汉诺塔是如何实现的 下面是有三个盘子的示例: 从左到右一次是 A柱 B柱 C柱 A柱:起始位置 B柱:目标位置 C柱:过度位置 汉诺塔为题即是,将A柱上的所有盘子移动到B柱上,且每次只能移动一个盘子,并且小盘子必须在大盘子上面 2.汉诺塔问题画图详解 下面的例子是以A柱为起始位置,B柱为中间位置,C柱为目标位置的 如果初始状态下:A柱只有一个盘子:A->C A柱有两个盘子:A->B A->C B-&g

  • JavaSE递归求解汉诺塔问题的思路与方法

    JavaSE递归求解汉诺塔问题的思路与方法

    目录 1. 汉诺塔的介绍和玩法 2. 汉诺塔问题的思路 3. 用递归的代码实现 总结 1. 汉诺塔的介绍和玩法 汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具. 一共有3根柱子(A.B.C),A柱子由下到上放着由大到小的盘子,我们需要将A柱子上的盘子移到C柱子上,每次只能移动一个盘子,且在任意一次移动中,大盘子都必须处于小盘子下方. 2. 汉诺塔问题的思路 若A柱子上只有1个盘子,只需要移动1步:A->C 若A柱子上有2个盘子,需要移动3步:A->B,A-

随机推荐