Всем привет! Пока решал одну задачу наткнулся на такую проблему:
ax+by+cz+dk...=sum Нужно вычислить кол-во решений в натуральных числах.
С клавиатуры вводится sum , коеффициенты(в данном случае это(x,y,z,k...), и кол-во данных коеффициентов, а значит кол-во слагаемых.
Понял вот что создаем 2 массива: один с коеффициентами, другой, забитый нулями , с a,b,c,d.... ТАк вот в чем загвоздка:
Не получается сделать нормальный цикл чтобы перебирались все значения, те чтобы сначала d+1 до dk=sum далее c+1 , потом снова d+1 д dk-sum.
Короче метод счет. Как это сделать, если количество любое ( до 500) !
Заранеее спасибо.
Полная версия: Кол-во решений линейного уравнения.
Вместо цикла - рекурсия.
Цитата(Федосеев Павел @ 4.01.2015 18:46) 
Вместо цикла - рекурсия.
Ок, попробую
Я попробовал решить примерно так.
На входе:
a - массив коэффициентов линейного диофантового уравнения (все значащие >=1)
n - размер массива
sum - сумма
На выходе:
Count - количество решений
Чтобы не было разночтений, приведу вид уравнения, которое решается
a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]=sum,
где
a[i] - коэффициенты уравнения, все a[i]>=1
x[i] - искомые переменные, все x[i]>=1.
Это решение линейного диофантового уравнения со следующими ограничениями:
- коэффициенты - натуральные числа (>=1);
- решения x ищутся на множестве натуральных чисел (>=1).
PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк).
На входе:
a - массив коэффициентов линейного диофантового уравнения (все значащие >=1)
n - размер массива
sum - сумма
На выходе:
Count - количество решений
Чтобы не было разночтений, приведу вид уравнения, которое решается
a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]=sum,
где
a[i] - коэффициенты уравнения, все a[i]>=1
x[i] - искомые переменные, все x[i]>=1.
Код
program LinearDiophantineEquation;
const
n = 5;
type
TArray = array [1..n] of integer;
procedure ShowSolve(EtSum, n: integer; const a, x: TArray);
var
sum, i: integer;
begin
sum := 0;
for i := 1 to n do
begin
sum := sum + a[i] * x[i];
Write(a[i], '*', x[i]);
if i <> n then
Write('+');
end;
Write('=', sum);
if sum = EtSum then
writeln(' - Ok')
else
begin
writeln(' - wrong solution!');
halt;
end;
end;
{функция решает диофантово уравнение и возвращает количество решений}
function Solve(n: integer; const a: TArray; EtSum: integer): QWord;
var
Count: QWord;
x: TArray; {массив текущего решения}
function f(i, sum: integer): integer;
begin
if sum < 0 then
exit;
if i = 0 then
exit;
if i = 1 then
begin
if sum mod a[1] = 0 then
begin
Inc(Count);
x[1] := sum div a[1];
Write('Solution #', Count: 8, ' is: ');
ShowSolve(EtSum, n, a, x);
end;
end
else
begin
x[i] := 0;
repeat
Inc(x[i]);
if sum - a[i] * x[i] <= 0 then
break;
f(i - 1, sum - a[i] * x[i]);
until False;
end;
end;
begin
Count := 0;
f(n, EtSum);
Solve := Count;
end;
var
a: TArray = (1, 2, 3, 4, 5);
var
sum: integer;
Count: QWord;
begin
sum := 121;
writeln;
Count := Solve(n, a, sum);
Write('There is ', Count, ' variants of a solutions.');
end.
const
n = 5;
type
TArray = array [1..n] of integer;
procedure ShowSolve(EtSum, n: integer; const a, x: TArray);
var
sum, i: integer;
begin
sum := 0;
for i := 1 to n do
begin
sum := sum + a[i] * x[i];
Write(a[i], '*', x[i]);
if i <> n then
Write('+');
end;
Write('=', sum);
if sum = EtSum then
writeln(' - Ok')
else
begin
writeln(' - wrong solution!');
halt;
end;
end;
{функция решает диофантово уравнение и возвращает количество решений}
function Solve(n: integer; const a: TArray; EtSum: integer): QWord;
var
Count: QWord;
x: TArray; {массив текущего решения}
function f(i, sum: integer): integer;
begin
if sum < 0 then
exit;
if i = 0 then
exit;
if i = 1 then
begin
if sum mod a[1] = 0 then
begin
Inc(Count);
x[1] := sum div a[1];
Write('Solution #', Count: 8, ' is: ');
ShowSolve(EtSum, n, a, x);
end;
end
else
begin
x[i] := 0;
repeat
Inc(x[i]);
if sum - a[i] * x[i] <= 0 then
break;
f(i - 1, sum - a[i] * x[i]);
until False;
end;
end;
begin
Count := 0;
f(n, EtSum);
Solve := Count;
end;
var
a: TArray = (1, 2, 3, 4, 5);
var
sum: integer;
Count: QWord;
begin
sum := 121;
writeln;
Count := Solve(n, a, sum);
Write('There is ', Count, ' variants of a solutions.');
end.
Это решение линейного диофантового уравнения со следующими ограничениями:
- коэффициенты - натуральные числа (>=1);
- решения x ищутся на множестве натуральных чисел (>=1).
PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк).
Цитата(Федосеев Павел @ 5.01.2015 13:35)
Я попробовал решить примерно так.
На входе:
a - массив коэффициентов линейного диофантового уравнения (все значащие >=1)
n - размер массива
sum - сумма
На выходе:
Count - количество решений
Чтобы не было разночтений, приведу вид уравнения, которое решается
a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]=sum,
где
a[i] - коэффициенты уравнения, все a[i]>=1
x[i] - искомые переменные, все x[i]>=1.
Код
program LinearDiophantineEquation;
const
n = 5;
type
TArray = array [1..n] of integer;
procedure ShowSolve(EtSum, n: integer; const a, x: TArray);
var
sum, i: integer;
begin
sum := 0;
for i := 1 to n do
begin
sum := sum + a[i] * x[i];
Write(a[i], '*', x[i]);
if i <> n then
Write('+');
end;
Write('=', sum);
if sum = EtSum then
writeln(' - Ok')
else
begin
writeln(' - wrong solution!');
halt;
end;
end;
{функция решает диофантово уравнение и возвращает количество решений}
function Solve(n: integer; const a: TArray; EtSum: integer): QWord;
var
Count: QWord;
x: TArray; {массив текущего решения}
function f(i, sum: integer): integer;
begin
if sum < 0 then
exit;
if i = 0 then
exit;
if i = 1 then
begin
if sum mod a[1] = 0 then
begin
Inc(Count);
x[1] := sum div a[1];
Write('Solution #', Count: 8, ' is: ');
ShowSolve(EtSum, n, a, x);
end;
end
else
begin
x[i] := 0;
repeat
Inc(x[i]);
if sum - a[i] * x[i] <= 0 then
break;
f(i - 1, sum - a[i] * x[i]);
until False;
end;
end;
begin
Count := 0;
f(n, EtSum);
Solve := Count;
end;
var
a: TArray = (1, 2, 3, 4, 5);
var
sum: integer;
Count: QWord;
begin
sum := 121;
writeln;
Count := Solve(n, a, sum);
Write('There is ', Count, ' variants of a solutions.');
end.
const
n = 5;
type
TArray = array [1..n] of integer;
procedure ShowSolve(EtSum, n: integer; const a, x: TArray);
var
sum, i: integer;
begin
sum := 0;
for i := 1 to n do
begin
sum := sum + a[i] * x[i];
Write(a[i], '*', x[i]);
if i <> n then
Write('+');
end;
Write('=', sum);
if sum = EtSum then
writeln(' - Ok')
else
begin
writeln(' - wrong solution!');
halt;
end;
end;
{функция решает диофантово уравнение и возвращает количество решений}
function Solve(n: integer; const a: TArray; EtSum: integer): QWord;
var
Count: QWord;
x: TArray; {массив текущего решения}
function f(i, sum: integer): integer;
begin
if sum < 0 then
exit;
if i = 0 then
exit;
if i = 1 then
begin
if sum mod a[1] = 0 then
begin
Inc(Count);
x[1] := sum div a[1];
Write('Solution #', Count: 8, ' is: ');
ShowSolve(EtSum, n, a, x);
end;
end
else
begin
x[i] := 0;
repeat
Inc(x[i]);
if sum - a[i] * x[i] <= 0 then
break;
f(i - 1, sum - a[i] * x[i]);
until False;
end;
end;
begin
Count := 0;
f(n, EtSum);
Solve := Count;
end;
var
a: TArray = (1, 2, 3, 4, 5);
var
sum: integer;
Count: QWord;
begin
sum := 121;
writeln;
Count := Solve(n, a, sum);
Write('There is ', Count, ' variants of a solutions.');
end.
Это решение линейного диофантового уравнения со следующими ограничениями:
- коэффициенты - натуральные числа (>=1);
- решения x ищутся на множестве натуральных чисел (>=1).
PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк).
Спасибо, щас разберусь!
Цитата(Федосеев Павел @ 5.01.2015 13:35)
Я попробовал решить примерно так.
На входе:
a - массив коэффициентов линейного диофантового уравнения (все значащие >=1)
n - размер массива
sum - сумма
На выходе:
Count - количество решений
Чтобы не было разночтений, приведу вид уравнения, которое решается
a[1]*x[1]+a[2]*x[2]+...+a[n]*x[n]=sum,
где
a[i] - коэффициенты уравнения, все a[i]>=1
x[i] - искомые переменные, все x[i]>=1.
Код
program LinearDiophantineEquation;
const
n = 5;
type
TArray = array [1..n] of integer;
procedure ShowSolve(EtSum, n: integer; const a, x: TArray);
var
sum, i: integer;
begin
sum := 0;
for i := 1 to n do
begin
sum := sum + a[i] * x[i];
Write(a[i], '*', x[i]);
if i <> n then
Write('+');
end;
Write('=', sum);
if sum = EtSum then
writeln(' - Ok')
else
begin
writeln(' - wrong solution!');
halt;
end;
end;
{функция решает диофантово уравнение и возвращает количество решений}
function Solve(n: integer; const a: TArray; EtSum: integer): QWord;
var
Count: QWord;
x: TArray; {массив текущего решения}
function f(i, sum: integer): integer;
begin
if sum < 0 then
exit;
if i = 0 then
exit;
if i = 1 then
begin
if sum mod a[1] = 0 then
begin
Inc(Count);
x[1] := sum div a[1];
Write('Solution #', Count: 8, ' is: ');
ShowSolve(EtSum, n, a, x);
end;
end
else
begin
x[i] := 0;
repeat
Inc(x[i]);
if sum - a[i] * x[i] <= 0 then
break;
f(i - 1, sum - a[i] * x[i]);
until False;
end;
end;
begin
Count := 0;
f(n, EtSum);
Solve := Count;
end;
var
a: TArray = (1, 2, 3, 4, 5);
var
sum: integer;
Count: QWord;
begin
sum := 121;
writeln;
Count := Solve(n, a, sum);
Write('There is ', Count, ' variants of a solutions.');
end.
const
n = 5;
type
TArray = array [1..n] of integer;
procedure ShowSolve(EtSum, n: integer; const a, x: TArray);
var
sum, i: integer;
begin
sum := 0;
for i := 1 to n do
begin
sum := sum + a[i] * x[i];
Write(a[i], '*', x[i]);
if i <> n then
Write('+');
end;
Write('=', sum);
if sum = EtSum then
writeln(' - Ok')
else
begin
writeln(' - wrong solution!');
halt;
end;
end;
{функция решает диофантово уравнение и возвращает количество решений}
function Solve(n: integer; const a: TArray; EtSum: integer): QWord;
var
Count: QWord;
x: TArray; {массив текущего решения}
function f(i, sum: integer): integer;
begin
if sum < 0 then
exit;
if i = 0 then
exit;
if i = 1 then
begin
if sum mod a[1] = 0 then
begin
Inc(Count);
x[1] := sum div a[1];
Write('Solution #', Count: 8, ' is: ');
ShowSolve(EtSum, n, a, x);
end;
end
else
begin
x[i] := 0;
repeat
Inc(x[i]);
if sum - a[i] * x[i] <= 0 then
break;
f(i - 1, sum - a[i] * x[i]);
until False;
end;
end;
begin
Count := 0;
f(n, EtSum);
Solve := Count;
end;
var
a: TArray = (1, 2, 3, 4, 5);
var
sum: integer;
Count: QWord;
begin
sum := 121;
writeln;
Count := Solve(n, a, sum);
Write('There is ', Count, ' variants of a solutions.');
end.
Это решение линейного диофантового уравнения со следующими ограничениями:
- коэффициенты - натуральные числа (>=1);
- решения x ищутся на множестве натуральных чисел (>=1).
PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк).
Разобрался, программу подстроил под себя. Теперь вопрос , как эт этого перейти к системе уравнений ax+by+c=0 . Сумма =0 , вводится матрица по 3 элемента в строке (a,b,c) , n строк, . Далее я так понимаю нужно в функции f , в нахождении правильного решения подставлять циклическую проверку для всех остальных уравнений. Но вот как это реализовать не получается( ошибка на ошибке получается)
буду рад, если вы поможете еще раз
Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок:
1. Поиск в интернет дал мне несколько статей в Wikipedia (как русская, так и английская - выбор языка статьи в левой колонке, а английские версии всех статей по технике почему-то более полные, сложные), сайт алгоритмов "e-maxx.ru", ещё статьи в pdf(яндекс, гугл).
2. После прочтения я понял, что глубокий матаппатат есть для случая a*x1+b*x2+c=0 (как для чисел, так и для матриц). Это уравнение в целых числах имеет бесконечное множество решений (кстати, аналитическое - по формуле). Матаппарат разрабатывался 2,5 тысячи лет, есть наработки, доступные по лицензии Public Domain.
3. Изначальное условие задачи было об одном уравнении со многими переменными, фигурировала фраза, указывающее на конечное множество решений. Это привело меня к мысли об ограничении диапазона значений коэффициентов и корней уравнения только натуральными числами - в противном случае не выполняется условие конечности количества решений. Рекурсией я организовал цикл по всем неизвестным (пока n - не последний элемент, то вычисляется сумма слагаемых уравнения, когда n - последний, то проверяется сумма на равенство правой части уравнения).
К чему это я. Т.к. задача усложнилась, то с ходу я её не понял. Предлагаю тебе сформулировать её ещё раз (в том числе и для себя), ознакомиься с матаппаратом, создать несколько тестовых примеров, написать тестовую программу, решающую только эту задачу, выложить код. Лучше будет, если ты приведёшь словесное описание (или ссылку на пояснительный материал) алгоритма (способа) решения.
1. Поиск в интернет дал мне несколько статей в Wikipedia (как русская, так и английская - выбор языка статьи в левой колонке, а английские версии всех статей по технике почему-то более полные, сложные), сайт алгоритмов "e-maxx.ru", ещё статьи в pdf(яндекс, гугл).
2. После прочтения я понял, что глубокий матаппатат есть для случая a*x1+b*x2+c=0 (как для чисел, так и для матриц). Это уравнение в целых числах имеет бесконечное множество решений (кстати, аналитическое - по формуле). Матаппарат разрабатывался 2,5 тысячи лет, есть наработки, доступные по лицензии Public Domain.
3. Изначальное условие задачи было об одном уравнении со многими переменными, фигурировала фраза, указывающее на конечное множество решений. Это привело меня к мысли об ограничении диапазона значений коэффициентов и корней уравнения только натуральными числами - в противном случае не выполняется условие конечности количества решений. Рекурсией я организовал цикл по всем неизвестным (пока n - не последний элемент, то вычисляется сумма слагаемых уравнения, когда n - последний, то проверяется сумма на равенство правой части уравнения).
К чему это я. Т.к. задача усложнилась, то с ходу я её не понял. Предлагаю тебе сформулировать её ещё раз (в том числе и для себя), ознакомиься с матаппаратом, создать несколько тестовых примеров, написать тестовую программу, решающую только эту задачу, выложить код. Лучше будет, если ты приведёшь словесное описание (или ссылку на пояснительный материал) алгоритма (способа) решения.
Цитата(Федосеев Павел @ 11.01.2015 14:51)
Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок:
1. Поиск в интернет дал мне несколько статей в Wikipedia (как русская, так и английская - выбор языка статьи в левой колонке, а английские версии всех статей по технике почему-то более полные, сложные), сайт алгоритмов "e-maxx.ru", ещё статьи в pdf(яндекс, гугл).
2. После прочтения я понял, что глубокий матаппатат есть для случая a*x1+b*x2+c=0 (как для чисел, так и для матриц). Это уравнение в целых числах имеет бесконечное множество решений (кстати, аналитическое - по формуле). Матаппарат разрабатывался 2,5 тысячи лет, есть наработки, доступные по лицензии Public Domain.
3. Изначальное условие задачи было об одном уравнении со многими переменными, фигурировала фраза, указывающее на конечное множество решений. Это привело меня к мысли об ограничении диапазона значений коэффициентов и корней уравнения только натуральными числами - в противном случае не выполняется условие конечности количества решений. Рекурсией я организовал цикл по всем неизвестным (пока n - не последний элемент, то вычисляется сумма слагаемых уравнения, когда n - последний, то проверяется сумма на равенство правой части уравнения).
К чему это я. Т.к. задача усложнилась, то с ходу я её не понял. Предлагаю тебе сформулировать её ещё раз (в том числе и для себя), ознакомиься с матаппаратом, создать несколько тестовых примеров, написать тестовую программу, решающую только эту задачу, выложить код. Лучше будет, если ты приведёшь словесное описание (или ссылку на пояснительный материал) алгоритма (способа) решения.
Нужно поставить дом, чтобы до самой далекой улицы расстояние было минимальным.
Гарантируется, что решение единственно и не существует 4 улиц образующих ромб. Ограничение по времени 1 секунда.
Входной файл:
В первой строке 2 <= N <= 100 – число улиц .
Дальше N строк по три дробных числа a, b, c – коэффициенты уравнения ax + by + c = 0 – задающего прямую – улицу.
Выходной файл:
x y – два подряд идущих числа – координаты дома с точностью не менее 5 знаков после запятой.
Примеры:
Вход:
2
1 0 0
0 1 0
Выход:
0 0
Вроде как подумал, делается также, но потом каждое из верных решений( для ax+by+c=0 их бесконенчо много. как вы подметили) подставляется в следущее уравнение и так до конца, в случае если подходит, оно выводится.Хотя я тут начал было сомневаться, тк чистым подбором задача может решаться намного больше 1 секунды.
Кажется, это задача не на диофантовы уравнения, а, скорее, на геометрию или алгебраическую геометрию - не помню точно название этого раздела.
Почему? Диофантовы уравнения исключительно целочисленны, а в условии: "координаты дома с точностью не менее 5 знаков после запятой".
Тут матмодель из геометрии, а решение - может быть, из динамического программирования или из чего-то другого - даже простых геометрических соображений.
Почему? Диофантовы уравнения исключительно целочисленны, а в условии: "координаты дома с точностью не менее 5 знаков после запятой".
Тут матмодель из геометрии, а решение - может быть, из динамического программирования или из чего-то другого - даже простых геометрических соображений.
Цитата(Федосеев Павел @ 11.01.2015 19:29)
Кажется, это задача не на диофантовы уравнения, а, скорее, на геометрию или алгебраическую геометрию - не помню точно название этого раздела.
Почему? Диофантовы уравнения исключительно целочисленны, а в условии: "координаты дома с точностью не менее 5 знаков после запятой".
Тут матмодель из геометрии, а решение - может быть, из динамического программирования или из чего-то другого - даже простых геометрических соображений.
Действительно, спасибо. Понял, что можно все решить с помощью определителя матрицы. методом крамера. В общем, если появятся вопросы напишу. Спасибо
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.