解决线性丢番图方程（详见示例）

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编写的，那就更酷了！算法/伪代码也可以。非常感谢。

- pavanlimo

---

很抱歉我的数学术语不好，已经有很长时间没做了。我正在尝试根据某些限制（对于其他人来说很复杂和不必要）随机生成一份试卷。我已经尽可能地使这个问题独立并简化了。 - pavanlimo

投票关闭；与编程无关。应该在类似math.stackexchange.com的网站上发布。 - Adam Robinson

我正在寻找以编程方式解决这个问题。在Klas的回答之后，我正在寻找解决丢番图方程的代码。在我看来，这绝对与编程有关。 - pavanlimo

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

- Dave Costa

---

请查看以下链接以获取上述算法的实现 - https://dev59.com/UG035IYBdhLWcg3wSN8G#6704483 - pavanlimo

这很糟糕。对于任何算法的扩展，都应该并且必须考虑到缩放问题。想象一下有多少程序员和软件开发人员遇到了同样的问题，将这个指数算法应用到他们的项目中。这更糟糕。如果您正在阅读此内容，请首先研究线性丢番图方程，尽管实现复杂，但是它是值得的。它属于整数规划代数学。 - D. Sikilai

真是太疯狂了，在数学堆栈交换中，有一个更好的答案需要在'A'矩阵上进行单模行操作或类似操作。但是提问者已经被踩了，所以可能很难找到这个问题。只需在理解数学后实现即可。 - D. Sikilai

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;
    }

}

- pavanlimo

---

该解决方案基于@Dave Costa（已接受）对问题的回答。 - pavanlimo

仅运行上述示例似乎显示了代码/算法存在一些问题。打印出许多总数！= 30，暗示着某种问题。 - Freddie Witherden

是的，我对上面的代码进行了一些小改动。不幸的是，我不记得在哪里做出了更改，也无法访问那段代码。 - pavanlimo

Answer 3

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

我建议您在谷歌上搜索“丢番图方程”。

我为您找到了一个解释。

- Klas Lindbäck

---

我认为这个问题是关于在Java中实现解决方案的，因此这是一个编程问题。为任意数量的可能系数实现解决方案似乎是一个有趣和相关的编码问题。提供一个链接比说“去谷歌一下”更有用。例如：http://mathworld.wolfram.com/DiophantineEquation.html - Steve

@Steve：这基本上是一个数学问题；问题与Java无关（无论使用什么算法，它都是相同的，不受语言影响）。 - Adam Robinson

根据常见问题解答中的描述：“如果你的问题通常涉及软件算法……那么你就来对了地方”。虽然这个问题可能不是针对Java特定的，但是提问者正在寻求一个软件算法，因此它是相关的。 - Steve

各位，是否有现成的代码库可以解决线性丢番图方程？我尝试过谷歌搜索，但没有结果。 - pavanlimo

Answer 4

一个暴力算法如下（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变量算法可能更优雅，但它可能不太实用。

---

如果你愿意花34欧元购买Springer Verlag的论文，这里有一篇论文链接，根据摘要，其中包含了解决N个变量情况的算法。

- Stephen C

---

感谢@Stephen提供的解决方案，我会尝试看看是否已经存在一些库。如果您找到了任何信息，请告诉我。 - pavanlimo

为什么i、j和/或k不能为负数？ - Justin Peel

如果它们可以是负数，那么就会有无限多个解。 （实际上，如果N>1并且存在任何一个解，则会有无限多个解。有一个简单的构造证明了这一点。） - Stephen C

@pavanlimo - 你的程序包括了对该主题先前文献的调查、正式的正确性证明、正式的复杂度分析和基准测试吗？ - Stephen C

Answer 5

有时候会出现没有解或者无限多解的情况。通常情况下，你需要额外的限制条件来匹配解。在你的问题中是否存在这种情况呢？

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

第一步是使用欧几里得算法来找到a和b的最大公约数，我们称之为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是一个整数。

第一步很容易扩展到多个变量。对于第二步的泛化我不太确定。我的第一个猜测是找到所有系数对的解，并将这些解组合起来。

- Elian Ebbing

Answer 6

这是一个Perl的解决方案。通过使用正则表达式进行“hack”操作。

按照这篇博客 post 中的方法，使用正则表达式解决代数方程。

我们可以使用以下脚本来解决3x + 2y + 5z = 40。

#!/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";

输出：x=11，y=1，z=1

著名的最老的弹钢琴难题最终变成了一个三元方程。

这种方法适用于变量实际上是正数且常数为正的条件。

- Chinmay Lokesh

---

这个如何扩展？我相信大数值会非常慢。 - Thorbjørn Ravn Andersen

Answer 7

续克拉斯的非常准确的答案：

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

摘自：沃尔夫勒姆数学世界

- posdef

---

我认为他在谈论非线性丢番图方程。对于线性丢番图方程，这应该是可能的。 - pavanlimo

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)

当我说“编码”时，数据结构看起来像这样。对于每个可能的系数，我们将得到一个(系数，[子答案])数组。尽可能地重用子答案以使数据结构尽可能小。如果无法重用，则可以递归地将其展开为答案数组，并且这样做会非常高效。 （实际上是O(nX)）。您将很少重复逻辑以发现相同的事实。 （但是返回的列表可能会变得非常大，仅因为有要返回的大量答案列表。）

- btilly