Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
279 / 156 / 52
Регистрация: 30.06.2011
Сообщений: 1,712
1

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

20.10.2017, 16:44. Показов 891. Ответов 12
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Приветствую всех. Необходимо реализовать алгоритм разложения по двум корзинам пронумерованных шаров. Который день бьюсь, все не получается. Подскажите...
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.10.2017, 16:44
Ответы с готовыми решениями:

Поиск количества размещений n шаров по m корзинам, с условиями
Задача 3. Сколькими способами можно разместить n одинаковых шаров по m различным корзинам при...

Найти число способов раскладки n различных шаров по m различным корзинам
Не знаю, какая тут формула используется, надуюсь на вашу помощь... Найти число способов раскладки...

Найти распределение вероятностей (извлечение пронумерованных шаров из урны)
Добры день! Знаю,что может задача есть и в инете,но мне нужна ее небольшая модификация.. Урна...

Реализовать рекурсивный алгоритм вычисления заданной матрицы,пользуясь формулой разложения по первой строке
Вычислить определитель заданной матрицы, пользуясь формулой разложения по первой строке: ...

12
Заблокирован
20.10.2017, 16:50 2
... информации избыточно
0
279 / 156 / 52
Регистрация: 30.06.2011
Сообщений: 1,712
20.10.2017, 17:15  [ТС] 3
Есть 2 корзины и N пронумерованных шаров (от 1 до N). N > 1. Реализовать алгоритм, который выведет на экран все возможные комбинации разложения этих шаров по корзинам. Необходимо учесть, что порядок помещения шаров в корзины не важен. Кроме этого, корзины не различимы (первый шар в первой корзине, второй шар во второй и наоборот это одно и то же).

Добавлено через 10 минут
Количество оригинальных комбинаций можно найти по формуле https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{(N-1)}-1. Но как находить сами эти комбинации?
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
Цитата Сообщение от d7d1cd Посмотреть сообщение
Необходимо учесть, что порядок помещения шаров в корзины не важен.
Соответственно, и порядок шаров в самих корзинах тоже не важен.
0
Заблокирован
20.10.2017, 17:28 6
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");
0
47 / 31 / 21
Регистрация: 04.04.2016
Сообщений: 209
20.10.2017, 17:28 7
Ну, можно кучей вложенных циклов попробовать.
например, внешний цикл формирует распределение кол-ва шаров по корзинам, а внутренний генерит номера этих шаров в пределах текущего кол-ва в корзине. Только нужно предусмотреть, чтобы во внешенем цикле кол-во не выходило за N/2
0
Диссидент
Эксперт C
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
Заблокирован
21.10.2017, 11:01 10
2(N-1)-1 откуда? N=3 какие варианты?
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
21.10.2017, 11:09 11
d7d1cd, оба ваши замечания совершенно справедливы.
Цитата Сообщение от d7d1cd Посмотреть сообщение
количество шаров будет ограничено разрядностью числа.
Придется моделировать "длинными числами". Представить раскладку как char R[N]. Моделировать придется только "+1".
Цитата Сообщение от d7d1cd Посмотреть сообщение
будут повторяться уже использованные варианты. Например, в одной корзине шары с номерами 1, 2, во второй 3, 4. Если корзины поменяются шарами, то это будет одно и то же.
Да, это я недоучел. Выход простой. Старший разряд всегда = 0. Как только он становится равным 1, перебор прекращаем

Добавлено через 3 минуты
Цитата Сообщение от MansMI Посмотреть сообщение
N=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
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]--;
    }
}
1
21.10.2017, 12:36
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.10.2017, 12:36
Помогаю со студенческими работами здесь

Реализовать алгоритм разбиения студентов на два кластера по двум переменными
Вот собственно такая задача: На листе Survey файла Survey.xls приведены данные об опросе 100...

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

алгоритм разложения функции
y(x)=Pi*x/((e^3x)-1). Я пробовал делать два раза но препод не принял. Даже не объяснил, что делать....

Алгоритм разложения чисел
Доброго времени суток,не знаю правильно ли я выбрал тему,да и не уверен есть ли ответ на мой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru