Цитата(5859267andrey @ 17.12.2006, 15:26  ) |
| помогите посчитать кол-во вариантов размена рубля монетами номиналом 1 2 3 5 10 15 20 копеек |
Всего: 63992 варианта.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > количество способов размена |
| Автор: 5859267andrey 17.12.2006, 16:26 |
| помогите посчитать кол-во вариантов размена рубля монетами номиналом 1 2 3 5 10 15 20 копеек |
| Автор: comp 17.12.2006, 17:22 |
| 5859267andrey, brute force |
| Автор: esperant0 17.12.2006, 18:47 | ||
динамическое программирование |
| Автор: Dov 17.12.2006, 22:01 | ||
Всего: 63992 варианта. |
| Автор: esperant0 18.12.2006, 08:40 | ||||
Автор не указал считаются ли одинаковые наборы с разным порядком на монетах разными. А пока это не определено решений два. А значит ваше не верное.  |
| Автор: SoWa 18.12.2006, 15:31 |
| Ну боже мой. Вы где учитесь и сколько вам лет?! Открываем учебник даже 11 класса в разделе комбинаторика. Сочетания. С повторениями. Принципиально не буду писать формулу, дабы хоть немного старались люди сами искать. esperant0, если решений два- то первое решение заведомо верно. Так как оно является решением. Аналогично со вторым. СУВ, SoWa |
| Автор: esperant0 18.12.2006, 21:34 | ||
Сочетания с повторениями, тут не подходит это раз. Ответ может быть и не верным при условии, что автор имел в веду второе решение. с ув. |
| Автор: Dov 18.12.2006, 21:57 | ||
esperant0, если не трудно, переведи на русский, недопонял.  |
| Автор: esperant0 18.12.2006, 22:55 | ||||
Наприме надо вернуть сдачу 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 способа. |
| Автор: Dov 19.12.2006, 01:12 |
| esperant0, тогда почему ты этот способ (2,2,2,2,2,2) считаешь за один? Это не правильно. Ты попереставляй двойки местами, сколько там нужно раз, и получишь ещё туеву хучу вариантов. А почему бы и нет? Здесь же (2,5,5) (5,5,2) (5,2,5) ты попереставлял. |
| Автор: SoWa 19.12.2006, 07:42 | ||
Позволь поинтересоваться, почему? Берем разные наборы монеток, ищем сочетания для каждого набора в отдельности, суммируем их. Вуа-ля, ответ. Разве нет? |
| Автор: esperant0 19.12.2006, 09:04 | ||||||
Потому, что 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. |
| Автор: Dov 19.12.2006, 19:20 | ||
Так в том то и дело, что нужно считать варианты по количеству монет, а не по их порядку.  А иначе, можно ещё по году выпуска монеты составлять варианты.  |
| Автор: esperant0 19.12.2006, 20:37 | ||||
Согласен с Вами, вообщем автор должен точно сказать, что считать. |
| Автор: 5859267andrey 21.12.2006, 00:05 |
порядок монет не важен. препод задал задачу - отобразить таблицу где столбцы - номинал монет, а в строках количество раз которое взяли монету что-бы сумма была равна 100 коп. простой вариант: 100 раз по копейке или 5 раз по 20. причем не обязательно чтобы присутствовали все монеты, т.е в столбцах может быть 0 раз по 5 или 15 копеек  |
| Автор: Dov 21.12.2006, 08:19 |
| 5859267andrey, на с / с++ устроит? |
| Автор: esperant0 21.12.2006, 16:24 |
| Пусть у нас для примера монеты достоинством 1 2 5. Пусть надо вернуть сдачю из х денег Тогда OTBET есть F(x,5)+F(x,2)+F(x,1) F(i,5)=F(i-5,5)+F(i-2,2)+F(i-1,1) F(0)=1 F(1)=1 F(2)=2 нетрудно обобщить вышеприведенное решение динам. программирования. |
| Автор: 5859267andrey 21.12.2006, 19:26 |
| на с\с++ нет. желательно на Delphi. |
| Автор: Dov 21.12.2006, 20:17 | ||
Жаль.  |
| Автор: 5859267andrey 22.12.2006, 18:57 |
| |