Есть N тарелок и M яблок.
Емкость тарелок (количество яблок на тарелке) не ограничивается, т.е. может быть любым от 0 до M.
Сколькими способами можно расположить яблоки на тарелках?
Здравствуйте, Vi2, Вы писали:
Vi2>Есть N тарелок и M яблок. Vi2>Емкость тарелок (количество яблок на тарелке) не ограничивается, т.е. может быть любым от 0 до M. Vi2>Сколькими способами можно расположить яблоки на тарелках?
Здравствуйте, Vi2, Вы писали:
Vi2>Есть N тарелок и M яблок. Vi2>Емкость тарелок (количество яблок на тарелке) не ограничивается, т.е. может быть любым от 0 до M. Vi2>Сколькими способами можно расположить яблоки на тарелках?
если яблоки различимы, то M^N, если неразличимы (как электроны ), то С(N-1, M+N-1)=
Здравствуйте, Atilla, Вы писали:
A>Здравствуйте, Vi2, Вы писали:
Vi2>>Есть N тарелок и M яблок. Vi2>>Емкость тарелок (количество яблок на тарелке) не ограничивается, т.е. может быть любым от 0 до M. Vi2>>Сколькими способами можно расположить яблоки на тарелках?
Ну, горкой, кружком, квадратиком
A>если яблоки различимы, то M^N, если неразличимы (как электроны ), то С(N-1, M+N-1)=
Если тарелки различимы.
Берем N-1 линеек. Выстраиваем яблоки в ряд. Получаем М-1 промежутков. Линейки можно расположить среди этих промежутков (M-1)!/(N-1)! способами. Каждое распределение линеек соответствует ровно одному разложению яблок по тарелкам. Соответственно, ответ: (M-1)!/(N-1)! = С(N-1, M+N-1)
Интереснее вариант, когда тарелки также неразличимы. Есть у кого ответ?
M>Интереснее вариант, когда тарелки также неразличимы. Есть у кого ответ?
Это эквивалентно задаче посчитать сколькими способами можно представить число M с помощью N слагаемых, что в свою очередь эквивалентно, представлению числа M любым количеством слагаемых, наибольшое из которых не превосходит N — а это помню, что связано с какими-то очень некрасивыми числами <какая-то фамилия> 2-го рода.
Здравствуйте, DOOM, Вы писали:
DOO>Здравствуйте, mihoshi, Вы писали:
DOO> M>>Интереснее вариант, когда тарелки также неразличимы. Есть у кого ответ?
DOO>Это эквивалентно задаче посчитать сколькими способами можно представить число M с помощью N слагаемых, что в свою очередь эквивалентно, представлению числа M любым количеством слагаемых, наибольшое из которых не превосходит N — а это помню, что связано с какими-то очень некрасивыми числами <какая-то фамилия> 2-го рода.
Я так и думл, что простыми формулами в таких случаях не обойтись.
Я бы это решал по индукции, вот только какую функцию лучше использоать...
Здравствуйте, mihoshi, Вы писали:
M>Я так и думл, что простыми формулами в таких случаях не обойтись.
M>Я бы это решал по индукции, вот только какую функцию лучше использоать...
Рекурсивно решение строится легко: пусть Pn(m) — число способов, которыми можно представить m, используя слагаемые не превосходящие n. Тогда
Pn(m) = P1(m-1) + P2(m-2) + ... + Pn(m-n) — здесь записано следующее. Пусть слагаемые упорядочены по убыванию, тогда P1(m-1) — соотвествует, тому, что первое = 1, тогда надо записать число m-1 слагаемыми, не превосходяшими 1 и т.д.
Дальше можно попробовать получить что-нибудь красивое
Здравствуйте, DOOM, Вы писали:
DOO>Здравствуйте, mihoshi, Вы писали:
M>>Я так и думл, что простыми формулами в таких случаях не обойтись.
M>>Я бы это решал по индукции, вот только какую функцию лучше использоать...
DOO> DOO>Рекурсивно решение строится легко: пусть Pn(m) — число способов, которыми можно представить m, используя слагаемые не превосходящие n. Тогда DOO>Pn(m) = P1(m-1) + P2(m-2) + ... + Pn(m-n) — здесь записано следующее. Пусть слагаемые упорядочены по убыванию, тогда P1(m-1) — соотвествует, тому, что первое = 1, тогда надо записать число m-1 слагаемыми, не превосходяшими 1 и т.д. DOO>Дальше можно попробовать получить что-нибудь красивое
DOO>Но еще приходится разбивать на случаи m>=n и m<n
Кажется, мимо. Вот если еще учесть, что в разложении может быть несколько одинаковых слагаемых — тогда да. Правда при этом сложность алгоритма еще на один порядок увеличивается, но более быстрого способа я не вижу.
Здравствуйте, mihoshi, Вы писали:
DOO>>Рекурсивно решение строится легко: пусть Pn(m) — число способов, которыми можно представить m, используя слагаемые не превосходящие n. Тогда DOO>>Pn(m) = P1(m-1) + P2(m-2) + ... + Pn(m-n) — здесь записано следующее. Пусть слагаемые упорядочены по убыванию, тогда P1(m-1) — соотвествует, тому, что первое = 1, тогда надо записать число m-1 слагаемыми, не превосходяшими 1 и т.д. DOO>>Дальше можно попробовать получить что-нибудь красивое
DOO>>Но еще приходится разбивать на случаи m>=n и m<n
M>Кажется, мимо. Вот если еще учесть, что в разложении может быть несколько одинаковых слагаемых — тогда да. Правда при этом сложность алгоритма еще на один порядок увеличивается, но более быстрого способа я не вижу.
Да нет, все правильно. Pn(m) раскладывается на непересекающиеся варианты, никаких повторений тут не будет.
Классическая задача о размене рубля разными монетами решается именно таким способом (есть и еще один, но он не проще).
Здравствуйте, Lexey, Вы писали:
M>>Кажется, мимо. Вот если еще учесть, что в разложении может быть несколько одинаковых слагаемых — тогда да. Правда при этом сложность алгоритма еще на один порядок увеличивается, но более быстрого способа я не вижу.
L>Да нет, все правильно. Pn(m) раскладывается на непересекающиеся варианты, никаких повторений тут не будет. L>Классическая задача о размене рубля разными монетами решается именно таким способом (есть и еще один, но он не проще).
У меня получилось следующее. Функция P(n,m) — число способов, которыми можно представить n, используя слагаемые не превосходящие m.
Здравствуйте, mihoshi, Вы писали:
M>Здравствуйте, Lexey, Вы писали:
M>>>Кажется, мимо. Вот если еще учесть, что в разложении может быть несколько одинаковых слагаемых — тогда да. Правда при этом сложность алгоритма еще на один порядок увеличивается, но более быстрого способа я не вижу.
L>>Да нет, все правильно. Pn(m) раскладывается на непересекающиеся варианты, никаких повторений тут не будет. L>>Классическая задача о размене рубля разными монетами решается именно таким способом (есть и еще один, но он не проще).
Опс, на свежую голову все-таки понял, что действительно неправильно.
M>У меня получилось следующее. Функция P(n,m) — число способов, которыми можно представить n, используя слагаемые не превосходящие m.
M>Тогда
M>P(n,1) = p(0,m) = 1
Хм, p(0,m) = 0. Впрочем, при условии n-mq > 0 это несущественно.
M>P(n,m) = sum(q:n>=n-mq>=1) P(n-mq, m-1)
Да, это правильный вариант.
M>Кстати, если вас интересуют такие задачи — см. http://acm.timus.ru
Здравствуйте, Lexey, Вы писали:
M>>У меня получилось следующее. Функция P(n,m) — число способов, которыми можно представить n, используя слагаемые не превосходящие m.
M>>Тогда
M>>P(n,1) = p(0,m) = 1
L>Хм, p(0,m) = 0. Впрочем, при условии n-mq > 0 это несущественно.
Упс, слегка наврал. Чтобы это работало надо
либо сделать
n-mq => 0 вместо n-mq => 0 (см. пример p(4,4)),
либо добавить условие
p(m, m) = 1 вместо p(0,m) = 1.
C(M + N — 1, N — 1)
Кр-ть — с.т.
