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

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

Answer 2

Я случайно написал для этого 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;
    }

}

Answer 3

Это математический вопрос, а не программный. Если у вас есть подходящий алгоритм, его реализация не должна быть слишком сложной.

Я предлагаю вам погулять по диофантовым уравнениям.

Я нашел объяснение для вас.

Answer 4

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

После этого блога post для решения алгебраических уравнений с использованием 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";

вывод: x = 11, y = 1, z = 1

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

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

Answer 5

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

Начнем с самой простой ситуации, когда есть два неизвестных 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 - целое число.

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

Answer 6

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

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

---

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

Answer 7

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

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

гг.

взято из: Wolfram MathWorld

Answer 8

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

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