Сколько всего способов получить 17 рублей монетами

Бросание монет. Решение задач на нахождение вероятности

На этой странице я расскажу об одном популярном классе задач, которые встречаются в любых учебниках и методичках по теории вероятностей — задачах про бросание монет (кстати, они встречаются в части В6 ЕГЭ). Формулировки могут быть разные, например «Симметричную монету бросают дважды. » или «Бросают 3 монеты . «, но принцип решения от этого не меняется, вот увидите.

найти вероятность, что при бросании монеты

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

Для задач о подбрасывании монеты существуют два основных метода решения, один — по формуле классической вероятности (фактически переборный метод, доступный даже школьникам), а также его более сложный вариант с использованием комбинаторики, второй — по формуле Бернулли (на мой взгляд он даже легче первого, нужно только запомнить формулу). Рекомендую по порядку прочитать про оба метода, и потом выбирать при решении подходящий.

Нужна помощь? Решаем теорию вероятностей на отлично

Классическая вероятность (перебор)
Классическая вероятность (комбинаторный подход)
Формула Бернулли
Полезные ссылки

Полезная страница? Сохрани или расскажи друзьям

1. Классическое определение вероятности

Для начала надо вспомнить саму формулу, по которой будем считать. Итак, вероятность находится как $P=m/n$, где $n$ — число всех равновозможных элементарных исходов нашего случайного эксперимента с подбрасыванием, а $m$ — число тех исходов, которые благоприятствуют событию (то есть тому, что указано в условии задачи). Но как найти эти загадочные исходы? Проще всего пояснить на примерах.

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

Итак, монету бросают дважды. Если обозначить буквой Р выпадение решки (цифры), а буквой О — выпадение орла (герба), то все возможные выпадения можно записать так: РР, ОР, РО и ОО (соответствено, выпали две решки, орел потом решка, решка потом орел и два орла). Подсчитываем число этих комбинаций и получаем $n=4$. Теперь из них надо отобрать только те, что удовлетворяют условию «орел выпадет ровно один раз», это комбинации ОР и РО и их ровно $m=2$. Тогда искомая вероятность равна $P=2/4=1/2=0.5$. Готово!

Пример 2. Дважды бросают симметричную монету. Найти вероятность того, что оба раза выпала одна сторона.

Так как монета снова подбрасывается два раза, множество всех элементарных исходов эксперимента (или комбинаций, как мы их называем здесь для удобства), точно такое же: РР, ОР, РО и ОО, $n=4$. А вот условию «оба раза выпала одна сторона» удовлетворяют другие комбинации: РР и ОО, откуда $m=2$. Нужная вероятность равна $P=2/4=1/2=0.5$.

Как видим, все довольно просто. Перейдем к чуть более сложной задаче.

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

Снова применим формулу классической вероятности. Шаг первый — выписываем все возможные комбинации уже для 3 бросков! Это будут: ООО, ООР, ОРО, ОРР, РОО, РОР, РРО, РРР. Смотри-ка, бросков всего на один больше, а комбинаций возможных уже $n=8$ (кстати, они находятся по формуле $n=2^k$, где $k$ — число бросков монеты).

Теперь из этого списка надо оставить только те комбинации, где О встречается 2 раза, то есть: ООР, ОРО, РОО, их будет $m=3$. Тогда вероятность события $P=m/n=3/8=0.375$.

Взяли разгон и переходим к 4 монетам.

Пример 4. Монету бросают 4 раза. Найти вероятность того, что герб выпадет от 2 до 3 раз.

Приступаем к вычислению. Шаг первый — выписываем все возможные комбинации для 4 бросков монеты. Чтобы проверить себя, сразу подсчитаем, что их должно получиться $n=2^4=16$ штук! Вот они:
OOOO, OOOP, OOPO, OOPP, OPOO, OPOP, OPPO, OPPP,
POOO, POOP, POPO, POPP, PPOO, PPOP, PPPO, PPPP.

Теперь выбираем те, где герб (он же орел, он же буква О) встречается 2 или 3 раза: OOOP, OOPO, OOPP, OPOO, OPOP, OPPO, POOO, POOP, POPO, PPOO, их будет $m=10$. Тогда вероятность равна $P=m/n=10/16=5/8=0.625$.

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

2. Комбинаторика + классическая вероятность

