[中学教育]四根柱子汉诺塔问题
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++;//记录次数
}
}