明天要去参加微软面试，不求顺利，但求体验。
这个题目答题的意思是:
给你一个容量为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快哦
然后我贴出代码
运行结果如下：
关于如何求最少的步数来求解这个问题，希望有朋友能够留言指教。