10

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

编辑 感谢@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 中，没有什么比这更酷了！算法/伪代码也可以。非常感谢。

4

8 回答 8

3

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

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

算法：

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
于 2011-04-01T12:39:20.647 回答
2

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

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

我为你找到了解释。

于 2011-04-01T12:29:29.580 回答
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;
    }

}
于 2011-07-15T08:35:52.260 回答
1

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

希尔伯特的第 10 个问题询问是否存在确定任意丢番图方程是否有解的算法。这种算法确实存在用于求解一阶丢番图方程。然而，Yuri Matiyasevich 在 1970 年证明了获得一般解决方案的不可能性

取自：Wolfram MathWorld

于 2011-04-01T12:39:39.993 回答
1

蛮力算法如下（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 变量情况进行推广，您需要转换为递归形式。

该算法适用O(f(size, a)^N)于某些功能f。

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

无论哪种方式，这对于N. 因此，虽然递归 N 变量算法会更优雅，但它可能不太实用。

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

于 2011-04-01T12:40:57.027 回答
1

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

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

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

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

第二步是找到所有解决方案。这意味着我们必须找到 all pand qsuch that 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 是一个整数。

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

于 2011-04-03T07:34:06.247 回答
1

这是 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

著名的最古老的钢琴拼图最终变成了一个 3 变量方程

This method applies for a condition that the variables are actually positive and the constant is positive.

于 2013-08-09T01:59:41.413 回答
0

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

更准确地说，如果您有n总和为 的变量X，那么您将得到答案。 并且不必很大，这会成为一个问题。O(Xn-1)Xn

也就是说，这里有一些 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)。）你将做很少的逻辑重复来一遍又一遍地发现相同的事实。（但是返回的列表可能会变得非常大，因为要返回的答案列表很大。）

于 2011-04-03T06:33:11.193 回答