Поясните работу с множествами

← →
Андрей Миронов (2010-01-24 16:11) [0]

Пожалуйста, дайте объяснения - не пойму, как применимы операции с множествами к решению этой задачи:
Дана непустая последовательность слов из стpочных pусских букв; между соседними словами - запятая, за последним словом - точка.Напечатать в алфавитном порядке все согласные буквы, котоpые входят только в одно слово.

← →
xayam © (2010-01-24 16:15) [1]

а что непонятно? делаешь множество согласных букв и ищешь пересечения с каждым словом из непустой последовательности из стpочных pусских букв

← →
Андрей Миронов (2010-01-24 16:17) [2]

То есть я должен пробежаться по каждому символу текущего слова и добавить его в отдельное множество, так? А как затем понять, что данный член из множества (буква) входила только в одно слово?

← →
xayam © (2010-01-24 16:26) [3]

> Андрей Миронов (24.01.10 16:17) [2]
> То есть я должен пробежаться по каждому символу текущего
> слова и добавить его в отдельное множество, так?

множество согласных - это ведь константа. Все буквы известны же?

> А как затем понять, что данный член из множества (буква)
> входила только в одно слово?

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

← →
Андрей Миронов (2010-01-24 16:29) [4]

Я не совсем понимаю ход ваших объяснений. Да, я могу сделать множество известных мне букв. И вот в цикле по элементам строки я нашел пересечение? Это ведь одна буква. Поясните подробнее, если возможно.

← →
xayam © (2010-01-24 16:44) [5]

> И вот в цикле по элементам строки я нашел пересечение? Это
> ведь одна буква.

ну е-мое теория то вообще проще пареной репы, почитал бы уже где :)
скажем, есть множество всех согласных S = ["б", "в", "г", "д" ...] и множество или массив заданных слов М = ["буква", "слово", "предложение"]. Тогда пересечение множества/массива S с множеством/массивом М будет равно для первого элемента "бкв", для второго - "слв" и т.д. Другое дело на каком языке это реализовывать, если php - там есть специальные функции для работы с несколькими массивами, delphi - для работы со множествами in (проверка вхождения) и * (пересечение множеств) и т.д.

← →
palva © (2010-01-24 20:55) [6]

Вам надо завести несколько переменных типа множество символов.
ss - в начале обработки занесите туда все согласные буквы.
s1 - здесь будет ответ, сначала будет пустым множеством.
и другие переменнные будут того же типа.
Цикл по словам
w := множество букв очередного слова; (вы должны обработать слово вручную)
t := ss*w; // кандидаты на добавление
sp := t - s1; // эти буквы вы действительно добавите
sm := t*s1; // эти буквы встретились уже во втором слове и их придется исключить из s1
ss := ss - sm // не будем больше иметь с этими буквами дела.
s1 :=s1 - sm + sp;
Конец цикла по словам
Печатаете результат s1 - опять цикл вручную.

← →
Андрей Миронов (2010-01-24 21:34) [7]

xayam, я это понял. Вопрос в том, как определить, что, скажем, в приведенном вами примере б,к,с и л встречаются всего один раз, а "в" - дважды?

← →
Андрей Миронов (2010-01-24 21:43) [8]

palva, поясните, пожалуйста, эти строки и поправьте меня:
sp := t - s1; // эти буквы вы действительно добавите sm := t*s1; // эти буквы встретились уже во втором слове и их придется исключить из s1 ss := ss - sm // не будем больше иметь с этими буквами дела. s1 :=s1 - sm + sp;
Предположим, t равно "бкв", тогда sp = бкв-пустое множество=бкв,
sm = бкв * пустое множество = пустое множество, ss = вновь все буквы и s1 = s1 + sp = бкв

Не ясно, что тут и зачем.

← →
palva © (2010-01-24 22:00) [9]

> Не ясно, что тут и зачем.

Ну значит все согласные буквы первого слова попали в s1.
Дальше посмотрите, что будет со вторым словом, в котором, предположим, тоже есть буква "б".
А если в третьем слове есть буква "б"? Попадет ли эта буква в s1, а если не попадет, то почему?

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

