Решение уравнения вида ax+by+cz = n;

@droft1312 · Регистрация: 12.03.2015

Author24 — интернет-сервис помощи студентам

Здравствуйте! У меня была задача про разрезание ленточки, и в общем я привел задачу к решению уравнения данного вида. В нем действуют условия, что: четыре целых числа n, a, b и c (1 ≤ n, a, b, c ≤ 4000) — длина исходной ленточки и разрешенные длины кусочков ленточки после разрезания, соответственно. Как можно подобрать корни данного уравнения? Заранее спасибо!

@Excalibur921 · 15.02.2016, 19:22

Может Симплекс метод? И чего вопрос в алгоритмах =).

@droft1312 · 16.02.2016, 12:40 **[ТС]**

А как его реализовать?

@Excalibur921 · 16.02.2016, 13:40

1)Погуглить =).
2) Убедиться что он подходит.
Глянуть как решают подобные. Найти готовые команды для мат пакетов.
Либо скачать книгу изучить вникнуть и сделать с нуля… но разве все это не очевидно?

@Igor3D · 16.02.2016, 15:53

Решение ур-я здесь совершенно ни при чем. Это "задача о монетках": как из монет заданных номиналов получить нужную сумму. Учебный пример "динамического программирования"

@droft1312 · 16.02.2016, 19:33 **[ТС]**

Я пытался решить данную задачу с помощью ДП, но никак не получилось. Не пойму какое нужно задать реккурентное соотношение.

@Igor3D · 17.02.2016, 04:50

Сообщение от droft1312

Я пытался решить данную задачу с помощью ДП, но никак не получилось. Не пойму какое нужно задать реккурентное соотношение.

Что-то "не то", нету там рекуррентного соотношения. Заводите "массив сумм" (n элементов) и на каждом шаге добавляете a, b, c заполняя новые эл-ты. Так в конце-концов доползете до n

@Shamil1 · 17.02.2016, 09:29

Сообщение от Igor3D

на каждом шаге добавляете a, b, c заполняя новые эл-ты

К чему добавляем и куда записываем?
При n = 100 у нас может быть 4850 решений (троек x, y, z). Каким образом мы извлечём все эти решения из "массива сумм", в которм 100 элементов?

Добавлено через 14 минут

Сообщение от droft1312

Как можно подобрать корни данного уравнения?

Ищите "решение линейных диофантовых уравнений с тремя неизвестными".

@Igor3D · 17.02.2016, 09:31

Сообщение от Shamil1

К чему добавляем и куда записываем?
При n = 100 у нас может быть 4850 решений (троек a, b, c). Каким образом мы извлечём все эти решения из "массива сумм", в которм 100 элементов?

На первом шаге у нас 3 эл-та значимы, напр с индексами 1, 2, 5 (a, b, c). Они имеют "длину пути" = 1 (монетка). Добавляем к эл-ту 1 еще монетку 1, попадаем на эл-т 2. Сравниваем длины путей - новый 2, старый 1, оставляем старый. Добавляем к эл-ту 1 еще монетку 2, попадаем на эл-т 3... Дальше рассказывать?

@Shamil1 · 17.02.2016, 09:40

Сообщение от Igor3D

Дальше рассказывать?

Я понял задачу так, что нужно решить уравнение вида ax+by+cz = n (в натуральных числах). Вы поняли задачу по-другому.

Добавлено через 2 минуты

Сообщение от Igor3D

напр с индексами 1, 2, 5 (a, b, c).

При n = 10 Ваш алгоритм даст ответ "2". Что делать автору с этим ответом?

@Igor3D · 17.02.2016, 10:23

Сообщение от Shamil1

При n = 10 Ваш алгоритм даст ответ "2". Что делать автору с этим ответом?

Значит корни (0, 0, 2), что никак не противоречит текущей постановке задачи

Если же хочется "все корни" или "с участием всех кусочков" или чего-то еще - пусть уточняет постановку.

Не по теме:

И алгоритм никак не мой :)

@Shamil1 · 17.02.2016, 10:48

Сообщение от Igor3D

Значит корни (0, 0, 2),

Как Вы получили эту цифру из ответа "2"?
При n = 7 ответ тоже "2".
Предложенный Вами алгоритм даёт минимально возможное количество кусочков. Одно число. ТС нужно как минимум три числа.

@Igor3D · 17.02.2016, 11:16

Сообщение от Shamil1

Предложенный Вами алгоритм даёт минимально возможное количество кусочков. Одно число. ТС нужно как минимум три числа.

