数据结构(java语言描述)递归实现——汉诺塔问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构(java语言描述)递归实现——汉诺塔问题,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1136字,纯文字阅读大概需要2分钟。
内容图文
1.汉诺塔问题描述
N阶汉诺塔:假设有3个分别命名为x,y,z的三个塔座,在x上有n个盘子,直径大小不同,有小到大按标号1,2,3...n排列,要借助y将n个盘子转移到z上,期间不能让小盘子压在大盘子上。规则:
- 每次至移动一个盘子;
- 盘子可以插在x,y,z任意一个塔座上;
- 任何时候都不能将大盘压在小盘上。
2.解题思路
当n=1时,直接把盘子由x——>z;
当n>1时,需利用y,首先将(n-1)个盘子由x——>y,把第n个实现x——>z,然后把问题转换为实现(n-1)个盘子由y——>z,借助x;
实现n个盘子由x到z的时候,先把n-1个搬到y上,把第n个搬到z上;然后再借助z,把n-1个盘子搬回x.
循环实现(n-1)个盘子由x到z.
注意:最初递归中涉及到搬盘子都用move()实现一落盘子中最大的那一个,可以在此坐标记。
3.代码
package hanoi;
public class hanoi {
private int c=0;
public void hanoi(int n,char x,char y,char z){
if (n==1)
{
move(x,1,z);
}else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
}
public void move(char x,int n,char z){
System.out.println("第"+ ++c +"次移动:"+n+"号盘子,"+x+"——>"+z);
}
public static void main(String[] args){
hanoi e=new hanoi();
e.hanoi(5, ‘x‘, ‘y‘, ‘z‘);
}
}
n=4时,运行结果:
第1次移动:1号盘子,x——>y
第2次移动:2号盘子,x——>z
第3次移动:1号盘子,y——>z
第4次移动:3号盘子,x——>y
第5次移动:1号盘子,z——>x
第6次移动:2号盘子,z——>y
第7次移动:1号盘子,x——>y
第8次移动:4号盘子,x——>z
第9次移动:1号盘子,y——>z
第10次移动:2号盘子,y——>x
第11次移动:1号盘子,z——>x
第12次移动:3号盘子,y——>z
第13次移动:1号盘子,x——>y
第14次移动:2号盘子,x——>z
第15次移动:1号盘子,y——>z
原文:http://www.cnblogs.com/xleer/p/5302727.html
内容总结
以上是互联网集市为您收集整理的数据结构(java语言描述)递归实现——汉诺塔问题全部内容,希望文章能够帮你解决数据结构(java语言描述)递归实现——汉诺塔问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。