сколькими способами можно разменять 50 рублей монетами
335. Сколькими способами можно разменять 50 рублей монетами в 1 и 5 рублей? Никольский С.М. Математика 5 класс
335.
Сколькими способами можно разменять 50 рублей монетами в 1 и 5 рублей?
11 способов, рассуждения аналогичны номеру 334.
По рисунку 50 определите, какая точка симметрична относительно точки О точке: а) A; б) В; в) С; г) D; д) М; е) N; ж) О.
( Подробнее. )
Кто решит задачу? Найдите объем прямоугольного параллелепипеда, дли на которого ширина и высота ( Подробнее. )
332.
Требуется распилить бревно на 6 частей. Каждый распил занимает 1 мин 30 с. Сколько времени потребуется на эту работу? ( Подробнее. )
Научный форум dxdy
Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Правила форума
В этом разделе нельзя создавать новые темы.
Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.
Размен монетами, найти количество способов
| Заслуженный участник |
 |
Последний раз редактировалось PAV 09.06.2011, 11:43, всего редактировалось 1 раз.
Сколькими способами можно разменять рубль на монеты достоинством в 1, 2, 5, 10, 20 и 50 копеек?
Это первая задача из задачника Полиа, Сеге «Задачи и теоремы из анализа». Я её решил, как мне кажется, дурацким способом, типа составления таблицы, и сведения задачи к аналогичным более простым. Кто знает способ проще?
| Заслуженный участник |
 |
| Заслуженный участник |
|
| Заслуженный участник |
 |
