Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
456r56
0 / 0 / 0
Регистрация: 04.06.2018
Сообщений: 8
1

Создайте процедуру, печатающую все подмножества множества {1, 2, …, N}

04.06.2018, 17:07. Просмотров 417. Ответов 6
Метки нет (Все метки)

Создайте процедуру, печатающую все подмножества множества {1, 2, …, N}. c++
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.06.2018, 17:07
Ответы с готовыми решениями:

Напечатать все подмножества множества {1...k}
Замучилась это делать - ничего не получается! Помогите кто-нибудь!

Перечислить все подмножества n элементного множества {1,2,.,n}
Помогите пожалуйста написать программу для этой задачи: Перечислить все подмножества n элементного...

Как можно получить все подмножества множества?
Например из множества, представлнного массивом должны получиться подмножества:

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

Вывести все подмножества множества (рекурсивная функция)
Ввожу например множество 1 2 3 4 Должно вывести вроде 2 3 4 1 3 4 1 2 4 1 2 3 1 2 1 3 1 4...

6
Fixer_84
1391 / 875 / 786
Регистрация: 30.04.2016
Сообщений: 2,921
03.08.2018, 18:48 2
456r56, здравствуйте! Можно, например, так:

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
31
32
#include <iostream> 
#include <cmath>
 
    using namespace std;
 
void printAllSubsets(int* set, int size) {
    size = pow(2, size);
    for (int i = 0; i < size; i++) {
        cout << "{ ";
        for (int j = 0; j < size; j++) {
            if (i & (1 << j))
                cout << set[j] << " ";
        }
        cout << "}\n";
    }
}
 
int main() {
    int n;
    cout << "Enter a number of elements in the set:\n";
    cout << "n = ";
    cin >> n;
    int* set = new int[n];
    for (int i = 0; i < n; i++) {
        set[i] = i + 1;
    }
    cout << "Output of the program:\n";
    printAllSubsets(set, n);
    delete [] set;
    system("pause");
    return 0;
}
0
Байт
Эксперт C
20652 / 13144 / 2770
Регистрация: 24.12.2010
Сообщений: 27,647
03.08.2018, 22:57 3
456r56, Если N<=63, то можно, например, так.
C++
1
2
3
4
5
6
7
8
unsigned long X, P=1, i;
int P=1;
for(i=0; i<N; i++) P*=2;
for(X=0; X<P; X++) {
  for(i=0; i<N; i++) 
    if (X&(1<<i)) cout << i+1 << " ";
  cout << endl;
}
Если же N больше, то битовую строку придется устроить немножко иначе. Но программа и без этого будет работать очень долго. И с этим ничего не попишешь. Ибо множество из 63 элементов имеет 263 подмножеств = 8*1018. Даже если предположить, что каждое подмножество выдается за один машинный такт, на компе 10 Гигафлоп это займет 8*108 сек = 25 лет
А увеличение N на 1 будет увеличивать время счета в 2 раза.

Добавлено через 4 минуты
Fixer_84, У вас похожий код, только мне очень кажется не очень правильным.
Границы цикла в строках 8 и 10, имхо, должны быть разными.
0
Новичок
Модератор
1532 / 999 / 470
Регистрация: 17.07.2012
Сообщений: 5,086
Завершенные тесты: 3
03.08.2018, 23:05 4
Цитата Сообщение от Байт Посмотреть сообщение
Fixer_84, У вас похожий код, только мне очень кажется не очень правильным.
Границы цикла в строках 8 и 10, имхо, должны быть разными.
Согласен. Мне вообще кажется там UB может быть из-за переполнения(сдвигаем например на 2^20 вместо 20).
0
Fixer_84
1391 / 875 / 786
Регистрация: 30.04.2016
Сообщений: 2,921
04.08.2018, 17:39 5
Цитата Сообщение от Новичок Посмотреть сообщение
Fixer_84, У вас похожий код, только мне очень кажется не очень правильным.
Границы цикла в строках 8 и 10, имхо, должны быть разными.
Да, я немного ошибся. Будет так:

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
31
32
#include <iostream> 
#include <cmath>
 
    using namespace std;
 
void printAllSubsets(int* set, int n) { 
    unsigned int size = pow(2, n);
    for (int i = 0; i < size; i++) {
        cout << "{ ";
        for (int j = 0; j < n; j++) {
            if (i & (1 << j))
                cout << set[j] << " ";
        }
        cout << "}\n";
    }
}
 
int main() {
    int n;
    cout << "Enter a number of elements in the set:\n";
    cout << "n = ";
    cin >> n;
    int* set = new int[n];
    for (int i = 0; i < n; i++) {
        set[i] = i + 1;
    }
    cout << "Output of the program:\n";
    printAllSubsets(set, n);
    delete [] set;
    system("pause");
    return 0;
}
0
Байт
Эксперт C
20652 / 13144 / 2770
Регистрация: 24.12.2010
Сообщений: 27,647
04.08.2018, 17:53 6
Fixer_84, я надеюсь, вы понимаете, что создавать массив set, каждый элемент которого однозначно и просто определяется его номером (set[i] = i+1) - не более чем излишество?
0
Fixer_84
1391 / 875 / 786
Регистрация: 30.04.2016
Сообщений: 2,921
04.08.2018, 18:11 7
Байт, вы правы. Я надеюсь, что тот кому нужна эта программа сможет заполнить массив самостоятельно. Просто в задании сказано
Цитата Сообщение от 456r56 Посмотреть сообщение
Создайте процедуру, печатающую все подмножества множества {1, 2, …, N}.
Поэтому я и заполнил его от 1 до N. А так, эта программа для любого множества работать будет.
0
04.08.2018, 18:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2018, 18:11

Перечислить все K элементные подмножества n элементарного множества
Перечислить все K элементные подмножества n элементарного множества пример и объяснение по этой...

Рекурсия: вывести на дисплей все возможные подмножества множества
создать процедуру с помощью рекурсии множественное число{1,2,..,N}

Ошибка в коде. Из числового множества A мощности n выбрать все подмножества
С числовой множества A мощности n выбрать все подмножества, сумма элементов каждого из которых...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru