注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

倒水问题-经典面试题  

2014-05-07 20:08:46|  分类: 热门面试题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

倒水问题

这个题目的版本非常之多,有微软版的,腾讯版的,新浪版的等等,最常见的是给你一个容量为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 */
05public 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>
08using namespace std;
09const string OPERATOR_NAME[7] = {
10    "装满A桶","装满B桶",
11    "将A桶清空","将B桶清空",
12    "A桶中水倒入B桶","B桶中水倒入A桶",
13    "成功"
14};
15int 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}

 一般性问题

有两个容器,容积分别为A升和B升,有无限多的水,现在需要C升水。 我们还有一个足够大的水缸,足够容纳C升水。起初它是空的,我们只能往水缸里倒入水,而不能倒出。 可以进行的操作是: 把一个容器灌满; 把一个容器清空(容器里剩余的水全部倒掉,或者倒入水缸); 用一个容器的水倒入另外一个容器,直到倒出水的容器空或者倒入水的容器满。     问是否能够通过有限次操作,使得水缸最后恰好有C升水。

输入:三个整数A, B, C,其中 0 < A , B, C <= 1000000000                输出:0或1,表示能否达到要求。

函数头部: c语言:1表示可以,0表示不可以 int can(int a,int b,int c);

c++语言: true表示可以,false表示不可以 bool can(int a,int b,int c);

java语言:true表示可以,false表示不可以 public class Main {public static boolean can(int a,int b,int c); }

上面的穷举法已经给出了一些结论:我们可以有这样一个公式:xA + yB = C ;
只要x,y有整数解,这个问题就是可解的。其中x,y 可以为负整数。 例如对于 A=3, B=5,  C=4,其实就是  3*A – 1*B = 4;  即向A中倒满了3次,B清空一次。

根据欧几里德扩展算法,gcd(A, B) = Ax + By,求出A和B的最大公约数,如果C能被最大公约数整除Gcd(A, B) 整除,那就可以实现水缸里恰好为C升水;
那题目就直接转换为求A 、B的最大公约数了,求公约数可以用辗转相除法,代码如下:

01#include <stdio.h>
02#include <stdlib.h>
03//求最大公约数
04int gcd(int a, int b)
05{
06    int m = a, n = b , r = 1;
07    while(1)
08    {
09        r = m % n;
10        if(r == 0)
11        {
12            return n;
13        }
14        else
15        {
16            m = n;
17            n = r;
18        }
19    }
20}
21//返回值1表示能使得水缸恰好有C升水,0表示不能
22int can(int a,int b,int c)
23{
24    int result = 0;
25    result = gcd(a,b);
26    if(c % result == 0 )
27    {
28        return 1;
29    }
30    else
31    {
32        return 0;
33    }
34}
35int main(void)
36{
37    int A , B , C;
38    A = 1234567;
39    B = 7654321;
40    C = 9999999;
41    printf("the result is %d",can(A,B,C));
42    return 0;
43}

同样,附带几个测试用例:

输入:A = 1234567,  B = 7654321 ,  C = 9999999,  输出:result = 1;

输入:A = 9999,  B = 5555,  C = 2222,   输出:result = 1;

输入:A = 1000000000,   B = 2,   C = 1 ,  输出:result = 0.

参考:http://www.cnblogs.com/bestDavid/p/Dropwarter.html

http://blog.csdn.net/morewindows/article/details/7481851

http://www.acmerblog.com/pour-water-problem-5615.html

  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018