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

[zhdanow5a]

Всем привет! Пока решал одну задачу наткнулся на такую проблему:
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) !
Заранеее спасибо.

[Федосеев Павел]

Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок:
1. Поиск в интернет дал мне несколько статей в Wikipedia (как русская, так и английская - выбор языка статьи в левой колонке, а английские версии всех статей по технике почему-то более полные, сложные), сайт алгоритмов "e-maxx.ru", ещё статьи в pdf(яндекс, гугл).
2. После прочтения я понял, что глубокий матаппатат есть для случая a*x1+b*x2+c=0 (как для чисел, так и для матриц). Это уравнение в целых числах имеет бесконечное множество решений (кстати, аналитическое - по формуле). Матаппарат разрабатывался 2,5 тысячи лет, есть наработки, доступные по лицензии Public Domain.
3. Изначальное условие задачи было об одном уравнении со многими переменными, фигурировала фраза, указывающее на конечное множество решений. Это привело меня к мысли об ограничении диапазона значений коэффициентов и корней уравнения только натуральными числами - в противном случае не выполняется условие конечности количества решений. Рекурсией я организовал цикл по всем неизвестным (пока n - не последний элемент, то вычисляется сумма слагаемых уравнения, когда n - последний, то проверяется сумма на равенство правой части уравнения).

К чему это я. Т.к. задача усложнилась, то с ходу я её не понял. Предлагаю тебе сформулировать её ещё раз (в том числе и для себя), ознакомиься с матаппаратом, создать несколько тестовых примеров, написать тестовую программу, решающую только эту задачу, выложить код. Лучше будет, если ты приведёшь словесное описание (или ссылку на пояснительный материал) алгоритма (способа) решения.

Сообщение отредактировано: Федосеев Павел - 11.01.2015 14:52

[zhdanow5a]

Скажу честно. С линейными диофантовыми уравнениями сталкиваюсь первый раз. Код я написал исходя из следующих посылок:
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 секунды.