Massive Algorithms: 倒水问题-经典面试题

倒水问题-经典面试题

最常见的是给你一个容量为5升的杯子和一个容量为3升的杯子，水不限使用，要求精确得到4升水.
2）编程实现
DFS（深度优先）搜索，每次我们有6种选择，只要不断的尝试下去，总可以搜索完所有的状态，找到一个解。也可以用宽度优先搜索（BFS）

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    }

X. http://blog.csdn.net/morewindows/article/details/7481851
可以用宽度优先搜索（BFS），也可以用穷举法。穷举法实现比较方便，其基本思想是用：用小桶容量的倍数对大桶的容量进行取余。
又在网上找到一个穷举法，利用了扩展欧几里得算法(同余定理)的一些概念。
穷举法实现比较方便，其基本思想是用：用小桶容量的倍数对大桶的容量进行取余。比如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升水。

const 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}

http://5261.github.io/Pour-water/
考虑三个容器内水量分别为

v_{0}

v_{1}

v_{2}

的状态

(v_{0}, v_{1}, v_{2})

，我们可以通过枚举所有可能的倒水操作，扩展出该状态的后继，于是该题又化归为图上最短路的问题，因为总水量是一定的(将水缸的容量和初始设为一个足够大的数)，并且都是整数，当

v_{0}

v_{1}

确定的时候，

v_{2}

也是确定的，也就是说我们可以仅通过

v_{0}

v_{1}

的值来确定一个状态，所以我们可以开一个二维数组来判重，这还是可以承受的。
如果是要求倒水步数最少，即为无权图最短路以BFS解决，如果要求倒水量最少，也可以加权搜索，即把一般队列换成优先队列，每次扩展倒水量最少的节点，同样可以解决，本题属于第一种情况。

#define STATE_SIZE 3*sizeof(int)
#define MAXCAP 126

struct Node{
    int volume[3];
    int dist;

    Node(int a, int b, int c){
        volume[0] = a, volume[1] = b, volume[2] = c;
        dist = 0;
    }

    Node(Node *father){
        memcpy(volume, father->volume, STATE_SIZE);
        dist = father->dist + 1;
    }
};

int cap[3];
int target;
bool visted[MAXCAP][MAXCAP];

inline int BFS(){
    std::queue<Node*> Q;
    Node *s = new Node(0, 0, 2 * MAXCAP);

    Q.push(s);
    s->dist = 0;
    visted[0][0] = true;
    while(!Q.empty()){
        Node *v = Q.front(); Q.pop();
        if(v->volume[0] == target || v->volume[1] == target) return v->dist;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++) if(i != j){
                // 枚举可能的倒水方案，从i倒水到j
                if(v->volume[i] == 0 || v->volume[j] == cap[j]) continue;
                //i中无水或j中已满，均不合法
                int amount = std::min(cap[j], v->volume[i] + v->volume[j]) - v->volume[j];
                // 细节: 确定倒水量
                Node *vi = new Node(v);
                int &a = vi->volume[i], &b = vi->volume[j];
                //技巧: 为比较长的变量名声明引用可以让代码更简洁清晰
                a -= amount;
                b += amount;
                if(!visted[a][b]){
                    visted[a][b] = true;
                    Q.push(vi);
                }
            }
        }
    }

    return -1;
}

http://www.cnblogs.com/hiddenfox/p/3395950.html

1 public static boolean can(int a,int b,int c) {
 2     int r;
 3     while (true) {
 4         r = a % b;
 5         if (r != 0) {
 6             a = b;
 7             b = r;
 8         } else {
 9             break;
10         }
11     } 
12     return c%b == 0;    //b现在是最大公约数，若c能被b整除，则可以
13 }

一般性问题

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

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

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

对题目做简要的处理分析后，C升水是可以分多次倒入的，假设A > B，那么每次可以倒的水的量为A , B , (A + B) ,( A - B)升水，设置4个因子，分别为x1 , x2, x3, x4 , (x1 , x2, x3, x4 属于整数)，如果可以使得水缸最后恰好有C升水，那么必然存在整数x1 , x2, x3, x4，使得

Ax1 + Bx2 + (A + B)x3 + (A - B)x4 = C 等式成立;
对等式做一定的变换，得到公式
(x1 + x3 + x4)A + (x2 + x3 - x4)B = C ; --( 1-1 )
　　设 x = x1 + x3 + x4 , y = x2 + x3 - x4 , x, y 均为整数;最终得到公式
xA + yB = C ; --( 1-2 )
x1 , x2, x3, x4 可以假设为正整数，用几个for循环可以实现，但是时间复杂度太

扩展的欧几里德算法，算法描述：
定理：
　　对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by.
　　根据欧几里德扩展算法，Gcd(A, B) = Ax + By，求出A和B的最大公约数，如果C能被最大公约数整除Gcd(A, B) 整除，那就可以实现水缸里恰好为C升水；

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

int 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}

参考：http://www.cnblogs.com/bestDavid/p/Dropwarter.html
https://github.com/aishangzoulu/raylew_algorithm/blob/master/src/main/java/com/raylew/algorithm/book1/%E5%80%92%E6%B0%B4%E9%97%AE%E9%A2%98.java
http://blog.csdn.net/morewindows/article/details/7481851
http://blog.csdn.net/crazy1235/article/details/18964001

有两个容器，容积分别为A升和B升，有无限多的水，现在需要C升水。

我们还有一个足够大的水缸，足够容纳C升水。起初它是空的，我们只能往水缸里倒入水，而不能倒出。

可以进行的操作是：

把一个容器灌满；
把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）；
用一个容器的水倒入另外一个容器，直到倒出水的容器空或者倒入水的容器满。

问是否能够通过有限次操作，使得水缸最后恰好有C升水。

输入：三个整数A, B, C，其中 0 < A , B, C <= 1000000000

输出：0或1，表示能否达到要求。

    public static boolean can(int a,int b,int c) {
  int res = mod(a, b);
  if(c%res == 0){
   return true;
  }else{
   return false;
  }
    }
 public static int mod(int a, int b){
  if(a % b == 0){
   return b;
  }else{
   return mod(b, a%b);
  }
 }

倒水问题-经典面试题

http://5261.github.io/Pour-water/
考虑三个容器内水量分别为

http://www.cnblogs.com/hiddenfox/p/3395950.html

1 public static boolean can(int a,int b,int c) { 2 int r; 3 while (true) { 4 r = a % b; 5 if (r != 0) { 6 a = b; 7 b = r; 8 } else { 9 break; 10 } 11 } 12 return c%b == 0; //b现在是最大公约数，若c能被b整除，则可以 13 }
一般性问题

Labels

Popular Posts

倒水问题-经典面试题

http://5261.github.io/Pour-water/考虑三个容器内水量分别为

http://www.cnblogs.com/hiddenfox/p/3395950.html

1 public static boolean can(int a,int b,int c) { 2 int r; 3 while (true) { 4 r = a % b; 5 if (r != 0) { 6 a = b; 7 b = r; 8 } else { 9 break; 10 } 11 } 12 return c%b == 0; //b现在是最大公约数，若c能被b整除，则可以 13 } 一般性问题

Labels

Popular Posts

http://5261.github.io/Pour-water/
考虑三个容器内水量分别为

1 public static boolean can(int a,int b,int c) { 2 int r; 3 while (true) { 4 r = a % b; 5 if (r != 0) { 6 a = b; 7 b = r; 8 } else { 9 break; 10 } 11 } 12 return c%b == 0; //b现在是最大公约数，若c能被b整除，则可以 13 }
一般性问题