Архив форумов ЦИТФорума

[Aragaer]

Забыл напрочь все, уже третий день сижу над задачкой:
Сколькими способами можно разложить 10 кусков сахара по 4-м стаканам (все куски сахара идентичны, все стаканы тоже).

Аналогичную задачу с разноцветными чашками вместо стаканов я все-таки решил, там ответ - (k+x)!/(k!x!), где k - число чашек сверх одной (три то есть), а x - число кусков сахара. Объяснение очень простое - это как раз число различных сочетаний из x букв "С" и k символов "|". Каждое такое сочетание соответствует одному способу раскладывания сахара (в первую чашку пойдет столько кусков сахара, сколько букв С до первого знака |, во вторую - от первого до второго и т.д.)

Была также задача совсем простая - по разноцветным чашкам раскладывать разноцветные же соломинки. Там все совсем элементарно: (кол-во чашек)^(кол-во соломинок).
Как видно, нет способа превратить задачу о чашках-соломинках в задачу о чашках-сахаре. И похоже, что стаканы-сахар к чашкам-сахару также не сводятся, должен быть какой-то другой способ решения. Но какой?
_________________
Open your eyes.
And Awaken.

[Mishak]

Это похоже перестановки с повторениями.
Если N-куски сахара а M - чашки, то число всех размещений равно
P(N,M-1) = (N+M-1)!/N!(M-1)!

[Aragaer]

Задачу с сахаром и стаканами я вроде даже решил - вывел довольно хитрую реккурентную формулу, но собрать ее во что-то логичное не получилось. Вот она:

Число способов разложить x кусков сахара по k чашкам:
f(x, k) = Сумма(от i=0 до округление_вниз(x/k))f(x-k*i, k-1);
f(x, 1) = 1 для любого x.
Идея решения заключается в том, что стаканы отсортированы по невозрастанию сахара в них и мы просто перебираем варианты, сколько кусков сахара положить в последний (от 0 до x/k). После чего столько же кладем во все остальные и переходим к следующему с конца стакану.

Следующая задачка тоже, как ни странно, оказалась непростой:
7 разноцветных соломинок, 4 одинаковых стакана. Выводится реккурентная формула, но вот ее как раз во что-то такое собрать можно...
_________________
Open your eyes.
And Awaken.