Можно ввести 
— количество вариантов размена суммы в 
копеек монетами достоинств 
и считать с помощью рекуррентного уравнения 
| Заслуженный участник |
|
| Заслуженный участник |
|
| Заслуженный участник |
|
| Заслуженный участник |
|
Xaositect
Это вторая задача в задачнике. 
. Коэффициент при 
равен 
.
Только как это поможет найти конкретно это число? Не понял, что значит последовательно выписать?
| Заслуженный участник |
|
Я имел в виду, что это выражение не сразу же получается, а последовательно.
, 
и т.д.
Ну а как поможет найти. 
, потому что каждый 
делит 
Для 
ряд можно явно выписать через «цешки», в результате получим какую-то формулу 
, для 
явное выражение.
| Заслуженный участник |
|
Зачем последовательно? Сразу видно.
| Заслуженный участник |
|
| Заслуженный участник |
|
|
|
Сколькими способами можно разменять рубль на монеты достоинством в 1, 2, 5, 10, 20 и 50 копеек?
Это первая задача из задачника Полиа, Сеге «Задачи и теоремы из анализа». Я её решил, как мне кажется, дурацким способом, типа составления таблицы, и сведения задачи к аналогичным более простым. Кто знает способ проще?
Вроде было же.
Правильный ответ 343.
| Заслуженный участник |
|
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей
Олимпиадное хобби. Размен монет
Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта http://uva.onlinejudge.org/. Сегодня нам предстоит решить задачу о размене монет из области динамического программирования. Задача не очень сложная, но есть над чем поразмыслить, поэтому заинтересовавшихся прошу под кат. К слову, это третья наша задача, но, безусловно, из всех самая интересная.
Небольшое лирическое отступление.
Мой программистский путь начался далеко не в 3 года, когда многие будущие программисты уже разбирали калькулятор и делали из него компьютер. Я начал заниматься программированием в школе в 8 классе. К слову сказать, моя школа была далека от технического направления, поэтому в своих начинаниях я был почти одинок. Но, благодаря директору нашей школы, у нас был «кружок» по программированию, где мы готовились к школьной олимпиаде по программированию. Нас там было не более трех человек единовременно, но нашего преподавателя, к счастью, это не расстраивало. Моим преподавателем программирования был Кавокин А.А., отчасти благодаря ему я и встал на столь удивительный путь программиста. Так вот, каждый урок наш наставник начинал с логической задачки, чтобы мы расшевелили свои извилины. Это мне настолько нравилось в школе, что я решил вас тоже так помучить, поэтому сегодня мы начнем с небольшой логической задачки, которая поможет нам размяться.
Логическая задачка для разминки:
В нашем городе проезд в общественном транспорте оплачивается непосредственно во время поездки, для чего по автобусу курсирует кондуктор, собирая со всех плату за проезд. Стоимость билета составляет 20 рублей. Однажды, на одной из остановок в автобус зашли 5 человек. Один из них молча заплатил кондуктору 100 рублей, и тот, не задавая никаких вопросов, отсчитал 5 билетов и отдал платившему. Вопрос: как кондуктор догадался, что оплата происходит сразу за всех пятерых, при условии, что ничто не указывало на то, что все они были вместе?
Позволю оставить задачу без ответа, потому что уверен в вашей сообразительности. А как только в комментариях появится правильный ответ, сразу вынесу ссылку сюда.
UPD: Ответ найден в комментарии пользователя ogra
Условие
Надеюсь задачка, которую я вам подкинул для разогрева, успешно подействует на вашу мозговую активность. Сейчас мы, наконец-то займемся решением олимпиадной задачи. Наша сегодняшняя задача — это задача о размене монет.
Краткий перевод условия задачи
После закупки в большом универмаге Мелу досталась сдача в размере 17 центов. Он получил одну десятицентовую монету, одну пятицентовую и 2 монеты по 1 центу. Позже, в этот же день, он делал покупки в мини-маркете, где тоже получил сдачу в размере 17 центов. На этот раз он получил две монеты по 5 центов и 7 монет по 1 центу. Тогда Мел задался вопросом: «Как много магазинов я могу посетить и получить сдачу в 17 центов различным набором монет?» После небольшого мозгового штурма, он определил, что ответ 6. Тогда он бросил вызов вам для решения более общего случая.
Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму.
Входные данные: ввод будет состоять из множества чисел между 0 и 30000 включительно, по одному в каждой строке.
Выходные данные: на каждое входное число, нужно определить число комбинаций и вывести, как показано в примере.
Output:
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.
Как обычно, рекомендую вам самим попытаться решить задачу. А как только решите, возвращайтесь к нам и хвастайтесь своим результатом.
Решение
Задача явно из области динамического программирования, а такие задачи, как правило, решаются с помощью рекурсивных зависимостей. Нам необходимо определить, какая именно рекурсивная зависимость в нашем случае.
Можно сразу заметить, что число комбинаций не отличается при сдаче от 1 цента до 4 — это 1 вариант, при сдаче от 5 центов до 9 — это 2 варианта, при сдаче от 10 центов до 14 — это 4 варианта и т.д. Это происходит потому, что внутри такой «пятерки» монеты достоинством в 1 цент невозможно ничем заменить. Таким образом мы определили, что решать задачу для каждого числа бессмысленно, поэтому мы будем решать ее для каждой «пятерки».
Также можно заметить, комбинации для каждой следующей «пятерки» точно повторяют комбинации предыдущей «пятерки» (с добавлением в конец комбинации нужного числа монет по 1 центу) и некоторого числа новых комбинаций. Становится понятным, что число комбинаций следующей «пятерки» имеет зависимость от числа комбинаций предыдущих «пятерок». Нарисуем таблицу, где столбцами будут «пятерки», а строками виды монет, а на пресечении будет определяться, какое количество новых комбинаций породил данных вид монет ( в комбинации со всеми более мелкими) на конкретном шаге — «пятерке»:
| 1 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 | 55 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 |
| 25 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 4 | 5 |
| 50 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| ∑ | 1 | 2 | 4 | 6 | 9 | 13 | 18 | 24 | 31 | 39 | 50 | 62 |
В последней строке выведено число комбинаций на данной «пятерке»
К примеру: на шаге 35 (8 пятерка: 35-39)
имея только 1 центовую монету, новых комбинаций не появляется,
из монет 1 цент и 5 центов, можно выдумать 1 новую комбинацию: 5+5+5+5+5+5+5+1(от 0 до 4)
1 цент, 5 центов, 10 центов — 3 комбинации: 10+10+10+5+1(от 0 до 4), 10+10+5+5+5+1, 10+5*5+1
1, 5, 10, 25 — 2 новых комбинации: 25+10+1, 25+5+5+1
Число новых комбинаций на каждом шаге из монет 1 цент и 5 центов равняется 1, потому что это комбинация порождается добавлением 5 центовой монеты к предыдущей комбинации. Т.е. для второй пятерки 5+1, потом 5+5+1, потом 5+5+5+1 и т.д., по 1 новой комбинации на каждом шаге.
Также в этой таблице не трудно углядеть рекурсивную зависимость: число новых комбинаций на шаге i, составленных из монет 1-10 равняется числу новых комбинаций из монет 1-5 на шаге i-1 плюс число новых комбинаций из монет 1-10 на шаге i-2 (когда у нас в распоряжении было на 1 десятицентовую монету меньше). Аналогично для 25-ти центовой монеты и 50-ти центовой монеты.
В итоге мы имеем 2 формулы и 3 рекурсивных зависимости:
N(1, i) = 0, кроме N(1, 0) = 1
N(5, i) = 1
N(10, i) = N(5, i-1) + N(10, i-2)
N(25, i) = N(10, i-3) + N(25, i-5)
N(50, i) = N(25, i-5) + N(50, i-10)
S(i) = S(i-1) + N(1, i) + N(5, i) + N(10, i) + N(25, i) + N(50, i)
Где N — это матрица, определенная выше, а S — искомое число комбинаций.
Теперь нам остается лишь просчитать нужное число шагов от начала до запрашиваемой «пятерки», подсчитывая на каждом шаге общее число комбинаций (S). Учитывая тот факт, что тестов в задаче будет много, можно использовать для новых тестов, ранее просчитанный кусок матрицы и дополнять лишь ее недостающую часть. Еще очень важно понимать, что при максимальной сумме, заданной условием задачи: 30000 центов, суммарное число комбинаций перевалит за пределы int и даже long, поэтому для подсчета числа комбинаций рекомендую использовать 8 байтовые беззнаковые переменные.
Полагаю, что есть более изящное решение, чем предложенное выше, но я его пока не вижу, поэтому жду от вас интересных алгоритмов. Мое решение на C++ можно скачать тут. Проверить правильность своего решения можно здесь (требуется регистрация). Удачи, господа!