Надо заметить, что если действовать исключительно переборным методом (как это делалось выше), с ростом числа монет быстро растет число комбинаций (для 5 монет — 32, для 6 монет — 64 и так далее), так что и вероятность ошибиться при выписывании исходов велика, метод решения теряет свою простоту и привлекательность.

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

Пример 4. Монету бросают 4 раза. Найти вероятность того, что герб выпадет от 2 до 3 раз.

Найдем количество всех равновозможных элементарных исходов эксперимента, заключающегося в бросании 4 монет. Все исходы можно закодировать некоторой последовательностью вида $X_1 X_2 X_3 X_4$, где $X_i=O$ (в $i$-ый раз выпал орел) или $X_i=P$ (в $i$-ый раз выпала решка). Найдем число всех таких последовательностей. Значение $X_1$ (результат первого броска) может быть выбран 2 способами (орел или решка), значение $X_2$ (результат второго броска) может быть выбран 2 способами (орел или решка), и так далее. Итого получим всего $n=2\cdot 2\cdot 2\cdot 2=16$ различных исходов. Или, если использовать формулу комбинаторики для числа размещений с повторениями из 2 объектов по 4 позициям, сразу получим $n=A_4^2=2^4=16$.

Найдем число благоприятствующих исходов с использованием комбинаторики. Сначала найдем число таких последовательностей, где О встречается ровно 2 раза. Выбираем $C_4^2$ способами 2 позиции, где будет стоять О (на остальных тогда ставим решки). Аналогично для последовательностей, где О встречается ровно 3 раза — $C_4^3$ способами выбираем 3 позиции, где будет стоять О (на оставшейся позиции записывается решка). Подсчитывая число сочетаний и складывая, найдем количество благоприятствующих комбинаций: $$ m=C_4^2+C_4^3=\frac+\frac=\frac+4=6+4=10. $$ Итого получаем такое же значение вероятности: $P=m/n=10/16=0.625$.

Конечно, этот подход кажется сложнее из-за более формального математического описания решения, но гораздо легче масштабируется.

Например, если рассмотреть подобную задачу:

Пример 5. Монету бросают 8 раз. Найти вероятность того, что герб выпадет ровно 4 раза

Ответ можно получить без выписывания 256 комбинаций (. ), просто по аналогии с примером выше: $$ n=2^8=256;\\ m=C_8^4=\frac=\frac=70;\\ P=\frac=\frac=0.273. $$

Ради полноты изложения приведу еще пример задачи, решаемой подобным образом (но если хотите, можете сразу переходить к более простому способу 3).

Пример 6. Монету подбрасывают 6 раз. Найти вероятность того, что гербы выпадут два раза и только подряд, а в остальные разы будут только решки.

Найдем количество всех равновозможных элементарных исходов эксперимента, заключающегося в бросании 6 монет. Так как каждый бросок дает 2 возможных исхода (О или Р), всего получим $n=2^6=64$ элементарных исхода (комбинации вида ОРОРОР, ОООРРР и т.д.).

Найдем число благоприятствующих исходов. Мысленно объединим два герба, которые должны появиться рядом, в один объект (ОО). Остается выбрать ему место среди остальных 4 решек (так гербов должно выпасть 2, то решек — 6-2=4). Существует $m=C_5^1=5$ способов выбрать позицию в последовательности из 5 объектов. Для наглядности, если выбрана позиция 2, то есть оба герба стоят на втором месте, это комбинация Р(ОО)РРР, если выбрана позиция 4 — РРР(ОО)Р.
Искомая вероятность: $P=m/n=5/64=0.078$.

Способ 3. Формула Бернулли

Рассмотрим общую задачу о подбрасывании монет.
Пусть бросается $n$ монет (или, что тоже самое, монета бросается $n$ раз). Нужно вычислить вероятность того, что герб появится в точности $k$ раз.

Так как броски монет — события независимые (результат броска одной монеты не влияет на последующие броски), вероятность выпадения герба в каждом броске одинакова (и равна $p=1/2=0.5$), то можно для вычисления вероятности применить формулу Бернулли: $$ P=P_n(k)=C_n^k \cdot p^k \cdot (1-p)^ = C_n^k \cdot \left(1/2\right)^k \cdot \left(1-1/2\right)^=C_n^k \cdot \left(1/2\right)^n. $$

