?

Log in

No account? Create an account
В математике я не сильна :( - Трава Зю. Её слушают.
Зю, когда Бог тебя создавал, он был укурен©
curlyzu
curlyzu
В математике я не сильна :(
30 выдохнули || выдохнуть
Comments
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 рублёвых монеты).
30 выдохнули || выдохнуть