原文:http://www.acmerblog.com/pour-water-problem-5615.html
倒水问题
这个题目的版本非常之多,有微软版的,腾讯版的,新浪版的等等,最常见的是给你一个容量为5升的杯子和一个容量为3升的杯子,水不限使用,要求精确得到4升水。问题会有两种形式:
1) 直接以简答的方式给定方案
这个比较简单,即便是不知道什么原理,也可以很快凑出来。假设两个杯子分别为x 5升杯, y 3升杯 : 装满 x ; x -> y ;清空Y ;x -> y ;装满 x ;x -> y
解决方案会有多个,写出一个即可。
2) 编程实现
解法也比较多,我首先想到的DFS(深度优先)搜索,每次我们有6种选择,只要不断的尝试下去,总可以搜索完所有的状态,找到一个解。也可以用宽度优先搜索(BFS)。
使用DFS搜索实现的Java代码:
01 |
/** |
02 |
* @author coder
|
03 |
* @copyright www.acmerblog.com
|
04 |
*/
|
05 |
public class PourWater {
|
06 |
//所有的6中操作。
|
07 |
static String operations[] = { " 装满 x " , " 装满 y " , " 清空X " , " 清空Y " , " x -> y " , " y -> x " };
|
08 |
static Stack<Integer> stack = new Stack<Integer>();
|
09 |
static int L1,L2 ; //两个杯子的容量
|
10 |
static int target; //目标容量
|
11 |
static int len;
|
12 |
//防止重复搜索
|
13 |
static boolean dp[][] ;
|
14 |
public static void dfs( int x, int y){
|
15 |
if (dp[x][y]) return ;
|
16 |
dp[x][y] = true ;
|
17 |
//找到解决方案
|
18 |
if (x == target || y == target){
|
19 |
System.out.println( "dfs方法 一个倒水方案:" );
|
20 |
for ( int oper:stack)
|
21 |
System.out.println(operations[oper]);
|
22 |
return ;
|
23 |
}
|
24 |
stack.push( 0 );
|
25 |
dfs(L1,y);
|
26 |
stack.pop();
|
27 |
28 |
stack.push( 1 );
|
29 |
dfs(x,L2);
|
30 |
stack.pop();
|
31 |
32 |
stack.push( 2 );
|
33 |
dfs( 0 ,y);
|
34 |
stack.pop();
|
35 |
36 |
stack.push( 3 );
|
37 |
dfs(x, 0 );
|
38 |
stack.pop();
|
39 |
40 |
//x向y倒水
|
41 |
stack.push( 4 );
|
42 |
if (x >= (L2-y) ) //x倒不完,还有剩余
|
43 |
dfs(x - (L2-y),L2);
|
44 |
else
|
45 |
dfs( 0 ,y + x); //x没有剩余
|
46 |
stack.pop();
|
47 |
48 |
//y向x倒水,需要判断能否倒完
|
49 |
stack.push( 5 );
|
50 |
if (y >= (L1-x))
|
51 |
dfs(L1,y - (L1-x));
|
52 |
else
|
53 |
dfs( 0 ,y + x);
|
54 |
stack.pop();
|
55 |
}
|
56 |
57 |
public static void main(String[] args) {
|
58 |
L1 = 5 ;
|
59 |
L2 = 3 ;
|
60 |
target = 4 ;
|
61 |
len = Math.max(L1, L2) + 1 ;
|
62 |
dp = new boolean [len][len];
|
63 |
dfs( 0 , 0 );
|
64 |
}
|
65 |
} |
又在网上找到一个穷举法,利用了扩展欧几里得算法(同余定理)的一些概念。
。穷举法实现比较方便,其基本思想是用:用小桶容量的倍数对大桶的容量进行取余。比如3升的桶和5升的桶得到4升水可以这样做:
3 % 5 = 3
6 % 5 = 1
9 % 5 = 4
成功得到4升水。(PS:上面的过程用如何用文字描述了?)
同样,用7升的桶和11升的桶得到2升水可以这样做:
7 % 11 = 7
14 % 11 = 3
21 % 11 = 10
28 % 11 = 6
35 % 11 = 2
成功得到2升水。
哈哈,有了这个基本思想在用笔算答案时简直是遇神杀神,遇佛杀佛,又方便又快速!如果要求用程序来实现如何做了?easy,将倒水问题的基本思想用易于编程的话来翻译下——不断用小桶装水倒入大桶,大桶满了立即清空,每次判断下二个桶中水的容量是否等于指定容量。有了这个倒水问题的编程指导方针后代码非常容易写出:
01 |
//热门智力题 - 打水问题 |
02 |
//基本思想:用小桶容量的倍数对大桶的容量进行取余。 |
03 |
//指导方针:不断用小桶装水倒入大桶,大桶满了立即清空, |
04 |
//每次判断下二个桶中水的容量是否等于指定容量。 |
05 |
#include<iostream> |
06 |
#include <vector> |
07 |
#include<string> |
08 |
using namespace std;
|
09 |
const string OPERATOR_NAME[7] = {
|
10 |
"装满A桶" , "装满B桶" ,
|
11 |
"将A桶清空" , "将B桶清空" ,
|
12 |
"A桶中水倒入B桶" , "B桶中水倒入A桶" ,
|
13 |
"成功"
|
14 |
}; |
15 |
int main()
|
16 |
{ |
17 |
cout<< "热门智力题 - 打水问题" <<endl;
|
18 |
cout<< " --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n" <<endl;
|
19 |
20 |
int a_volume, b_volume, goal_volume;
|
21 |
vector<string> record; //记录操作步数
|
22 |
int ai;
|
23 |
int i, a_water, b_water;
|
24 |
25 |
cout<< "请输入A桶容量,B桶容量,目标容量:" ;
|
26 |
cin>>a_volume>>b_volume>>goal_volume;
|
27 |
a_water = b_water = 0; //A桶,B桶中有多少升水
|
28 |
char szTemp[30];
|
29 |
while ( true )
|
30 |
{
|
31 |
if (a_water == 0) //A桶没水,就装满水
|
32 |
{
|
33 |
a_water = a_volume;
|
34 |
sprintf (szTemp, " A:%d B:%d" , a_water, b_water);
|
35 |
record.push_back(OPERATOR_NAME[0] + szTemp); //fill A
|
36 |
}
|
37 |
else
|
38 |
{
|
39 |
//如果A桶的水比(B桶容量-B桶的水)要多
|
40 |
if (a_water > b_volume - b_water)
|
41 |
{
|
42 |
//A桶的水==A桶的水+B桶的水-B桶容量
|
43 |
a_water = a_water + b_water- b_volume;
|
44 |
b_water = b_volume; //B桶的水装满了
|
45 |
sprintf (szTemp, " A:%d B:%d" , a_water, b_water);
|
46 |
record.push_back(OPERATOR_NAME[4] + szTemp); //A->B
|
47 |
if (a_water == goal_volume)
|
48 |
break ;
|
49 |
b_water = 0; //将B桶清空
|
50 |
sprintf (szTemp, " A:%d B:%d" , a_water, b_water);
|
51 |
record.push_back(OPERATOR_NAME[3] + szTemp);
|
52 |
}
|
53 |
else
|
54 |
{
|
55 |
//B桶的水==A桶的水+B桶的水
|
56 |
b_water += a_water;
|
57 |
a_water = 0;
|
58 |
sprintf (szTemp, " A:%d B:%d" , a_water, b_water);
|
59 |
record.push_back(OPERATOR_NAME[4] + szTemp); //A->B
|
60 |
if (b_water == goal_volume)
|
61 |
break ;
|
62 |
}
|
63 |
}
|
64 |
}
|
65 |
record.push_back(OPERATOR_NAME[6]); //success
|
66 |
cout<< "\n---------------------------------------------------" <<endl;
|
67 |
cout<< "一个可行的倒水方案如下" <<endl;
|
68 |
vector<string>::iterator pos;
|
69 |
for (pos = record.begin(); pos != record.end(); pos++)
|
70 |
cout<<*pos<<endl;
|
71 |
cout<< "---------------------------------------------------" <<endl;
|
72 |
return 0;
|
73 |
} |
相关推荐
CSDN 编程大赛 倒水问题,这道题不难,也正是这个原因,我这道题出了些问题,后面改进,可惜却没机会在测试它,因为这题下线了
NULL 博文链接:https://touch-2011.iteye.com/blog/1038893
1、 编程解决如下数学问题:有12升水,怎样利用一个8升和一个5升的容器将水分为两个6升?要求以如下格式打印出分水步骤。(20分) a12 b8 c5 12 0 0 * * * ( “*”表示当前状态下每个容器的盛水量) ........
有两个水壶,一个盛满可以4公斤水,另一个3公斤水,水壶没有任何标记。怎样在能装4公斤的水壶里恰好只装2公斤水。使用状态空间法和盲目广度优先搜索算法解决这个问题。
两个杯子倒水问题,两个版本解决方案,BFS遍历方式,csdn
智力测试题经常遇到类似的逻辑题,给几个容量不等的杯子,让你倒出多少的水。 ...点击这里试试杯子倒水问题自动求解吧 算法基本逻辑: 每个杯子有倒满、倒空、倒入其它杯子的操作,所以总共是: 杯
java项目_五五开倒水 java项目_五五开倒水 java项目_五五开倒水
Jugs问题求解C++
用VC控制台实现的倒水程序 “倒水”算法代码实现
题目描述: 有两个容量分别为 x升 和 y升 的水壶以及无限多...水壶问题就是两个壶的最小公约数与想得到的水的升数是否成倍数问题(除去几个特殊情况,特殊情况在代码中有写到) 当z是最小公约数的整数倍时,可以利用两
常见题目列表: 1.海盗分金问题 2.帽子/疯狗问题 3.称球问题 4.分金条问题 5.猴子搬香蕉问题 6.飞机加油问题 7.硬币游戏 8.倒水问题 9.帽子问题 10.年龄问题
面试经典总结,百度大牛PPT讲解: 1.海盗分金问题 2.帽子/疯狗问题 3.称球问题 4.分金条问题 5.猴子搬香蕉问题 6.飞机加油问题 7.硬币游戏 8.倒水问题 9.帽子问题 10.年龄问题
包含题目:1、二项式公式计算;2、简单分形树;3、三水杯倒水问题;4、九宫格问题;5、租船问题;6、基因序列比较;7、数独问题;8、动态演示快速排序、归并排序;
打包带走吧 哈哈哈,一些算法题目还有acm的题目 包含解题思路和代码。 最大黑区域 硬币划分 乘积最大 瓷砖问题 倒水问题 合唱队形 马路上的树 逆波兰表达式 三人养蜂问题 土地划分问题
这是我在大学期间做的一个算法的课设,做的还算可以,有详细的答辩文档以及代码注释,对于难的地方都有标注二项式公式计算 绘制一个简单的分形树 ...三壶倒水问题 任务安排问题 写的还算可以吧,最后评定等级是优秀
DFT的matlab源代码 ...模拟水缸倒水问题 other little Python code MontyHallSmlt: Monty Hall Simulation findFileInWindows: as it's name fiveEngineerProgs:five-programming-problems-every-softw
两桶a,b打水来回倒水来取得c升水的经典问题
对量水问题给出产生式系统描述,并画出状态空间图。有两个无刻度标志的水壶,分别可装5升和2升的水。设另有一水缸,可用来向水壶灌水或倒出水,两个水壶之间,水也可以相互倾灌。已知5升壶为满壶,2升壶为空壶,问...
分巧克力 报数游戏 二十进制的加法 倒水 几个问题的个人实现