【程序设计思维与实践 week2 作业题】倒水问题

题目描述

倒水问题 “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
Sample Output
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
success

Notes

如果你的输出与Sample Output不同,那没关系。对于某个"A B C"本题的答案是多解的,不能通过标准的文本对比来判定你程序的正确与否。 所以本题由 SPJ(Special Judge)程序来判定你写的代码是否正确。

思路

经典逻辑问题,两个杯子能否凑出目标容量x,在于是否存在i使得(i*(b-a)+b)%a等于c%a (a<b)。由于此题并没有让求解最少操作次数,本人用了一个很偷懒的办法,就是先不断循环倒水,使得B中剩余容量x%a == c%a。然后再比较x和c的大小,决定是加a升水或者减去a升水。
所以核心问题在于如何求解x。做法是先让B中满水,B中剩余水量记为x,若x%a != c%a,则不断倒空a升水直到B中剩余水x小于a,然后进入换水环节:将B中水倒入x,B倒满,再把B中部分水倒入A剩余空间,B中剩下的水即为新的x(数学表达形式x = b-a+x),注意最后要倒空A,以便于下一轮循环的操作。反复进行这段操作,直到满足目标条件。

总结

瞄了一眼其他同学的有用bfs遍历+map记录操作名字的,emm这不失为一种好的方法,毕竟对于求少操作次数还是很管用的,用map也可以减少中间路径的记录成本。

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<queue> 
using namespace std;
int a,b,c;
int x;
void f(){
	while (x > a){
		x -= a;
		cout << "pour B A" <<endl;
		cout << "empty A" <<endl;
	}
}
void sub(){
	while (x != c){
		x -= a;
		cout << "pour B A" <<endl;
		if (x == c){
			cout << "success" <<endl;
			return;
		}
		cout << "empty A" <<endl;
	}	
} 
void add(){
	while (x != c){
		x += a;
		cout << "fill A" <<endl;
		cout << "pour A B" <<endl;
		if(x == c){
			cout << "success" <<endl;
			return;
		}
	}
}
int main(){
//	freopen("1.txt","r",stdin);
	while (cin >> a >> b >> c){
		x = b;
		cout << "fill B" <<endl;	
		//求正确的模
		while (x % a != c % a){
			f();
			cout << "pour B A" <<endl;
			cout << "fill B" <<endl;
			cout << "pour B A" <<endl;
			cout << "empty A" <<endl;
			x = b - a + x;
		}
		//求解	
		if (x == c)
			cout << "success" <<endl;
		if (x > c) sub();
		if (x < c) add();
	}
	return 0;
}
上一篇:R语言里一些画图程序不能在循环里正常保存的解决办法


下一篇:Flood Fill-dfs