明天要去参加微软面试，不求顺利，但求体验。

这个题目答题的意思是:

给你一个容量为A升的桶和一个容量为B升的桶，水不限使用，要求精确得到Q升水.请说明步骤

当数字比较小的时候,我们可以通过大脑穷举来得到结果,但这里有两个问题,当数字很大的时候怎么解?题目给定的数据是否有解?

首先判断是否有解?

题目可以理解为,x为用A的次数,y为用B的次数,Q为目标值

Q = A * x + B * y Q =目标值.

Q必须是 Gcd(A,B)(也就是A,B的最大公约数)的倍数,否则无解,如果 Gcd(A,B) == 1, 任何Q都是可解的

最简单的方法就是把A的水不断的向B中倒(B向A中倒也行),知道得到最终结果,如果桶满了,就清空该桶.举个例子

A = 3, B = 4 并且 Q = 2 重复得从 A->B

A B

0 0 4 0 1 3 1 0 0 1 4 1 2 3 <-A桶中得到2了

试试从  B->A

A B

0 0 0 3 3 0 3 3 4 2 <- B中也得到了2 但是注意,从 B->A 比从 A->B快哦

然后我贴出代码

#include "stdafx.h"
#include <iostream>
#include <vector>
#include<string>

using namespace std;

//热门智力题 - 打水问题
//基本思想：用A桶容量的倍数对B桶的容量进行取余。
//指导方针：不断用A桶装水倒入B桶，B桶满了立即清空
//每次判断下二个桶中水的容量是否等于指定容量。
const string OPERATOR_NAME[7] = {
	"装满A桶",
	"装满B桶",
	"将A桶清空",
	"将B桶清空",
	"A桶中水倒入B桶",
	"B桶中水倒入A桶",
	"成功得到结果"
};
int max(int a,int b)
{
	return a>b?a:b;
}
int gcd(int m,int n)
{
	int temp,p,r;
	//n存放最小数，m存放最大数
	if(n>m){
		temp = n;
		n = m;
		m = temp;
	}
	p=n*m;//先取得两个数的积
	while(n!=0){
		r=m%n;
		m=n;
		n=r;
	}
return m;
}
int _tmain(int argc, _TCHAR* argv[])
{
	int    a_capacity, b_capacity, goal_capacity;
	vector<string> record;       //记录操作过程
	int a_water, b_water;

	cout<<"请输入A桶容量，B桶容量，目标容量Q：";
	cin>>a_capacity>>b_capacity>>goal_capacity;
	a_water = b_water = 0; //A桶，B桶中有多少升水

	//判断是否一定可解
	if (a_capacity<=0 || b_capacity<=0 || goal_capacity<=0)
	{
		cout<<"请保证所以容量大于0"<<endl;
		return -1;
	}
	if (goal_capacity>max(a_capacity,b_capacity))
	{
		cout<<"要量出的容量应该小于其中桶容量"<<endl;
		return -2;
	}
	//如果可解则解之
	if(goal_capacity%gcd(a_capacity,b_capacity)==0)
	{
		//存放临时的字符串构造
		char szTemp[30];
		while (true)
		{
			if (a_water == 0)//A桶没水,就装满水
			{
				a_water = a_capacity;
				sprintf(szTemp, "         A:%d  B:%d", a_water, b_water);
				record.push_back(OPERATOR_NAME[0] + szTemp);//先填满 A桶
			}
			else
			{
				//如果A桶的水比(B桶容量-B桶的水)要多，也就是多于没装满的B桶空出来的部分，A桶会剩下
				if (a_water > b_capacity - b_water)
				{
					//A桶向B桶倒水直到B桶满，此时A桶的水==A桶的水+B桶的水-B桶容量
					a_water = a_water + b_water- b_capacity;
					b_water = b_capacity;		 //B桶的水装满了
					sprintf(szTemp, "  A:%d  B:%d", a_water, b_water); 
					record.push_back(OPERATOR_NAME[4] + szTemp);//A->B	
					if (a_water == goal_capacity)
						break;
					b_water = 0;			//将B桶清空
					sprintf(szTemp, "       A:%d  B:%d", a_water, b_water); 
					record.push_back(OPERATOR_NAME[3] + szTemp);
				}
				else
				{
					//A桶小于装满B桶需要的水，此时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_capacity) 
						break;
				}
			}
		}
		record.push_back(OPERATOR_NAME[6]);	//break出来说明成功了
		cout<<"\n---------------------------------------------------"<<endl;
		cout<<"以下下是一种方案"<<endl;
		vector<string>::iterator pos;
		for (pos = record.begin(); pos != record.end(); pos++)
			cout<<*pos<<endl;
		cout<<"---------------------------------------------------"<<endl;
	}
	else
	{
		cout<<"此情况下无解"<<endl;
	}

	return 0;
}

运行结果如下：

关于如何求最少的步数来求解这个问题，希望有朋友能够留言指教。