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

@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]--;
    }
}

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. 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? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

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

	Реализовать алгоритм разложения по двум корзинам пронумерованных шаров 20.10.2017, 16:44. Показов 1171. Ответов 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