Модераторы: volvo877, Snowy, MetalFan
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Вывести все подмножества множества 
:(
    Опции темы
Innuendo
Дата 6.12.2006, 19:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 745
Регистрация: 24.12.2005
Где: Молдова

Репутация: нет
Всего: 6



Блин, вроде программка простенькая, но я  с множествами никогда не работал, и чё-то не получается
есть множество M=['A','B','C','D']
надо вывести все подмножества. Чё-то не получается.. если бы массив, я бы сделал, а с множествами как-то не особо работается


--------------------
=)
PM MAIL ICQ Jabber   Вверх
Zero
Дата 6.12.2006, 21:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24



Ну общий принцип такой:
Код

var
  M:set of char;
  i:integer;
Begin
  m := ['A','B','C','D'];
  for i:=1 to 255 do
    if chr(i) in m then
      write(chr(i),' ');
end.

PM MAIL ICQ   Вверх
volvo877
Дата 6.12.2006, 22:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116



Цитата(Innuendo @  6.12.2006,  18:47 Найти цитируемый пост)
надо вывести все подмножества

Комбинаторика? Слово "множество", кстати, еще не означает, что тебе надо работать с типом Set ... Вот программа, печатающая все возможные подмножества множества из N элементов:

Код
Var N : Longint;
    Count : Longint;
    I : Longint;

Procedure PrintSet(X : Longint);
Var P : Integer;
Begin
 Write('{ ');
 P:=N;
 While X <> 0 Do
  Begin
   If X Mod 2 = 1 Then Write(P, ' ');
   Dec(P);
   X:=X Div 2;
  End;
 Writeln('}');
End;

Begin
 N:=4;
 Count:=1 Shl N; {2^N}
 For I:=0 To Count - 1 Do
  PrintSet(I);
End.


А уж что именно печатать вместо цифр 1 .. N - это ты и должен брать из своего M... У тебя там символы - значит,
Код

Write(Chr(Ord('A') + P - 1), ' ');
Количество символов во входном множестве тоже можешь посчитать, используя In, а не задавать прямо в программе...
PM MAIL   Вверх
Innuendo
Дата 7.12.2006, 22:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 745
Регистрация: 24.12.2005
Где: Молдова

Репутация: нет
Всего: 6



Zero
С таким алгоритмом множества по 2, 3, 4 элемента не будут выводится вроде

volvo877, Да, комбинаторика... Множества это что-то типа сочетаний. Я сам как раз и написал без множеств SET.
Но это задание в учебнике было: есть множество M:=['A','B','C','D'] и надо вывести все подмножества... Типа надо работать именно с сетом, а не с массивами, константами и т.д.


--------------------
=)
PM MAIL ICQ Jabber   Вверх
Kuvaldis
Дата 8.12.2006, 03:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: нет
Всего: 61



volvo877
Это быстрый в написании вариант,  но, к сожалению, медленно работающий. (хотя автор и не уточнял про скорость) smile 
Множество представлено вектором наличия. При получении следующего множества нужно стремиться, чтобы оно отличалось от предыдущего как можно меньше, в идеале, в одном месте.
Эта проблема генерации решена так
Код

Коды Грея    
...    
Этот алгоритм позволяет перебирать все наборы Bm так, чтобы каждый следующий набор    
отличался от предыдущего только в одном разряде. Построенная с помощью этого    
алгоритма последовательность наборов называется кодом Грея. Вообще, n-разрядный код    
Грея — это упорядоченная (возможно, циклическая) последовательность, состоящая из    
 2n n-разрядных кодовых слов, каждое из которых отличается от соседнего в одном разряде.    
Будем рассматривать бинарные коды Грея порядка n. Итак, на вход алгоритма подается    
единственное число n, которое указывает порядок кода Грея. По ходу выполнения    
алгоритма мы получим последовательность всех подмножеств n-элементного множества,    
в которой каждое последующее подмножество получается из предыдущего добавлением    
или удалением единственного элемента (наименьшим возможным изменением) — код Грея.    
При этом каждое подмножество будет представляться бинарной последовательностью    
B[1], …, B[n].    
Gray-Generation(n)    
 1  for i := 1 to n do B[i] := 0;    
 2  i := 0;    
 3  repeat    
 4      write (B[i], …, B[n]);    
 5      i := i + 1; p := 1; j := i;    
 6      while j mod 2 = 0 do    
 7          begin    
 8              j := j/2; p := p + 1;  // количество 2 в разложении числа на прост. множители + 1    
 9          end;    
10      if p ≤ n then B[p] := 1 − B[p];    
11  until p > n  


Обоснование можно точно посмотреть в книге Новиков "Дискретная математика для программистов". 
Да и в Сети думаю, оно есть....


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
volvo877
Дата 8.12.2006, 20:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116



Kuvaldis, я понимаю, что это - не самый быстрый вариант... Но дело все в том, что ведь и предложенный тобой алгоритм, и любой из... ну, навскидку, еще трех-четырех, которые я смогу привести - не работают со множествами, а только с массивами/числами...

Автору, как выяснилось, это не подходит...
PM MAIL   Вверх
Innuendo
Дата 9.12.2006, 19:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 745
Регистрация: 24.12.2005
Где: Молдова

Репутация: нет
Всего: 6



volvo877, а вообще реально это как-то делать с множествами? с множествами не так много операций можно делать... вызов элемента по индексу. Задачку не мне задали, это меня попросили. Я им дал вариант с массив и константой стринговой 'ABCD' из которой вынимались элементы, а с множествами не наю =)

Но уже ладно, задание уже не нужно (хотя всё равно интересно, можно ли такое сделать, и если нельзя то почему это задание в конце темы Set  и в условии дан set =) )


--------------------
=)
PM MAIL ICQ Jabber   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi"
THandle
Rrader
volvo877

Запрещается!

1. Обсуждать и делится взломанными компонентами или программным обеспечением

2. Публиковать ссылки на варез

3. Оффтопить

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, THandle, Rrader, volvo877.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Object Pascal: кроссплатформенные технологии | Следующая тема »


 




[ Время генерации скрипта: 0.0723 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.