2018-03-11 17:39:22
一、辗转相除法
在数学中,辗转相除法,又称欧几里得算法(英语:Euclidean algorithm),是求最大公约数的算法。
证明:
记gcd(a, b) = d
r = a - bk,r 是b对a的余数,由于a是d的倍数,b是d的倍数,k是整数,那么r必是d的倍数。
因此gcd(a, b) == gcd(b, a % b)
private int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
二、扩展欧几里得 / 贝祖定理
定理:等式 ax + by = c (其中a,b,c均是整数)存在整数解的充要条件是c % gcd(a, b) == 0,也就是说c是a,b最大公约数的倍数。
证明:
记gcd(a, b) = d
辗转相除的过程如下
a / b = s1 ... r1
b / r1 = s2 ... r2
r1 / r2 = s3 ... r3
...
rn - 1 / rn = sn + 1 ... rn + 1
rn / rn + 1 = sn + 2 ... d
现在开始反代,
d = rn - rn + 1 * sn +2
此时,d是可以通过rn,rn + 1组合得到。
将rn + 1消掉
d = rn - (rn - 1 - rn * sn + 1)
此时,d是可以通过rn - 1,rn 组合得到。
同理消除,最后d可以通过a,b组合得到。
三、Water and Jug Problem
问题描述:
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?
如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许:
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水,直到装满或者倒空
示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
问题求解:
如果单纯的去思考两个杯子之间的倒来倒去,那么问题就会变得非常复杂。有一种简化思路是,考虑有一个大的杯子,而x,y只是向大杯子中添加或者取出水,如果最终大杯子中数目等于给定的数,那么返回true。
其实就是寻找z = ax + by等式是否有解,也就是规约到了裴蜀定理的概念中,只需要判断z % gcd(x, y)即可。
public boolean canMeasureWater(int x, int y, int z) {
if (x + y < z) return false;
if (x == z || y == z || x + y == z) return true;
return z % gcd(x, y) == 0;
} private int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}