← →
Андрей Миронов (2010-01-24 22:12) [10]

Мне кажется, тут просто ваши комментарии не вполне ясны. Ну вот как понять "вы действительно добавите"? Куда? И почему "встретились уже во втором слове" и как их "придется исключить", если там просто пересечение? Далее зачем-то убираете что-то из начального множества букв и делаете малопонятную операцию с результатом. Поясните, если можете, почему написано именно так и что значат эти операции?

← →
xayam © (2010-01-24 22:17) [11]

> Андрей Миронов (24.01.10 22:12) [10]
> Мне кажется, тут просто ваши комментарии не вполне ясны.
> Ну вот как понять "вы действительно добавите"? Куда? И
> почему "встретились уже во втором слове" и как их "придется
> исключить", если там просто пересечение? Далее зачем-то
> убираете что-то из начального множества букв и делаете малопонятную
> операцию с результатом. Поясните, если можете, почему написано
> именно так и что значат эти операции?

слушай, palva расписал тебе уже всю поднаготную, пора говорить ему спасибо и в остальном самому разбирать. Операции то должен осилить? :)

← →
Андрей Миронов (2010-01-24 22:20) [12]

Простите, я, конечно, премного благодарен, но я не могу понять логику программы, а не операции с множествами. Если несложно, уделите мне немного времени и опишите смысл операций в алгоритме palva.

← →
palva © (2010-01-24 22:26) [13]

Вы алгоритм-то покрутили? Работает или нет?

"Вы действительно добавите", значит эти буквы прибавятся к s1 при обработке данного слова. - Не всех же кандидатов добавлять.

> и как их "придется исключить", если там просто пересечение?

Это сначала пересечение. А потом мы это пересечение вычитаем из s1, то есть исключаем.

> Далее зачем-то убираете что-то из начального множества букв

Затем, чтобы если буква "б" встретилась в третий раз, чтобы она не добавилась к s1

А написал я так потому, что мне показалось, что это будет работать. Могу в этом и ошибаться. И написать можно по-другому, очень многими способами и с множествами, и без множеств.

← →
Андрей Миронов (2010-01-24 22:45) [14]

Мне все равно осталось непонятно ваше решение, поэтому я сделал свое:

результат = [], цикл по словам
символы текущего слова = []
берем все согласные текущего слова (согласные)
находим пересечение р-та и этих символов - это и будет символы, что уже были, а на первом шаге соотно это пустое мн-во, т.к. р-т пуст
добавляем в р-т символы текущего и вычитаем р-т пересечения

Нормально?

← →
palva © (2010-01-24 23:26) [15]

Хорошо делаете, что пишете свое. Вы алгоритм на бумажке прокручивать умеете? Неужели не учили? А отладчиком пользоваться? В конечном счете на вопрос "Нормально?" вам должен ответить не я а компьютер на прогоне теста. Напишите программу, придумайте достаточно большой тест, чтобы все случаи проверить, и вперед.

Попробуйте взять строку, где в каждом слове по букве б. На первом слове эта буква добавится в s1, на втором вычтется, на третьем добавится, на четвертом вычтется. Вы этого хотели? А ваш приказ компьютеру - сделать именно это.

← →
korneley © (2010-01-24 23:39) [16]

> Андрей Миронов (24.01.10 22:45) [14]
> Нормально?

Нет. Отсутствует история дублей. См [6]
ss := ss - sm // не будем больше иметь с этими буквами дела.

А то на втором слове удалишь, а на третьем опять добавишь.

← →
Андрей Миронов (2010-01-24 23:40) [17]

Вы имеете ввиду, что я неверно написал? А как же тогда сделать, чтобы уж точно не добавлялось вновь то, что уже удалилось? Удалять непосредственно из константного множества согласных букв?

← →
Андрей Миронов (2010-01-24 23:46) [18]

korneley, так а как еще можно решить эту проблему? Может, просто завести дополнительное множество, в котором буду собирать все ранее добавленные множества, и перед добавлением в р-т проверять, есть ли уже такие?

← →
korneley © (2010-01-24 23:49) [19]

> Андрей Миронов (24.01.10 23:40) [17]
> А как же тогда сделать,
> чтобы уж точно не добавлялось вновь то, что уже удалилось?

