首页 > 剑指offer > 倒水问题-经典面试题
2014
04-10

倒水问题-经典面试题

倒水问题

这个题目的版本非常之多,有微软版的,腾讯版的,新浪版的等等,最常见的是给你一个容量为5升的杯子和一个容量为3升的杯子,水不限使用,要求精确得到4升水。问题会有两种形式:

1) 直接以简答的方式给定方案

这个比较简单,即便是不知道什么原理,也可以很快凑出来。假设两个杯子分别为x 5升杯, y  3升杯 :  装满 x  ; x -> y  ;清空Y  ;x -> y  ;装满 x  ;x -> y

解决方案会有多个,写出一个即可。

2) 编程实现

解法也比较多,我首先想到的DFS(深度优先)搜索,每次我们有6种选择,只要不断的尝试下去,总可以搜索完所有的状态,找到一个解。也可以用宽度优先搜索(BFS)。

使用DFS搜索实现的Java代码:

/**
 * @author coder
 * @copyright www.acmerblog.com
 */
public class PourWater {
	//所有的6中操作。
	static String operations[] = {" 装满 x ", " 装满 y "," 清空X ", " 清空Y ", " x -> y ", " y -> x "};
	static Stack<Integer> stack = new Stack<Integer>();
	static int L1,L2 ;//两个杯子的容量
	static int target; //目标容量
	static int len;
	//防止重复搜索
	static boolean dp[][] ;
	public static void dfs(int x,int y){
		if(dp[x][y]) return;
		dp[x][y] = true;
		//找到解决方案
		if(x == target || y == target){
			System.out.println("dfs方法 一个倒水方案:");
			for(int oper:stack)
				System.out.println(operations[oper]);
			return;
		}
		stack.push(0);
		dfs(L1,y);
		stack.pop();

		stack.push(1);
		dfs(x,L2);
		stack.pop();

		stack.push(2);
		dfs(0,y);
		stack.pop();

		stack.push(3);
		dfs(x,0);
		stack.pop();

		//x向y倒水
		stack.push(4);
		if(x >= (L2-y) )  //x倒不完,还有剩余
			dfs(x - (L2-y),L2);
		else
			dfs(0 ,y + x); //x没有剩余
		stack.pop();

		//y向x倒水,需要判断能否倒完
		stack.push(5);
		if(y >= (L1-x))
			dfs(L1,y - (L1-x));
		else
			dfs(0,y + x);
		stack.pop();
	}

	public static void main(String[] args) {
		 L1 = 5;
		 L2 = 3;
		target = 4;
		 len = Math.max(L1, L2) + 1;
		 dp = new boolean[len][len];
		dfs(0,0);
	}
}

又在网上找到一个穷举法,利用了扩展欧几里得算法(同余定理)的一些概念。

。穷举法实现比较方便,其基本思想是用:用小桶容量的倍数对大桶的容量进行取余。比如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,将倒水问题的基本思想用易于编程的话来翻译下——不断用小桶装水倒入大桶,大桶满了立即清空,每次判断下二个桶中水的容量是否等于指定容量。有了这个倒水问题的编程指导方针后代码非常容易写出:

//热门智力题 - 打水问题
//基本思想:用小桶容量的倍数对大桶的容量进行取余。
//指导方针:不断用小桶装水倒入大桶,大桶满了立即清空,
//每次判断下二个桶中水的容量是否等于指定容量。
#include<iostream>
#include <vector>
#include<string>
using namespace std;
const string OPERATOR_NAME[7] = {
	"装满A桶","装满B桶",
	"将A桶清空","将B桶清空",
	"A桶中水倒入B桶","B桶中水倒入A桶",
	"成功"
};
int main()
{
	cout<<"热门智力题 - 打水问题"<<endl;
	cout<<"  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n"<<endl;

	int    a_volume, b_volume, goal_volume;
	vector<string> record;       //记录操作步数
	int    ai;
	int    i, a_water, b_water;

	cout<<"请输入A桶容量,B桶容量,目标容量:";
	cin>>a_volume>>b_volume>>goal_volume;
	a_water = b_water = 0; //A桶,B桶中有多少升水
	char szTemp[30];
	while (true)
	{
		if (a_water == 0)//A桶没水,就装满水
		{
			a_water = a_volume;
			sprintf(szTemp, "         A:%d  B:%d", a_water, b_water); 
			record.push_back(OPERATOR_NAME[0] + szTemp);//fill A
		}
		else
		{
			//如果A桶的水比(B桶容量-B桶的水)要多
			if (a_water > b_volume - b_water)
			{
				//A桶的水==A桶的水+B桶的水-B桶容量
				a_water = a_water + b_water- b_volume;
				b_water = b_volume;		 //B桶的水装满了
				sprintf(szTemp, "  A:%d  B:%d", a_water, b_water); 
				record.push_back(OPERATOR_NAME[4] + szTemp);//A->B	
				if (a_water == goal_volume)
					break;
				b_water = 0;			//将B桶清空
				sprintf(szTemp, "       A:%d  B:%d", a_water, b_water); 
				record.push_back(OPERATOR_NAME[3] + szTemp);
			}
			else
			{
				//B桶的水==A桶的水+B桶的水
				b_water += a_water;	
				a_water = 0;
				sprintf(szTemp, "  A:%d  B:%d", a_water, b_water);
				record.push_back(OPERATOR_NAME[4] + szTemp);//A->B
				if (b_water == goal_volume) 
					break;
			}
		}
	}
	record.push_back(OPERATOR_NAME[6]);	//success
	cout<<"\n---------------------------------------------------"<<endl;
	cout<<"一个可行的倒水方案如下"<<endl;
	vector<string>::iterator pos;
	for (pos = record.begin(); pos != record.end(); pos++)
		cout<<*pos<<endl;
	cout<<"---------------------------------------------------"<<endl;
	return 0;
}

 一般性问题

有两个容器,容积分别为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的最大公约数了,求公约数可以用辗转相除法,代码如下:

#include <stdio.h>
#include <stdlib.h>
//求最大公约数
int gcd(int a, int b)
{
    int m = a, n = b , r = 1;
    while(1)
    {
        r = m % n;
        if(r == 0)
        {
            return n;
        }
        else
        {
            m = n;
            n = r;
        }
    }
}
//返回值1表示能使得水缸恰好有C升水,0表示不能
int can(int a,int b,int c)
{
    int result = 0;
    result = gcd(a,b);
    if(c % result == 0 )
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main(void)
{
    int A , B , C;
    A = 1234567;
    B = 7654321;
    C = 9999999;
    printf("the result is %d",can(A,B,C));
    return 0;
}

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

输入: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