四根柱子汉诺塔问题.doc

Hanoi:为汉诺塔问题 一、运行结果 二、源程序 import java.util.Scanner; /** * 问题描述: * 由原来的三根柱子，变为四根柱子，最终要把a柱子上的全部移到b柱子上 * * 思路分析: * 假设有n个圆盘，三根柱子，a，b，c，需要把n个盘子（从下往上按照大小顺序摞着）从a柱移动到b柱， * 再找来了一根一模一样的柱子d，通过这个柱子来更快的把所有的盘子移到第三个柱子上。 * 这道题和之前都有很大的不同，加了一根柱子，意味着有的时候可用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。 * 首先我们先计算移动的次数： * 核心公式为：count4 4柱子时总移动次数 2*B[j]+A[i-j]，即 * j个盘子移动到第四个柱子，然后把剩下的i-j个在第四个不能用的情况下移到第三个 * * 补充： * 三根柱子时的次数计算 * 假设移动n个盘子需要移动f n 次，所以把n-1个盘子移动到b柱子上，需要移动f n-1 次， * 然后把第n个盘子移动到c柱子上，需要移动1次，最后把n-1个盘子移动到c柱子上，需要移动f n-1 次， * 综上所述，一共移动了f n 2f n-1 +1次 */ public class Hanoi static int count 0; //统计移动次数 可不需要，因为最少次数已经与n的值对应的记录在数组B中，即B[n] /** * 主函数 */ public static void main String[] args int n; //盘子数 int flag_j; //记录找到的j的值 int[] A new int[65]; // 数组A:用来记录未加第四个柱子时候的移动次数情况 int[] B new int[65]; // 数组B:用来记录加了第四个柱子的情况 /*根据三个柱子移动策略给数组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 int i 2; i 65; i++ // 从i 2开始 A[i] 2 * A[i - 1] + 1; // f n 2f n-1 +1 /* * 将n个盘子分为两部分，即前j个 和 后n-j个 * 且把前 j个用四个柱子的方法，后i-j个用三个柱子的方法 * 下面主要是找到使移动次数最少的j值 */ int count4; //记录四根柱子时，移动的总次数 int min; //移动的最少次数，以用来和四个柱子时的其他情况进行比较 int[] C new int[65]; // 数组C:用来记录当前i下找到的的j值 C[1] 0; // 设置i 1时，初始值为0，即只有一个盘子时，令j 0 C[2] 0; // 设置i 2时，初始值为0，即只有两个盘子时，令j 0 //注意：此时的i相当于盘子数n for int i 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 int j 1; j i; j++ count4 2 * B[j] + A[i - j]; // j个移动到第四个柱子，然后把剩下的i-j个在第四个柱子不能用的情况下，移到第三个柱子 /* * 如果三根柱子时的次数min 大于 四根柱子时的次数flag，则用flag更