Я полагал Вы "в курсе" - это очень популярная задачка. С этого "динамическое программирование" начинается, и, практически, заканчивается. Во всяком случае я не знаю ничего другого

Когда в эл-т вписывается новый путь (мин число монеток), то записывается также индекс "откуда пришли". После того как сумма достигнута, "маршрут" разматывается по этим записанным индексам. Идея в построении всех оптимальных путей до каждой суммы (а не только заданной), не заботясь о том войдет ли этот путь в конечный. Оптимальный - значит пишем. Какой-то да дотянется до конечного

@Mysterious Light · 17.02.2016, 11:20

droft1312, может, просто перебором по z=1..n?
Для каждого конкретного z диафантово уравнение ax+by=m, m=n-cz, решается стандартным методом спуска (рекурсивный/итерационый алгоритм, на каждом этапе которого слагаемое с большим коэффициентом переносится с правую сторону, обе части делятся на менший коэффициент и утверждается, что простая дробь является натуральным числом)
5x+3y=23 → y=7-x+(2-2x)/3 → пусть z=(2-2x)/3, y=7-x+z, 3z+2x=2 → x=1-z-z/2 → ...

Igor3D, оцените сложность Вашего алгоритма по времени и памяти как функцию от (a,b,c).

@Shamil1 · 17.02.2016, 14:49

Сообщение от Igor3D

Я полагал Вы "в курсе"

В курсе чего?

@Igor3D · 17.02.2016, 15:21

Сообщение от Mysterious Light

Igor3D, оцените сложность Вашего алгоритма по времени и памяти как функцию от (a,b,c).

И не подумаю

- Как вскипятить чайник?
- Ну наливаем в него воду, ставим на огонь и ждем пока закипит
- А если в нем уже есть вода?
- Тогда еще проще - выливаем воду, и задача сводится к решенной

Если есть хорошо известное решение - его надо тупо применять, а не заниматься изобретением велосипеда (хоть бы он и в 100 раз лучше).

@droft1312 0 / 0 / 1 Регистрация: 12.03.2015 Сообщений: 15
		1
	Решение уравнения вида ax+by+cz = n; 15.02.2016, 18:02. Показов 3550. Ответов 15 Метки алгоритмы, с++ (Все метки) Здравствуйте! У меня была задача про разрезание ленточки, и в общем я привел задачу к решению уравнения данного вида. В нем действуют условия, что: четыре целых числа n, a, b и c (1 ≤ n, a, b, c ≤ 4000) — длина исходной ленточки и разрешенные длины кусочков ленточки после разрезания, соответственно. Как можно подобрать корни данного уравнения? Заранее спасибо! 0

@Excalibur921 1471 / 826 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	15.02.2016, 19:22	2
	Может Симплекс метод? И чего вопрос в алгоритмах =). 0

@droft1312 0 / 0 / 1 Регистрация: 12.03.2015 Сообщений: 15
	16.02.2016, 12:40 [ТС]	3
	А как его реализовать? 0

@Excalibur921 1471 / 826 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	16.02.2016, 13:40	4
	Сообщение было отмечено droft1312 как решение Решение 1)Погуглить =). 2) Убедиться что он подходит. Глянуть как решают подобные. Найти готовые команды для мат пакетов. Либо скачать книгу изучить вникнуть и сделать с нуля… но разве все это не очевидно? 1

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,752
	16.02.2016, 15:53	5
	Решение ур-я здесь совершенно ни при чем. Это "задача о монетках": как из монет заданных номиналов получить нужную сумму. Учебный пример "динамического программирования" 0

