求解线性丢番图方程（参见实例说明）
让我先澄清一下（在你们解雇我之前），这不是一个家庭作业问题而且我不是大学生。 🙂
编辑感谢@Klas和其他人，我的问题现在归结为一个需要以编程方式解决的数学方程式。
我正在寻找一种解决Linear Diophantine Equation的算法/代码。 对于像我这样的小凡人，这里的方程式如下：
例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，没有什么可以更酷！ 算法/伪代码也可以。 非常感谢。
强制递归是一种选择，具体取决于允许值或值数量变大的程度。
假设：用户输入（被乘数）总是不同的正整数。 要找到的系数必须是非负整数。
算法：
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
这是一个数学问题而不是编程问题。 一旦你有了一个合适的算法，那么它的强制性就不会太难了。
我建议你谷歌关于丢番图方程。
我找到了你的解释 。
我碰巧为此编写了Java代码。 请自便。 这些解决方案尚未经过广泛测试，但到目前为止似乎运行良好。
package expt.qp; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map; public class LinearDiophantine { private Map sol = new LinkedHashMap(); private Map coeff = new HashMap(); /** * @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 coeffCopy = new HashMap(ld.coeff); int total=30; // Real algo begins here ld.findPossibleSolutions(total, coeffCopy); } private void findPossibleSolutions(int total, Map 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 coeffCopy = new HashMap(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 coeff) { int largestKey = coeff.keySet().iterator().next(); for(int i : coeff.keySet()) { if(coeff.get(i)>coeff.get(largestKey)) { largestKey=i; } } return largestKey; } }
加上Klas非常准确的答案：
希尔伯特的第10个问题询问是否存在用于确定任意丢番图方程是否具有解的算法。 对于一阶丢番in方程的解，确实存在这样的算法。 然而，Yuri Matiyasevich在1970年certificate了无法获得一般解决方案
取自： Wolfram MathWorld
蛮力算法如下（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变量大小写，您需要转换为递归forms。
对于某些函数f O(f(size, a)^N)该算法是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变量案例的算法。
没有或无限多的解决方案。 通常情况下，您有一个解决方案必须匹配的额外约束。 你的问题就是这种情况吗？
让我们从最简单的情况开始，其中有两个未知的情况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 * (Xx) + b * (Yy) = 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是整数。
第一步很容易扩展到多个变量。 我不确定第二步的概括。 我的第一个猜测是找到所有系数对的解决方案并组合这些解决方案。
这是Perl的解决方案。 而不是使用正则表达式的黑客攻击。
在此博客文章之后使用正则表达式解决代数方程。
我们可以使用以下脚本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
着名的Oldest戏剧钢琴拼图最终成为一个3变量方程式
该方法适用于变量实际为正且常数为正的条件。
没有库这样做的原因类似于为什么你不会找到一个库来进行排列 – 你生成了太多的数据，这可能是错误的做法。
更确切地说，如果你有n变量的总和为X ，那么你将得到O(X n-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])数组。 只要有可能，它会重用subanswers以使数据结构尽可能小。 如果你不能，你可以递归地将它扩展回一系列答案，这样你就会非常高效。 （实际上它是O(nX) 。）你会很少重复逻辑来反复发现相同的事实。 （但是返回的列表可能会变得非常大，因为有大量的答案要返回。）