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

一尘不染

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

algorithm

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

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

阅读 540

2020-07-28

共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

2020-07-28