`
gaotong1991
  • 浏览: 92983 次
  • 来自: 北京
社区版块
存档分类
最新评论

倒水问题-经典面试题

 
阅读更多

原文: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

 

4
1
分享到:
评论

相关推荐

    微软的面试题及答案-超变态但是很经典

    ### 微软的面试题及答案 #### 逻辑思维与数学能力题目 1. **时间计算题**: - 一昼夜需要1小时,那么同理,一昼夜需要多少小时? - 这个问题看似简单,实际上是考察应聘者的逻辑思维能力。正确答案是“一昼夜...

    经典面试50题(免费分享).pdf

    【安全相关的面试题解析】 1. 请谈谈你的朋友、亲近者的情况。 在面试中,这个问题可能旨在了解你的社交圈子以及你与他人的关系,间接评估你的团队合作能力和人际交往能力。在回答时,应强调与朋友和亲近者的良好...

    微软的面试题

    ### 微软面试题解析 #### 一、速度与时间问题 **题目描述:** - 一辆汽车在平路上行驶可以达到60km/h的速度,但在上坡时速度只有30km/h。问如何使这辆车保持平均速度为60km/h? **解析:** 这个问题的关键在于理解...

    几道微软面试题,给大家参考一下(很有意思的)

    根据给定文件的信息,我们可以提炼出以下相关的IT知识点: ...以上就是对这些微软面试题的解析,这些问题不仅考验了应试者的逻辑思维能力,还考察了解决实际问题的能力。通过这类题目,可以锻炼思维的灵活性和创造性。

    世界500强使用频率最高的面试题

    **解析**:这是一道经典的时间测量题。可以通过先点燃绳子的两端,同时点燃第二根绳子的一端。当第一根绳子烧完时,已经过去了半小时;此时再点燃第二根绳子的另一端,当第二根绳子完全烧完时,恰好过去了一个小时。...

    IBM面试题.doc

    【知识点详解】 ...以上就是IBM面试题中涉及的几个主要知识点,包括逻辑推理、策略制定、数学运算和问题解决能力。这些问题考察了面试者在实际工作中可能遇到的问题解决技巧,体现了IBM对员工思维能力的高要求。

    IT面试智力题

    以下是一些可能会在IT面试中遇到的经典智力题及其解析: 1. **猴子分桃**:假设五只猴子发现一堆桃子,它们决定每晚吃掉一半,但又怕被其他猴子偷吃,于是每晚吃完后都再放回一颗。连续四晚后,只剩下一颗桃子。问...

    面试常见智力题解答

    面试经典总结,百度大牛PPT讲解: 1.海盗分金问题 2.帽子/疯狗问题 3.称球问题 4.分金条问题 5.猴子搬香蕉问题 6.飞机加油问题 7.硬币游戏 8.倒水问题 9.帽子问题 10.年龄问题

    面试时常见的智力题

    在面试过程中,智力题是一种常见的考核方式,用来评估应聘者的逻辑思维能力、问题解决技巧以及创新能力。这些题目通常不依赖于特定的专业知识,而是侧重于考察个人的智商和思维方式。以下是一些面试时可能会遇到的...

    微软面试题

    ### 微软面试题解析 #### 一、烧绳计时问题 **题目:** 烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子,问如何用烧绳的方法来计时一个小时十五分钟呢? **解析:** 为了实现计时一个...

    银海面试题20060301.doc

    这个问题是经典的数学问题。步骤如下: 1. 使用7升瓶子装满水。 2. 将7升瓶子的水倒入5升瓶子,此时7升瓶子剩余2升。 3. 空掉5升瓶子,将7升瓶子剩下的2升水倒入5升瓶子。 4. 再次用7升瓶子装满水。 5. 用7升瓶子中...

    微软经典测试题及详细参考答案

    这些题目涵盖了逻辑思维、数学应用、概率计算、问题解决等多个方面,这些都是IT行业常见的面试题类型,用于考察应聘者的逻辑推理能力和创新思维。下面逐一解析这些知识点: 1. **计时问题**:这类问题通常涉及时间...

    75道逻辑思维题答案

    【1】此题是一道经典的液体倒水问题。通过一系列操作,最终目的是在6升的壶里得到3升水。步骤如下: 1. 先将5升壶装满水,倒入6升壶,此时6升壶有5升水。 2. 再次将5升壶装满,用它向6升壶倒水,直到6升壶满,此时5...

    微软面试题及答案(很需要开放性思维啊)宣贯.pdf

    1. **海盗分宝石**:这是一个经典的博弈论问题,涉及到最大化个人利益的策略。 2. **飞机加油**:需要找出最少的资源分配策略以完成任务。 3. **汽车加油**:路径规划和资源管理,可能需要设计一种策略使得汽车能...

    华为软件测试笔试题!厉害!厉害!厉害!厉害!厉害!厉害!厉害!厉害!

    根据给定文件的信息,我们可以提炼出与华为软件测试笔试题相关的知识点。...通过阅读和研究华为的软件测试笔试题,不仅有助于准备面试,还能加深对软件测试领域的理解,为未来的职业发展打下坚实的基础。

    三个水桶等分8升水的问题(Python)

    这个问题是经典的逻辑与算法问题,通常出现在编程面试或者智力题中。它要求使用三个容量不同的水桶,通过倒水操作将一定量的水等分成三份。在这个案例中,目标是将8升水等分为三份,每份2.666...升。这个问题的关键...

    75个经典的智力题目-大型企业喜欢出的智力题

    2. **5升和6升水壶问题**:利用这两壶水的容量差异,通过倒水操作得到特定体积的水。这里需要找到5和6的公倍数,即30,然后设计一系列操作使得最终剩余3升水。 3. **三名枪手决斗**:这是一个概率和策略结合的问题...

    思维创新题(智力测试题)

    1. **5升和6升水壶取3升水**:这是一个经典的数学问题,涉及到容积转换和操作。解决这个问题需要通过一系列倒水操作,找到合适的步骤组合。 2. **盛满水的玻璃杯间隔问题**:这是一个空间想象和逻辑推理题,通过...

    75道逻辑思考题及答案

    【逻辑思考题】是智力测试和面试中常见的一部分,它们旨在评估个人的推理能力、问题解决技巧和逻辑思维。以下是一些逻辑思考题及其解答,这些题目的解答过程展现了逻辑推理的重要性。 【1】5升和6升水壶取3升水的...

Global site tag (gtag.js) - Google Analytics