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更新min * 并记录下此时j的值，即得到了怎么分割盘子，才能使最终的移动次数最少 */ if (min > count4) { min = count4; flag_j = j; } B[i] = min; // 将min赋给B[i]，即四根柱子时，i个盘子从a->d 的次数 C[i] = flag_j; // 找到了当前i下的j值 } } Scanner scanner = new Scanner(System.in); while (true) { System.out.print("请输入一个n值(应为1-64之间的整数，输入0结束程序):"); n = scanner.nextInt(); if(n == 0) { System.out.println("ByeBye"); break; } if(n > 64 || n < 1) { System.out.println("输入的n有误，请重新输入"); continue; } char a = 'a', b = 'b', c = 'c', d = 'd'; hanoi(n, a, b, c, d, C); // 把n个盘子从a柱子移动到b柱子 System.out.println("共移动了: " + B[n] + " 次"); System.out.println("共移动了: " + count + " 次");//与B[n]的值是一样的 count = 0;//次数置零 } } /** * 移动（使用四个柱子的移动方式） */ public static void hanoi(int n, char a, char b, char c, char d, int C[]){ int j = C[n]; //j个盘子使用四个柱子的移动方式 if (n > 0) { hanoi(j, a, d, b, c, C);// 把j个盘子移动到d柱子上 hanoi_basic_3(n - j, a, b, c);// 把n-j个盘子移动到b柱子上（使用三个柱子的移动方式） hanoi(j, d, b, a, c, C); // 把j个盘子移动到b柱子上 } } /** * 把n-j个盘子移动到b柱子上（使用三个柱子的移动方式） */ public static void hanoi_basic_3(int n, char a, char c, char b){ if(n > 0) { hanoi_basic_3(n - 1, a, b, c);// 把n-1个盘子移动到c柱子上 move(n, a, c); // 把a移动到c hanoi_basic_3(n - 1, b, c, a); // 把第n个盘子移动到c柱子上 } } /** * 在控制台打印移动情况 */ public static void move(int n, char a, char c){ System.out.println(a + "->" + c); count++;//记录次数 }}。