Сколькими способами можно разменять монетами

Сколькими способами можно разменять монету?

Сколькими способами можно раскрасить ребра графа
Доброго времени суток. Скоро меня настигнет дедлайн для получения зачета по алгебре, а я все никак.

Сколькими способами можно составить такую мозаику (с точностью до поворотов и осевых симметрий квадрата)?
Здравствуйте, форумчане 🙂 Столкнулся впервые с такой вот задачкой из темы «Задачи на раскраски».

Сколькими способами можно разменять
Сколькими способами можно разменять 100руб в 5,10,20 и 50 руб? решить рекурсией..помогите.

Сколькими способами можно разменять рубль?
сколькими способами можно разменять рубль на монеты достоинством в 10, 15, 20 и 50 копеек.

Иными словами, сколько есть неотрицательных решений в целых числах у уравнения x + 2y + 4z + 10w = 20

Добавлено через 4 минуты
Отсюда уже кое-что видно. Например, то, что x — четно. x = 2v
2(v+y) + 4z + 10w = 20
u + 2z + 5w = 10 (u=v+y)

Добавлено через 5 минут
Для w есть 3 варианта.
w = 2 — 1 способ
w = 1 приводит к u + 2z = 5. Возможные способы легко перебрать.
w = 0 => u + 2z = 10 — тоже можно перебрать.

Добавлено через 1 минуту
Дальше чуток усидчивости и аккуратности, и решение — вот оно!

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

Как-то так:
2: 50+50
3: —
4: 50+20+20+10
5: 50+20+20+5+5; 50+20+10+10+10
6: 50+20+10+10+5+5; 50+10+10+10+10+10; 20+20+20+20+10+10
. .

Добавлено через 8 минут
Пропущено:
5: 20+20+20+20+20

Но вот я не вижу схемы составления этих комбинаций. Хотя, видимо, она у вас есть. Такого алгоритма, который бы позволял гарантировать, что повторов не будет и ни одна комбинация не будет пропущена.
Я понимаю, что разбиение всего множества на классы по количеству монет гарантирует отсутствие повторов (если внутри каждого класса повторов нет, что наверное, легко проверить визуально). Но вот как внутри одного класса обеспечить все варианты?

Добавлено через 6 минут
Кстати, можно предложить легкую модификацию задачи. Добавить 3-х копеечные монеты.
Нетрудно заметить, что их число должно быть кратно 5. И можно вместо них рассматривать 15-ти копеечные.

Добавлено через 4 минуты
В общем-то понятно, что при увеличении количества номиналов комбинаторная сложность возрастает (как и у всех комбинаторных задач). И по-хорошему здесь надо программу писать.
Но мне просто любопытны, что здесь поддается «ручному» учету

На улицу не пускают. Заняться надо же чем-то

Источник

комбинаторика — Размен 110000 рублей [закрыт]

Скольким способами можно разменять 110 000 рублей монетами в 1, 2 и 5 рублей?

Как я понимаю, тут нужно использовать формулы сочетаний из комбинаторики, но я не понимаю как :\

задан 11 Янв ’15 13:57

Вопрос был закрыт. Причина — «Повтор вопроса». Закрывший — EdwardTurJ 11 Янв ’15 14:27

1 ответ

Нужно подсчитать число решений уравнения $%x+2y+5z=110000$% в целых неотрицательных числах. Здесь $%x$% — число рублёвых монет, $%y$% — число двухрублёвых, $%z$% — пятирублевых.

Придавая $%z$% различные значения от $%0$% до $%22000$%, будем получать уравнения вида $%x+2y=5(22000-z)$%. Для фиксированного $%N$% уравнение $%x+2y=N$% имеет $%[N/2]+1$% решение, где квадратные скобки означают целую часть. Действительно, $%y$% может принимать любое значение от $%0$% до $%[N/2]$% включительно, и $%x$% далее однозначно выражается из равенства $%x=N-2y$%.

Число $%N=5(22000-z)$% в правой части уравнения принимает значения $%0$%, $%5$%, $%10$%, $%15$%, . , $%110000$%. Значения $%[N/2]+1$% при этом получаются равными $%1$%, $%3$%, $%6$%, $%8$%, . , $%55001$%. Все эти числа надо сложить между собой. Закономерность тут достаточно простая: после первой 1 происходит увеличение то на 2, то на 3 — с чередованием. Если сложить числа попарно, не считая самого последнего, то получится арифметическая прогрессия $%4+14+24+\cdots+109994$%, в которой ровно 11000 членов. Применяя формулу для суммы членов прогрессии, имеем $%(4+109994)\cdot11000/2$%, к которой надо прибавить самое последнее слагаемое $%55001$%. Получится $%605044001$%, и это конечный ответ.

