Число способов разменять 1 руб по 1,5,10,20,50 коп

[troy]

Подскажите как решать эту задачу:
Даны достаточное количество монет номиналом 1 коп, 5 коп, 10 коп, 20 коп. и 50 коп.
Надо найти число всех вариантов составления 100 коп.
?
Так и сяк думал ничего не придумал, давно математику в руки не брал )))))

Добавлено спустя 4 минуты 47 секунд:

Дайте хоть направление в какую сторону копать?

Добавлено спустя 7 минут 11 секунд:

Правильно ли копать в сторону ДИОФАНТОВЫХ УРАВНЕНИИ
если разложить задачу так ;
(a1) + 5*(a2) + 10 *(a3) + 20*(a4) + 50*(a5)=100

[Brukvalub]

Я бы стал решать задачу перебором, причем перебор бы я вел по убыванию номинала 50 коп. может встретиться 0, 1 или 2раза. Если 50+50 - это один вариант. Если 50 коп. берется один раз, то нужно вторые 50 коп. разложить в сумму меньших номиналов, и т.д.

[troy]

Я же так всю свое оставщуюся жизнь буду перебирать ))))

[Brukvalub]

troy писал(а):

Я же так всю свое оставщуюся жизнь буду перебирать

Думаю, что дольше проживете

[Альберт120446]

Вариант решения:
5 имеет 1разложение (р).
10 =5+5 - 3 р
20 = 10 + 10 - 13 р
50 = 20 + 20 +10 - 4 р
50 = 20 +10 +10 +10 - 28 р
50 = 10 + 10 + 10 + 10 + 10 - 244 р
Всего для 50 есть 276 р
100 = 50 + 50 - 1 р
100 = 50 + 276 р = 276 р
100 = 276 р х 276 р = 76176
Итак, суммируя для 100 получаем 76453 варианта, может ошибся, не проверял

[Zealint]

troy в сообщении #88270 писал(а):

Подскажите как решать эту задачу:
Даны достаточное количество монет номиналом 1 коп, 5 коп, 10 коп, 20 коп. и 50 коп.
Надо найти число всех вариантов составления 100 коп.?

Самый простой способ: составляем производящую функцию -

$$G(z)=\frac{1}{1-z}\frac{1}{1-z^5}\frac{1}{1-z^{10}}\frac{1}{1-z^{20}}\frac{1}{1-z^{50}}$$

и находим коэффициент при $z^{100}$ в разложении функции в ряд. Для этого открываем систему компьютерной алгебры (я взял Maple) и пишем

series ( 1/(1-z)/(1-z^5)/(1-z^10)/(1-z^20)/(1-z^50), z, 101 );

Смотрим на коэффициент: 343 - это и есть правильный ответ, при условии, что порядок монет не принимается во внимание (т. е. если 6=1+5=5+1 - один и тот же способ).

[juna]

Можно и чисто по-программистски

Используется синтаксис Lisp

(defun count-change (amount) 
  (cc amount 5)) 
(defun cc (amount kinds_of_coins) 
  (cond ((= amount 0) 1) 
         ((or (< amount 0) (= kinds_of_coins 0)) 0) 
         (t (+ (cc amount 
                        (- kinds_of_coins 1)) 
                   (cc (- amount 
                           (first_denomination kinds_of_coins)) 
                        kinds_of_coins))))) 
(defun first_denomination (kinds_of_coins) 
  (cond ((= kinds_of_coins 1) 1) 
         ((= kinds_of_coins 2) 5) 
         ((= kinds_of_coins 3) 10) 
         ((= kinds_of_coins 4) 20) 
         ((= kinds_of_coins 5) 50))) 
 

Используется синтаксис Lisp

 >(count-change 100)
343
 

[iig]

Ну вы даете проблемы!
У нас в Белоруси коробка спичек стоит 50 рублей,
а тут копейки считают.
А зарплата миллионы.Может кто разменяет?

Строгое предупреждение за оффтопик!

[superdemon]

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

-- Вс дек 26, 2010 12:34:20 --

