Форум программистов, компьютерный форум CyberForum.ru

Задача на множества - C++

Восстановить пароль Регистрация
 
Yashman
 Аватар для Yashman
1 / 3 / 0
Регистрация: 02.07.2011
Сообщений: 90
15.11.2012, 19:09     Задача на множества #1
Товарищи программисты, помогите решить задачу! Дано множество натуральных чисел. Надо составить все подмножества, сумма элементов которых равна числу Х. Сперва вводится кол-во элементов множества, потом все элементы, затем число Х. Пример (см. спойлер):
Кликните здесь для просмотра всего текста
Ввод:
12
1 5 7 3 10 8 9 2 4 6 11 13
15
Вывод:
4 11
2 13
9 6
9 2 4
3 2 4 6
3 8 4
3 10 2
7 2 6
7 8
5 4 6
5 8 2
5 10
5 7 3
1 8 6
1 8 2 4
1 10 4
1 3 11
1 3 9 2
1 7 3 4
1 5 9
1 5 3 6
1 5 3 2 4
1 5 7 2


Вот программа, которая выводит все подможества, состоящие из двух элементов:
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
#include <iostream>
 
using namespace std;
 
int main(int argc, const char * argv[])
{
    int size;
    cout << "Enter size: ";
    cin >> size;
    int *numbers = new int[size];
    cout << "Enter numbers: ";
    for (int i = 0; i < size; i++)
        cin >> numbers[i];
    int target;
    cout << "Enter target: ";
    cin >> target;
    int sum = 0;
    for (int i = 0; i < size-1; i++)
    {
        for (int j = i+1; j < size; j++)
        {
            sum = numbers[i];
            sum += numbers[j];
            if (sum == target)
                cout << numbers[i] << " " << numbers[j] << "\n";
        }
    }
    return 0;
}
Можно заменить цикл той программы на этот и будут выбраны подмножества, состоящие из 3 элементов:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < size-2; i++)
    {
        for (int j = i+1; j < size-1; j++)
        {
            for (int k = j+1; k < size; k++)
            {
                sum = numbers[i] + numbers[j];
                sum += numbers[k];
                if (sum == target)
                    cout << numbers[i] << " " << numbers[j] << " " << numbers[k] << "\n";
            }
        }
    }
Внимание вопрос: как создать универсальную программу, способную выбирать абсолютно все возможные подмножества? Конечно, можно вручную написать цикл на каждый случай, но это глупо и потом, если будет введено много чисел и большое число Х, могут появится подмножества из тысяч элементов. Заранее благодарю!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2012, 19:09     Задача на множества
Посмотрите здесь:

Множества. Проверка множества на наличие элемента в нем C++
Множества. Вычислить количество элементов множества Q, связанного c исходными множествами C++
C++ Удалить из множества А минимальный элемент множества В
C++ Число изъять из множества А, если оно является элементом множества А, но не является элементом множества В
Множества . Найти разность полученного множества с заданным C++
Квадрат с вершинами из первого множества накрывает все точки второго множества и имеет минимальную площадь C++
C++ Задача на множества
Задача с использованием множества: каких символов в заданной строе больше: русских или латинских? C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 18:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru