math - 解决水壶问题

Question

在阅读一些时 lecture notes在初步数论中，我遇到了解决方案
水壶问题( 有两个水壶)总结如下:

利用两个数的 GCD 的性质，GCD(a,b) 是 a 和 b 的最小可能线性组合，因此某个量 Q 只能由 2 个水壶测量，如果 Q 是 an*GCD(a, b)，由于 Q=sA + tB，其中:

n = a positive integer
A = capacity of jug A
B=  capacity of jug B

然后讨论解决方法

解决方案的另一个模型是将各种状态建模为人工智能中经常采用的状态空间搜索问题。

我的问题是:还有哪些其他已知方法可以为解决方案建模，以及如何建模？谷歌并没有吐出太多。

Answer 1

严格适用于 2 Jug 问题

Q = A * x + B * y

Q = 您需要的加仑数。

注: Q 必须是 Gcd(A,B) 的倍数，否则无解。如果 Gcd(A,B) == 1，则有任何 Q 的解。

1) 方法一:
Extended Euclid's Algorithm将比任何图形算法更快地解决它。

2) 方法二:
这是一个天真的方法。 (注意，这可以抛出 2 个解决方案，您必须选择哪个更短)

有问题的问题可以通过 repeatedly 简单解决从一个桶 A 填充到另一个桶 B(顺序无关紧要)，直到它填满你想要的数量......ofcoz，当一个桶填满时，你清空它并继续。

    A = 3, B = 4 and Q = 2

反复填充A->B

    A B
   ######
    0 0
    4 0
    1 3
    1 0
    0 1
    4 1
    2 3 <-Solution

让我们试着观察如果我们反过来会发生什么，
填写 B->A

A  B
#####
0  0
0  3
3  0
3  3
4  2 <- Solution

在这种情况下，填充 B->A 比 A->B 更快地为我们提供目标状态

通用 N 水壶
这是一个有趣的 paper