|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.09.2015, 19:18 | #1 |
Новичок
Джуниор
Регистрация: 04.09.2008
Сообщений: 2
|
Помогите с задачей
Вечер добрый. Подскажите хотя бы алгоритм.
Игровой автомат принимает монеты только двух видом а рублей и b рублей. У игрока имеется неограниченный набор монет а и b, Удастся ли набрать s рублей, без сдачи. s,a,b вводятся пользователем. |
22.09.2015, 19:26 | #2 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,758
|
Берете максимальное из а и б. Делите с на максимум с остатком. Берете остаток и делите на меньшее, если остаток 0, то набрали. Годится?
|
22.09.2015, 19:30 | #3 |
Новичок
Джуниор
Регистрация: 04.09.2008
Сообщений: 2
|
|
22.09.2015, 19:48 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
В цикле начиная с ноль монет любого достоинства до тех пор пока или их сумма превысит s, или остаток s делится нацело на монету другого достоинства. Насчет оптимальности не думал, может решение p51x по другому сформировать и будет сильно оптимальней
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 22.09.2015 в 19:50. |
22.09.2015, 22:31 | #5 | |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,758
|
Цитата:
|
|
23.09.2015, 11:17 | #6 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Так не получится. Вообще-то это диофантово уравнение первой степени с двумя неизвестными и сводится к нахождению НОД а и b, и если этот НОД является делителем s, то все ok, иначе неудача. Насколько нахождение НОД оптимальней цикла предложенного в #4 пусть ТС разбирается
И тоже не совсем так - так показывается, что есть решение в целых числах, в том числе и отрицательных. А нужно показать факт существования решения в неотрицательных числах
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 23.09.2015 в 11:31. |
24.09.2015, 11:39 | #7 |
Пользователь
Регистрация: 29.06.2012
Сообщений: 39
|
Примерно так можно.
Код:
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
помогите с задачей | Alex26RusLink | Помощь студентам | 3 | 25.10.2009 02:27 |
Помогите с задачей | Noxil | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 30.10.2008 19:20 |
помогите с задачей | StakanpORTvejna | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 11.10.2008 19:19 |
Помогите с задачей.. | vit_al | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 24.04.2008 13:48 |