明天要去参加微软面试，不求顺利，但求体验。
这个题目答题的意思是:
给你一个容量为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; } 运行结果如下：
...