?

Log in

No account? Create an account
В математике я не сильна :( - Трава Зю. Её слушают.
Зю, когда Бог тебя создавал, он был укурен©
curlyzu
curlyzu
В математике я не сильна :(
Про сашин отит, и как мы к врачу ходили
про мою прекрасную работу и ужасных клиентов .

И вопрос в массы: имеется какая-то сумма, например, 16 рублей: проезд в автобусе.
Как можно посчитать количество вариантов купюр и монет?

Метки: , ,

30 выдохнули || выдохнуть
Comments
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 08:41 (UTC) (Ссылка)
Посчитать - с учтом вариантов дал 1000р получил сдачу 984р?
По мне так проще нарисовать програмку которая будет строить деревья ,к сожалению - не бинарные :( - а потом посчитать число ветвей. Метод конечно "грубой силы", но какого-то универсального алгоритма дающего на выходе количество вариантов для подобных задач я навскидку не вспоминаю :(
curlyzu From: curlyzu Date: Декабрь, 11, 2008 08:54 (UTC) (Ссылка)
нинини.
сдача не в счет :) именно: сколько вариантов собрать такую сумму есть?
foksu From: foksu Date: Декабрь, 11, 2008 09:40 (UTC) (Ссылка)
какие монеты-купюры есть в наличии?:) наши обычные рублями? или еще копейки и прочее?
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 09:49 (UTC) (Ссылка)
А вот про копейки я забыл :(
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 09:57 (UTC) (Ссылка)
с копейками - умножаем числовариантов собрать рублями на число вариантов собрать рубль копейками ;)
foksu From: foksu Date: Декабрь, 11, 2008 10:02 (UTC) (Ссылка)
ну не совсем:))))
там же не будет учтены варианты, когда все собрано только рублями;) + есть возможность учесть несколько раз повторяющиеся наборы.
комбинаторика покоя не дает:)
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 10:05 (UTC) (Ссылка)
вот повторяющиеся наборы это да, засада. Но можно прикинуть верхнюю границу ;)
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 10:04 (UTC) (Ссылка)
их меньше чем 1090 штук ;)
взять рубль сразу
или собрать два раза по 50 коп.
50 коп можно взять сразу или собрать 5 раз по 10 копеек (но тут будут повторы сильно уменьшающие действительные способы)
10 копеек можно собрать 4 способами...
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 09:47 (UTC) (Ссылка)
25 вроде
1) 16х1
2) 14х1+1х2
3) 12х2+2х2
4) 11х1+1х5
5) 10х1+3х2
6) 9х1+1х2+1х5
7) 8х1+4х2
8) 7х1+2х2+1х5
9) 6х1+5х2
10) 6х1+2х5
11) 6х1+1х10
12) 5х1+3х2+1х5
13) 4х1+6х2
14) 4х1+1х2+2х5
15) 4х1+1х2+1х10
16) 3х1+4х2+1х5
17) 2х1+7х2
18) 2х1+2х2+2х5
19) 2х1+2х2+1х10
20) 1х1+5х2+1х5
21) 1х1+3х5
22) 1х1+1х5+1х10
23) 8х2
24) 3х2+2х5
25) 3х2+1х10
Посчитанонно на бумажке построением дерева
алгоритм примерно такой -
1) ветвь "растим" до требуемой суммы узлами наименьшего номинала.
2) двигаясь вверх по ветви, из каждого узла пытаемся построить ветвь из номиналов больших чем используемый в узле (исключает повторы, т.к. комбинации 5-1 и 1-5 - равнозначны).

как-то так.
Алгоритм не сильно детаизирован, там еще условие на конечные узлы и существование ветвей - по равенству требуемой сумме ;)
denspb From: denspb Date: Декабрь, 11, 2008 10:52 (UTC) (Ссылка)
Общая идея рассчёта такая:
Заведём такую функцию
F(P, C) - количество способов набрать сумму P, используя монеты достоинством не старше C.
Для самой мелкой монеты это 1, если P делится на C, и 0, если не делится (ну нельзя набрать 3 рубля, имея только 2-рублёвые монеты).

