0

给定方程：

K = Ap + Bq + Cr + Ds.

我试过的解决方案：

我们已经知道的术语：A、B、C、D、K

在给定 p, q, r 的情况下找到术语 s；

p=0, q=0, r=1;
compute() => s = (K - Ap - Bq - Cr)/D;

继续直到s 变为 < 0； 对于所有项 p=0, q=0, r=1...n;

同样继续，直到s 变为 < 0； 对于 p=0, q=1..n, r=1...n 的所有项；

和，

最后，继续直到s 变为 < 0； 对于 p=1..n、q=1..n 和 r=1..n 的所有项；

编码 3 个循环用于更新 p、q 和 r。

如果 K 变大，例如 1000...、8145、45000 等，则需要更多时间来计算；

请不要建议外部库...我正在寻找编码解决方案。

示例片段

for (int i = 0; i < preSpecifiedIterations; i++)
{
 p = i;

 if (A * p > K)  //Exit condition ; if Ap > K
  break;

  for (int j = 0; j < preSpecifiedIterations; j++)
  {
   q = j;

   if (B * q > K) //Exit condition ; if Bq > K
    break;

   for (int k = 1; k < preSpecifiedIterations; k++)
   {
    r = k;
    // compute s given p, q, and r;
    s = (K - (A * p) - (B * q) - (C * r)) / D;

    if (s < 0) //Exit condition ; don't process if s < 0 i.e negative values
     break;
    else
     ...
   }
  }
}

另外，如果有人注意到：preSpecifiedIterations -> 是否可以确定在计算之前需要多少次迭代？

有没有更好的算法来解决上述问题？

非常感谢阅读。

4

1 回答 1

4

对于 StackOverflow，这不是一个很好的问题；对于数学站点之一来说更好。但无论如何我都会在这里回答。

您当然可以比蛮力做得更好，就像您在这里所做的那样。您应该能够在几微秒内计算出答案。

当且仅当 (A, B, C, D) 的最大公约数整除 K 时，存在解。这就是贝祖身份的扩展形式。

为了确定 (1) gcd 是什么以及 (2) p, q, r, s 的值是什么，您可以使用Extended Euclidean Algorithm，您可以在此处阅读：

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

我的建议是首先编写一个程序来求解以下形式的简单线性丢番图方程ax + by = c。完成此操作后，请阅读 Wikipedia 文章中名为“超过两个数字的情况”的部分，该部分描述了如何扩展算法以处理您的情况。

于 2013-04-18T13:39:12.373 回答