求解线性丢番图方程（参见示例说明）

Question

让我首先澄清一下（在你们解雇我之前），这不是家庭作业问题，我也不是大学生。 :)

编辑 感谢@Klas 和其他人，我的问题现在归结为一个需要以编程方式解决的数学方程。

我正在寻找一种解决线性丢番图方程的算法/代码。 对于像我这样的普通人来说，这样的方程如下所示：

示例 1：3x + 4y + 5z = 25（查找 x、y、z 的所有可能值）

示例 2：10p + 5q + 6r + 11s = 224（查找 p,q,r,s 的所有可能值）

示例 3：8p + 9q + 10r + 11s + 12t = 1012（查找所有p、q、r、s、t 的可能值）

我尝试谷歌搜索但无济于事。我本以为已经编写了一些代码来解决这个问题。如果你们遇到过某种已经实现了这一点的图书馆，请告诉我。如果解决方案是用 Java 编写的，那么没有什么比这更酷的了！算法/伪代码也可以。非常感谢。

Answer 1

暴力递归是一种选择，具体取决于您允许的值或值的数量达到多大。

假设：用户输入（被乘数）始终是不同的正整数。要找到的系数必须是非负整数。

算法：

Of the multiplicands, let M be the largest.
Calculate C=floor(F/M).
If F=M*C, output solution of the form (0,0,...,C) and decrement C
If M is the only multiplicand, terminate processing
Loop from C down to 0 (call that value i)
  Let F' = F - i*M
  Recursively invoke this algorithm:
    The multiplicands will be the current set minus M
    The goal value will be F'
  For each solution output by the recursive call:
     append i to the coefficient list and output the solution

Answer 2

我碰巧为此编写了 Java 代码。请帮助自己。这些解决方案尚未经过广泛测试，但到目前为止似乎运行良好。

package expt.qp;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class LinearDiophantine {

    private Map<Integer, Integer> sol = new LinkedHashMap<Integer, Integer>();
    private Map<Integer, Integer> coeff = new HashMap<Integer, Integer>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        // Fill up the data
        // 3x + 4y + 5z + 3a = 25
        LinearDiophantine ld = new LinearDiophantine();
        ld.coeff.put(1, 1);ld.coeff.put(2, 2);ld.coeff.put(3, 3);ld.coeff.put(4, 4);
        Map<Integer, Integer> coeffCopy = new HashMap<Integer, Integer>(ld.coeff);
        int total=30;

        // Real algo begins here
        ld.findPossibleSolutions(total, coeffCopy);

    }

    private void findPossibleSolutions(int total, Map<Integer, Integer> coeff) {
        int index=returnLargestIndex(coeff);
        int range = (int) Math.floor(total/coeff.get(index));
        if(range*coeff.get(index) == total) {
            sol.put(index, range);
            displaySolution();
            //System.out.println();
            range--;
        }
        if(coeff.size() == 1) {
            return;
        }
        while(range>=0) {
            int remTotal = total - range*coeff.get(index);
            Map<Integer, Integer> coeffCopy = new HashMap<Integer, Integer>(coeff);
            coeffCopy.remove(index);
            sol.put(index, range);
            findPossibleSolutions(remTotal, coeffCopy);
            range--;
        }
    }

    private void displaySolution() {
        int total = 0;
        for(int i : sol.keySet()) {
            //System.out.print(coeff.get(i)+"("+sol.get(i)+"), ");
            total = total + (coeff.get(i)*sol.get(i));
        }
        if(total != 30)
            System.out.print(total+",");
    }

    /**
     * @param coeff
     */
    private int returnLargestIndex(Map<Integer, Integer> coeff) {
        int largestKey = coeff.keySet().iterator().next();
        for(int i : coeff.keySet()) {
            if(coeff.get(i)>coeff.get(largestKey)) {
                largestKey=i;
            }
        }
        return largestKey;
    }

}

Answer 3

这是一个数学问题，而不是一个编程问题。一旦有了合适的算法，实现它应该不会太难。

我建议你用谷歌搜索丢番图方程。

我找到了解释

Answer 4

添加克拉斯非常准确的答案：

希尔伯特的第十个问题询问是否存在一种算法来确定任意丢番图方程是否有解。对于一阶丢番图方程的求解，确实存在这样的算法。然而，尤里·马蒂亚塞维奇 (Yuri Matiyasevich) 在 1970 年证明了获得通用解决方案的不可能性

摘自：Wolfram MathWorld

Answer 5

暴力算法如下（3 个变量的情况）：

