倒水问题

liqinwyyx

浏览: 10655 次

最近访客更多访客>>

liuwenchao

woodding2008

lhg317

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

这个题目的版本非常之多，有微软版的，腾讯版的，新浪版的等等，最常见的是给你一个容量为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
}