算法分析之量水问题

算法分析之量水问题"/>

算法分析之量水问题

问题描述

• 有两个容器A和B，容积分别为a升和b升，有无限多的水，现在需要c升水。
• 我们还有一个足够大的水缸C，足够容纳c升水。起初它是空的，我们只能往水缸里倒入水,而不能倒出。
• 可以进行的操作是:
  <1>把一个容器灌满;
  <2>把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）
  <3>用一个容器的水倒入另外一个容器，直到倒出水的容器空或者傲入水的容器满。
• 问是否能够通过有限次操作,使得水缸c中最后恰好有c升水。
• 输入:三个整数a, b, c，其中0<a, b, c<=10000
• 输出:0或1，表示能否达到要求;如果能达到要求，则请给出具体的操作步骤序列。
  

问题解决

1.确定问题是否有解

参考文章
要确定使用容器A和容器B，依照倒水规则进行倒水能否得到c升水，可以转化为
用A盛，倒B里，B满了，就倒掉。 最终 A盛M次，B盛N次。结果c = aM -bN。
或者是反过来c = bN - aM,即求|aM - bN| = c.
要使|aM - bN| = c，且a,b,c都是大于零的整数，只要求a和b的最大公因数，是否可以被c整除，就可以确定问题是否有解了。

2.给出具体的操作步骤序列

确定问题有解，接下来就是得到具体的操作步骤序列
问题中c,b,c三个值会有三种情况。
1.c >= a+b ，水缸中还需倒入的水的体积 大于等于大容器和小容器的体积和
2.c >= a && c < a+b，水缸中还需倒入的水的体积 小于大容器和小容器的体积和 且 大于大容器的体积
3.c > 0 && c < a，水缸中还需倒入的水的体积 小于大容器的体积
第1、第2种情况比较好解决，就是尽可能使用整个容器，进行倒水。
情况3可以通过两个容器间相互倾倒得到，比较复杂。
参考文章
解决：以量杯作为树的结点，在树中找出一条路径( 分支 )，使得路径终结点的当前水量为c升，那么问题就得到解决。把以下六个操作作为子结点 .求解的过程就是在这棵树中找到一条路径．使得路径终结点处，两个容器任意一个容器中的水为c升．
对容器的六种操作

• A->B 表A容器倒入B容器
• B->A 表B容器倒入A容器
• A->E 表将A容器的水倒空
• B->E 表将B容器的水倒空
• F->A 表将A容器倒满
• F->B 表将B容器杯倒满

3.代码实现