Бли-и-ин!!! Ну какой вы... непонятливый... Исключи их из множества согласных и всё.

← →
Андрей Миронов (2010-01-24 23:52) [20]

Простите, что раздражаю вас, просто очень хотелось бы понять. Возможно, конечно, вам эта тема сразу легко далась, но не для всех людей все сразу становится ясно. Я, к сожалению, отношусь ко вторым. В общем, просто в свой алгоритм я добавляю Sogl = Sogl - CurrSogl, где Sogl - общее множество согласных, а CurrSogl - множество согласных текущего слова. Так?

Для ясности позволю прозволю себе прокомментировать [6]

1. w := множество букв очередного слова; (вы должны обработать слово вручную)
2. t := ss*w; // кандидаты на добавление
Это, надеюсь понятно

3. sp := t - s1; // эти буквы вы действительно добавите
Буквы еще не присутствующие в результате, стало быть реально добавляемые.

4. sm := t*s1; // эти буквы встретились уже во втором слове и их придется исключить из s1
Буквы присутствующие в результате, а даже точнее, второй раз встреченные, дальше будет ясно почему именно второй.

5. ss := ss - sm // не будем больше иметь с этими буквами дела.
Вот! Убираем дубли из проверочного множества, дабы дальше в п.2 на следующем слове они вообще не выбирались. Зачем они нам?

6. s1 :=s1 - sm + sp;
Собственно результат вычитаем дубли и добавляем чего вообще в нем не было

> как определить, что, скажем, в приведенном вами примере б,к,с и л встречаются всего один раз, а "в" - дважды?

procedure TForm1.Button1Click(Sender: TObject); type TSet = set of char; var s1, s2, s3: TSet; ch: char; cl: integer; begin s1:= ["б","у","к","в","а"]; s2:= ["с","л","о","в","о"]; s3:= ["п","р","е","д","л","о","ж","е","н","и","е"]; for ch:= "а" to "я" do begin cl:= 0; if ch in s1 then inc(cl); if ch in s2 then inc(cl); if ch in s3 then inc(cl); ListBox1.Items.Add(ch + " = " + IntToStr(cl)) end; end;

> sniknik © (25.01.10 00:38) [22]

Значит типизированные константы побоку?
Следование "дурным" рекомендациям или жизненная позиция?

> sniknik © (25.01.10 00:38) [22]

Так ему придётся ещё цикл внутри по словам лепить :) Я бы вообще взял массив типа CharCount : array["а".."я"] of integer и одним проходом по входному массиву посчитал кто и сколько раз в (разных словах) встречался
что-то типа
fillchar(CharCount, sizeof(CharCount), 0); TempSet := []; for i := 1 to Length(s) do begin if s[i] in [" ", ","] then TempSet := [] else if (s[i] in Consonants) and not (s[i] in TempSet) then begin inc(CharCount[s[i]]); TempSet := TempSet + [s[i]]; end; end;

> ему ж только согласные нужны

А гласных всё равно меньше, примерно раза в два :))

> Германн © (25.01.10 01:08) [23]
> Значит типизированные константы побоку?

Как это! У меня, в [25] подразумевается
const Consonants : set of char = ["б", "в", "г", "д", "й", "ж", "з", "к", "л", "м", "н", "п", "р", "с", "т", "ф", "х", "ц", "ч", "ш", "щ"];
:)))

> Как это! У меня, в [25]

Ну я же не тебе адресовал вопрос. А Николаю.

код для понимания должен быть простым, и очевидным (т.е. никаких операций по умолчанию и "за кадром"), т.что можете считать это жизненным принципом.

> Так ему придётся ещё цикл внутри по словам лепить :)
если поймет, то не придется. код не готовый для задачи, а для понимания принципа.
в данном случае
> как определить, что, скажем, в приведенном вами примере б,к,с и л встречаются всего один раз, а "в" - дважды?
т.е. сколько вхождений символов в наборах.
а уж разделить на гласные не гласные, проблем не должно быть (спрашивал то не это, значит вроде знает).

Поясните работу с множествами Найти похожие ветки