Реализовать алгоритм разложения по двум корзинам пронумерованных шаров

@d7d1cd · Регистрация: 30.06.2011

Студворк — интернет-сервис помощи студентам

Приветствую всех. Необходимо реализовать алгоритм разложения по двум корзинам пронумерованных шаров. Который день бьюсь, все не получается. Подскажите...

@MansMI · 20.10.2017, 16:50

... информации избыточно

@d7d1cd · 20.10.2017, 17:15 **[ТС]**

Есть 2 корзины и N пронумерованных шаров (от 1 до N). N > 1. Реализовать алгоритм, который выведет на экран все возможные комбинации разложения этих шаров по корзинам. Необходимо учесть, что порядок помещения шаров в корзины не важен. Кроме этого, корзины не различимы (первый шар в первой корзине, второй шар во второй и наоборот это одно и то же).

Добавлено через 10 минут
Количество оригинальных комбинаций можно найти по формуле $https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{(N-1)}-1$ . Но как находить сами эти комбинации?

@Pink_Pank · 20.10.2017, 17:19

А порядок шаров в корзине имеет значение?

@d7d1cd · 20.10.2017, 17:23 **[ТС]**

Сообщение от d7d1cd

Необходимо учесть, что порядок помещения шаров в корзины не важен.

Соответственно, и порядок шаров в самих корзинах тоже не важен.

@MansMI · 20.10.2017, 17:28

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void set(int **a,int n,int N,int *p)
{
    for(int i=0; i<2; i++)
    {
        a[i][p[i]++]=n;
        if(*p+p[1]<N) set(a,n+1,N,p);
        else
        {
            for(int k=0; k<*p; k++) cout<<a[0][k]<<" ";
            cout<<"-";
            for(int k=0; k<p[1]; k++) cout<<a[1][k]<<" ";
            cout<<endl;
        }
        p[i]--;
    }
}
 