import java.util.*;public class Solution1 {//大容器全称static String bigC = "【容器A】";//小容器全称static String smallC = "【容器B】";//水缸全称static String vat = "【水缸C】";//水缸C中此时水的体积static int curC;// m*a + n*b = cpublic static void main(String[] args) {Scanner input = new Scanner(System.in);int a, b, c;System.out.println("请输入容器A的容量：");a = input.nextInt();System.out.println("请输入容器B的容量：");b = input.nextInt();System.out.println("请输入水缸的容量：");c = input.nextInt();if (!(a > 0 && a < 10001 && b > 0 && b < 10001 && c > 0 && c < 10001)) {System.out.println("输入的数超出范围");System.exit(1);}if (!hasR(a, b, c)) {System.out.println(0);} else {System.out.println(1);getRes(a, b, c);}System.out.print(">>>>>>>>>>>>>>结束>>>>>>>>>>>>>>");}public static void getRes(int a, int b, int c) {bigC = a >= b ? bigC : smallC;smallC = bigC.equals("【容器A】") ? "【容器B】" : "【容器A】";if (a < b) {int temp = a;a = b;b = temp;}if (c >= (a + b)) {//情况一：c > a+bsituation1(a, b, c);} else if (c >= a && c < (a + b)) {//情况二：c >= a && c < a+bsituation2(a, b, c);} else {//情况三：c > 0 && c < asituation3(a, b, c);}}// 情况一： c >= a+b ，水缸中还需倒入的水的体积 大于等于大容器和小容器的体积和public static void situation1(int a, int b, int c) {System.out.println(">>>>>>>>>>>>>>情况一开始>>>>>>>>>>>>>>");//重复的次数（将大容器和小容器都装满，倒入水缸中的次数）int count = c / (a + b);curC += (count * (a + b));System.out.println("往" + bigC + "和" + smallC +"都倒满水后，倒入" + vat + "中，重复" +count + "次。此时" + vat + "中水的体积为" + curC + "升。");if (c % (a + b) != 0) {//还需倒入水缸中的水大小int reminder = c % (a + b);//c-count*(a+b)getRes(a, b, reminder);//考虑剩下的水如何倒（此时reminder肯定小于a+b,可能是情况二和情况三）}}//情况二：c >= a && c < a+b，水缸中还需倒入的水的体积 小于大容器和小容器的体积和 且 大于大容器的体积public static void situation2(int a, int b, int c) {System.out.println(">>>>>>>>>>>>>>情况二开始>>>>>>>>>>>>>>");//直接往水缸中倒入大容器体积的水curC += a;System.out.println("往容器" + bigC + "到满水后，倒入" + vat + "中，此时" + vat + "中水的体积为" + curC + "升。");if (c != a) {//c-a!=0//还需倒入水缸中的水大小int reminder = c - a;getRes(a, b, reminder);//考虑剩下的水如何倒（此时reminder肯定小于a,只可能是情况三）}}//情况三：c > 0 && c < a，水缸中还需倒入的水的体积 小于大容器的体积public static void situation3(int a, int b, int c) {System.out.println(">>>>>>>>>>>>>>情况三开始>>>>>>>>>>>>>>");//采用广度优先算法Queue<Node> queue = new LinkedList<>();Set<String> set = new HashSet<>();queue.add(new Node(0, 0, ""));int tempA, tempB;String mark;String process;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {Node node = queue.poll();//1.尝试将 容器A 中的水倒入容器 B （容器A不为空，容器B不为满）if (node.curA != 0 && node.curB != b) {tempA = node.curA + node.curB > b ? node.curA + node.curB - b : 0;tempB = Math.min(node.curA + node.curB, b);mark = tempA + "," + tempB;process = "将" + bigC + "中的水倒入" + smallC + "，此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n";if (tempA == c) {System.out.print(node.processes + process);curC += tempA;tempA = 0;System.out.print("将" + bigC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (tempB == c) {System.out.print(node.processes + process);curC += tempB;tempB = 0;System.out.print("将" + smallC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (!set.contains(mark)) {//是否之前出现过set.add(mark);queue.add(new Node(tempA, tempB, node.processes + process));}}//2.尝试将 容器B 中的水倒入容器 A （容器B不为空，容器A不为满if (node.curB != 0 && node.curA != a) {tempA = Math.min(node.curA + node.curB, a);tempB = node.curA + node.curB > a ? node.curA + node.curB - a : 0;mark = tempA + "," + tempB;process = "将" + smallC + "中的水倒入" + bigC + "，此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n";if (tempA == c) {System.out.print(node.processes + process);curC += tempA;tempA = 0;System.out.print("将" + bigC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (tempB == c) {System.out.print(node.processes + process);curC += tempB;tempB = 0;System.out.print("将" + smallC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (!set.contains(mark)) {//是否之前出现过set.add(mark);queue.add(new Node(tempA, tempB, node.processes + process));}}//3.尝试将 容器A 中的水倒空（容器A不为空）if (node.curA != 0) {tempA = 0;tempB = node.curB;mark = tempA + "," + tempB;process = "将容器" + bigC + "中的水倒空，此时" + vat + "中水的体积为" + curC + "升，容器"+ bigC + "中水体积为" + tempA + "升，容器" + smallC + "中水体积为" + tempB + "升。\n";if (tempA == c) {System.out.print(node.processes + process);curC += tempA;tempA = 0;System.out.print("将" + bigC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (tempB == c) {System.out.print(node.processes + process);curC += tempB;tempB = 0;System.out.print("将" + smallC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (!set.contains(mark)) {//是否之前出现过set.add(mark);queue.add(new Node(tempA, tempB, node.processes + process));}}//4.尝试将 容器B 中的水倒空（容器B不为空）if (node.curB != 0) {tempA = node.curA;tempB = 0;mark = tempA + "," + tempB;process = "将" + smallC + "中的水倒空，此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水体积为" + tempA + "升，" + smallC + "中水体积为" + tempB + "升。\n";if (tempA == c) {System.out.print(node.processes + process);curC += tempA;tempA = 0;System.out.print("将" + bigC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (tempB == c) {System.out.print(node.processes + process);curC += tempB;tempB = 0;System.out.print("将" + smallC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (!set.contains(mark)) {//是否之前出现过set.add(mark);queue.add(new Node(tempA, tempB, node.processes + process));}}//5.尝试将 容器A 填满水（容器A不为满）if (node.curA != a) {tempA = a;tempB = node.curB;mark = tempA + "," + tempB;process = "将" + bigC + "用水填满，此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水体积为" + tempA + "升，" + smallC + "中水体积为" + tempB + "升。\n";if (tempA == c) {System.out.print(node.processes + process);curC += tempA;tempA = 0;System.out.print("将" + bigC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (tempB == c) {System.out.print(node.processes + process);curC += tempB;tempB = 0;System.out.print("将" + smallC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (!set.contains(mark)) {//是否之前出现过set.add(mark);queue.add(new Node(tempA, tempB, node.processes + process));}}//6.尝试将 容器B 填满水（容器B不为满）if (node.curB != b) {tempA = node.curA;tempB = b;mark = tempA + "," + tempB;process = "将" + smallC + "用水填满，此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水体积为" + tempA + "升，" + smallC + "中水体积为" + tempB + "升。\n";if (tempA == c) {System.out.print(node.processes + process);curC += tempA;tempA = 0;System.out.print("将" + bigC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (tempB == c) {System.out.print(node.processes + process);curC += tempB;tempB = 0;System.out.print("将" + smallC + "中的水倒入" + vat + ",此时" + vat + "中水的体积为" + curC + "升，"+ bigC + "中水的体积为" + tempA + "升，" + smallC + "中水的体积为" + tempB + "升。\n");return;}if (!set.contains(mark)) {//是否之前出现过set.add(mark);queue.add(new Node(tempA, tempB, node.processes + process));}}}}}//自定义节点static class Node {//该节点位置的 大容器中水的体积curA，小容器中水的体积curB，以及过程描述processesint curA, curB;String processes;public Node(int curA, int curB, String processes) {this.curA = curA;this.curB = curB;this.processes = processes;}}//判断是否存在结果private static boolean hasR(int a, int b, int c) {int gcf = getGCF(a, b);if (c % gcf != 0) return false;return true;}//求两个数的最大公因数private static int getGCF(int a, int b) {for (int i = Math.min(a, b); i > 1; i--) {if (a % i == 0 && b % i == 0) {return i;}}return 1;}
}

4.实现效果