В Java для некоторой общей упрощенной реализации потребуется по крайней мере два класса:
Некоторый делегат для перехода к рекурсивному алгоритму, чтобы вы могли получать обновления, где бы ни находилось выполнение.Что-то вроде:
public interface IDelegate {
public void found(List<CombinationFinder.FoundElement> nstack);
}
Реализация для , что-то вроде:
public class CombinationFinder {
private CombinationFinder next;
private int multiplier;
public CombinationFinder(int multiplier) {
this(multiplier, null);
}
public CombinationFinder(int multiplier, CombinationFinder next) {
this.multiplier = multiplier;
this.next = next;
}
public void setNext(CombinationFinder next) {
this.next = next;
}
public CombinationFinder getNext() {
return next;
}
public void search(int max, IDelegate d) {
Stack<FoundElement> stack = new Stack<FoundElement>();
this.search(0, max, stack, d);
}
private void search(int start, int max, Stack<FoundElement> s, IDelegate d) {
for (int i=0, val; (val = start + (i*multiplier)) <= max; i++) {
s.push(i);
if (null != next) {
next.search(val, max, s, d);
} else if (val == max) {
d.found(s);
}
s.pop();
}
}
static public class FoundElement {
private int value;
private int multiplier;
public FoundElement(int value, int multiplier) {
this.value = value;
this.multiplier = multiplier;
}
public int getValue() {
return value;
}
public int getMultiplier() {
return multiplier;
}
public String toString() {
return value+"*"+multiplier;
}
}
}
И, наконец, для настройки и запуска (тестирования):
CombinationFinder a1 = new CombinationFinder(20);
CombinationFinder a2 = new CombinationFinder(5);
CombinationFinder a3 = new CombinationFinder(10);
a1.setNext(a2);
a2.setNext(a3);
a1.search(100, new IDelegate() {
int count = 1;
@Override
public void found(List<CombinationFinder.FoundElement> nstack) {
System.out.print("#" + (count++) + " Found : ");
for (int i=0; i<nstack.size(); i++) {
if (i>0) System.out.print(" + ");
System.out.print(nstack.get(i));
}
System.out.println();
}
}
});
Выводит 36 решений.
С помощью этой концепции вы можете иметь столько внутренних циклов, сколько хотите, и даже настраивать каждый из них, если хотите через наследование.Вы можете даже без проблем использовать объекты (например: a1.setNext(a1);).
** ОБНОВЛЕНИЕ **
Просто потому, что мне нравится monty *Решение 1028 * , я не смог устоять перед его тестированием, и вот результат, немного подправленный.
ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ всекредиты идут на Монти для алгоритма
public class PolynomialSolver {
private SolverResult delegate;
private int min = 0;
private int max = Integer.MAX_VALUE;
public PolynomialSolver(SolverResult delegate) {
this.delegate = delegate;
}
public SolverResult getDelegate() {
return delegate;
}
public int getMax() {
return max;
}
public int getMin() {
return min;
}
public void setRange(int min, int max) {
this.min = min;
this.max = max;
}
public void solve(int[] constants, int total) {
solveImpl(constants, new int[constants.length], total, 0, 0);
}
private void solveImpl(int[] c, int[] v, int t, int n, int r) {
if (n == c.length) { //your end condition for the recursion
if (r == t) {
delegate.solution(c, v, t);
}
} else if (r <= t){ //keep going
for (int i=min, j; (i<=max) && ((j=r+c[n]*i)<=t); i++) {
v[n] = i;
solveImpl(c, v, t, n+1, j);
}
}
}
static public interface SolverResult {
public void solution(int[] constants, int[] variables, int total);
}
static public void main(String...args) {
PolynomialSolver solver = new PolynomialSolver(new SolverResult() {
int count = 1;
@Override
public void solution(int[] constants, int[] variables, int total) {
System.out.print("#"+(count++)+" Found : ");
for (int i=0, len=constants.length; i<len; i++) {
if (i>0) System.out.print(" + ");
System.out.print(constants[i]+"*"+variables[i]);
}
System.out.println(" = " + total);
}
});
// test some constants = total
solver.setRange(-10, 20);
solver.solve(new int[] {20, 5, 10}, 100); // will output 162 solutions
}
}