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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
Wolandello
1 / 1 / 0
Регистрация: 06.06.2009
Сообщений: 35
#1

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

31.10.2009, 16:39. Просмотров 1317. Ответов 4
Метки нет (Все метки)

Задано натуральное число n, определить и вывести на экран (по одному разу) все подмножества множества 1 .. n
с заданной суммой S (числа в каждом подмножеству повторяться не могут)
Народ подскажите решение
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2009, 16:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос подмножества (C++):

подмножества и множества - C++
Разработать алгоритм генерации всех подмножеств n-элемента множества Помогите решить ее!

множества подмножества - C++
Помогите пожалуйста!!! Мне нужна программа этот алгоритмa ......C++..... Пусть есть набор элементов в массиве a длины n. Строим...

Разбить множество на подмножества - C++
Здравствуйте, помогите пожалуйста, нужно разбить множество из n элементов на всеми способами k подмножеств например ввод n=3({1,2,3}),...

Подмножества указанной длины в множестве - C++
Прошу помочь мне, задача состоит в том, чтобы вывести на экран все подмножества длиной k, множества n. k<=n в заранее благодарен

Сгенерировать все k -элементные подмножества из N - C++
Дело все в том, что мне надо написать программу, которой на вход давался файл с N целых чисел через пробел, пользователь дает на ввод число...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Андрейка
419 / 223 / 27
Регистрация: 25.03.2009
Сообщений: 744
31.10.2009, 18:14 #2
http://www.cyberforum.ru/cpp/thread39207.html
Wolandello
1 / 1 / 0
Регистрация: 06.06.2009
Сообщений: 35
31.10.2009, 20:50  [ТС] #3
Спасибо, но это совсем не то

Добавлено через 6 минут
Припустим N=4 S=6
подмножества:
{1},{1,2},{1,2,3},{1,2,3,4},{2},{2,3},{2,3,4},{3},{3,4},{4},{1,3},{1,4},{2,4},{1,3,4}
программа должна выдать:
{1,2,3},{2,4}
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
31.10.2009, 22:51 #4
Пусть S=A[0]+A[1]+A[2]+...+A[N-1].
При этом чтобы не повторяться будем считать что A[0]>A[1]>A[2]>..
Но в тоже время в конце может быть хвост нулей.
Например S=6=4+2+0+0
Осталось грамотно сделать полный перебор
Перебирать нужно так - A[0] от N до 0, A[1] перебираем от S-A[0] до 0 и так далее,
A[2] перебираем от S-A[0]-A[1] до 0 и так далее.
Способ перебора гарантирует что варианты не будут повторяться.
А полный перебор гарантирует, что будут найдены все варианты.

Добавлено через 46 секунд
Есть небольшая проблема в том, что N - это не константа и просто N вложенными циклами не сделать.
Chea
6 / 6 / 0
Регистрация: 29.09.2009
Сообщений: 41
01.11.2009, 08:14 #5
Код
# include <conio.h>
# include <stdio.h>
# include <string.h>

char * _rez;
int func (  char* mas,   // ìàññèâ - èñõîäíîå ìíîæåñòâî
            int n,      // ðàçìåðíîñòü ìíîæåñòâà
            int sum,    // òðåáóåìàÿ ñóììà
            int s,      // óæå íàéäåííàÿ ñóììà
            char* rez    // ñîáèðàåìîå ïîäìíîæåñòâî
         )
   {
      if (s==sum) 
         {
            printf ("%s\n",_rez);
            return 1;
         }
      if (s>sum) return 0;
      if (n<=0) return 0;
      for (int i=0;i<n;i++)
         {
            rez[0]=mas[i];
            func(mas+i+1,n-i-1,sum,s+mas[i]-'0',rez+1);
            rez[0]=0;
         }
      
   }

int main ()
{
   char mas[]="123456";
   int n=strlen(mas);
   int sum=6;
   char * rez=new char[n+1];
   int i;

   _rez=rez;

   for (i=0;i<=n;i++) rez[i]=0;

    func (mas,n,sum,0,rez);
   delete rez;
   getch();      
}
Добавлено через 2 минуты
int func ( char* mas, // массив - исходное множество
int n, // размерность множества
int sum, // искомая сумма
int s, // уже набранная сумма
char* rez // собираемое подмножество
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2009, 08:14
Привет! Вот еще темы с ответами:

Сравнить два подмножества в матрице - C++
подскажите пжл как сравнить 2 подмножества в матрице

Задача о сумме подмножества. Псевдокод в код С++ - C++
Доброго времени суток. Пожалуйста, помогите в решении следующей проблемы: необходимо данный псевдокод перевести в исполняемый код С++ (см....

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

Разбиение множества на подмножества с одинаковыми суммами - C++
Здраствуйте. Есть такая задача: разбить последовательность чисел от 1 до n * n на n подмножеств так, чтобы все они состояли из n чисел и...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
01.11.2009, 08:14
Ответ Создать тему
Опции темы

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