Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/14: Рейтинг темы: голосов - 14, средняя оценка - 4.64
look123
0 / 0 / 0
Регистрация: 07.10.2016
Сообщений: 20
1

Вывести все подмножества множества (рекурсивная функция)

21.10.2016, 18:29. Просмотров 2610. Ответов 3

Ввожу например множество 1 2 3 4
Должно вывести вроде
2 3 4
1 3 4
1 2 4
1 2 3
1 2
1 3
1 4
2 3
2 4
3 4
1
2
3
4

Пока что получается нормально вывести
2 3 4
1 3 4
1 2 4
1 2 3
а как с остальными?..
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
 
int rec(int *mas, int m, int n);
int n;
int null;
int m;
 
int main () {
 
    cout << "n = ";
    cin >> n;
    cout << "Array: ";
 
    m = n-1;
    null = 0;
 
    int* mas = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> mas[i];
    }
    
    while (n != 0) {
        rec(mas, m, n);
        n--;
    }
    
    system("pause");
    return 0;
}
 
int rec(int *mas, int m, int n) {
    for (int i = 0; i < n; i++) {
        if (i != null) {
            cout << mas[i] << " ";
        }
    }
    null++;
    cout << endl;
 
    if (m == 0) {
        return 0;
    }
    else  
        rec(mas, --m, n);   
 
    return 0;
}
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2016, 18:29
Ответы с готовыми решениями:

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

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

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

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

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

3
afront
1064 / 1009 / 754
Регистрация: 29.02.2016
Сообщений: 3,200
22.10.2016, 08:28 2
Лучший ответ Сообщение было отмечено look123 как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
    int N = 4;
    int m[4] = { 1,2,3,4};
    int i, mx, j;
    for(i=0, mx=1; i < N; i++) 
        mx *= 2;  // Вместо pow(2, N)
     for(i=0; i < mx; i++) 
     {
      for(j=0; j < N; j++)
       if ((i >> j) & 1) std::cout << m[j];
      std::cout << std::endl;
     }
    
    return 0;
2
look123
0 / 0 / 0
Регистрация: 07.10.2016
Сообщений: 20
22.10.2016, 19:04  [ТС] 3
Цитата Сообщение от afront Посмотреть сообщение
if ((i >> j) & 1)
а что это за условие?
0
Байт
Эксперт C
20578 / 13083 / 2756
Регистрация: 24.12.2010
Сообщений: 27,449
31.10.2016, 16:37 4
look123, Вот получил в личку.
Цитата Сообщение от look123
Задача: вывести все подмножества заданного множества.

Я нашел то решение, что мне нужно, вот:

#include <vector>
#include <string>
#include <iostream>
using namespace std;

void rec(vector<int>&mas, int num, string s);

int main() {
int n;
cout << "N = ";
cin >> n;

vector<int> arr(n);
cout << "Array: ";

for (int i = 0; i < n; i++) {
cin >> arr[i];
}

rec(arr,0,"");
system("pause");
}

void rec(vector<int>&mas, int num, string s) {

if (num == mas.size()) {
cout << s << endl;
return;
}
rec(mas,num+1,s);
s = s + to_string(mas[num]) + ' ';
rec(mas,num+1,s);

}
Работает отлично, но я не совсем понимаю этого
C++
1
2
3
4
if (num == mas.size()) {
        cout << s << endl;
        return;
   }
и этого
C++
1
2
3
rec(mas,num+1,s); 
s = s + to_string(mas[num]) + ' ';
rec(mas,num+1,s);
Я понимаю, что каждая строка делает в отдельности, но не понимаю как оно работает в целом.
Можете пожалуйста объяснить сам алгоритм работы этой рекурсивной функции?
А ты правила читал? На пункт 4.6 обратил внимание? И поверь, он прописан не напрасно. Получать такие вещи - противно. И шансов на получение помощи не увеличивает. Скорее, наоборот.
0
31.10.2016, 16:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.10.2016, 16:37

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

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

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


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

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

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