Источник

Зона кода

Рассмотрим следующую задачу.

Каким количеством способов можно разменять тысячерублёвую купюру монетами по 1руб., 2руб., 5руб., 10руб.?

Решим задачу четырьмя способами. Различаться они будут степенью использования в них математического аппарата. В первом способе математика использоваться почти не будет: мы сразу же напишем программу. А в последнем нам удастся обойтись без программирования вообще: задача будет решена математически. Второй и третий способы будут занимать промежуточное положение между первым и последним. Все способы в порядке возрастания степени участия в них математики мы весьма условно назовём способами «двоечника», «троечника», «хорошиста» и «отличника».

Интересно будет проследить за тем, как, по мере перехода от «двоечника» к «троечнику» и от «троечника» к «хорошисту», объёмы предварительных математических выкладок будут расти, а программы будут становиться всё более и более эффективными.

Надеюсь, что словосочетания «математический аппарат» и «математические выкладки» не отпугнут читателя от ознакомления со статьёй. Математику мы будем использовать достаточно простую, да и программы будут простыми тоже, поэтому данный материал можно смело рекомендовать для прочтения новичкам.

Способ «двоечника»

Первое же, что может прийти на ум – это метод перебора. Ясно, что в любом размене тысячерублёвой купюры десятирублёвых монет может быть от 0 до 100, пятирублёвых – от 0 до 200, двухрублёвых – от 0 до 500 и рублёвых – от 0 до 1000. Переберём всевозможные наборы из перечисленных монет, в которых монета каждого достоинства встречается число раз, попадающее в соответствующий ей диапазон. Для каждого такого набора вычислим его рублёвый эквивалент и подсчитаем случаи, в которых он будет равен 1000р.

Программу, реализующую такой ломовой перебор, написать очень легко:

Думаю, программа проста для понимания. Переменная s – это счётчик случаев, в которых количество рублей в наборе равно 1000. Во внешнем цикле перебираем всевозможные количества «десяток», во вложенном в него – количества «пятёрок», далее – количества «двушек», наконец, в самом внутреннем цикле перебираются количества рублей.

Итак, мы имеем 4 вложенных друг в друга цикла, общее количество итераций самого внутреннего цикла – более 10,1 млрд. На моём среднем по мощности ноутбуке программа работает полминуты! Но, несмотря на свою чудовищную неэффективность, она выдаёт правильный ответ – 1712051. Задача решена!

Если мы разделим ответ на количество всех итераций и выразим частное в процентах, то получим примерно 0,017%. Этот процент можно считать «коэффициентом полезного действия» данного метода. Именно такова доля «полезных» итераций в их общем количестве. Таким образом, примерно 99,98% итераций – это условный «балласт», на который тратится компьютерное время. Давайте избавимся от этих трат.

Способ «троечника»

Изменим программу. Внешний цикл оставим нетронутым. Во вложенном в него цикле изменим верхний предел изменения переменной b . Новый предел, который мы будем хранить в переменной m , теперь будет зависеть от текущего значения переменной a . Понятно, что для любого значения a значение b должно быть таково, чтобы выполнялось неравенство 10 * a + 5 * b . Это означает, что значение m , т. е. максимально возможное значение b , должно удовлетворять равенству 10 * a + 5 * m = 1000 , откуда m = 200 — 2 * a .

Что касается третьего и четвёртого цикла, то они нам не нужны. Действительно, если фиксировано количество «десяток» ( a ) и «пятёрок» ( b ), то совсем несложно подсчитать, каким количеством способов можно представить оставшуюся сумму (т. е. 1000 — 10 * a — 5 * b ) в виде «двушек» и рублей.

Это число способов равно максимальному количеству «двушек», которое может «поместиться» в оставшейся сумме (обозначим его, например, p ), сложенному с единицей. Объясняется это тем, что любое количество двухрублёвых монет от 1 до p может быть дополнено рублёвыми монетами до оставшейся суммы, а добавляемая к p единица соответствует единственному способу представления оставшейся суммы без использования «двушек».

Для получения p нужно выполнить целочисленное деление оставшейся суммы на 2. Таким образом, количество способов представления оставшейся суммы в виде двухрублёвых и однорублёвых монет (т. е. p + 1 ) равно (1000 — 10 * a — 5 * b) / 2 + 1 (деление на 2 здесь, разумеется, целочисленное). Именно это количество мы на каждой итерации внутреннего цикла будем теперь добавлять к счётчику s .

