求解线性不定方程(见示例说明)

Question

让我首先澄清一下(在你们解雇我之前),这不是一个家庭作业问题而且我不是大学生.:)

编辑 感谢@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,没有什么可以更酷!算法/伪代码也可以.非常感谢.

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