То есть, мы вывели общую формулу, дающую ответ на вопрос «какова вероятность того, что герб появится в точности $k$ раз из $n$» (запишем в трех эквивалентных видах, выбирайте удобный для себя): $$ P=C_n^k \cdot \left(1/2\right)^n=\frac=C_n^k \cdot 0.5^n, \quad C_n^k=\frac. $$

А теперь все задачи решаются проще простого, вот глядите!

Подставляем $n=2, k=1$ и получаем $P=C_2^1 \cdot \left(1/2\right)^2=2 \cdot \frac=\frac=0.5.$

Пример 4. Монету бросают 4 раза. Найти вероятность того, что герб выпадет от 2 до 3 раз.

Это уже третий способ решения задачи!
Подставляем $n=4, k=2$ и $k=3$, получаем $$P=C_4^2 \cdot \left(1/2\right)^4+C_4^3 \cdot \left(1/2\right)^4=(6+4) \cdot \frac=\frac=0.625.$$

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

Подставляем $n=3, k=0$ и получаем $P=C_3^0 \cdot \left(1/2\right)^3=1 \cdot \frac=\frac=0.125.$

Пример 8. Пусть бросают 8 монет. Найти вероятность того, что орел не менее 7 раз.

Подставляем $n=8, k=7$ и $k=8$ и получаем $$P=C_8^8 \cdot \left(1/2\right)^8+ C_8^7 \cdot \left(1/2\right)^8=(1+8) \cdot \frac=\frac=0.035.$$

Таким образом, используя одну простейшую формулу, можно решать множество задач, причем неважно, 3 монеты бросается, или 30, сложность расчетов примерно одинакова. Но, если число бросков становится очень большим, удобнее использовать приближенные формулы Муавра-Лапласа, о которых можно узнать здесь.

Понравилось? Добавьте в закладки

Полезные ссылки

Решебник по вероятности

А здесь вы найдете более 200 задач о бросании монет с полными решениями (вводите часть текста для поиска своей задачи):

Определить количество способов оплаты N рублей с помощью монет достоинством 1, 2, 5, 10 рублей

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

Дано натуральное число N (N<100). Определить количество способов оплаты N рублей с помощью монет достоинством 1, 2, 5, 10 рублей. (Использовать цикл в цикле, желательно, как можно проще).

Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Определить число способов выплаты суммы n руб. с помощью монет достоинством 1, 2, 5 рублей
22. Дано натуральное число n(n<100). a) Определить число способов выплаты суммы n руб. с помощью.

Способы выплаты суммы n с помощью монет достоинством 1,2,5,10 рублей
нужно составить програлу в делфи. в консольном окне. получить все способы выплаты суммы n с.

Определить сколько монет достоинством в 20 и 50 рублей и каковы их порядковые номера
В коллекции нумизмата не более чем 90 монет всех возможных достоинств.Определить сколько монет.

Требуется определить количество способов выплаты n рублей монетами по 1, 2, 5 и 10 рублей
Требуется определить количество способов выплаты nn рублей монетами по 1, 2, 5 и 10 рублей. На.

Эксперт Pascal/Delphi

2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661

1 2 3 4 5 6 7 8 9 10

var n,n1,n2,n5,n10,c:integer; begin write('n=');readln(n); for n1:=1 to n-17 do for n2:=1 to n-17 do for n5:=1 to n-17 do for n10:=1 to n-17 do if n1+n2*2+n5*5+n10*10=n then c:=c+1; writeln('Способов:',c); end.

9874 / 5242 / 3306
Регистрация: 17.08.2012
Сообщений: 16,012

Joy, в задании не сказано, что необходимо использовать монеты всех указанных номиналов. Получается какая-то нелепая ситуация: менее 17 рублей оплатить невозможно. Где Вы видели продавца, который накладывал бы столь несуразные условия на оплату? К тому же, у Вас количество итераций в циклах явно излишнее.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

var n, n1, n2, n5, n10, c: integer; begin write('n = '); readln(n); c := 0; for n10 := 0 to n div 10 do for n5 := 0 to n div 5 do for n2 := 0 to n div 2 do for n1 := 0 to n do if n = 10 * n10 + 5 * n5 + 2 * n2 + n1 then begin inc(c); break end; writeln('Способов: ', c); readln end.

Задача о сумме

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