Этих выкладок уже вполне достаточно, чтобы написать второй вариант программы:

Программа выдаёт тот же результат, что и раньше, а время её работы составляет доли секунды. Это программа уже построена на подсчёте искомого количества способов, а не на переборе огромного количества вариантов, среди которых имеется львиная доля тех, которые нас не устраивают.

Несложно подсчитать общее число итераций внутреннего цикла:

∑ a = 0 100 200 — 2 a + 1 = ∑ a = 0 100 201 — 2 ∑ a = 0 100 a = 201 · 101 — 2 · 100 · 101 2 = 101 2 = 10201 .

Здесь мы использовали хорошо известные формулы для нахождения сумм:

∑ k = 0 n c = n + 1 c , ∑ k = 0 n k = n n + 1 2 .

Как мы видим, общее число итераций внутреннего цикла, по сравнению с предыдущим вариантом, снизилось на 6 порядков!

Заметим, что если бы мы решали задачу, в которой размен тысячи необходимо было осуществлять с помощью монет достоинством 1руб., 5руб., 10руб., то на каждой внутренней итерации нужно было бы увеличивать счётчик на 1. Это означает, что окончательное его значение совпало бы с общим числом внутренних итераций, т. е. с числом 10201. Таким, образом, мы, в качестве побочного эффекта, получили аналитическое решение задачи о количестве способов, которым можно осуществить описанный в начале абзаца обмен. Это число равно 10201.

Дальнейшие усовершенствования программы уже не приведут к хоть сколько-нибудь заметному увеличению производительности, поскольку программа уже выполняется почти мгновенно. Однако, из любви к искусству программирования, останавливаться мы не будем.

Способ «хорошиста»

В этом разделе мы получим выражение искомого количества способов размена в виде суммы, поле чего напишем программу для её вычисления.

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

Несложно заметить, что t может принимать значения 0, 5, 10, . 1000. Таким образом, количество групп равно 201. Пусть s_k – число способов размена, содержащихся в группе, соответствующей значению t, равному 5k. Тогда S – искомое количество способов размена тысячерублёвой купюры, можно представить в виде:

S = ∑ k = 0 200 s k .

Выразим s_k через k. Для этого представим s_k в виде u_kv_k, где u_k – число способов, которыми можно набрать 5k рублей однорублёвыми и двухрублёвыми монетами, а v_k – число способов, которыми можно набрать оставшиеся 1000-5k рублей пятирублёвыми и десятирублёвыми монетами.

Найдём u_k. Воспользуемся способом, уже применявшимся нами в предыдущем разделе: разделим 5k на 2 «нацело» и добавим единицу:

Квадратные скобки здесь обозначают целую часть заключённого в них числа.

Теперь найдём v_k. Задача о нахождении количества способов набора 1000-5k рублей пятирублёвыми и десятирублёвыми монетами эквивалентна задачи о нахождении количества способов набора однорублёвыми и двухрублёвыми монетами суммы в 5 раз меньшей, т. е. 200-k рублей. Снова делим на 2 «нацело» и добавляем единицу:

v k = 200 — k 2 + 1 = 100 — k 2 + 1 = 101 — k 2 .

В итоге, получаем:

s k = u k · v k = 5 k 2 + 1 · 101 — k 2 ,

S = ∑ k = 0 200 5 k 2 + 1 · 101 — k 2 .

Формула получена, теперь можно составлять программу:

Заметим, что при написании программы выражение 101 — k 2 было закодировано как (202 — k) / 2 .

Программа выдаёт всё тот же результат – 1712051, используя при этом один-единственный цикл, в ходе которого выполняется 201 итерация.

Способ «отличника»

А теперь давайте решим задачу без использования программирования. Частью нашего решения являются математические выкладки, уже выполненные в предыдущем разделе. Нам остаётся лишь найти число S, воспользовавшись последней формулой предыдущего раздела.

Индекс k, принимающий все целые чётные значения от 0 до 200 включительно, можно представить в виде 2m, где новый индекс m принимает все целые значения от 0 до 100 включительно. Воспользовавшись заменой k=2m, запишем S₀ в виде суммы и найдём её:

S 0 = ∑ m = 0 100 5 · 2 m 2 + 1 · 101 — 2 m 2 = ∑ m = 0 100 5 m + 1 · 101 — m =
= ∑ m = 0 100 — 5 m 2 + 504 m + 101 = — 5 ∑ m = 0 100 m 2 + 504 ∑ m = 0 100 m + ∑ m = 0 100 101 = — 5 · 100 · 101 · 201 6 +
+ 504 · 100 · 101 2 + 101 2 = — 1691750 + 2545200 + 10201 = 863651 .

