倒水问题

问题描述

“fill A” 表示倒满A杯，“empty A” 表示倒空A杯，“pour A B” 表示把A的水倒到B杯并且把B杯倒满或A倒空。

input

输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A ≤ B 、C ≤ B ≤ 1000 、A和B互质。

Output

你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始，不应该有空行或任何尾随空格。

Sample

input: 
2 7 5
2 7 4

output: 
fill B
pour B A
success 
fill A
pour A B
fill A
pour A B
success

解题思路

两水杯(a容量与b容量)中加水/倒水/相互倒水，目标为c容量，由于题目不会给出错误数据，所以直接暴力执行循环即可。

首先装满A，判断是否满足C，满足则success，否则不断地往B中倒水，不停的判断当前A、B的情况是否满足C，若满足则break，否则继续循环。循环过程中若有一方满了，则判断是否满足C，不满足清空满的杯子，继续循环。

源代码

#include <iostream>
using namespace std;

int main() {
	int a, b, c;
	int x, y;// a, b当前水量

	while (!(cin >> a >> b >> c).eof()) {
		x = y = 0;
		while (1) {
			cout << "fill A" << endl;//先装满a
			x = a;//a当前容量为a 赋值给x
			if (x == c) {//若a达到目的
				cout << "success" << endl;
				break;
			}
			while (x > 0) {//a非空时执行循环
				if ((b - y) >= x) {// 若b当前可容下当前的a
					cout << "pour A B" << endl;
					y = y + x;//更新当前b
					x = 0;//当前a为0
				}
				else {//若容不下
					cout << "pour A B" << endl;//还是a倒给b
					x = x - (b - y);// a中也有剩余
					y = b;// b就满了
				}
				if (x == c) {//判断 若达到目的
					cout << "success" << endl;
					break;
				}
				if (y == c)//当前b达到目的
					break;
				if (y == b) {//若b满
					cout << "empty B" << endl;
					y = 0;
				}
			}
			if (x == c)//重复 不输出
				break;
			if (y == c) {//若b打到目的
				cout << "success" << endl;
				break;
			}
		}
	}
	return 0;
}

尝试过的错误代码

#include <iostream>
using namespace std;

int main() {
	int a, b, c;
	while (!(cin >> a >> b >> c).eof()) {
		if (a == c) {//若目标水量为 a
			cout << "fill A" << endl;
			cout << "success" << endl;
		}
		if (c % a == 0 && a != c) {//若目标水量为a的倍数
			int countA = c / a;//这样子a往b中倒c/a次就行了
			for (int i = 0; i < countA; i++) {
				cout << "fill A" << endl;
				cout << "pour A B" << endl;
			}
			cout << "success" << endl;
		}
		if (b == c) {//若目标水量为b
			cout << "fill B" << endl;
			cout << "success" << endl;
		}
        //从b满开始算 若目标水量是从b中扣除整数个a的量
		if ((b - c) % a == 0 && b != c) {
			int countB = (b - c) / a;//扣除次数
			cout << "fill B" << endl;
			if (countB == 1)//若只需1次
				cout << "pour B A" << endl;
			else {//否则 要清空a
				for (int i = 0; i < countB - 1; i++) {
					cout << "pour B A" << endl;
					cout << "empty A" << endl;
				}
				cout << "pour B A" << endl;
			}
			cout << "success" << endl;
		}
	}

	return 0;
}

上述代码忽略了用A把B装满，要装满的最后一次A中还剩水量恰好为C的情况，比如A = 3, B = 13, C = 2。后来换了其他思路想，未提交新情况的代码测试，所以未知是否能通过。

Google后其他人的思路

只有6种状态：fill A、fill B、empty A、empty B、pour A B、pour B A，每次做出一次选择。这是一个隐式迷宫问题，每次在一个状态做出6种选择，判断是否到达“出口”，因此可采用BFS解题。