算法题：8升满壶5升3升空壶倒出4升水
2019-09-24 本文已影响0人
Murray66
原题
给一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，想个办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满
在网上看到这道题，觉得挺有趣的，就花时间做了一下。虽然乍一看挺有思路，实现起来还是费了不少劲。
思路
- 用广度遍历来做，把三个瓶子的状态标志成一个值，每次只进行一次倒水操作。
- 用一个集合记录已经出现过的状态，新的状态不能和集合里已有状态重复。
- 为了记录操作路径，每个状态需要有个指针指向上一个状态
代码
public class PourWater {
public static void main(String[] args) {
pourWater();
}
/**
* Status类，用String类型存状态，用int的话出现类似053这样的状态比较麻烦
* 用last指向上一个状态
*/
static class Status {
public String statusCode;
public Status last;
public Status(String statusCode) {
this.statusCode = statusCode;
}
}
//倒水的方法
private static void pourWater() {
Status root = new Status("800");
//Set记录出现过的状态
Set<String> statusSet = new HashSet<>();
statusSet.add(root.statusCode);
//LinkedList实现广度遍历
Queue<Status> queue = new LinkedList<>();
queue.add(root);
//resCount记录解题有几种方法
int resCount = 0;
//结束条件为queue为空，当所有状态都存进Set里了，queue自然会变空
while (!queue.isEmpty()) {
Status cur = queue.poll();
String[] stringDatas = cur.statusCode.split("");
//打印当前状态，并把值赋进int数组，方便后续计算
int[] datas = new int[3];
for (int i = 0; i < stringDatas.length; i++) {
System.out.print(stringDatas[i] + " ");
datas[i] = Integer.parseInt(stringDatas[i]);
}
System.out.println();
System.out.println("----------------");
if (datas[1] != 5 && datas[0] != 0) {
//如果8杯子可以给5杯子倒水
int[] temp = new int[3];
System.arraycopy(datas, 0, temp, 0, datas.length);
if (datas[0] + datas[1] >= 5) {
temp[0] = temp[0] - (5 - temp[1]);
temp[1] = 5;
} else {
temp[1] = temp[1] + temp[0];
temp[0] = 0;
}
if (calculate(temp, cur, statusSet, queue)) {
resCount++;
}
}
if (datas[2] != 3 && datas[0] != 0) {
//如果8杯子可以给3杯子倒水
int[] temp = new int[3];
System.arraycopy(datas, 0, temp, 0, datas.length);
if (datas[0] + datas[2] >= 3) {
temp[0] = temp[0] - (3 - temp[2]);
temp[2] = 3;
} else {
temp[2] = temp[2] + temp[0];
temp[0] = 0;
}
if (calculate(temp, cur, statusSet, queue)) {
resCount++;
}
}
if (datas[1] != 0 && datas[0] != 8) {
//如果5杯子可以给8杯子倒水
int[] temp = new int[3];
System.arraycopy(datas, 0, temp, 0, datas.length);
if (datas[1] + datas[0] >= 8) {
temp[1] = temp[1] - (8 - temp[0]);
temp[0] = 8;
} else {
temp[0] = temp[0] + temp[1];
temp[1] = 0;
}
if (calculate(temp, cur, statusSet, queue)) {
resCount++;
}
}
if (datas[1] != 0 && datas[2] != 3) {
//如果5杯子可以给3杯子倒水
int[] temp = new int[3];
System.arraycopy(datas, 0, temp, 0, datas.length);
if (datas[1] + datas[2] >= 3) {
temp[1] = temp[1] - (3 - temp[2]);
temp[2] = 3;
} else {
temp[2] = temp[2] + temp[1];
temp[1] = 0;
}
if (calculate(temp, cur, statusSet, queue)) {
resCount++;
}
}
if (datas[2] != 0 && datas[1] != 5) {
//如果3杯子可以给5杯子倒水
int[] temp = new int[3];
System.arraycopy(datas, 0, temp, 0, datas.length);
if (datas[2] + datas[1] >= 5) {
temp[2] = temp[2] - (5 - temp[1]);
temp[1] = 5;
} else {
temp[1] = temp[1] + temp[2];
temp[2] = 0;
}
if (calculate(temp, cur, statusSet, queue)) {
resCount++;
}
}
if (datas[2] != 0 && datas[0] != 8) {
//如果3杯子可以给8杯子倒水
int[] temp = new int[3];
System.arraycopy(datas, 0, temp, 0, datas.length);
if (datas[2] + datas[0] >= 8) {
temp[2] = temp[2] - (8 - temp[0]);
temp[0] = 8;
} else {
temp[0] = temp[0] + temp[2];
temp[2] = 0;
}
if (calculate(temp, cur, statusSet, queue)) {
resCount++;
}
}
}
System.out.println("resCount: " + resCount);
}
private static boolean calculate(int[] datas, Status cur, Set<String> statusSet, Queue<Status> queue) {
//尝试生成状态，如果无法生成，status为空
//如果可以生成，判断状态中是否包含4
//如果包含4，打印操作路径
//如果不包含4，状态加入队列继续广度遍历
Status status = newStatus(datas, cur, statusSet);
if (isSuccess(datas)) {
printProcess(status);
return true;
} else {
if (status != null) {
queue.add(status);
}
}
return false;
}
//尝试生成状态
private static Status newStatus(int[] datas, Status cur, Set<String> set) {
String statusCode = intArrayToString(datas);
if (!set.contains(statusCode)) {
Status temp = new Status(statusCode);
temp.last = cur;
set.add(statusCode);
return temp;
}
return null;
}
//判断是否包含4
private static boolean isSuccess(int[] datas) {
for (int data : datas) {
if (data == 4) {
return true;
}
}
return false;
}
//打印操作路径
private static void printProcess(Status lastStatus) {
ArrayList<Status> arr = new ArrayList<>();
while (lastStatus != null) {
arr.add(lastStatus);
lastStatus = lastStatus.last;
}
for (int i = arr.size() - 1; i >= 0; i--) {
System.out.print(arr.get(i).statusCode + " ");
}
System.out.println();
}
private static String intArrayToString(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int value : arr) {
sb.append(value);
}
return sb.toString();
}
}
结果
有两种办法
8 0 0
----------------
3 5 0
----------------
5 0 3
----------------
0 5 3
----------------
3 2 3
----------------
5 3 0
----------------
6 2 0
----------------
2 3 3
----------------
6 0 2
----------------
2 5 1
----------------
1 5 2
----------------
800 350 323 620 602 152 143
7 0 1
----------------
7 1 0
----------------
800 503 530 233 251 701 710 413
resCount: 2
