原文: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 |
} |
原文:http://www.acmerblog.com/pour-water-problem-5615.html
相关推荐
### 微软的面试题及答案 #### 逻辑思维与数学能力题目 1. **时间计算题**: - 一昼夜需要1小时,那么同理,一昼夜需要多少小时? - 这个问题看似简单,实际上是考察应聘者的逻辑思维能力。正确答案是“一昼夜...
【安全相关的面试题解析】 1. 请谈谈你的朋友、亲近者的情况。 在面试中,这个问题可能旨在了解你的社交圈子以及你与他人的关系,间接评估你的团队合作能力和人际交往能力。在回答时,应强调与朋友和亲近者的良好...
### 微软面试题解析 #### 一、速度与时间问题 **题目描述:** - 一辆汽车在平路上行驶可以达到60km/h的速度,但在上坡时速度只有30km/h。问如何使这辆车保持平均速度为60km/h? **解析:** 这个问题的关键在于理解...
根据给定文件的信息,我们可以提炼出以下相关的IT知识点: ...以上就是对这些微软面试题的解析,这些问题不仅考验了应试者的逻辑思维能力,还考察了解决实际问题的能力。通过这类题目,可以锻炼思维的灵活性和创造性。
**解析**:这是一道经典的时间测量题。可以通过先点燃绳子的两端,同时点燃第二根绳子的一端。当第一根绳子烧完时,已经过去了半小时;此时再点燃第二根绳子的另一端,当第二根绳子完全烧完时,恰好过去了一个小时。...
【知识点详解】 ...以上就是IBM面试题中涉及的几个主要知识点,包括逻辑推理、策略制定、数学运算和问题解决能力。这些问题考察了面试者在实际工作中可能遇到的问题解决技巧,体现了IBM对员工思维能力的高要求。
以下是一些可能会在IT面试中遇到的经典智力题及其解析: 1. **猴子分桃**:假设五只猴子发现一堆桃子,它们决定每晚吃掉一半,但又怕被其他猴子偷吃,于是每晚吃完后都再放回一颗。连续四晚后,只剩下一颗桃子。问...
面试经典总结,百度大牛PPT讲解: 1.海盗分金问题 2.帽子/疯狗问题 3.称球问题 4.分金条问题 5.猴子搬香蕉问题 6.飞机加油问题 7.硬币游戏 8.倒水问题 9.帽子问题 10.年龄问题
在面试过程中,智力题是一种常见的考核方式,用来评估应聘者的逻辑思维能力、问题解决技巧以及创新能力。这些题目通常不依赖于特定的专业知识,而是侧重于考察个人的智商和思维方式。以下是一些面试时可能会遇到的...
### 微软面试题解析 #### 一、烧绳计时问题 **题目:** 烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子,问如何用烧绳的方法来计时一个小时十五分钟呢? **解析:** 为了实现计时一个...
这个问题是经典的数学问题。步骤如下: 1. 使用7升瓶子装满水。 2. 将7升瓶子的水倒入5升瓶子,此时7升瓶子剩余2升。 3. 空掉5升瓶子,将7升瓶子剩下的2升水倒入5升瓶子。 4. 再次用7升瓶子装满水。 5. 用7升瓶子中...
这些题目涵盖了逻辑思维、数学应用、概率计算、问题解决等多个方面,这些都是IT行业常见的面试题类型,用于考察应聘者的逻辑推理能力和创新思维。下面逐一解析这些知识点: 1. **计时问题**:这类问题通常涉及时间...
【1】此题是一道经典的液体倒水问题。通过一系列操作,最终目的是在6升的壶里得到3升水。步骤如下: 1. 先将5升壶装满水,倒入6升壶,此时6升壶有5升水。 2. 再次将5升壶装满,用它向6升壶倒水,直到6升壶满,此时5...
1. **海盗分宝石**:这是一个经典的博弈论问题,涉及到最大化个人利益的策略。 2. **飞机加油**:需要找出最少的资源分配策略以完成任务。 3. **汽车加油**:路径规划和资源管理,可能需要设计一种策略使得汽车能...
根据给定文件的信息,我们可以提炼出与华为软件测试笔试题相关的知识点。...通过阅读和研究华为的软件测试笔试题,不仅有助于准备面试,还能加深对软件测试领域的理解,为未来的职业发展打下坚实的基础。
这个问题是经典的逻辑与算法问题,通常出现在编程面试或者智力题中。它要求使用三个容量不同的水桶,通过倒水操作将一定量的水等分成三份。在这个案例中,目标是将8升水等分为三份,每份2.666...升。这个问题的关键...
2. **5升和6升水壶问题**:利用这两壶水的容量差异,通过倒水操作得到特定体积的水。这里需要找到5和6的公倍数,即30,然后设计一系列操作使得最终剩余3升水。 3. **三名枪手决斗**:这是一个概率和策略结合的问题...
1. **5升和6升水壶取3升水**:这是一个经典的数学问题,涉及到容积转换和操作。解决这个问题需要通过一系列倒水操作,找到合适的步骤组合。 2. **盛满水的玻璃杯间隔问题**:这是一个空间想象和逻辑推理题,通过...
【逻辑思考题】是智力测试和面试中常见的一部分,它们旨在评估个人的推理能力、问题解决技巧和逻辑思维。以下是一些逻辑思考题及其解答,这些题目的解答过程展现了逻辑推理的重要性。 【1】5升和6升水壶取3升水的...