мне немного не ясно,что во всех этих функциях значит "z"? что это за переменная?
я конечно извиняюсь, за некоторую заторможенность в математике, но нельзя ли как то поподробнее (для чайников, что называется).
У меня есть монетки 1,5,10,20,50. мне можно использовать не более 10 монеток и надо составить число 100. какой конечной формулой можно воспользоваться?

[Ales]

superdemon в сообщении #391744 писал(а):

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

$\frac{1}{1-z}\frac{1}{1-z^5}\frac{1}{1-z^{10}}\frac{1}{1-z^{20}}\frac{1}{1-z^{50}}=$
$=(1+z+z^2+z^3+....)(1+z^5+(z^5)^2+....)(1+z^{10}+(z^{10})^2+....)(1+z^{20}+(z^{20})^2+....)(1+z^{50}+(z^{50})^2+....)$

Если все перемножить, то коэффициент при $z^{100}$ будет равен числу всевозможных составлений 100 из 1,5,10,20,50.

-- Вс дек 26, 2010 15:45:00 --

superdemon в сообщении #391744 писал(а):

мне можно использовать не более 10 монеток

Если у Вас такое ограничение, то предложенное решение через производящую функцию не подходит.

Даже без ограничения: не представляю как быстро найти коэффициент при $z^{100}$ без программы.

-- Вс дек 26, 2010 16:04:07 --

Ограничение на число монет, кажется, упрощает задачу.
Есть два случая:
- монеты в 1 коп. не используются, делить на 5 и считать аналогичное число для 20 из не более чем десяти монет по 1,2,4,10;
- используется 5 монет по 1 коп. и одна монета 5 коп, тоже делить на пять и считать число для 18 из не более чем четырех монет по 1,2,4,10.
Найти число вариантов для каждого случая и сложить.

[APTEM]

Решается также с помощью производящих функций.

1) Если есть не более 10 монет каждого вида:

$$f(z)=(1+z+z^2+...+z^{10})*(1+(z^5)+(z^5)^2+...+(z^5)^{10})*...*(1+(z^{50})+(z^{50})^2+...+(z^{50})^{10})$$

Коэффициент перед $z^{100}$ будет ответом.

2) Если количество монет каждого вида не ограничено, но при составлении рубля можно использовать не более 10 монет (всех видов):

$$f(z,x)=\frac{1}{1-x*z}\frac{1}{1-x*(z^{5})}\frac{1}{1-x*(z^{10})}\frac{1}{1-x*(z^{20})}\frac{1}{1-x*(z^{50})}$$

Ответ - сумма коэффициентов перед $z^{100},x*z^{100},...,x^{10}*z^{100}$

Степень при x показывает нам количество монет использованных в комбинации, степень при z - сумму номиналов монет.

Комбинируя эти идеи, можно решить более сложные вариации данной задачи.

[Zealint]

APTEM в сообщении #396344 писал(а):

Решается также с помощью производящих функций.

А вы не видели, что то же самое написано в посте от "Вт янв 26, 2010 10:47:18"?

[APTEM]

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

[Ales]

APTEM в сообщении #396344 писал(а):

Решается также с помощью производящих функций.

На самом деле, это не совсем так, или совсем не так.
Использование производящих функций дает способ решения (алгоритм), но он не помогает.
Ведь надо вычислить 1000 чисел. Без специальной программы это невозможно сделать за разумное время и без ошибок.

-- Вс янв 09, 2011 10:53:37 --

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

[Simba]

Мудрить не стоит, если порядок важен, то F(1,5,10,20,50;100)=F(1,5,10,20,50;99)+F(1,5,10,20,50;95)+F(1,5,10,20,50;90)+F(1,5,10,20,50;80)+F(1,5,10,20,50;50)=..., в общем то, это тот же самый перебор, просто ,практически, он удобнее, где F(1,5,10,20,50;N) - означает кол-во способов составить сумму N из монет достоинтсва 1,5,10,20,50. А формула означает, которую я привел означает, что сначала мы положим на 1ое место 1, тогда сумма станет 99, затем на 1ое место 5, тогда сумма 95 итд. Иного решения я не вижу.