@droft1312 0 / 0 / 1 Регистрация: 12.03.2015 Сообщений: 15
	16.02.2016, 19:33 [ТС]	6
	Я пытался решить данную задачу с помощью ДП, но никак не получилось. Не пойму какое нужно задать реккурентное соотношение. 0

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,752
	17.02.2016, 04:50	7
	Сообщение от droft1312 Я пытался решить данную задачу с помощью ДП, но никак не получилось. Не пойму какое нужно задать реккурентное соотношение. Что-то "не то", нету там рекуррентного соотношения. Заводите "массив сумм" (n элементов) и на каждом шаге добавляете a, b, c заполняя новые эл-ты. Так в конце-концов доползете до n 1

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,474
	17.02.2016, 09:29	8
	Сообщение от Igor3D на каждом шаге добавляете a, b, c заполняя новые эл-ты К чему добавляем и куда записываем? При n = 100 у нас может быть 4850 решений (троек x, y, z). Каким образом мы извлечём все эти решения из "массива сумм", в которм 100 элементов? Добавлено через 14 минут Сообщение от droft1312 Как можно подобрать корни данного уравнения? Ищите "решение линейных диофантовых уравнений с тремя неизвестными". 0

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,752
	17.02.2016, 09:31	9
	Сообщение от Shamil1 К чему добавляем и куда записываем? При n = 100 у нас может быть 4850 решений (троек a, b, c). Каким образом мы извлечём все эти решения из "массива сумм", в которм 100 элементов? На первом шаге у нас 3 эл-та значимы, напр с индексами 1, 2, 5 (a, b, c). Они имеют "длину пути" = 1 (монетка). Добавляем к эл-ту 1 еще монетку 1, попадаем на эл-т 2. Сравниваем длины путей - новый 2, старый 1, оставляем старый. Добавляем к эл-ту 1 еще монетку 2, попадаем на эл-т 3... Дальше рассказывать? 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,474
	17.02.2016, 09:40	10
	Сообщение от Igor3D Дальше рассказывать? Я понял задачу так, что нужно решить уравнение вида ax+by+cz = n (в натуральных числах). Вы поняли задачу по-другому. Добавлено через 2 минуты Сообщение от Igor3D напр с индексами 1, 2, 5 (a, b, c). При n = 10 Ваш алгоритм даст ответ "2". Что делать автору с этим ответом? 0

	17.02.2016, 15:21

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,752
	17.02.2016, 10:23	11
	Сообщение от Shamil1 При n = 10 Ваш алгоритм даст ответ "2". Что делать автору с этим ответом? Значит корни (0, 0, 2), что никак не противоречит текущей постановке задачи Если же хочется "все корни" или "с участием всех кусочков" или чего-то еще - пусть уточняет постановку. Не по теме: И алгоритм никак не мой :) 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,474
	17.02.2016, 10:48	12
	Сообщение от Igor3D Значит корни (0, 0, 2), Как Вы получили эту цифру из ответа "2"? При n = 7 ответ тоже "2". Предложенный Вами алгоритм даёт минимально возможное количество кусочков. Одно число. ТС нужно как минимум три числа. 0

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,752
	17.02.2016, 11:16	13
	Сообщение от Shamil1 Предложенный Вами алгоритм даёт минимально возможное количество кусочков. Одно число. ТС нужно как минимум три числа. Я полагал Вы "в курсе" - это очень популярная задачка. С этого "динамическое программирование" начинается, и, практически, заканчивается. Во всяком случае я не знаю ничего другого Когда в эл-т вписывается новый путь (мин число монеток), то записывается также индекс "откуда пришли". После того как сумма достигнута, "маршрут" разматывается по этим записанным индексам. Идея в построении всех оптимальных путей до каждой суммы (а не только заданной), не заботясь о том войдет ли этот путь в конечный. Оптимальный - значит пишем. Какой-то да дотянется до конечного 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,162 Записей в блоге: 24
	17.02.2016, 11:20	14
	droft1312, может, просто перебором по z=1..n? Для каждого конкретного z диафантово уравнение ax+by=m, m=n-cz, решается стандартным методом спуска (рекурсивный/итерационый алгоритм, на каждом этапе которого слагаемое с большим коэффициентом переносится с правую сторону, обе части делятся на менший коэффициент и утверждается, что простая дробь является натуральным числом) 5x+3y=23 → y=7-x+(2-2x)/3 → пусть z=(2-2x)/3, y=7-x+z, 3z+2x=2 → x=1-z-z/2 → ... Igor3D, оцените сложность Вашего алгоритма по времени и памяти как функцию от (a,b,c). 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,474
	17.02.2016, 14:49	15
	Сообщение от Igor3D Я полагал Вы "в курсе" В курсе чего? 0

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,752
	17.02.2016, 15:21	16
	Сообщение от Mysterious Light Igor3D, оцените сложность Вашего алгоритма по времени и памяти как функцию от (a,b,c). И не подумаю - Как вскипятить чайник? - Ну наливаем в него воду, ставим на огонь и ждем пока закипит - А если в нем уже есть вода? - Тогда еще проще - выливаем воду, и задача сводится к решенной Если есть хорошо известное решение - его надо тупо применять, а не заниматься изобретением велосипеда (хоть бы он и в 100 раз лучше). 0