2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Матлаб: как получить все решения диофантова уравнения?
Сообщение12.10.2023, 18:20 
Стандартный решатель solve выдает первое найденное решение и закачивает работу:
Используется синтаксис Matlab M
n=25;
% === Условия на переменные ===
syms x y integer
assumeAlso(x>0)
assumeAlso(y>0)
% === Уравнение ===============
eq=3*x+4*y==n ;
S=solve(eq,x,y);
x=S.x
y=S.y
На выходе получаем решение 7 и 1. Проблема в том, что оно не единственно - есть еще 3 и 4.
Как заставить Матлаб выдавать все решения?

 
 
 
 Re: Матлаб: как получить все решения диофантова уравнения?
Сообщение13.10.2023, 03:13 
Аватара пользователя
Я не знаток Матлаба, но могу предложить решение для данного случая. Посмотрите на картинку в оффтопе.

(Оффтоп)

Изображение

Наклонные прямые линии задаются уравнениями $3x+4y=n$. Каждой прямой соответствует своё $n$, и оно указано в жёлтых кружочках. Одновременно кружочки отмечают целочисленные решения уравнения для "своих" $n$.
Например, кружочек с числом $17$ стоит на прямой $3x+4y=17$, а его координаты $x=3,y=2$ — решение этого уравнения.

Будем перечислять решения в порядке возрастания $x$ (т.е. убывания $y$). Сначала учтём условие $x>0$, но проигнорируем условие $y>0$. Тогда для каждого $n$ получится следующее.
1) Имеется решение с минимальным значением $x$. Обозначим это значение $x_0$. Оно равно $1,2,3$ или $4$, и определяется остатком от деления $n$ на $4$. (Это видно по картинке: например, $x_0=3$ для значений $n=13,17,21,25,29,...$, которые идут "через 4".) Зная $x_0$, сразу находим соответствующее $y_0=\frac{n-3x_0}{4}$.
2) Если $(x,y)$ — решение, то следующее решение будет $(x+4,y-3)$. Тогда общая формула для всех решений будет
$x_n=x_0+4n$
$y_n=y_0-3n$

Дальше легко найти максимальное $n$, при котором выполняется условие $y_n>0$. Ниже в скрипте оно обозначено nf. Соответствующие $x,y$ обозначены xf и yf. Если nf получилось отрицательным, то решений нет, скрипт в этом случае выдаёт пустую матрицу.
В итоге:
Используется синтаксис Matlab M
n=25;
x0=4-mod(n,4);
y0=(n-3*x0)/4;
nf=floor((y0-1)/3);
xf=x0+nf*4;
yf=y0-nf*3;
x=x0:+4:xf;
y=y0:-3:yf;
Sol=[x' y']

 
 
 
 Re: Матлаб: как получить все решения диофантова уравнения?
Сообщение13.10.2023, 13:02 
Аватара пользователя
svv в сообщении #1613367 писал(а):
Тогда общая формула для всех решений будет
$x_n=x_0+4n$
$y_n=y_0-3n$

Дальше легко найти максимальное $n$, при котором выполняется условие $y_n>0$.
Ой, конечно же, надо было обозначить другой буквой:
$x_k=x_0+4k$
$y_k=y_0-3k$
Дальше легко найти максимальное $k$, при котором выполняется условие $y_k>0$.

 
 
 
 Re: Матлаб: как получить все решения диофантова уравнения?
Сообщение13.10.2023, 14:48 
Спасибо конечно, но есть одна проблема - мне нужно реализовать в Матлабе общий случай, то есть для произвольного числа переменных и произвольной верхней планки коэффициента при каждой переменной . Если заставить Матлаб выдавать все решения, то я понимаю как это сделать, если же идти по предложенному Вами пути - не понимаю. Буду признателен за подсказку!

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group