помогите посчитать кол-во вариантов размена рубля монетами номиналом 1 2 3 5 10 15 20 копеек

Это сообщение отредактировал(а) 5859267andrey - 17.12.2006, 16:27

5859267andrey, brute force

динамическое программирование

Всего: 63992 варианта.   

Автор не указал считаются ли одинаковые наборы с разным порядком на монетах разными.


А пока это не определено решений два. А значит ваше не верное.  

Ну боже мой.
Вы где учитесь и сколько вам лет?! Открываем учебник даже 11 класса в разделе комбинаторика. Сочетания. С повторениями.
Принципиально не буду писать формулу, дабы хоть немного старались люди сами искать.
esperant0, если решений два- то первое решение заведомо верно. Так как оно является решением. Аналогично со вторым.

СУВ, SoWa

Сочетания с повторениями, тут не подходит это раз.


Ответ может быть и не верным при условии, что автор имел в веду второе решение.


с ув.

esperant0, если не трудно, переведи на русский, недопонял.   

Наприме надо вернуть сдачу 12 монетами по 2 и 5.


Ответ 1: это можно сделать следующими способами (2,2,2,2,2,2) (2,5,5)(5,5,2) (5,2,5)  - всего 4 способа


Ответ 2: (2,2,2,2,2,2) (2,5,5)  - 2 способа.

esperant0, тогда почему ты этот способ (2,2,2,2,2,2)  считаешь за один? Это не правильно. Ты попереставляй двойки местами, сколько там нужно раз, и получишь ещё туеву хучу вариантов. А почему бы и нет? Здесь же (2,5,5) (5,5,2) (5,2,5) ты попереставлял.   

Позволь поинтересоваться, почему?
Берем разные наборы монеток, ищем сочетания для каждого набора в отдельности, суммируем их. Вуа-ля, ответ. Разве нет?

Это сообщение отредактировал(а) SoWa - 19.12.2006, 07:44

Потому, что 
5 2 2 и 2 2 5 различаются. Чем? Порядком монет. А 2 2 2 2 2 2 и 2 2 2 2 2 2 этим не различаются.

Так вот, если автора интересует количество с пособов учитывающее порядок то ответ один, если порядок не учитывается ответ другой.


Ваше третие решение с утверждением что 222222 и 222222 разные способы я не понял, но вполне возможно оно имеет право существовать. Только определите формально что оно из себя представляет.

Добавлено @ 09:07 

А как мы берем разные наборы монет?  Количество наборов может быть экспоненциально, и соответсвенно ваше решение преведет к double exponental time complexity что не есть хорошо. Динамическое программирование приведет к exponental time complexity.

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

Согласен с Вами, вообщем автор должен точно сказать, что считать.

порядок монет не важен. препод задал задачу - отобразить таблицу где столбцы - номинал монет, а в строках количество раз которое взяли монету что-бы сумма была равна 100 коп. простой вариант: 100 раз по копейке или 5 раз по 20. причем не обязательно чтобы присутствовали все монеты, т.е в столбцах может быть 0 раз по 5 или 15 копеек