3L, 5L, 8L三个水桶等分8L水 Java(递归, 穷举)

　

三个水

题目

有三个容积分别是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
---------------------------------------

相关阅读

DDR3L是什么意思 DDR3和DDR3L内存的区别有哪些？

DDR3和DDR3L的区别有哪些？最近在网上购买笔记本内存的时候，发现笔记本DDR3内存分为2种，一种是标准的DDR3内存，另外还有一种DDR3L内存

几大免费统计工具的比较：cnzz、5la、量子恒道

统计工具对站长来说，特别是新入门站长来说，相当重要。对统计工具的需要体现在以下几个方面：1、对自己的站有一个大致的了解，起码可以