279 / 156 / 52
Регистрация: 30.06.2011
Сообщений: 1,712
|
|
1 | |
Реализовать алгоритм разложения по двум корзинам пронумерованных шаров20.10.2017, 16:44. Показов 891. Ответов 12
Метки нет (Все метки)
Приветствую всех. Необходимо реализовать алгоритм разложения по двум корзинам пронумерованных шаров. Который день бьюсь, все не получается. Подскажите...
0
|
20.10.2017, 16:44 | |
Ответы с готовыми решениями:
12
Поиск количества размещений n шаров по m корзинам, с условиями Найти число способов раскладки n различных шаров по m различным корзинам Найти распределение вероятностей (извлечение пронумерованных шаров из урны) Реализовать рекурсивный алгоритм вычисления заданной матрицы,пользуясь формулой разложения по первой строке |
279 / 156 / 52
Регистрация: 30.06.2011
Сообщений: 1,712
|
|
20.10.2017, 17:15 [ТС] | 3 |
Есть 2 корзины и N пронумерованных шаров (от 1 до N). N > 1. Реализовать алгоритм, который выведет на экран все возможные комбинации разложения этих шаров по корзинам. Необходимо учесть, что порядок помещения шаров в корзины не важен. Кроме этого, корзины не различимы (первый шар в первой корзине, второй шар во второй и наоборот это одно и то же).
Добавлено через 10 минут Количество оригинальных комбинаций можно найти по формуле . Но как находить сами эти комбинации?
0
|
47 / 31 / 21
Регистрация: 04.04.2016
Сообщений: 209
|
|
20.10.2017, 17:19 | 4 |
А порядок шаров в корзине имеет значение?
0
|
279 / 156 / 52
Регистрация: 30.06.2011
Сообщений: 1,712
|
|
20.10.2017, 17:23 [ТС] | 5 |
0
|
Заблокирован
|
||||||
20.10.2017, 17:28 | 6 | |||||
0
|
47 / 31 / 21
Регистрация: 04.04.2016
Сообщений: 209
|
|
20.10.2017, 17:28 | 7 |
Ну, можно кучей вложенных циклов попробовать.
например, внешний цикл формирует распределение кол-ва шаров по корзинам, а внутренний генерит номера этих шаров в пределах текущего кол-ва в корзине. Только нужно предусмотреть, чтобы во внешенем цикле кол-во не выходило за N/2
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
20.10.2017, 19:18 | 8 |
Каждая раскладка может быть представлена последовательностью нулей и единиц. А эта последовательность - целым числом от 0 до 2N-1
Перебираете простым циклом все такие числа. Каждому числу ставите в соответствие раскладки по корзинам. (разряд = 0 - первая корзина, = 1 - вторая) Аналогично решается задача для 3-х, ... К корзин. Только вместо двойки будет К. И разбор по разрядам чуток посложнее. Хотя и не очень.
1
|
279 / 156 / 52
Регистрация: 30.06.2011
Сообщений: 1,712
|
|
21.10.2017, 10:51 [ТС] | 9 |
Байт, Ваш вариант хорош, но имеет, на мой взгляд, два недостатка. Первый это то, что количество шаров будет ограничено разрядностью числа. Второй, это то, что метод избыточен, то есть в нем будут повторяться уже использованные варианты. Например, в одной корзине шары с номерами 1, 2, во второй 3, 4. Если корзины поменяются шарами, то это будет одно и то же.
Добавлено через 6 минут Или же я не понял Вашего решения...
1
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
21.10.2017, 11:09 | 11 |
d7d1cd, оба ваши замечания совершенно справедливы.
Придется моделировать "длинными числами". Представить раскладку как char R[N]. Моделировать придется только "+1".
Да, это я недоучел. Выход простой. Старший разряд всегда = 0. Как только он становится равным 1, перебор прекращаем
Добавлено через 3 минуты 000 - все шары в одной корзине 001 010 011 Да, 2N-1. -1 не нужна.
1
|
279 / 156 / 52
Регистрация: 30.06.2011
Сообщений: 1,712
|
|
21.10.2017, 12:30 [ТС] | 12 |
MansMI, при количестве шаров 3 будет 3 варианта.
Байт, -1 надо. Просто забыл в условии указать, что в корзине должен быть хотя бы один шар.
0
|
Заблокирован
|
||||||
21.10.2017, 12:36 | 13 | |||||
1
|
21.10.2017, 12:36 | |
21.10.2017, 12:36 | |
Помогаю со студенческими работами здесь
13
Реализовать алгоритм разбиения студентов на два кластера по двум переменными Реализовать столкновение шаров алгоритм разложения функции Алгоритм разложения чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |