?

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: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 миллиона вариантов? я ж щас руками сяду считать...
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р
curlyzu From: curlyzu Date: Декабрь, 11, 2008 11:35 (UTC) (Ссылка)
хотя не, с третьего прочтения начинаю понимать. а автоматизировать это как-то?
я помню из курса математики, что есть последовательности, функции и интегралы. а вот что как применяют, уже не помню.
denspb From: denspb Date: Декабрь, 11, 2008 11:53 (UTC) (Ссылка)
Да вообще-то это было динамическое программирование.
Мы же тут не перебором всех вариантов занимаемся, нам только количество вариантов надо подсчитать.
foksu From: foksu Date: Декабрь, 11, 2008 11:14 (UTC) (Ссылка)
Зю, уточни, пожалуйста, условия задачки, и я тебе расскажу, как мы их решаем с пятиклассниками:)
curlyzu From: curlyzu Date: Декабрь, 11, 2008 11:31 (UTC) (Ссылка)
а я мало написала? количество вариантов числа бумажек и монеток, из которых можно собрать 16 рублей.
30 выдохнули || выдохнуть