让我先澄清一下 (在你们解雇我之前),这不是家庭作业问题,我也不是大学生。:)
编辑感谢 @ 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<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;
}
}
加上 Klas 非常准确的答案:
Hilbert ’ s 10th problem asked if an algorithm existed for determining whether an arbitrary Diophantine equation have a solution.Such an algorithm does exist for the solution of first-order Diophantine equations.However,the impossib
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(53条)