Java与C++分别用递归实现汉诺塔详解
作者:Demo龙 时间:2021-10-23 01:28:59
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为辅助塔
}
}
}
来源:https://zal321.blog.csdn.net/article/details/124134208
标签:Java,汉诺塔,C++
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java SpringMVC框架开发之数据导出Excel文件格式实例详解
2023-11-10 21:11:18
Spark网站日志过滤分析实例讲解
2021-06-08 12:59:24
![](https://img.aspxhome.com/file/2023/7/60927_0s.png)
Java8新特性之默认方法(default)浅析
2023-10-03 10:41:13
![](https://img.aspxhome.com/file/2023/1/62051_0s.png)
java客户端Jedis操作Redis Sentinel 连接池的实现方法
2023-08-19 10:55:19
JFinal实现伪静态的方法
2023-07-17 12:11:37
![](https://img.aspxhome.com/file/2023/0/57630_0s.jpg)
详解java接口基础知识附思维导图
2023-11-09 10:07:28
![](https://img.aspxhome.com/file/2023/1/58861_0s.png)
iOS实现微信朋友圈与摇一摇功能
2023-06-16 13:59:48
![](https://img.aspxhome.com/file/2023/6/78286_0s.gif)
阿里、华为、腾讯Java技术面试题精选
2023-11-25 02:29:39
![](https://img.aspxhome.com/file/2023/4/59904_0s.jpg)
详解Java中switch的新特性
2023-11-24 23:41:54
![](https://img.aspxhome.com/file/2023/4/60154_0s.webp)
IDEA插件EasyCode及MyBatis最优配置步骤详解
2023-11-09 03:19:19
详解Java中的三种流程控制语句
2023-11-04 17:06:34
![](https://img.aspxhome.com/file/2023/2/58852_0s.png)
微服务分布式架构实现日志链路跟踪的方法
2023-11-29 15:43:16
![](https://img.aspxhome.com/file/2023/3/60123_0s.jpg)
Mybatis-plus多租户项目实战进阶指南
2023-10-10 18:14:43
Spring Cache+Redis缓存数据的实现示例
2023-11-26 11:53:20
![](https://img.aspxhome.com/file/2023/0/60060_0s.png)
C#实现观察者模式(Observer Pattern)的两种方式
2023-06-20 21:05:18
![](https://img.aspxhome.com/file/2023/0/66130_0s.png)
Flutter使用sqflite处理数据表变更的方法详解
2023-10-21 11:05:49
![](https://img.aspxhome.com/file/2023/3/139083_0s.webp)
Flutter Widgets之标签类控件Chip详解
2023-06-26 14:22:35
![](https://img.aspxhome.com/file/2023/0/120090_0s.jpg)
Flutter 容器盒子模型的使用示例
2023-06-18 18:47:43
![](https://img.aspxhome.com/file/2023/4/85974_0s.png)
Java多线程Thread类的使用详解
2023-11-11 13:08:11
![](https://img.aspxhome.com/file/2023/3/59013_0s.png)
微信第三方登录Android实现代码
2023-07-27 08:05:49
![](https://img.aspxhome.com/file/2023/6/85986_0s.png)