四根柱子汉诺塔问题.doc

《四根柱子汉诺塔问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.....................最新资料整理推荐.....................Hanoi:为汉诺塔问题一、运行结果二、源程序importjava.util.Scanner;/***问题描述:*由原来的三根柱子，变为四根柱子，最终要把a柱子上的全部移到b柱子上*9.....................最新资料整理推荐.....................*思路分析:*假设有n个圆盘，三根柱子，a，b，c，需要把n个盘子（从下往上按照大小顺序摞着）从a柱移动到b柱，*再找来了一根一模一样的柱子d，通过这个柱子来更快的把所有的盘子移

2、到第三个柱子上。*这道题和之前都有很大的不同，加了一根柱子，意味着有的时候可用3根柱子，有的时候可用4根柱子，*当把j个小盘子移动到d盘上时，有四根柱子可用，而当把n-j个盘子从a移动到b时，仅有三根柱子可用。*这里我们就要找到j的值，使所有移动的次数和最小。**解决方法：*依然采用分治法。*首先把j个盘子移动到d柱子上（通过四个柱子可用的算法），需要B[j]次移动，*然后把n-j个盘子移动到b柱子上（通过三个柱子可用的算法），需要A[n-j]次移动，*然后把d中的j个盘子移动到b柱子上，需要B[j]次移动。*我们可以用j的大小循环，找到移动次数最小的j。

3、*首先我们先计算移动的次数：*核心公式为：count4(4柱子时总移动次数)=2*B[j]+A[i-j]，即*j个盘子移动到第四个柱子，然后把剩下的i-9.....................最新资料整理推荐.....................j个在第四个不能用的情况下移到第三个**补充：*三根柱子时的次数计算*假设移动n个盘子需要移动f(n)次，所以把n-1个盘子移动到b柱子上，需要移动f(n-1)次，*然后把第n个盘子移动到c柱子上，需要移动1次，最后把n-1个盘子移动到c柱子上，需要移动f(n-1)次，*综上所述，一共移动了f(n)=2f(

4、n-1)+1次*/publicclassHanoi{staticintcount=0;//统计移动次数(可不需要，因为最少次数已经与n的值对应的记录在数组B中，即B[n])/***主函数*/publicstaticvoidmain(String[]args){intn;//盘子数intflag_j;//记录找到的j的值int[]A=newint[65];//数组A:用来记录未加第四个柱子时候的移动次数情况9.....................最新资料整理推荐.....................int[]B=newint[65];//数组B:用来

5、记录加了第四个柱子的情况/*根据三个柱子移动策略给数组A赋值(下面描述是按照将a柱上盘子移动到c柱上的问题来叙述的)，即*假设移动n个盘子需要移动f(n)次，所以把n-1个盘子移动到c柱子上，需要移动f(n-1)次，*然后把第n个盘子移动到c柱子上，需要移动1次，*最后把n-1个盘子移动到c柱子上，需要移动f(n-1)次，综上所述，一共移动了f(n)=2f(n-1)+1次*/A[1]=1;//即三个柱子时，当i=1的时候，表示移动一个盘子，只需要移动一次for(inti=2;i<65;i++){//从i=2开始A[i]=2*A[i-1]+1;//f(n)=

6、2f(n-1)+1}/**将n个盘子分为两部分，即前j个和后n-j个*且把前j个用四个柱子的方法，后i-j个用三个柱子的方法*下面主要是找到使移动次数最少的j值*/intcount4;//记录四根柱子时，移动的总次数intmin;9.....................最新资料整理推荐.....................//移动的最少次数，以用来和四个柱子时的其他情况进行比较int[]C=newint[65];//数组C:用来记录当前i下找到的的j值C[1]=0;//设置i=1时，初始值为0，即只有一个盘子时，令j=0C[2]=0;//设置i=2

7、时，初始值为0，即只有两个盘子时，令j=0//注意：此时的i相当于盘子数nfor(inti=3;i<=64;i++){min=A[i];//假设没加第四个柱子的结果次数为min的初值B[1]=1;//可知i=1时，即一个盘子从柱子a->d，移动次数为1次B[2]=3;//i=2时，即两个盘子从柱子a->d，移动次数为3次flag_j=0;for(intj=1;j

8、flag，则用flag更新min*9...............