void main(int argc,char **argv)
{
    int n;
    cout<<"N:";
    cin>>n;
    int *a[2];
    a[0]=new int[n];
    a[1]=new int[n];
    int p[2]={0,0};
    set(a,1,n,p);
    delete[] a[0];
    delete[] a[1];
    system("pause");

@Pink_Pank · 20.10.2017, 17:28

Ну, можно кучей вложенных циклов попробовать.
например, внешний цикл формирует распределение кол-ва шаров по корзинам, а внутренний генерит номера этих шаров в пределах текущего кол-ва в корзине. Только нужно предусмотреть, чтобы во внешенем цикле кол-во не выходило за N/2

Байт · 20.10.2017, 19:18

Каждая раскладка может быть представлена последовательностью нулей и единиц. А эта последовательность - целым числом от 0 до 2^N-1
Перебираете простым циклом все такие числа. Каждому числу ставите в соответствие раскладки по корзинам. (разряд = 0 - первая корзина, = 1 - вторая)
Аналогично решается задача для 3-х, ... К корзин. Только вместо двойки будет К. И разбор по разрядам чуток посложнее. Хотя и не очень.

@d7d1cd · 21.10.2017, 10:51 **[ТС]**

Байт, Ваш вариант хорош, но имеет, на мой взгляд, два недостатка. Первый это то, что количество шаров будет ограничено разрядностью числа. Второй, это то, что метод избыточен, то есть в нем будут повторяться уже использованные варианты. Например, в одной корзине шары с номерами 1, 2, во второй 3, 4. Если корзины поменяются шарами, то это будет одно и то же.

Добавлено через 6 минут
Или же я не понял Вашего решения...

@MansMI · 21.10.2017, 11:01

2^(N-1)-1 откуда? N=3 какие варианты?

Байт · 21.10.2017, 11:09

d7d1cd, оба ваши замечания совершенно справедливы.

Сообщение от d7d1cd

количество шаров будет ограничено разрядностью числа.

Придется моделировать "длинными числами". Представить раскладку как char R[N]. Моделировать придется только "+1".

Сообщение от d7d1cd

будут повторяться уже использованные варианты. Например, в одной корзине шары с номерами 1, 2, во второй 3, 4. Если корзины поменяются шарами, то это будет одно и то же.

Да, это я недоучел. Выход простой. Старший разряд всегда = 0. Как только он становится равным 1, перебор прекращаем

Добавлено через 3 минуты

Сообщение от MansMI

N=3 какие варианты?

000 - все шары в одной корзине
001
010
011
Да, 2^N-1. -1 не нужна.

@d7d1cd · 21.10.2017, 12:30 **[ТС]**

MansMI, при количестве шаров 3 будет 3 варианта.
Байт, -1 надо. Просто забыл в условии указать, что в корзине должен быть хотя бы один шар.

@MansMI · 21.10.2017, 12:36

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void set(int **a,int n,int N,int *p)
{
    int m=1+(n>1);
    for(int i=0; i<m; i++)
    {
        a[i][p[i]++]=n;
        if(n<N) set(a,n+1,N,p);
        else
        if(*p && p[1])
        {
            for(int k=0; k<*p; k++) cout<<a[0][k]<<" ";
            cout<<"- ";
            for(int k=0; k<p[1]; k++) cout<<a[1][k]<<" ";
            cout<<endl;
        }
        p[i]--;
    }
}

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@d7d1cd 279 / 156 / 52 Регистрация: 30.06.2011 Сообщений: 1,712

	Реализовать алгоритм разложения по двум корзинам пронумерованных шаров 20.10.2017, 16:44. Показов 1167. Ответов 12 Метки нет (Все метки) Приветствую всех. Необходимо реализовать алгоритм разложения по двум корзинам пронумерованных шаров. Который день бьюсь, все не получается. Подскажите... 0

@MansMI 1615 / 1181 / 552 Регистрация: 08.01.2012 Сообщений: 4,558
	20.10.2017, 16:50
	... информации избыточно 0

@d7d1cd 279 / 156 / 52 Регистрация: 30.06.2011 Сообщений: 1,712
	20.10.2017, 17:15 [ТС]
	Есть 2 корзины и N пронумерованных шаров (от 1 до N). N > 1. Реализовать алгоритм, который выведет на экран все возможные комбинации разложения этих шаров по корзинам. Необходимо учесть, что порядок помещения шаров в корзины не важен. Кроме этого, корзины не различимы (первый шар в первой корзине, второй шар во второй и наоборот это одно и то же). Добавлено через 10 минут Количество оригинальных комбинаций можно найти по формуле $https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{(N-1)}-1$ . Но как находить сами эти комбинации? 0

@Pink_Pank 47 / 31 / 21 Регистрация: 04.04.2016 Сообщений: 209
	20.10.2017, 17:19
	А порядок шаров в корзине имеет значение? 0

@Pink_Pank 47 / 31 / 21 Регистрация: 04.04.2016 Сообщений: 209
	20.10.2017, 17:28
	Ну, можно кучей вложенных циклов попробовать. например, внешний цикл формирует распределение кол-ва шаров по корзинам, а внутренний генерит номера этих шаров в пределах текущего кол-ва в корзине. Только нужно предусмотреть, чтобы во внешенем цикле кол-во не выходило за N/2 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	20.10.2017, 19:18
	Каждая раскладка может быть представлена последовательностью нулей и единиц. А эта последовательность - целым числом от 0 до 2^N-1 Перебираете простым циклом все такие числа. Каждому числу ставите в соответствие раскладки по корзинам. (разряд = 0 - первая корзина, = 1 - вторая) Аналогично решается задача для 3-х, ... К корзин. Только вместо двойки будет К. И разбор по разрядам чуток посложнее. Хотя и не очень. 1

@d7d1cd 279 / 156 / 52 Регистрация: 30.06.2011 Сообщений: 1,712
	21.10.2017, 10:51 [ТС]
	Байт, Ваш вариант хорош, но имеет, на мой взгляд, два недостатка. Первый это то, что количество шаров будет ограничено разрядностью числа. Второй, это то, что метод избыточен, то есть в нем будут повторяться уже использованные варианты. Например, в одной корзине шары с номерами 1, 2, во второй 3, 4. Если корзины поменяются шарами, то это будет одно и то же. Добавлено через 6 минут Или же я не понял Вашего решения... 1

@MansMI 1615 / 1181 / 552 Регистрация: 08.01.2012 Сообщений: 4,558
	21.10.2017, 11:01
	2^(N-1)-1 откуда? N=3 какие варианты? 0

@d7d1cd 279 / 156 / 52 Регистрация: 30.06.2011 Сообщений: 1,712
	21.10.2017, 12:30 [ТС]
	MansMI, при количестве шаров 3 будет 3 варианта. Байт, -1 надо. Просто забыл в условии указать, что в корзине должен быть хотя бы один шар. 0