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

Установить, является ли одно множество подмножеством другого - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.63
bigar
 Аватар для bigar
53 / 53 / 23
Регистрация: 18.02.2011
Сообщений: 146
19.02.2011, 01:40     Установить, является ли одно множество подмножеством другого #1
помогите пожалуста)))
1)Создать множества А,В,С- псевдослучайных чисел из натурального ряда;
2)Поэлементно сравнивая множества:
- установить, яляется ли одно множество подмножеством другого
-найти пересичение множеств;
-найти объединение множеств
-симетрическую разность
-найти множества являющиеся дополнением
Может есть алгоритмы???
буду очень благодарен
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2011, 01:40     Установить, является ли одно множество подмножеством другого
Посмотрите здесь:

В массиве слов найти пару слов, из которых одно является обращением другого C++
В тексте найти пару слов, из которых одно является обращением другого C++
C++ Си является подмножеством С++?
C++ Проверить, является ли один массив подмножеством другого
В заданном предложении найти пару слов, из которых одно является обращением другого C++
C++ Определить, является ли множество X подмножеством множества Y
Указатели: написать функцию, проверяющую, является ли массив В подмножеством массива А C++
Определить не является ли одно слово обращением (перевертышем) другого C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
19.02.2011, 13:46     Установить, является ли одно множество подмножеством другого #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Набросал коротенько реализацию.
Отличие от задания: нет как такового "поэлементного сравнения" при операциях над множествами.
Недоработка: функция PrintAllNumbers не печатает отрицательные значения (ну их в шахту).
Может быть косяк в MSVS и BC из-за типов данных, нет возможности проверить.
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#ifdef _MSC_VER
  typedef __int16 int16_t;
  typedef unsigned __int16 uint16_t;
#else
  #include <stdint.h>
#endif
 
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cstring>
 
class Set {
 public:
  typedef int16_t ValueType;
  typedef uint16_t UnsignedValueType;
  typedef unsigned char StorageType;
  Set()
    : data_size_((1 << (sizeof(ValueType) * 8)) / (sizeof(StorageType) * 8)),
      data_(new StorageType[data_size_]) {
    for (int i = 0; i < data_size_; ++i)
      data_[i] = 0;
  }
  Set(const Set &other)
    : data_size_(other.data_size_),
      data_(new StorageType[data_size_]) {
    for (size_t i = 0; i < data_size_; ++i)
      data_[i] = other.data_[i];
  }
  ~Set() {
    delete [] data_;
  }
  int Has(ValueType value) const {
    UnsignedValueType uvalue = static_cast<UnsignedValueType>(value);
    return data_[uvalue / (sizeof(StorageType) * 8)] &
           (1 << (uvalue % (sizeof(StorageType) *8 )));
  }
  void Add(ValueType value) const {
    UnsignedValueType uvalue = static_cast<UnsignedValueType>(value);
    data_[uvalue / (sizeof(StorageType) * 8)] |=
                  (1 << (uvalue % (sizeof(StorageType) * 8)));
  }
  void Remove(ValueType value) const {
    UnsignedValueType uvalue = static_cast<UnsignedValueType>(value);
    data_[uvalue / (sizeof(StorageType) * 8)] &=
                  ~(1 << (uvalue % (sizeof(StorageType) * 8)));
  }
  bool IsEmpty() const {
    for (size_t i = 0; i < data_size_; ++i)
      if (data_[i] != 0)
        return false;
    return true;
  }
  size_t DataSize() const {
    return data_size_;
  }
  Set Intersection(const Set &other) {
    Set result;
    for (int i = 0; i < data_size_; ++i)
      result.data_[i] = data_[i] & other.data_[i];
    return result;
  }
  Set Union(const Set &other) {
    Set result;
    for (int i = 0; i < data_size_; ++i)
      result.data_[i] = data_[i] | other.data_[i];
    return result;
  }
  Set Complement(const Set &other) {
    Set result;
    for (int i = 0; i < data_size_; ++i)
      result.data_[i] = data_[i] & ~other.data_[i];
    return result;
  }
  Set &operator=(const Set &other) {
    if (&other != this) {
      data_size_ = other.data_size_;
      delete [] data_;
      data_ = new StorageType[data_size_];
      for (size_t i = 0; i < data_size_; ++i)
        data_[i] = other.data_[i];
    }
    return *this;
  }
  void PrintAllNumbers() {
    for (UnsignedValueType i = 0; i <= (1 << (sizeof(ValueType) * 8) - 1); ++i)
      if (Has(i))
        printf("%d ", ValueType(i));
    printf("\n");
  }
 private:
  size_t data_size_;
  StorageType *data_;
};
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
  Set a, b, c;
 
  for (int i = 0; i < 10; ++i) a.Add(rand() % 10);
  for (int i = 0; i < 10; ++i) b.Add(rand() % 10);
 
  printf("Set a: ");
  a.PrintAllNumbers();
  printf("Set b: ");
  b.PrintAllNumbers();
 
  printf("Union: ");
  a.Union(b).PrintAllNumbers();
 
  printf("Intersection: ");
  a.Intersection(b).PrintAllNumbers();
 
  printf("Symmetric difference: ");
  a.Complement(b).Union(b.Complement(a)).PrintAllNumbers();
 
  printf("Complement b in a: ");
  a.Complement(b).PrintAllNumbers();
  printf("Complement a in b: ");
  b.Complement(a).PrintAllNumbers();
  return  0;
}

Не по теме:

Посмотрим на благодарность.

Nameless One
19.02.2011, 14:21
  #3

Не по теме:

Цитата Сообщение от lemegeton Посмотреть сообщение
Посмотрим на благодарность.
Скорее будет: "А можно как-нибудь попроще?"

BIOSonar
2 / 2 / 0
Регистрация: 17.01.2010
Сообщений: 40
05.04.2012, 19:07     Установить, является ли одно множество подмножеством другого #4
мне вот пригодилось. благодарствую.
Andr1y
Сообщений: n/a
29.10.2014, 20:22     Установить, является ли одно множество подмножеством другого #5
спасибо за пример, но если можно без наследования. надо только перегрузка операторов
Yandex
Объявления
29.10.2014, 20:22     Установить, является ли одно множество подмножеством другого
Ответ Создать тему
Опции темы

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