Решение линейного диофантова уравнения (примеры см. в описании)

Рекурсия грубой силы является опцией, в зависимости от того, насколько большим вы позволите стать значению или количеству значений.

Предположения: вводимые пользователем данные (множимое) всегда являются различными положительными целыми числами. Находимые коэффициенты должны быть целыми неотрицательными числами.

Алгоритм:

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;
    }

}

Добавляя к очень точному ответу Класа:

10-я проблема Гильберта спрашивала, существует ли алгоритм для определения того, имеет ли решение произвольное диофантово уравнение. Такой алгоритм существует для решения диофантовых уравнений первого порядка. Однако невозможность получения общего решения доказал Юрий Матиясевич в 1970 г.

взято из: Wolfram MathWorld

Алгоритм грубой силы выглядит следующим образом (случай с 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] равны 1) f(size, a) равно size.

В любом случае, это довольно ужасно для больших значений N. Таким образом, хотя рекурсивный алгоритм с N-переменной был бы более элегантным, он, вероятно, не очень практичен.

Если вы готовы раскошелиться на 34 евро в пользу Springer Verlag, вот ссылка на статью, (согласно аннотации) включает алгоритм решения случая N переменных.

Решений либо нет, либо бесконечно много. Часто бывает так, что у вас есть дополнительное ограничение, которому должно соответствовать решение. Так ли это в вашей проблеме?

Начнем с самой простой ситуации, когда есть два неизвестных a*x + b*y = c:

Первый шаг заключается в использовании алгоритма Евклида для нахождения НОД a и b, назовем его d. В качестве бонуса алгоритм предоставляет x' и y', так что a*x' + b*y' = d. Если d не делит c, то решения нет. В противном случае решение:

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

Второй шаг – найти все решения. Это означает, что мы должны найти все p и q такие, что 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 — целое число.

Первый шаг легко распространить на несколько переменных. Я не уверен в обобщении второго шага. Моим первым предположением было бы найти решение для всех пар коэффициентов и объединить эти решения.

Это решение на Perl. скорее взломать с помощью Regex.

После этого блога пост для решения алгебраических уравнений с использованием регулярных выражений.

мы можем использовать следующий скрипт для 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";

вывод: х=11, у = 1, г = 1

знаменитая головоломка Самый старый играет на пианино заканчивается уравнением с тремя переменными

Этот метод применяется для условия, переменные на самом деле положительны, а константа положительна.

Причина, по которой нет библиотеки, которая делает это, аналогична тому, почему вы не найдете библиотеку для выполнения перестановок - вы генерируете так много данных, что это, вероятно, неправильно.

Точнее, если у вас есть n переменных, сумма которых составляет X, то у вас будет O(Xn-1) ответов. X и n не обязательно должны быть очень большими, чтобы это стало проблемой.

Тем не менее, вот пример 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).) Вы будете очень мало повторять логику, чтобы открывать одни и те же факты снова и снова. (Однако возвращаемый список может стать очень большим просто потому, что существует большой список возвращаемых ответов.)