Алгоритм решения диофантовых уравнений c

Линейное диофантово уравнение и 4 способа его решения

Разделы: Математика

Првило 1. Если с не делится на d, то уравнение ах + ву = с не имеет решений в целых числах. Н.О.Д.(а,в) = d.

Правило 2. Чтобы найти решение уравнения ах + ву = с при взаимно-простых а и в, нужно сначала найти решение (Х_о ; у_о) уравнения ах + ву = 1; числа СХ_о , Су_о составляют решение уравнения ах + ву = с.

Решить в целых числах (х,у) уравнение

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

Знаем, что если Н.О.Д.(а;в) =1, т.е. а и в взаимно-простые числа, то уравнение (1)

имеет решение в целых числах х и у. Н.О.Д.(5;8) =1. Методом подбора находим частное решение: Х_о = 7; у_о =2.

Итак, пара чисел (7;2) — частное решение уравнения (1).

Значит, выполняется равенство: 5 x 7 – 8 x 2 = 19 … (2)

Вопрос: Как имея одно решение записать все остальные решения?

Вычтем из уравнения (1) равенство (2) и получим: 5(х -7) – 8(у — 2) =0.

Отсюда х – 7 = . Из полученного равенства видно, что число (х – 7) будет целым тогда и только тогда, когда (у – 2) делится на 5, т.е. у – 2 = 5n, где n какое-нибудь целое число. Итак, у = 2 + 5n, х = 7 + 8n, где n Z.

Тем самым все целые решения исходного уравнения можно записать в таком виде:

n Z.

Второй способ. Решение уравнения относительно одного неизвестного.

Решаем это уравнение относительно того из неизвестных, при котором наименьший (по модулю) коэффициент. 5х — 8у = 19 х = .

Остатки при делении на 5: 0,1,2,3,4. Подставим вместо у эти числа.

Если у = 0, то х = =.

Если у =1, то х = =.

Если у = 2, то х = = = 7 Z.

Если у =3, то х = =.

Если у = 4 то х = =.

Итак, частным решением является пара (7;2).

Тогда общее решение: n Z.

Третий способ. Универсальный способ поиска частного решения.

Для решения применим алгоритм Евклида. Мы знаем, что для любых двух натуральных чисел а, в, таких, что Н.О.Д.(а,в) = 1 существуют целые числа х,у такие, что ах + ву = 1.

1. Сначала решим уравнение 5m – 8n = 1 используя алгоритм Евклида.

2. Затем найдем частное решение уравнения (1)по правилу 2.

3. Запишем общее решение данного уравнения (1).

1. Найдем представление: 1 = 5m – 8n. Для этого используем алгоритм Евклида.

8 = 5 1 + 3.

5 = 3

3 = 2 .

Из этого равенства выразим 1. 1 = 3 — 2 = 3 – (5 — 3 ) =

