算法之穷举（泊松分酒）
- 2019 年 10 月 27 日
- 筆記
穷举法
又称暴力破解法，就是把所有条件，相关情况统统考虑进去，让计算机进行检索，指导得出与之所有条件符合的结果
（但是，暴力破解法对计算机资源耗费严重，如果条件太复杂，运算速度缓慢，为了解决这一问题，我们可以事先把与之不相关的条件进行限制，减少计算机的运算量）
泊松分酒
有3个容器，容量分别为12升，8升，5升。其中12升中装满酒，另外两个空着。
要求你只用3个容器操作，最后使得某个容器中正好有6升酒。
分酒规则 1 –> 2 –> 3 –> 1
- 大瓶子只能倒入中瓶子
- 中瓶子只能倒入小瓶子
- 小瓶子只能倒入大瓶子
- 小瓶子只有在已经装满的情况下才能倒入大瓶子
- 若小瓶子被倒空，则无论中瓶子是否满，应马上从中瓶子倒入小瓶子
之所以要规定倒酒的顺序是为了防止状态重复。而根据这5条规则，大瓶子每次倒入中瓶子的酒总是8升，小瓶子每次倒入大瓶子的酒总是5升。
代码实现
package cn.itcast.recursion; public class ShareWine { public static void main(String[] args) { ShareWine shareWine = new ShareWine(); shareWine.backBottle(12, 0, 0); } //定义三个瓶子的容量 private int b1 = 12; private int b2 = 8; private int b3 = 5; private int m = 6;//目标酒量 //假设一开始，12,0,0 public void backBottle(int bb1, int bb2, int bb3) { System.out.println("bb1酒量:" + bb1 + " bb2酒量:" + bb2 + " bb3酒量:" + bb3); if (bb1 == m || bb2 == m || bb3 == m) { System.out.println("find the bottle"); return; } //瓶子2还有酒&&瓶子3没满 if (bb2 != 0 && bb3 != b3) { //没到5升，倒不满 if (bb2 + bb3 <= b3) { backBottle(bb1, 0, bb2 + bb3); } else { //第二个参数：刚开始bb2有那么多酒，倒进bb3之后，bb3满了，bb2就等于之前的bb2 -（满了之后的b3-没倒之前的bb3） backBottle(bb1, bb2 - (b3 - bb3), b3); } //瓶子3满了，往瓶子1倒 } else if (bb3 == b3) { //没到12升，倒不满 if (bb3 + bb1 <= b1) { backBottle(bb1 + bb3, bb2, 0); } else { backBottle(b1, bb2, bb3 - (b1 - bb1)); } //从瓶子1往瓶子2倒酒 } else if (bb2 == 0) { if (bb1 >= b2) { backBottle(bb1 - b2, b2, bb3); } else { backBottle(0, bb1, bb3); } } } }
打印结果：
bb1酒量:12 bb2酒量:0 bb3酒量:0
bb1酒量:4 bb2酒量:8 bb3酒量:0
bb1酒量:4 bb2酒量:3 bb3酒量:5
bb1酒量:9 bb2酒量:3 bb3酒量:0
bb1酒量:9 bb2酒量:0 bb3酒量:3
bb1酒量:1 bb2酒量:8 bb3酒量:3
bb1酒量:1 bb2酒量:6 bb3酒量:5
