摘要:汉诺塔问题有三根柱子,源杆,暂存杆,目的杆上有层盘子,由小到大向下排列,现需要将杆的盘子移到杆中要求大的盘在下面,小的盘在上面一次只能移动一个盘子个人思路先分析问题,用数学的归纳法当只有一个盘时,直接移动当有两个盘时,先将小的移到暂存杆,再
汉诺塔问题:
有三根柱子,源杆A,暂存杆temp,目的杆C A上有n层盘子,由小到大向下排列,现需要将A杆的盘子移到C杆中
要求:1)大的盘在下面,小的盘在上面 2)一次只能移动一个盘子 个人思路:先分析问题,用数学的归纳法 当只有一个盘时,直接移动; 当有两个盘时,先将小的移到暂存杆,再将大的移到目的杆C,最后将暂存杆temp的小盘移到目的杆C中; 当有三个盘时,在下面的代码中的注释中写有详细步骤 ...... n个盘时,把它看做两部分一是上面的(n-1)盘,二是第n个盘,先将(n-1)首先将上面的(n-1)个盘子从A杆借助C杆移至temp杆,其次剩下第n个盘,直接放至C杆,最后一次递归调用解决即可。 其中汉诺塔层数可以由程序内存储读取或者键盘输入,c为程序计数器,计算移动盘的次数
import java.util.Scanner; public class Hanoi { int c=0;//计数器,计算移动的次数 public void moveone(int n, String A, String C) { System.out.println("move " + n + " from " + A + " to " + C); } public void movesome(int n, String A, String temp, String C) { c++; if (n <= 0) { System.out.println("number error"); return; } else if (n == 1) { moveone(n, A, C); } else { movesome(n - 1, A, C, temp); // 首先将上面的(n-1)个盘子从A杆借助C杆移至temp杆 moveone(n, A, C); // 然后将编号为n的盘子从A杆移至C杆 movesome(n - 1, temp, A, C); // 将剩下的(n-1)个盘子从temp杆借助A杆移至C杆 } //草稿纸上手写汉诺塔三层的实现 // moveone(1,A,C); // moveone(2,A,temp); // moveone(1,C,temp); // moveone(3, A, C); // moveone(1, temp, A); // moveone(2, temp, C); // moveone(1, A, C); } public static void main(String[] args) { //层数 System.out.println("请输入汉诺塔层数:"); Scanner input =new Scanner(System.in); int in=input.nextInt(); int l = 3; Hanoi h = new Hanoi(); // h.moveone(l,A,C);//程序内存储读取 h.movesome(in, "初始位置", "临时存放地", "目的地址"); System.out.println("汉诺塔的实现需要的移动次数:"+h.c); // h.movesome(l, "初始位置", "临时存放地", "目的地址"); } }
程序运行结果:
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/73732.html
摘要:那么,有了循环,为什么还要用递归呢在某些情况下费波纳切数列,汉诺塔,使用递归会比循环简单很多很多话说多了也无益,让我们来感受一下递归吧。 递归介绍 本来预算此章节是继续写快速排序的,然而编写快速排序往往是递归来写的,并且递归可能不是那么好理解,于是就有了这篇文章。 在上面提到了递归这么一个词,递归在程序语言中简单的理解是:方法自己调用自己 递归其实和循环是非常像的,循环都可以改写成递归...
摘要:前言相信大家在面试或者工作中偶尔会遇到递归算法的提问或者编程,我们今天来聊一聊从数学归纳法到理解递归算法。这种广义的数学归纳法应用于数学逻辑和计算机科学领域,称作结构归纳法。 showImg(https://img-blog.csdnimg.cn/20190426221838971.gif);showImg(https://img-blog.csdnimg.cn/20190429222...
阅读 2565·2021-11-18 10:07
阅读 1061·2021-08-03 14:04
阅读 708·2019-08-30 13:08
阅读 2543·2019-08-29 15:33
阅读 1036·2019-08-29 14:07
阅读 2941·2019-08-29 14:04
阅读 1413·2019-08-29 11:19
阅读 1127·2019-08-29 10:59