В двух словах суть проблемы описывается так: экспоненциальная зависимость. То есть выпуск нового типа монет несуществующего доселе номинала влечёт за собой увеличение количества комбинаций монет в два раза. Ещё один номинал – ещё в два раза, и так до условной бесконечности. При галопирующей инфляции, когда новые монеты/купюры выпускаются достаточно часто, для решения задачи придётся покупать более мощный компьютер. А где на это взять деньги при галопирующей то инфляции?

Итак, решение, которое на самом деле достаточно просто.
Если представить отрезок от нуля до С (сдача) с нанесёнными на ней точками, соответствующими номиналам монет, то любой интеллектуальный человек увидит примерно следующую картинку:

Ну, возможно в других цветах.
Итак, что мы можем сказать про красные точки? Конечно же то, что число, соответствующее любой этой точке, есть сумма, которую мы можем выдать в виде сдачи. Причём одной монетой. Возможно кто-то увидел что-то другое, но я, как художник, вкладывал именно этот смысл. И, как художник же, дорисую на этой картинке ещё одну точку, соответствующую сумме первой (слева направо) точки с этой же точкой (всё правильно: получится удвоенный номинал). Дорисую этим же цветом, ибо новая точка означает то же самое – эта сумма так же может быть сдачей.

Далее беру первую точку и суммирую со второй, даже если вторая точка это предыдущая сумма (это неважно, ибо все точки здесь равны). Новую точку опять нанесу на отрезок.

Если новая точка выходит за пределы отрезка, то ничего не рисуем, а возвращаемся к началу отрезка и берём следующую точку, то есть вторую. Далее то же самое (слева направо).
Собственно, когда точка С (напомню, это сдача) станет красной, можно считать, что решение найдено. А можно пройти полный цикл и найти оптимальное решение, что бы количество монет было минимальным.

С точки зрения программирования, здесь два цикла. Первый от 0 до С/2 (нет необходимости брать первую точку большей С/2, т.к. вторая точка всегда больше первой и в сумме они выйдут за границы отрезка). Второй цикл является встроенным в первый, он начинается с той же точки, на которую указывает внешний цикл и до момента, когда сумма покинет границы отрезка.
По сути это перебор: мы не теряем ни одного варианта, и гарантированно найдём оптимальное решение, или придём к выводу, что решения нет.

Давайте подсчитаем количество итерации внутри наших циклов. По внешнему циклу – это С/2, по внутреннему – где-то столько же. Умножим С/2 * С/2 = (С^2) / 4. Округлим до С в квадрате. Это наихудший вариант, когда весь наш отрезок просто состоит из красных точек. Если же между точками будут пробелы, количество итераций значительно уменьшится.
Как видим при определении сложности решения задачи мы не используем количество номиналов монет. Эта величина напрямую совсем никак не влияет на сложность решения. Влияют величины этих номиналов, скажем монета в 1 цент и сделает этот отрезок полностью красным. Поэтому эту монету лучше и не брать в расчёт, а в конце решения взять ближайшую к С красную точку и набросать сверху одноцентовиков. Но это уже момент оптимизации алгоритма, а она за рамками этой статьи.

Вот собственно и всё, что хотелось бы сказать. Рабочую версию программы можно найти здесь: github link

1. В файле init.h задать COINS_NUMBER — количество номиналов монет, и AMOUNT — сумма сдачи.
2. В файле coinc.c указать номиналы монет в массиве coins.
3. Под Linux запустить make_sh.
4. Запустить программу app на выполнение

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

Приведу какой-нибудь забавный пример. Представим, что в какой-нибудь стране к власти пришли математики и ввели в обращения 32 номинала монет: 2, 3, 5, 7, 11, 13, 17, 19… 131. Для удобства счёта выбрали только простые числа (ну не смешно ли?). И, что бы убедиться, что денежная реформа прошла успешно, послали в магазине гонца разменять купюру 5333 (тоже простое число). Кассир на стареньком одноядернике решил задачу: 39 монет номиналом 131 пифагороцентов, одну монету 127 и одну 97. Расчёт занял 3 секунды и чуть больше мегабайта памяти. Правительству доложили, что народ реформой доволен, считает быстро.

P.S. Кстати иметь номиналы монет в виде простых чисел – на самом деле хорошая идея, ибо любую сумму можно представить двумя или тремя монетами, и нет смысла в больших кошельках.

