首页 > 搜索 > 河内,代码实现和分析算法长度,汉诺塔(河内塔)算法与心得

河内,代码实现和分析算法长度,汉诺塔(河内塔)算法与心得

互联网 2020-10-21 18:01:31
在线算命,八字测算命理

问题:给定一个由n个圆盘组成的塔,这些圆盘按照大小递减的方式套在三根桩柱中的一根上。我们的目的是要将整个塔移动到另一根桩柱上,每次只能移动一个圆盘,且较大的圆盘在移动过程中不能放置在较小的圆盘上面。

这里写图片描述

思路: 显而易见,当圆盘的数目比较小时,很好移动。当n为1时,直接将圆盘移到B柱上;当n为2时,就需要借助另外一根桩柱,首先将圆盘1移到C柱上(假设另外一个为C柱),将圆盘2移动到B柱上,再将圆盘一移动到B柱上,一共要移动3步(可以自行模拟一下);当n为3时,需要7步;当n的值很大时,需要首先借助B柱,将上面n-1个盘移到C柱上,再将第n个盘移到B柱,再借助A柱,将C柱上的n-1个盘移到B柱上,完成移动。这是一个递归的过程,移动n个盘就要先移动n-1个盘,移动n-1个盘就要先移动n-2个盘,一直到只有一个盘。

计算:首先我们来计算移动n个盘需要移动多少次。1个盘—-1次 2的1次方减12个盘—-3次 2的2次方减13个盘—-7次 2的3次方减1一直到n。发现规律了吗?移动n个盘需要移动2的n次方减1

递归公式为:这里写图片描述(证明方法为数学归纳法)

心得: 那么类似河内塔这样具有递归性质的问题解题步骤如下:1.研究小的情形。2.对有意义的量求出数学表达式并给出证明。3.对数学表达式求出封闭形式并予以证明。

java完整代码:

package arithmeticDesign;//汉罗塔的设计import java.util.Scanner;public class TowerOfHanoi {static int count=1;//用来记录生成步骤的条数public static void main(String[] args) {// TODO Auto-generated method stubScanner s=new Scanner(System.in);int n=s.nextInt();move(n,"A","B","C");}/** * 将n个盘子从A移到B,C作为辅助的柱子 * @param n 原来有多少个盘 * @param A 原来放置盘子的柱子 * @param B B柱子 * @param C C柱子 */public static void move(int n,String A,String B,String C) {if(n==1){System.out.println("第"+count+++"步:"+"将第1个盘从"+A+"移到"+B);}else{move(n-1,A,C,B);System.out.println("第"+count+++"步:"+"将第"+n+"个盘从"+A+"移到"+B);move(n-1,C,B,A);}};}
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多