6

我正在寻找一种方法来确定方程是否存在解，例如： 3n1+4n2+5n3=456，其中n1,n2,n3是正整数。

或更一般地说：是否存在零或正整数n1,n2,n3 ... 来求解方程k1n1+k2n2+k3n3...=m其中k1,k2,k3 ... 和m是已知的正整数。

我不需要找到解决方案 - 只需确定是否存在解决方案。

编辑：

关于该算法的实际使用：

在通信库中，我想在处理消息之前根据其大小确定给定消息是否有效。例如：我知道一条消息包含零个或多个 3 字节元素、零个或多个 4 字节元素和零个或多个 5 字节元素。我收到一条 456 字节的消息，我想在进一步检查其内容之前确定其有效性。当然，消息的标题包含每种类型的元素数量，但我想通过传递类似pair<MsgType,vector<3,4,5>>.

4

7 回答 7

16

你问的是正则表达式

(xxx|xxxx|xxxxx)*

匹配 xx...x，其中 x 出现 456 次。

这是 O(n+a^2) 中的一个解决方案，其中 a 是左侧数字中的最小值（在本例中为 3）。

假设您的数字是 6,7,15。我将以 6x+7y+15z 形式表示的数字称为“可用”。您将检查给定的号码是否可用。

如果你能够得到某个数字 n，那么你肯定能够得到 n+6、n+12、n+18 - 一般来说，对于所有 k >= 0，n+6k。另一方面，如果你无法得到某个数字 n，那么 n-6 肯定也不可用（如果你能得到 (n-6)，那么 (n-6)+6=n 将可用），这意味着 n-12， n-18, n-6k 也不可用。

假设您已确定 15 可用但 9 不可用。在我们的例子中，15=6*0+7*0+15*1 但无论如何都无法得到 9。因此，根据我们之前的推理，15+6k 可用于所有 k >= 0，而 9-6k 可用于所有 k >= 0 则不可用。如果您有某个数字除以 6 得到 3 作为余数（3、9、15、21，...），您可以快速回答：数字 <= 9 不可用，数字 >= 15 可用。

确定除以 6 的所有可能余数（即 0、1、2、3、4、5）就足够了，可用的最小数是多少。（我刚刚表明余数 3 的这个数字是 15）。

怎么做：创建一个顶点为 0、1、2、3、4、5 的图形。对于给定的所有数字 k (7,15 - 我们忽略 6)，添加一条从 x 到 (x + k) mod 6 的边。给它权重 (x + k) div 6. 使用Dijkstra 算法，使用 0 作为初始值节点。算法找到的距离将正是我们正在搜索的那些数字。

在我们的例子中 (6,7,15)，数字 7 产生 0 -> 1（权重 1），1 -> 2（权重 1），2 -> 3（权重 1），...，5 -> 0（权重 1）和数字 15 给出 0 -> 3（权重 2）、1 -> 4（权重 2）、...、5 -> 1（权重 2）。从 0 到 3 的最短路径有一条边 - 它的权重为 2。因此 6*2 + 3 = 15 是余数为 3 的最小数字。6*1 + 3 = 9 不可用（好吧，我们之前手动检查过）。

和正则表达式有什么联系？好吧，每个正则表达式都有一个等效的有限自动机，我构建了其中一个。

这个问题，允许多个查询，出现在波兰奥赛上，我翻译了解决方案。现在，如果你现在听到有人说计算机科学对真正的程序员没有用处，那就打他的脸吧。

于 2009-09-24T13:19:32.013 回答
3

据此，如果{n1, n2, n3, ...} 的最大公因数不是 m 的除数，则无解。此页面仅显示 {n1, n2} 的示例，但它扩展到更大的系统。新问题是编写一个算法来找到最大公因数，但鉴于原始问题，这很简单。

所以你的算法的一部分会找到 gcf({n1,n2,...}) 然后看看它是否是 m 的一个因子。如果不是，则不存在解决方案。这并不能完全表明存在解决方案，但它可以快速显示不存在，这仍然很有用。

于 2009-09-23T19:06:03.307 回答
2

看起来您正在谈论具有整数约束的不等式系统。现实情况是您正在解决这个系统：

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

以及 n1, n2, n3 是整数的附加约束。这是一个线性规划问题。不幸的是，解决这种具有整数约束的系统的一般情况是 NP-complete。但是，有许多算法可以为您解决它。

于 2009-09-23T18:58:35.733 回答
2

这与Frobenius 硬币问题有关，对于 n>3，该问题尚未解决。

于 2009-09-24T11:48:58.233 回答
1

蛮力方法（伪代码）：

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

另见http://mail.python.org/pipermail/python-list/2000-April/031714.html

编辑：在通信库中，这是没有意义的，因为它需要立即工作。在 OP 的应用程序中，我可能会使用某种哈希，但他的方法听起来很有趣。

于 2009-09-23T19:01:49.237 回答
1

这是关于 2 号案例的内容。我还没有弄清楚如何缩放它：

给定 2 个互质整数 x 和 y，存在正整数 a 和 b，使得ax+by=c对于所有c>=(x-1)(y-1)

基本上，这是可行的，因为如果您假设x<y，您可以用 (0, y, 2y, 3y, ..., (x-1)y) 表示所有整数 mod x。现在，通过添加 x 的某个正倍数，您可以得到 [(x-1)(y-1),(x-1)y] 之间的所有整数，就像 (x-1)(y- 1) 和 (x-1)y-1 之前已经表达过。

  1. GCD(x,y)。如果 c 不是倍数，则返回 false。
  2. 如果 GCD(x,y) > 1，将 x,y,c 除以 GCD
  3. 如果 c > (x-1)(y-1)，则返回 true
  4. 其他蛮力

对于蛮力：

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false
于 2009-09-23T23:46:44.387 回答
1

也许以下信息无关紧要，因为它不处理一般情况，但是......

如果问题是确定给定的正整数 K 是否可以形成为 sum 3*n1 + 4*n2 + 5*n3，对于非负整数 n1、n2、n3，那么答案是“是”，因为 K >= 3。

罗森著名的教科书《离散数学及其应用》，第 3 页。第六版的第 287 章证明了“每张 12 美分或更多的邮资，只需使用 4 美分和 5 美分的邮票就可以形成”，使用归纳法。

基本步骤是 12 美分的邮资可以用 3 张 4 美分的邮票组成。

归纳步骤认为，如果使用 4 美分邮票 P(k) 为真，则只需用 5 美分邮票替换 4 美分邮票即可证明 P(k+1) 为真。如果不使用 4 美分邮票 P(k) 为真，那么，因为 k>=12，我们至少需要 3 个 5 美分邮票来形成我们的总和，3 个 5 美分邮票可以用 4 个 4 美分邮票代替邮票达到k+1。

为这个问题扩展上述解决方案只需要考虑更多的情况。

于 2009-09-25T19:30:25.760 回答