2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Возможные сочетания
Сообщение25.11.2014, 12:25 
Здравствуйте, уважаемые форумчане. Требуется помощь в решении следующей задачи. Суть ее такова. Пусть есть определенное число B = 10 число груш. Есть число ящиков равное 3. Алгоритм следующий:
Сначала беру B = 0, т.е. сколькими способами можно разложить 0 груш по трем ящикам: ответ один способ: 0 груш в первый, во второй и в третий.
Затем беру B = 1, т.е. сколькими способами можно разложить 1 грушу по трем ящикам: ответ 3 способа: 1 0 0, 0 1 0, 0 0 1.
После этого В = 2, число способов 6 и так далее. Т.е. с помощью такого алгоритма мне требуется перебрать все варианты. Следует также учитывать, что число ящиков может быть гораздо больше. Вопрос состоит в следующем, реально ли каким-то образом вывести общую формулу, которую потом можно будет запрограммировать и чтобы с помощью нее считались различные сочетания? Подтолкните, пожалуйста, на верный путь.

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 12:33 
Есть стандартный прием "шаров и перегородок".
Почитайте, например тут, задача 32.

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 14:21 
Здесь вопрос ставится не о числе комбинаций, а о том какие они будут. Можно ли как-то связать представленный алгоритм с биноминальным разложением?

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 14:41 
Аватара пользователя
12d3 в сообщении #935889 писал(а):
чтобы с помощью нее считались различные сочетания?

Afina в сообщении #935939 писал(а):
Здесь вопрос ставится не о числе комбинаций, а о том какие они будут.


Так что нужно-то? Посчитать количество комбинаций (вариантов)? В итоге программа выдаёт одно число. Или чтобы программа выдавала весь список комбинаций?

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 14:48 
Нужен список комбинаций, число комбинаций просто считается

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 14:59 
Для трех корзин алгоритм перебора такой.
Сначала кладем все груши в первую корзину.
На каждом шаге делаем следующую операцию:
Если в первой корзине есть груши, перекладываем одну штуку во вторую, иначе из второй перекладываем одну грушу в третью, а все остальное в первую.
Когда такую операцию нельзя выполнить, это значит, что мы уже все перебрали.
На случай произвольного количества корзин надо подумать немного.

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 15:25 
1. Стоит добавить четвёртую корзину, куда складывать груши, не попавшие в первые три.
2. Как вариант. Примитивный способ: берём последнюю, $n$-ю грушу. Кладём в первую корзину. Прочие $n-1$ раскладываем по четырём корзинам рекурсивным вызовом. Потом перекладываем её во вторую, снова раскладываем прочие по четырём корзинам рекурсивным вызовом, потом в третью и в четвёртую.

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 16:00 
Afina в сообщении #935886 писал(а):
Пусть есть определенное число B = 10 число груш. Есть число ящиков равное 3.

Afina в сообщении #935886 писал(а):
требуется перебрать все варианты.

Эквивалентно задаче: представить 10 в виде четырех слагаемых, когда порядок слагаемых важен.

 
 
 
 Re: Возможные сочетания
Сообщение25.11.2014, 16:04 
Evgenjy в сообщении #935998 писал(а):
Эквивалентно
Это если груши неразличимы. Возможно, так и есть.

 
 
 
 Re: Возможные сочетания
Сообщение26.11.2014, 11:35 
Спасибо большое за советы. Еще такой вопрос: правильно ли я понимаю, что 10 груш - это множество, а если я их буду распределять по корзинам, то найду подмножества этого множества?

 
 
 
 Re: Возможные сочетания
Сообщение26.11.2014, 13:29 
Ну, если вы думаете, что вам это чем-то поможет...

 
 
 
 Re: Возможные сочетания
Сообщение26.11.2014, 17:36 
Еще один вопрос. Тоже с грушами. Когда они уже помещены в корзины.
Число груш 6, число корзин - 3. Теперь нужно из каждой корзины взять по одной груше и переложить какждую комбинацию груш в новую корзину. Т.е. в данном случае таких корзин будет $2^{3}$.
$\begin{pmatrix}
1 &2  &3 \\ 
4 &5  &6 
\end{pmatrix}$

Теперь возвращаясь к начальной задаче, пусть тоже будет 6 груш и три корзины. Тогда хочу уточнить там число комбинаций будет $(1 + 6)^{3}$?

 
 
 
 Re: Возможные сочетания
Сообщение26.11.2014, 22:18 
Аватара пользователя
:?: Ничего не поняла.Какую "каждую комбинацию"? По одной груше, которые были взяты? Или те, что остались? И как положить "комбинацию" в корзину - все груши в одну, что ли?
И что означает сия матрица $2\times 3$? И откуда число $2^3=8$ корзин?

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group