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

подмножества

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

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

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

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

Подмножества множества
Здравствуйте, можете пожалуйста объяснить работу этого кода? Желательно поподробнее, что делает...

Разбить множество на подмножества
Здравствуйте, помогите пожалуйста, нужно разбить множество из n элементов на всеми способами k...

Разбить множество на подмножества
Добрый день. Нужна помощь с задачей: Имеем множество с N разными числами. Необходимо разбить на...

4
Андрейка
422 / 226 / 87
Регистрация: 25.03.2009
Сообщений: 744
31.10.2009, 18:14 2
http://www.cyberforum.ru/cpp/thread39207.html
0
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}
0
odip
Эксперт С++
7167 / 3225 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
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 вложенными циклами не сделать.
0
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 // собираемое подмножество
0
01.11.2009, 08:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2009, 08:14

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

Найти все подмножества длины 3
Найти все подмножества длины 3 множества A = {1,2,3,4,5,6}. Я сделал так, чтобы это был...

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


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

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

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