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

от admin 14.03.2023

14.03.2023

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

Можно ввести $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 raquo; /> Ну, если хочется красиво, то можно производящие функции для <img decoding async$ , $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)$ последовательно выписать и получить общее выражение, но оно будет страшное.

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

Я имел в виду, что это выражение не сразу же получается, а последовательно.
$$f_1 = \frac<1><1-\xi> raquo; />, <img decoding async$ получается $600-50-20-10-5-2-1=512$ -ой степени. Жесть . А разложение $$\frac<1><(1-\xi)^m> raquo; /> правда простое — просто <img decoding async$ поделить).
Ну а как поможет найти.
$$\frac<1><(1-\xi)(1-\xi^2)(1-\xi^5)(1-\xi^<10>)(1-\xi^<20>)(1-\xi^<50>)> = \frac<P(\xi)><(1-\xi^<100>)^6> raquo; />, потому что каждый <img decoding async$ получается $600-50-20-10-5-2-1=512$ -ой степени. Жесть .
Свободный член — . А коэффициент при сотой степени — тайна. Короче, эти соображения конкретно для $n=100$ задачу не помогают решить.
Не такая уж и тайна:
$$ P(\xi)=(\xi +1)^2 \left(\xi ^4+\xi ^3+\xi ^2+\xi +1\right)^2 \left(\xi ^<40>-\xi ^<30>+\xi ^<20>-\xi ^<10>+1\right)^6 \left(\xi ^<50>+2 \xi ^<40>+2 \xi ^<30>+2 \xi ^<20>+2 \xi ^<10>+1\right)^5 \left( \xi ^4-\xi ^3+\xi ^2-\xi +1 \right)^3 raquo; /> Правда, всё одно с цешками придётся повозиться. Сколькими способами можно разменять рубль на монеты достоинством в 1, 2, 5, 10, 20 и 50 копеек? Это первая задача из задачника Полиа, Сеге «Задачи и теоремы из анализа». Я её решил, как мне кажется, дурацким способом, типа составления таблицы, и сведения задачи к аналогичным более простым. Кто знает способ проще? Вроде было же. Правильный ответ 343. — Вс июн 06, 2010 19:58:17 — То есть я хотел сказать, что выписывание производящей функции и разложение её в ряд в Maple — это самый простой способ решения. Самый простой из «ручных» способов описан в книге «Конкретная Математика» где-то рядом со страницей 363. Там надо составлять таблицу по принципу сведения задачи к более простой, как, по-видимому, и сделал автор темы. В общем случае задача не решена за <img decoding async$ , конечно, простое, но не считается решением для этой задачи.

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

Mrdenk

Чтобы решить эту задачу, будем решать более мелкие.

Например, сколькими способами можно разменять 4 рубля монетами 2 и 1?

Очевидно, что чтобы узнать, сколько есть способов получить 4 рубля, мы можем сложить количество способов получения двух рублей и трех, так как только из них мы можем с помощью 1 рубля и 2 рублей получить 4 рубля. Воспользуемся этой идеей и составим таблицу для нашей задачи, там где левый столбик число монет, а правый, количество способов

Три рубля мы можем получить как из двух рублей, так и из нуля, сложим их способы

Для 5 рублей теперь надо проверять суммы на 5 меньше, получим сумму способов из 0, 2, 4

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

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

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

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

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

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

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

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

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

Можно ввести $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$» /> Ну, если хочется красиво, то можно производящие функции для <img decoding=$ , $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)$ последовательно выписать и получить общее выражение, но оно будет страшное.

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

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

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

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

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

$P(\xi)$ получается $600-50-20-10-5-2-1=512$ -ой степени. Жесть .
Свободный член — . А коэффициент при сотой степени — тайна. Короче, эти соображения конкретно для $n=100$ задачу не помогают решить.
Не такая уж и тайна:
$$ P(\xi)=(\xi +1)^2 \left(\xi ^4+\xi ^3+\xi ^2+\xi +1\right)^2 \left(\xi ^<40>-\xi ^<30>+\xi ^<20>-\xi ^<10>+1\right)^6 \left(\xi ^<50>+2 \xi ^<40>+2 \xi ^<30>+2 \xi ^<20>+2 \xi ^<10>+1\right)^5 \left( \xi ^4-\xi ^3+\xi ^2-\xi +1 \right)^3 $» /> Правда, всё одно с цешками придётся повозиться. <div style=$

Читать:

Elenberg ht 410 как включить радио

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

Вроде было же.
Правильный ответ 343.

— Вс июн 06, 2010 19:58:17 —

То есть я хотел сказать, что выписывание производящей функции и разложение её в ряд в Maple — это самый простой способ решения. Самый простой из «ручных» способов описан в книге «Конкретная Математика» где-то рядом со страницей 363. Там надо составлять таблицу по принципу сведения задачи к более простой, как, по-видимому, и сделал автор темы. В общем случае задача не решена за $O(1)$ даже для трех произвольных монет. Решение за $O(n)$ , конечно, простое, но не считается решением для этой задачи.

Задача по информатике на собеседовании в IT-компанию. »Размен монет»

Всем привет! Сегодня решим задачу по информатике, которую часто дают на собеседованиях в различные IT-компании (или похожую ей).

Задача: Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму, введённую с клавиатуры. Максимальная сумма 1000 центов.

Решение: Рассмотрим на примере. Пусть сумма будет равна 25 центов.

Сначала пытаемся использовать самые большие монеты. Монета в 50 центов в данном случае не пригодится. Поэтому берём в 25 центов. Это уже 1 вариант. Так же мы можем разбить сумму в 25 центов и без монеты в 25 центов (Т.е использовав монеты достоинством в 10, 5, 1). На рисунке показан этот случай стрелкой влево.

Число 25 можно разбить, использовав 10-ти центовые монеты, а можно и более мелкими монетами(5, 1). Поэтом от 25-ти на рисунке идут опять две стрелочки. Если мы используем монету достоинством в 10 центов, то мы кладём 10 и нам теперь необходимо разбить уже 15. Число 15 опять мы может разбить, использовав 10-ти центовые монеты, а можно 15 разбить и более мелкими монетами. И т.д. Продолжая эту логику у нас от каждого числа будет по 2 стрелочки. Продолжаем раскладывать, пока у нас не получатся элементарные варианты. Количество вариантов обозначены красным цветом.

Почему от некоторых чисел на рисунке идёт по 1-му варианту ? Это происходит из-за того, что мы в этих вариантах решили разбить число самыми маленькими монетами в 1 цент. Таким образом, даже большие числа вроде 20, будут раскладываться в этих случаях единственным образом 20 = 1 + . + 1. А почему от 5 идёт два варианта ? Число пять можно разложить, как пяточком, так и по 1 центу.

Теперь просуммируем все числа красным цветом и получим количество вариантов. У нас получается число 13

Данный тип задач может попасться и на олимпиаде по информатике. Реализовывать будем на языке программирования C#!

Ещё одна схема для суммы 37 приведена на рисунке. Получается 24 комбинации.

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

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

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

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

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

Задача по информатике на собеседовании в IT-компанию. »Размен монет»

Сколько всего значащих цифр двоичной записи числа 120

Сколько всего суббот и воскресений в году

Похожие статьи