int sum = 25;
int a1 = 3;
int a2 = 4;
int a3 = 5;
for (int i = 0; i * a1 <= sum; i++) {
    for (int j = 0; i * a1 + j * a2 <= sum; j++) {
        for (int k = 0; i * a1 + j * a2 + k * a3 <= sum; k++) {
            if (i * a1 + j * a2 + k * a3 == sum) {
                System.out.println(i + "," + j + "," + k);
            }
        }
    }
}

为了将其推广到 N 个变量的情况，您需要转换为递归形式。

对于某些函数f，该算法是O(f(size, a)^N)。

• 我们可以按如下方式在 f 上设置界限：size / MaxValue(a) <= f(size, a) <= size / MinValue(a)。
• 在最坏的情况下（所有 a[i] 都是 1），f(size, a) 是 size< /代码>。

无论哪种方式，对于较大的 N 值来说，这都是相当可怕的。因此，虽然递归 N 变量算法会更优雅，但它可能不太实用。

---

如果您愿意向 Springer Verlag 支付 34 欧元，这里有一篇论文的链接，其中（根据摘要）包括解决 N 变量情况的算法。

Answer 6

要么没有解，要么有无限多个解。通常情况下，您有解决方案必须匹配的额外约束。您的问题是否属于这种情况？

让我们从最简单的情况开始，有两个未知数 a*x + b*y = c：

第一步是使用 欧几里得算法来求a和b的GCD，我们称之为d 。作为奖励，该算法提供了 x' 和 y'，使得 a*x' + b*y' = d。如果 d 不能整除 c，则无解。否则，解决方案是：

x = x' * (c/d)
y = y' * (c/d)

第二步，找到所有解决方案。这意味着我们必须找到所有 p 和 q，使得 a*p + b*q = 0。如果 (x,y) 和 (X, Y) 都是解，那么

a * (X-x) + b * (Y-y) = 0

答案是 p = b/d 并且q = -a/d 其中 d = GCD(a,b) 并且已在步骤 1 中计算出来。现在的通用解决方案是：

x = x' * (c/d) + n * (b/d)
y = y' * (c/d) - n * (a/d)

其中 n 是整数。

第一步很容易扩展到多个变量。我不确定是否可以概括第二步。我的第一个猜测是找到所有系数对的解决方案并将这些解决方案组合起来。

Answer 7

这是 Perl 中的解决方案。而是使用正则表达式进行黑客攻击。

按照此博客帖子使用正则表达式求解代数方程。

我们可以使用以下脚本

#!/usr/bin/perl
$_ = 'o' x 40;
$a = 'o' x 3;
$b = 'o' x 2;
$c = 'o' x 5;
$_ =~ /^((?:$a)+)((?:$b)+)((?:$c)+)$/;
print "x = ", length($1)/length($a), "\n";
print "y = ", length($2)/length($b), "\n";
print "z = ", length($3)/length($c), "\n";

输出 3x + 2y + 5z = 40： x=11, y = 1, z = 1

著名的 最古老的钢琴谜题最终是一个 3 变量方程

此方法适用于 条件变量实际上为正且常数为正。

Answer 8

没有库可以执行此操作的原因类似于您找不到库来执行排列的原因 - 您生成了如此多的数据，这可能是错误的做法。

更准确地说，如果您有 n 个变量，其总和为 X，那么您将拥有 O(Xn-1)答案。 X 和 n 不必非常大，这也会成为问题。

也就是说，这里有一些 Python 可以相当有效地计算出对答案进行编码的所有必要信息：

def solve_linear_diophantine (*coeff_tuple):
    coeff = list(coeff_tuple)
    constant = coeff.pop()

    cached = []
    for i in range(len(coeff)):
        # Add another cache.
        cached.append({})

    def solve_final (i, remaining_constant):
        if remaining_constant in cached[i]:
            return cached[i][remaining_constant]
        answer = []
        if i+1 == len(coeff):
            if 0 == remaining_constant%coeff[i]:
                answer = [(remaining_constant/coeff[i], [])]
        else:
            for j in range(remaining_constant/coeff[i] + 1):
                finish = solve_final(i+1, remaining_constant - j*coeff[i])
                if finish is not None:
                    answer.append((j, finish))
        if 0 == len(answer):
            cached[i][remaining_constant] = None
            return None
        else:
            cached[i][remaining_constant] = answer
            return answer

    return solve_final(0, constant)

当我说“编码”时，数据结构如下所示。对于每个可能的系数，我们将获得一个 (coefficient, [subanswers]) 数组。只要有可能，它就会重用子答案以使数据结构尽可能小。如果你不能，你可以递归地将其扩展回一系列答案，这样做会非常高效。 （事实上​​，它的复杂度为O(nX)。）您只需很少的逻辑重复就能一遍又一遍地发现相同的事实。 （但是，返回的列表可能会变得非常大，因为要返回大量答案。）