= 3 — 5 = 3 = (8 — 5 — 5 82 -5

= 5(-2). Итак, m = -3, n = -2.

2. Частное решение уравнения (1): Х_о = 19m; у_о =19n.

Отсюда получим: Х_о =19; у_о =19 .

Пара (-57; -38)- частное решение (1).

3. Общее решение уравнения (1): n Z.

Четвертый способ. Геометрический.

1. Решим уравнение 5х – 8у = 1 геометрически.

2. Запишем частное решение уравнения (1).

3. Запишем общее решение данного уравнения (1).

Отложим на окружности последовательно друг за другом равные дуги, составляющие

-ю часть полной окружности. За 8 шагов получим все вершины правильного вписанного в окружность 8-угольника. При этом сделаем 5 полных оборотов.

На 5 – ом шаге получили вершину, соседнюю с начальной, при этом сделали 3 полных оборота и еще прошли — ю часть окружности, так что х = у + .

Итак, Х_о = 5, у_о =3 является частным решением уравнения 5х – 8у = 1.

2. Частное решение уравнения (1): Х_о = 19 у_о =19

3. Общее решение уравнения (1): n Z.

Линейные диофантовы уравнения

Диофантово уравнение — это полиномиальное уравнение, обычно с двумя или более неизвестными, так что требуются только интегральные решения. Интегральное решение — это такое решение, при котором все неизвестные переменные принимают только целые значения.

Даны три целых числа a, b, c, представляющих линейное уравнение вида: ax + by = c. Определите, имеет ли уравнение такое решение, чтобы x и y были целыми значениями.

Примеры :

Решение:
Для линейных уравнений диофантовых уравнений интегральные решения существуют тогда и только тогда, когда GCD коэффициентов двух переменных делит постоянный член идеально. Другими словами, интегральное решение существует, если GCD (a, b) делит c.

Таким образом, алгоритм определения наличия интегрального решения уравнения довольно прост.

• Найти ГКД а и б
• Проверьте, если c% GCD (a, b) == 0
• Если да, то напечатайте Возможно
• Иначе печать невозможна

Ниже приведена реализация вышеуказанного подхода.

// C ++ программа для проверки растворов диофанта
// уравнения
#include

using namespace std;

// функция полезности для поиска GCD из двух чисел

int gcd( int a, int b)

return (a%b == 0)? abs (b) : gcd(b,a%b);

// Эта функция проверяет, являются ли интегральные решения
// возможно

bool isPossible( int a, int b, int c)

return (c%gcd(a,b) == 0);

int a = 3, b = 6, c = 9;

isPossible(a, b, c)? cout «Possible\n» :

cout «Not Possible\n» ;

isPossible(a, b, c)? cout «Possible\n» :

cout «Not Possible\n» ;

isPossible(a, b, c)? cout «Possible\n» :

cout «Not Possible\n» ;

// Java-программа для проверки решений
// диофантовы уравнения

// Сервисная функция для поиска GCD

static int gcd( int a, int b)

// Эта функция проверяет, является ли интеграл

static boolean isPossible( int a,

return (c % gcd(a, b) == 0 );

public static void main (String[] args)

int a = 3 , b = 6 , c = 9 ;

if (isPossible(a, b, c))

System.out.println( «Not Possible» );

a = 3 ; b = 6 ; c = 8 ;

if (isPossible(a, b, c))

System.out.println( «Not Possible» );

a = 2 ; b = 5 ; c = 1 ;

if (isPossible(a, b, c))

System.out.println( «Not Possible» );

// Этот код предоставлен anuj_67.

# Программа Python 3 для проверки решений
# диофантовых уравнений

from math import gcd

# Эта функция проверяет, является ли интеграл
# возможны решения

def isPossible(a, b, c):

return (c % gcd(a, b) = = 0 )

if __name__ = = ‘__main__’ :

if (isPossible(a, b, c)):

print ( «Not Possible» )

if (isPossible(a, b, c)):

print ( «Not Possible» )

if (isPossible(a, b, c)):

print ( «Not Possible» )

# Этот код предоставлен
# Surendra_Gangwar

// C # программа для проверки
// растворы диофантина
// уравнения

// Сервисная функция для поиска

// ГКД из двух чисел

static int gcd( int a, int b)

// Эта функция проверяет

// если интегральные решения

static bool isPossible( int a,

return (c % gcd(a, b) == 0);

public static void Main ()

int a = 3, b = 6, c = 9;

if (isPossible(a, b, c))

Console.WriteLine( «Not Possible» );

if (isPossible(a, b, c))

Console.WriteLine( «Not Possible» );

if (isPossible(a, b, c))

Console.WriteLine( «Not Possible» );

// Этот код предоставлен anuj_67.

// PHP программа для проверки решений
// диофантовы уравнения

// функция полезности для поиска
// GCD из двух чисел

function gcd( $a , $b )

return ( $a % $b == 0) ?

abs ( $b ) : gcd( $b , $a % $b );

// Эта функция проверяет, является ли интеграл
// возможны решения

function isPossible( $a , $b , $c )

return ( $c % gcd( $a , $b ) == 0);

if (isPossible( $a , $b , $c ) == true)

echo «Not Possible\n» ;

if (isPossible( $a , $b , $c ) == true)

echo «Not Possible\n» ;

if (isPossible( $a , $b , $c ) == true)

echo «Not Possible\n» ;

// Этот код предоставлен ajit ..
?>

Выход :

Как это работает?
Пусть GCD из «a» и «b» будет «g». г делит а и б. Это означает, что g также делит (ax + на) (если x и y являются целыми числами). Это подразумевает, что gcd также делит ‘c’, используя отношение ax + by = c. Обратитесь к этой вики-ссылке для более подробной информации.

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

позвольте мне начать с разъяснения того, что (прежде чем вы, ребята, уволите меня), это не проблема домашней работы, и я не студент университета. 🙂

редактировать Благодаря @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, ничто не может быть круче!. Алгоритм/псевдо-код также будет делать. Спасибо.

8 ответов

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

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

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

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

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

я случайно написал Java-код для этого. Пожалуйста, угощайтесь. Решения широко не тестируются, но, похоже, до сих пор работают хорошо.

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

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

алгоритм грубой силы выглядит следующим образом (3 переменных случая):

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

этот алгоритм O(f(size, a)^N) для некоторой функции f .

• мы можем установить границы f следующим образом: size / MaxValue(a) .
• в худшем случае (когда все a[i] С 1 ) f(size, a) is size .

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

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

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

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

первым шагом является использование алгоритм Евклида чтобы найти GCD a и b , назовем его d . В качестве бонуса алгоритм предоставляет x’ и y’ такие, что a*x’ + b*y’ = d . Если d не делит c , то решения нет. В противном случае решение:

второй шаг-найти все решения. Это означает, что мы должны найти все p и q такое, что a*p + b*q = 0 . Если оба (x,y) и (X, Y) решения, то

ответ p = b/d и q = -a/d здесь d = GCD(a,b) и уже рассчитывается на шаге 1. Общее решение теперь:

где n является целым числом.

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

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

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

мы можем использовать следующий скрипт для 3x + 2y + 5z = 40

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

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

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

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

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

тем не менее, вот некоторые Python, который довольно эффективно вычисляет все необходимая информация для кодирования ответа:

когда я говорю «кодировать», структура данных выглядит так. Для каждого возможного коэффициента, мы получим массив (coefficient, [subanswers]) . Когда это возможно, он повторно использует subanswers, чтобы сделать структуру данных как можно меньше. Если вы не можете рекурсивно развернуть это обратно в массив ответов, и при этом вы будете довольно эффективны. (На самом деле это O(nX) .) Вы будете делать очень мало повторения логики, чтобы обнаружить то же самое факты снова и снова. (Однако возвращаемый список может получить очень большой просто потому, что есть большой список ответов, которые должны быть возвращены.)