Здесь мы использовали три формулы, позволяющие вычислять суммы. Две из них мы приводили ранее, а третью приведём сейчас:

∑ k = 0 n k 2 = n n + 1 2 n + 1 6 .

Эти же три формулы понадобятся нам и для нахождения S₁.

Индекс k, принимающий все целые нечётные значения от 1 до 199 включительно, можно представить в виде 2m+1, где новый индекс m принимает все целые значения от 0 до 99 включительно. Воспользовавшись заменой k=2m+1, запишем S₁ в виде суммы и найдём её:

S 1 = ∑ m = 0 99 5 · 2 m + 1 2 + 1 · 101 — 2 m + 1 2 = ∑ m = 0 99 5 m + 3 + 1 2 · 100 + 1 2 — m =
= ∑ m = 0 99 5 m + 3 · 100 — m = ∑ m = 0 99 — 5 m 2 + 497 m + 300 = — 5 ∑ m = 0 99 m 2 + 497 ∑ m = 0 99 m + ∑ m = 0 99 300 =
= — 5 · 99 · 100 · 199 6 + 497 · 99 · 100 2 + 100 · 300 = — 1641750 + 2460150 + 30000 = 848400 .

S = S 1 + S 2 = 863651 + 848400 = 1712051 .

Выводы

Итак, мы решили задачу 4-мя способами. Первые 3 из них включали в себя написание программ. Для каждой из них было указано число итераций внутреннего цикла. Данная информация позволяет приближённо сравнить программы по производительности. Однако сравнение будет более точным, если в нём будут участвовать количества операций умножения и деления, задействованных в программах. Известно, что эти 2 операции требуют для своего выполнения значительно большего количества процессорного времени, чем операции сложения и вычитания, поэтому последними двумя мы пренебрежём.

Соберём в таблицу информацию о количествах циклов, итераций внутреннего цикла и числе операций умножения и деления.

Программа	Количество циклов	Количество итераций внутреннего цикла	Количество операций умножения и деления
«двоечника»	4	10 180 971 801	30 542 915 403
«троечника»	2	10 201	30 704
«хорошиста»	1	201	804

Как мы видим, информация, приведённая в последнем столбце, не вносит существенных корректив в результаты сравнений производительности программ. В соответствии с ней, вторая программа превосходит по производительности первую почти в 10 6 раз, а третья вторую – почти в 40 раз. В первом случае разрыв гигантский, а во втором – небольшой. «На глаз» заметить разницу во временах выполнения второй и третьей программ невозможно.

В заключение статьи проведём забавный мысленный эксперимент. Представим, что 4-м человекам предоставили в распоряжение компьютеры, бумагу, ручки и предложили решить нашу задачу. Предположим, что каждый из них выбрал один из способов, приведённых в статье, причём все выбрали разные способы. Будем считать, что способности этих людей примерно равны, тем не менее, назовём их условно «двоечником», «троечником», «хорошистом» и «отличником» в соответствии с выбранными ими способами. Зададимся вопросом: кто из них быстрее всех справится с задачей, а кто – медленнее?

Как мне представляется, «двоечник» решит задачу достаточно быстро. Например, за минуту придумает алгоритм, за минуту его реализует на компьютере, через полминуты работы программы ответ будет готов. «Троечник» будет возиться с алгоритмом на несколько минут дольше «двоечника», и, хоть его программа выполнится за доли секунды, по общему количеству времени «двоечнику» он уступит.

«Хорошисту» придётся разрабатывать алгоритм ещё дольше, и «троечнику» он проиграет. А вот отличник может в своих выкладках вообще увязнуть и потратить на решение полчаса или даже больше. Таким образом, он, скорее всего, «с треском» проиграет всем остальным.

Результаты могут показаться парадоксальными: интеллект проигрывает грубой ломовой силе. Означает ли это, что особого смысла в оптимизации программ может и не быть?

Вопрос очень простой, и я думаю, что ответ читателю известен. Если программа используется однократно, то, действительно, нет особой разницы в том, работает она полминуты или тысячную долю секунды. Но такие программы – редкость. В подавляющем большинстве случаев программное обеспечение рассчитано на многократное применение. И если на одном компьютере программа запускается на выполнение пару сотен тысяч раз, то снижение времени её работы даже на полсекунды весьма существенно! Ведь в данном примере суммарный выигрыш по времени превысит сутки! В таких случаях уместность оптимизации очевидна.

Источник