文章目录
- 智力题——5L的桶和3L的桶如何装4L的水
- 问题描述
- 直观分析
- 问题建模
- 问题解决
智力题——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());}}