倒水问题-经典面试题

原文：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，将倒水问题的基本思想用易于编程的话来翻译下——不断用小桶装水倒入大桶，大桶满了立即清空，每次判断下二个桶中水的容量是否等于指定容量。有了这个倒水问题的编程指导方针后代码非常容易写出：

view source

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