智力题——5L的桶和3L的桶如何装4L的水

问题描述

有一个5L的桶A和一个3L的桶B以及无限量的水，如何让5L的桶装4L的水。
支持操作：加水，倒水，A倒入B，B倒入A，除此之外不再支持其他操作，例如做记号或者借助其他工具

直观分析

直观分析就是利用我们的直观思维在草纸上不停的模拟这些操作，这个很不好说，对于简单问题你可能可以模拟出来，可是问题一旦复杂起来，就必须得对问题抽象建模。问题的最终解如下图：

A和B的水量转移状态如下：
(0,0)->(5,0)->(2,3)->(2,0)->(0,2)->(5,2)->(4,3)

问题建模

我们可以把转移过程画成一张图，如下是整张图的一部分，现在就转化成图论的遍历算法了，即从（0，0）找到一条路径到(4,x)即可，DFS和BFS我选择BFS，因为BFS天然可以求无向图最短路径，我们要保证操作最少

我们先进行一次状态压缩，把ab两个桶的水量压缩成一个整数，例如4，3压缩成43，这样采取取整和求余就可以分别得知ab的水量

问题解决

package com.lry.basic.algorithm.graph;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class WaterPuzzle {private int A=5;private int B=3;private int require=4;private boolean[] visited = new boolean[A*10+B+1];private int[] pre = new int[A*10+B+1];private int end = -1;private void bfs(){Queue<Integer> queue = new LinkedList<>();queue.offer(0);visited[0] = true;while(!queue.isEmpty()){int cur = queue.poll();int a = cur/10;int b = cur%10;List<Integer> nextList = next(a,b);for (int next:nextList) {if(!visited[next]){queue.offer(next);visited[next] = true;pre[next] = cur;//保存cur到next这条路径if(next/10==require||next%10==require){//找到一个解就提前返回end = next;return;}}}}}private List<Integer> next(int a,int b){//下一个状态的数组List<Integer> nextList = new ArrayList<>();//经过四种操作的nextList//给a装满水nextList.add(A*10+b);//给b装满水nextList.add(a*10+B);//a倒掉全部水nextList.add(b);//b倒掉全部水nextList.add(a*10);//a倒入bint x = Math.min(a,B-b);//看a中的水量和b中剩余的空间，谁小nextList.add((a-x)*10+b+x);//b倒入aint y = Math.min(b,A-a);//看b中的水量和a中剩余的空间，谁小nextList.add((a+y)*10+b-y);return nextList;}private Iterable<Integer> path(){List<Integer> res = new ArrayList<>();if(end==-1){return res;}int cur = end;while(cur!=0){res.add(0,cur);cur = pre[cur];}res.add(0,0);return res;}public static void main(String[] args) {WaterPuzzle puzzle = new WaterPuzzle();puzzle.bfs();System.out.println(puzzle.path());}}