|
分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击http://www.captainbed.net
package live.every.day.Programming.Stack;
/**
* 题目：
* 用栈来求解汉诺塔问题。
* 这里修改一下游戏规则：限制不能从最左侧的塔直接移到到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。
* 求当塔有N层的时候，打印最优移动过程和最优移动总步数。
*
* 思路：
* 递归的方法。
*
* @author Created by LiveEveryDay
*/
public class HanoiByStack1 {
public static int hanoi(int num, String left, String mid, String right) {
if (num < 1) {
return 0;
}
return process(num, left, mid, right, left, right);
}
private static int process(int num, String left, String mid, String right, String from, String to) {
if (num == 1) {
if (from.equals(mid) || to.equals(mid)) {
System.out.printf("Move 1 from %s to %s%n", from, to);
return 1;
} else {
System.out.printf("Move 1 from %s to %s%n", from, mid);
System.out.printf("Move 1 from %s to %s%n", mid, to);
return 2;
}
}
if (from.equals(mid) || to.equals(mid)) {
String another = (from.equals(left) || to.equals(left)) ? right : left;
int part1 = process(num - 1, left, mid, right, from, another);
int part2 = 1;
System.out.printf("Move %d from %s to %s%n", num, from, to);
int part3 = process(num - 1, left, mid, right, another, to);
return part1 + part2 + part3;
} else {
int part1 = process(num - 1, left, mid, right, from, to);
int part2 = 1;
System.out.printf("Move %d from %s to %s%n", num, from, mid);
int part3 = process(num - 1, left, mid, right, to, from);
int part4 = 1;
System.out.printf("Move %d from %s to %s%n", num, mid, to);
int part5 = process(num - 1, left, mid, right, from, to);
return part1 + part2 + part3 + part4 + part5;
}
}
public static void main(String[] args) {
int r = hanoi(2, "left", "mid", "right");
System.out.printf("It will move %d steps.", r);
}
}
// ------ Output ------
/*
Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.
*/
|