Кол-во решений линейного уравнения., метод счетчика, незнаю как сделать. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Кол-во решений линейного уравнения., метод счетчика, незнаю как сделать. |
zhdanow5a |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
Всем привет! Пока решал одну задачу наткнулся на такую проблему:
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) ! Заранеее спасибо. |
Федосеев Павел |
Сообщение
#2
|
Знаток Группа: Пользователи Сообщений: 481 Пол: Мужской Реальное имя: Федосеев Павел Репутация: 9 |
Вместо цикла - рекурсия.
|
zhdanow5a |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
|
Федосеев Павел |
Сообщение
#4
|
Знаток Группа: Пользователи Сообщений: 481 Пол: Мужской Реальное имя: Федосеев Павел Репутация: 9 |
Я попробовал решить примерно так.
На входе: 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. Это решение линейного диофантового уравнения со следующими ограничениями: - коэффициенты - натуральные числа (>=1); - решения x ищутся на множестве натуральных чисел (>=1). PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк). Сообщение отредактировано: Федосеев Павел - |
zhdanow5a |
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
Я попробовал решить примерно так. На входе: 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. Это решение линейного диофантового уравнения со следующими ограничениями: - коэффициенты - натуральные числа (>=1); - решения x ищутся на множестве натуральных чисел (>=1). PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк). Спасибо, щас разберусь! |
zhdanow5a |
Сообщение
#6
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
Я попробовал решить примерно так. На входе: 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. Это решение линейного диофантового уравнения со следующими ограничениями: - коэффициенты - натуральные числа (>=1); - решения x ищутся на множестве натуральных чисел (>=1). PS Был бы здесь volvo - он бы привёл более красивый вариант решения (рекурсия - его конёк). Разобрался, программу подстроил под себя. Теперь вопрос , как эт этого перейти к системе уравнений ax+by+c=0 . Сумма =0 , вводится матрица по 3 элемента в строке (a,b,c) , n строк, . Далее я так понимаю нужно в функции f , в нахождении правильного решения подставлять циклическую проверку для всех остальных уравнений. Но вот как это реализовать не получается( ошибка на ошибке получается) буду рад, если вы поможете еще раз |
Федосеев Павел |
Сообщение
#7
|
Знаток Группа: Пользователи Сообщений: 481 Пол: Мужской Реальное имя: Федосеев Павел Репутация: 9 |
Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок:
1. Поиск в интернет дал мне несколько статей в Wikipedia (как русская, так и английская - выбор языка статьи в левой колонке, а английские версии всех статей по технике почему-то более полные, сложные), сайт алгоритмов "e-maxx.ru", ещё статьи в pdf(яндекс, гугл). 2. После прочтения я понял, что глубокий матаппатат есть для случая a*x1+b*x2+c=0 (как для чисел, так и для матриц). Это уравнение в целых числах имеет бесконечное множество решений (кстати, аналитическое - по формуле). Матаппарат разрабатывался 2,5 тысячи лет, есть наработки, доступные по лицензии Public Domain. 3. Изначальное условие задачи было об одном уравнении со многими переменными, фигурировала фраза, указывающее на конечное множество решений. Это привело меня к мысли об ограничении диапазона значений коэффициентов и корней уравнения только натуральными числами - в противном случае не выполняется условие конечности количества решений. Рекурсией я организовал цикл по всем неизвестным (пока n - не последний элемент, то вычисляется сумма слагаемых уравнения, когда n - последний, то проверяется сумма на равенство правой части уравнения). К чему это я. Т.к. задача усложнилась, то с ходу я её не понял. Предлагаю тебе сформулировать её ещё раз (в том числе и для себя), ознакомиься с матаппаратом, создать несколько тестовых примеров, написать тестовую программу, решающую только эту задачу, выложить код. Лучше будет, если ты приведёшь словесное описание (или ссылку на пояснительный материал) алгоритма (способа) решения. Сообщение отредактировано: Федосеев Павел - |
zhdanow5a |
Сообщение
#8
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок: 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 секунды. |
Федосеев Павел |
Сообщение
#9
|
Знаток Группа: Пользователи Сообщений: 481 Пол: Мужской Реальное имя: Федосеев Павел Репутация: 9 |
Кажется, это задача не на диофантовы уравнения, а, скорее, на геометрию или алгебраическую геометрию - не помню точно название этого раздела.
Почему? Диофантовы уравнения исключительно целочисленны, а в условии: "координаты дома с точностью не менее 5 знаков после запятой". Тут матмодель из геометрии, а решение - может быть, из динамического программирования или из чего-то другого - даже простых геометрических соображений. |
zhdanow5a |
Сообщение
#10
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
Кажется, это задача не на диофантовы уравнения, а, скорее, на геометрию или алгебраическую геометрию - не помню точно название этого раздела. Почему? Диофантовы уравнения исключительно целочисленны, а в условии: "координаты дома с точностью не менее 5 знаков после запятой". Тут матмодель из геометрии, а решение - может быть, из динамического программирования или из чего-то другого - даже простых геометрических соображений. Действительно, спасибо. Понял, что можно все решить с помощью определителя матрицы. методом крамера. В общем, если появятся вопросы напишу. Спасибо |
Текстовая версия | 23.12.2024 19:55 |