题目

有三个容积分别是8升、5升和3升的水桶，其中容积为8升的水桶中有8升水，其它两个水桶是空的。三个水桶都没有刻度，问如何在不借助其它工具的情况下只使用这三个桶把8升水等分。

代码

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;/*** Created by GuanDS on 2018/8/22.*/
public class Test {private static int[] limits = new int[]{8, 5, 3};private static int count = 0;private static List<Set<String>> methods = new ArrayList<>();public static void main(String[] args) {change(new int[]{8, 0, 0}, new LinkedHashSet<>());System.out.println("共" + count + "种方式");for (Set<String> steps : methods) {System.out.println("---------------------------------------");for (String step : steps) {System.out.println(step);}System.out.println("---------------------------------------\n\n");}}public static void change(int[] array, Set<String> steps) {String str = array[0] + ", " + array[1] + ", " + array[2];if (steps.contains(str)) {// 方案已经被处理过了return;}if (array[0] == 4 && array[1] == 4) {steps.add("4, 4, 0");methods.add(steps);count++;return;}for (int i = 0; i < array.length; i++) { // 遍历出水桶if (array[i] == 0) { // 水桶没有水, 只能被注入continue;}for (int j = 0; j < array.length; j++) { // 遍历进水桶int[] temp = array.clone();if (i != j) { // 不能是自己if (array[j] == limits[j]) { // 被注入的桶已经满了continue;}int change = limits[j] - array[j]; // 要么把进水桶注满, 要么把出水桶的水用完if (array[i] < change) {change = array[i];}temp[j] = temp[j] + change; // 进水桶进水temp[i] = temp[i] - change; // 出水桶出水Set<String> stepsTemp = new LinkedHashSet<>(); // copy之前步骤, 做备份stepsTemp.addAll(steps);stepsTemp.add(str); // 记录此步骤change(temp, stepsTemp);}}}}}

结果

共16种方式
---------------------------------------
8, 0, 0
3, 5, 0
0, 5, 3
5, 0, 3
5, 3, 0
2, 3, 3
2, 5, 1
7, 0, 1
7, 1, 0
4, 1, 3
4, 4, 0
------------------------------------------------------------------------------
8, 0, 0
3, 5, 0
3, 2, 3
0, 5, 3
5, 0, 3
5, 3, 0
2, 3, 3
2, 5, 1
7, 0, 1
7, 1, 0
4, 1, 3
4, 4, 0
---------------------------------------...........---------------------------------------
8, 0, 0
5, 0, 3
5, 3, 0
2, 3, 3
2, 5, 1
3, 5, 0
3, 2, 3
6, 2, 0
6, 0, 2
1, 5, 2
1, 4, 3
4, 4, 0
---------------------------------------