И пример, который чуточку сложнее проверить. Монеты, сто номиналов в такой вот странной последовательности: 0101, 0202, 0303… 9898, 9999, 100100. Сумма сдачи: 101010. Поиск решения занял 1 секунду и чуть больше мегабайта памяти. А решения, собственно, и нет, то есть нельзя такими монетами набрать такую сумму. С этими же монетами проверка суммы в 1 миллион займёт 26 мегабайт и сотни секунд, что говорит об экспоненциальной зависимости от суммы, но не количества номиналов монет.

Если будет интересно, следующий раз напишу о том, как взять большое число, разбить его на любые две/три/… части, занести эти части в массив, туда же добавить несколько сотен рандомных чисел и, не подсматривая, найти в массиве составляющие исходного большого числа.

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Размен монетами, найти количество способов

На страницу 1 , 2 След.

Размен монетами, найти количество способов
06.06.2010, 15:57

Заслуженный участник

Последний раз редактировалось PAV 09.06.2011, 11:43, всего редактировалось 1 раз.

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

Это первая задача из задачника Полиа, Сеге «Задачи и теоремы из анализа». Я её решил, как мне кажется, дурацким способом, типа составления таблицы, и сведения задачи к аналогичным более простым. Кто знает способ проще?

Re: Размен монетами
06.06.2010, 16:04

Заслуженный участник

Re: Размен монетами
06.06.2010, 16:09

Заслуженный участник

Да. Как сделали?
Re: Размен монетами
06.06.2010, 16:13

Заслуженный участник

Можно ввести $q(n; k_1,\dots,k_m)$ — количество вариантов размена суммы в $n$ копеек монетами достоинств $k_1,\dots,k_m$ и считать с помощью рекуррентного уравнения $$q(n;k_1,\dots,k_m) = q(n;k_2,\dots,k_m>) + q(n-k_1;k_1,\dots,k_m),\quad q(0;k_1,\dots,k_m) = 1, q(-n;k_1,\dots,k_m) = 0, q(0;) = 1, q(n;) = 0$» /> Prelude> let q 0 _ = 1; q n _ | n < 0 = 0; q n [] = 0; q n ks = q n (tail ks) + q (n - (head ks)) ks Prelude> q 100 [1,2,5,10,20,50] 4562 Re: Размен монетами 06.06.2010, 16:17 <table cellspacing=$ Заслуженный участник

Xaositect
Я так и делал. Сначала на бумажке, потом в екселе
Re: Размен монетами
06.06.2010, 16:22

Заслуженный участник

Ну, если хочется красиво, то можно производящие функции для $q(n;1)$ , $q(n;1,2)$ , $q(1,2,5)$ , $q(n;1,2,5,10)$ , $q(n;1,2,5,10,20)$ , $q(n;1,2,5,10,20,50)$ последовательно выписать и получить общее выражение, но оно будет страшное.

Re: Размен монетами
06.06.2010, 16:27

Заслуженный участник

Ну а я набросал рекурсивную процедуру на Pascal (больше ни на чем не умею). Тоже не шибко умно.
Re: Размен монетами
06.06.2010, 16:29

Заслуженный участник

Xaositect
Это вторая задача в задачнике. $$f(\zeta)=\dfrac<1><(1-\zeta)(1-\zeta^2)(1-\zeta^5)(1-\zeta^<10>)(1-\zeta^)(1-\zeta^)>$» />. Коэффициент при <img decoding=$ равен $q(n;1,2,5,10,20,50)$ .

Только как это поможет найти конкретно это число? Не понял, что значит последовательно выписать?

Re: Размен монетами
06.06.2010, 16:52

Заслуженный участник

Padawan в сообщении #328319 писал(а):
Только как это поможет найти конкретно это число? Не понял, что значит последовательно выписать?

Я имел в виду, что это выражение не сразу же получается, а последовательно.
$$f_1 = \frac<1><1-\xi>$» />, <img decoding=$ явное выражение.

Re: Размен монетами
06.06.2010, 17:05

Заслуженный участник

Xaositect в сообщении #328335 писал(а):

$P(\xi)$ получается $600-50-20-10-5-2-1=512$ -ой степени. Жесть . А разложение $$\frac<1><(1-\xi)^m>$» /> правда простое — просто <img decoding=$ раз почленно продифференцировать (и еще на $m!$ поделить).