Тогда F(P,C) = Sum (i = 0 to floor(P/C)) { F(P - C * i, prev(C)).
То есть прикидываем, что будет если мы возьмём 0,1,2.... монеты достоинством C.

Тут есть фишка.
Некоторые параметры будут повторяться - например, F(6, 2) может быть вызван если 10 рублей набрали 10-рублёвой бумажкой, или 2 монетами по 5 рублей. Поэтому надо запомниать уже подсчитанные F(P, C), и встретив такие P,C во второй раз не считать, а использовать запомненное число.
denspb From: denspb Date: Декабрь, 11, 2008 11:14 (UTC) (Ссылка)
Для набора денег в 10, 5, 2, 1 руб., 50, 10, 5, 1 коп. вариантов будет 3640054.
curlyzu From: curlyzu Date: Декабрь, 11, 2008 11:32 (UTC) (Ссылка)
0.0
уверен?????
3,5 миллиона вариантов? я ж щас руками сяду считать...
denspb From: denspb Date: Декабрь, 11, 2008 11:49 (UTC) (Ссылка)
Угу. Каждый рубль можно разбить 159 - 1 вариантами на копейки. 2 рубля разбиваются уже 1015 - 1 вариантами на монеты не крупнее рубля. И дальше-больше.
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 12:40 (UTC) (Ссылка)
Многовато для 1 рубля - у меня 146 вариантов получается
число вариантов; пример; комментарий
1; 100x1;
1; 95x1+1x5;
2; 90x1+2x5 или 90x1+1x10;
2; 85x1+1x5+1x10;
3; 80x1+2x5+1x10;
3; 75x1+1x5+2x10;
4; 70x1+2x5+1x10;
4; 65x1+3x5+1x10;
5; 60x1+2x5+3x10;
5; 55x1+5x5+2x10;
6; 50x1+2x5+4x10;
Итак видим что 50 коп можно набрать 36ю способами а число вариантов разбиения остатка увеличивается на 1 каждые 10 копеек.
Значит есть еще 36 вариантов если 50х1 коп сразу заменить на соотв монету, или еще 6+7+7+8+8+9+9+10+10=74 варианта если продолжать собирать мелочью.
итого поличаем 36+36+74=146 вариантов разбиения одного рубля.

А вы как считали?
denspb From: denspb Date: Декабрь, 11, 2008 12:50 (UTC) (Ссылка)
У меня 50 коп. набирается 37 способами (включая вариант самой 50-копеечной монеты):

f(50, 5) = 11
f(40, 5) = 9
f(30, 5) = 7
f(20, 5) = 5
f(10, 5) = 3
f(0, 5) = 1

f(50, 10) = 36
f(0, 10) = 1

f(50, 50) = 37

Для сотни:
f(100, 5) = 21
f(90, 5) = 19
f(80, 5) = 17
f(70, 5) = 15
f(60, 5) = 13
f(50, 5) = 11
f(40, 5) = 9
f(30, 5) = 7
f(20, 5) = 5
f(10, 5) = 3
f(0, 5) = 1

f(0, 10) = 1
f(50, 10) = 36
f(100, 10) = 121


f(0, 50) = 1
f(100, 50) = 158

f(100, 100) = 159
eltar_spinne From: eltar_spinne Date: Декабрь, 11, 2008 13:09 (UTC) (Ссылка)
Вот вроде бы аналогично считаю, а f(100,10) = 110 получается. Причем для f(50,10) - результаты совпадают.
denspb From: denspb Date: Декабрь, 11, 2008 16:04 (UTC) (Ссылка)
F(100, 10) - это сумма всех f(i * 10 , 5)
Если мы отличаемся на 11, то вы не учили сумму, когда 50 набирается 5 10-копеечными монетами.
matholimp From: matholimp Date: Декабрь, 11, 2008 11:31 (UTC) (Ссылка)
Еще чуть-чуть и "откроете" метод ветвей и границ. Перебор здесь лучше сначала провести по разбиениям на целые рубли, начиная с более крупных монет 5+5+5+1, 5+5+2+2+2, 5+5+2+2+1+1, 5+5+2+1+1+1+1 и т.д. Затем в каждом из вариантов, где есть хотя бы одна монета в 1р., любое их число можно разбить на две по 50к. Затем в каждом из вариантов, где есть хотя бы одна монета в 50к., любое их число можно разбить на пять по 10к. Затем в каждом из вариантов, где есть хотя бы одна монета в 10к., любое их число можно разбить на две по 5к. Наконец, в каждом из вариантов, где есть хотя бы одна монета в 5к., любое их число можно разбить на пять по 1к.
curlyzu From: curlyzu Date: Декабрь, 11, 2008 11:33 (UTC) (Ссылка)
как плохо быть лохом. я уже ничего не понимаю.
curlyzu From: curlyzu Date: Декабрь, 11, 2008 11:33 (UTC) (Ссылка)
кстати, еще купюра есть. 10р
matholimp From: matholimp Date: Декабрь, 11, 2008 13:27 (UTC) (Ссылка)

Есть даже монета в 10р.

И до кучи её юбилейных версий. Считать разными вариантами?
curlyzu From: curlyzu Date: Декабрь, 11, 2008 11:35 (UTC) (Ссылка)
хотя не, с третьего прочтения начинаю понимать. а автоматизировать это как-то?
я помню из курса математики, что есть последовательности, функции и интегралы. а вот что как применяют, уже не помню.
denspb From: denspb Date: Декабрь, 11, 2008 11:53 (UTC) (Ссылка)
Да вообще-то это было динамическое программирование.
Мы же тут не перебором всех вариантов занимаемся, нам только количество вариантов надо подсчитать.
matholimp From: matholimp Date: Декабрь, 11, 2008 13:42 (UTC) (Ссылка)
Чтобы найти количество ПОДвариантов придется перебрать основные варианты:
0) 3 варианта без рублевой монеты: 10+2+2+2, 5+5+2+2+2 и 2+2+2+2+2+2+2+2,
1) 2 варианта с одной рублевой монетой: 10+5+1 и 5+5+5+1,
2) 3 варианта с двумя рублевыми монетами: 10+2+2+1+1, 5+5+2+2+1+1 и 2+2+2+2+2+2+2+1+1,
и т.д.
Затем аналогично найдите число К вариантов размелочить рубль.
Тогда для нахождения количества вариантов с мелочью умножьте 0) на 0, 1) на К, 2) на 2К, 3) на 3К и т.д.
При суммировании не потеряйте варианты без мелочи.
denspb From: denspb Date: Декабрь, 11, 2008 18:05 (UTC) (Ссылка)
У подхода есть порок - нельзя так просто умножать на K.
Пусть из монет мельче рубля есть только 40 коп и 60 коп.
Рубль ими можно разменять только 1 способом (или 2, если считать сам рубль).
Но вот 2 рубля уже можно разменать ещё и вариантом 40+40+40+40+40 коп. То, что мы не учтём такие варианты занизит нам результат.

С другой стороны, у нас есть ошибка, завышающая результат:
пусть монеты будут по 50 и 25 копеек.
Тогда K = 3
50,50
50,25,25
25,25,25,25
Но 2 рубля (по рублю) можно размелочить только 5 способами, а не 6ю:
50,50,50,50
50,50,50,25,25
50,50,25,25,25,25
50,25,25,25,25,25,25
25,25,25,25,25,25,25,25,
А всё потому, что варианты размена 2 * (50 + 2*25) и (2*50) и (4*25) совпадают.
matholimp From: matholimp Date: Декабрь, 12, 2008 13:17 (UTC) (Ссылка)

Порок не в подходе, а в конкретной его реализации

Сначала нужно взять К=2 и составить аналогичный список разбиений на монеты, кратные 50коп.
Затем нужно взять К=5 и составить аналогичный список разбиений на монеты, кратные 10коп.
Затем нужно взять К=2 и составить аналогичный список разбиений на монеты, кратные 5коп.
Наконец, нужно взять К=5 и составить аналогичный список разбиений на монеты, кратные 1коп.


matholimp From: matholimp Date: Декабрь, 12, 2008 13:22 (UTC) (Ссылка)

И где Вы видели монеты по 25 копеек?

У меня нет ни звука о размене 2-рублевой монеты. Её меняем только на две по рублю, а уже рубль меняем на более мелкие.
Возможно, я недостаточно подчеркнул этот момент, но не ошибся. Если в предыдущем комменте речь о моем недосмотре, то здесь - от начала до конца Ваша неверная интерпретация.
denspb From: denspb Date: Декабрь, 15, 2008 17:23 (UTC) (Ссылка)

Re: И где Вы видели монеты по 25 копеек?

Я понял ваш подход как такой:

Если мы можем разменять монету C более мелкими с помощью K способов (не включающих саму монету), то следующую монету P, равную по стоимости M * C, можно разменять таким количеством способов: разбиваем только на C (1 вариант) + разбиваем всё, кроме одной на C, а остаток - более мелкими (K вариантов) + разбиваем всё, кроме одной на 2 * C, а остаток - более мелкими (2*K вариантов) + ... + сразу разбиваем всё мелкими (M*K вариантов).

Собственно, у такого подхода есть два недостатка:
1) Он явно не работает в случае, если есть некратные друг другу номиналы (пример с монетами 40 и 60 коп). Пример, близкий к реальности - 5 рублей и 2 рубля. Не очень понятно, как в Вашей схеме получится разбиение 10 = 2+2+2+2+2.
2) Если сумма C разбивается К способами, то не факт, что сумма 2*С разбивается теми же номиналами 2*К способами. (это как-раз пример про монеты по 25 и 50 коп, я в нём прошу просто разбить 2 рубля, точнее, 2 рублёвых монеты).
foksu From: foksu Date: Декабрь, 11, 2008 11:14 (UTC) (Ссылка)
Зю, уточни, пожалуйста, условия задачки, и я тебе расскажу, как мы их решаем с пятиклассниками:)
curlyzu From: curlyzu Date: Декабрь, 11, 2008 11:31 (UTC) (Ссылка)
а я мало написала? количество вариантов числа бумажек и монеток, из которых можно собрать 16 рублей.
30 выдохнули || выдохнуть