Множества в Pascal
В Pascal множества обладают рядом особенностей. Все элементы одного множества должны принадлежать одному и тому же базовому типу. В качестве базового типа должен выступать порядковый тип, но не каждый.
Размер множества в Паскале ограничен предельно допустимым количеством элементов. Во множествах допускаются только такие элементы, порядковые значения которых в их базовых типах не выходят за границы 0..255. Для целочисленных множеств это означает, что в них могут присутствовать только числа от 0 до 255. Отрицательные элементы во множествах не допускаются.
Поэтому базовым типом не может выступать, например, integer . Если необходимо множество целочисленных объектов, то базовый тип должен объявлен как диапазон типа byte . Для символьных множеств базовым типом является char (в нем 256 значений с порядковыми номерами от 0 до 255).
Объявление множеств
В математике для обозначения множества используют фигурные скобки, например , в Паскале — квадратные, например [1, 3, 5]. Порядок элементов во множестве не имеет значения. Так множества [3, 6, 9] и [9, 3, 6] одинаковы.
По форме записи объявление переменной типа множество сходно с объявлением одномерного массива:
var имя: set of тип;Например, объявление переменной ch как множества с базовым типом char , имеет вид:
var ch: set of char;Можно сначала объявить тип множества, а потом использовать его для объявления переменных:
type t_ch = set of char; var ch1, ch2: t_ch;Часто в качестве базового типа используются перечисления и диапазоны:
type week_days = (Mon, Tue, Wed, Thu, Fri); var work_days: set of week_days; lett: set of 'A'..'Z';type nums = 5..25; var a: set of nums;Объявление переменной-множества не присваивает ей набора значений.
Построение множества
Чтобы во множестве появились элементы, необходимо выполнить оператор присваивания, в левой части которого стоит имя переменной-множества, а в правой — конструктор множества или некоторое выражение над множествами.
Конструктор множества — это заключенный в квадратные скобки перечень элементов, разделенных запятыми. В качестве элементов могут использоваться диапазоны значений:
type week_days = (Mon, Tue, Wed, Thu, Fri); var work_days: set of week_days; lett: set of 'A'..'Z'; begin work_days := [Mon, Wed, Thu]; lett := ['C', 'E'..'M', 'Z'] end.Следует помнить, что при задании множества порядок его элементов безразличен, но при задании диапазона такой порядок важен.
Множество, в котором нет элементов, называется пустым (или нуль-множеством). В языке программирования Паскаль обозначается квадратными скобками, между которыми нет элементов:
work_days := [ ];Множество может быть объявлено типизированной константой, для чего в описании после знака равенства следует указать конструктор множества. Например:
const lett: set of ['а'..'я'] = ['а', 'е', 'и', 'о', 'у', 'ы', 'э', 'ю', 'я'];Конструируя множества, можно использовать и переменные при условии, что их текущие значения попадают в диапазон базового типа множества. Так, если ch1 и ch2 имеют тип char , то допустима следующая последовательность операторов:
ch1 := 'A'; ch2 := 'K'; chs := [ch1, ch2, 'M'];В результате получится множество [‘A’, ‘K’, ‘M’].
Вывод элементов множества
В Pascal элементы множества нельзя вводить и выводить. Для организации их ввода-вывода следует использовать вспомогательные переменные. В то же время можно использовать множества как элементы типизированных файлов.
type nums = 0..10; var a: set of nums; i: byte; begin a := [3, 0, 2]; for i := 0 to 10 do if i in a then writeln(i); end.0 2 3Операции над множествами
- присвоение
- объединение
- пересечение
- дополнение
- тождественность
- нетождественность
- содержится во множестве
- содержит множество
- принадлежность элемента множеству
Объединение, пересечение и разность множеств
Над множествами выполнимы объединение (+), пересечение (*) и разность (-).
Объединение двух множеств A и B (A + B) – это новое множество, состоящее из элементов, принадлежащих множеству A или B, либо тому и другому одновременно.
var chs1, chs2, chs3: set of char; begin chs1 := ['a', 'b', 'd']; chs2 := ['m', 'd', 'e']; chs3 := chs1 + chs2 + ['k', 'n']; end.Результат: chs3 = [‘a’, ‘b’, ‘d’, ‘m’, ‘e’, ‘k’, ‘n’].
Пересечение двух множеств A и B (A * B) – это множество, состоящее из элементов, одновременно принадлежащих множествам A и B.
chs3 := chs1 * chs2;Результат: chs3 = [‘d’] .
Разность (дополнение) множеств A и B (A — B) – это новое множество, состоящее из элементов множества A, не вошедших в множество B.
chs1 := ['a', 'e', 't']; chs2 := chs1 – ['e'] < ['a', 't'] >chs3 := ['m', 'n', 't'] – chs2
Используя операции объединения, пересечения и разности, можно добавлять элементы к множествам или удалять их.
Для вставки и удаления элементов при работе с множествами в Pascal введены две процедуры:
include(имя_множества, элемент) exclude(имя_множества, элемент)
Первая из них позволяет выполнить добавление одного элемента в указанное множество, а вторая удалить. Например:
include (chs1, 'g'); < аналогично chs1 + ['g'] >exclude (chs2, 'a');
Операции сравнения множеств
Над множествами можно выполнять четыре операции сравнения: =, <>, >=,
Два множества A и B равны (A = B), если каждый элемент множества A является элементом множества B и наоборот.
Два множества A и B не равны (A <> B), если они отличаются хотя бы одним элементом.
Другими словами, операции = и <> используются для проверки эквивалентности: два значения переменной типа set считаются равными, если они состоят из одних и тех же элементов.
[1, 3] = [3, 1] возвращает true,
[1..3] = [1, 2, 3] возвращает true,
[1] <> [2] возвращает true,
[1, 2, 3] = [1, 4, 3] возвращает false,
[red, blue] = [red, yellow] возвращает false.
Множество A является подмножеством множества B (A = A), если каждый элемент из A присутствует в B.
Пустое множество [ ] содержится во всех множествах, т.е. всегда [ ]
in — операция проверки принадлежности элемента множеству
Имеется возможность выяснить, принадлежит ли данный элемент некоторому множеству. Для этого служит операция in . Пусть A – множество элементов некоторого базового типа, а x – переменная этого типа. Тогда выражение x in A истинно, если значение x является элементом множества A .
red in [red, yellow] возвращает true ;
red in [blue, green] возвращает false .
Замечание 1. Чтобы проверить, является ли значение n цифрой, удобно использовать операцию in следующим образом:
if n in [0..9] then …Замечание 2. Результат операции in может быть неопределенным в некоторых случаях. Пусть:
a: set of 1..50; x: integer.Если присвоить x число, большее максимального значения 50 (например, x := 55 ), то в этом случае результат операции x in a не всегда false .
Все операции сравнения множеств, а также операция in возвращают логическое значение true или false .
Приоритеты операций над множествами
В сложных выражениях над множествами операции имеют следующие приоритеты:
Программирование. Множества Pascal-Паскаль
Еще одним фундаментальным классом данных являются данные, структурированные в виде множеств.
О перечисляемых типах
Мы уже рассматривали три скалярных типа, которые, в принципе, являются перечисляемыми типами, – это boolean, char и integer. В самом деле, ведь каждый из этих типов можно задать следующим образом:
type
Boolean= (false, true);
char= #0..#255;
integer= -32768..32767;
(Представление #xxx означает, что должен быть взят символ, чей код в таблице ASCII равен xxx).
Это базовые типы, которые не требуется задавать каждый раз, уже определены в системе именно таким образом. Кроме них имеется еще несколько интервальных типов, с некоторыми из которых мы знакомы:
shortint>= -128..127;
longint= -2147483648..247483647;
byte= 0..255;
word= 0..65535;
Переменные, имеющие эти типы, могут принимать значения, лежащие в границах соответствующих интервалов.
Для работы с перечисляемыми типами существуют следующие функции, которые хранятся в библиотеке системных функций, и программист имеет к ним доступ:
ord(N) – возвращает номер элемента N в множестве;
succ(N) – возвращает следующее значение для N;
pred(N) – возвращает предыдущее значение для N.
Пользователь имеет возможность описать собственный перечисляемый тип данных. В общем виде это описание выглядит так:
В скобках перечисляются все возможные значения, которые может принимать переменная данного типа. Следует запомнить, что названия значений нельзя давать по-русски(это важно!).
Например, мы можем описать тип данных color и перечислить семь основных цветов:
type
color=(red, orange, yellow, green, blue, magenta);
При этом значения получают номера в порядке их перечисления, начиная с 0. Поэтому для данного типа справедливыми будут отношения элементов:
red < orange< yellow< green< blue< magenta;
ord(red)=0;
succ(blue)= magenta;
pred(green)=yellow;
Множественный тип данных Паскаля
Множественный тип данных Паскаля напоминает перечислимый тип данных. Вместе с тем множественный тип данных – набор элементов не организованных в порядке следования.
В математике множественный тип данных – любая совокупность элементов произвольной природы. Операции, которые производятся над множествами, по существу заключаются во включении и исключении элементов из множества.
Понятие множества в языке программирования значительно уже математического понятия.
В Паскале под множественным типом понимается конечная совокупность элементов, принадлежащих некоторому базовому типу данных.
В качестве базовых типов могут использоваться:
- перечислимые типы;
- символьный;
- байтовый;
- диапазонные на основе вышеперечисленных.
Такие ограничения связаны с формой представления множественного типа данных в Паскале и могут быть сведены к тому, чтобы функция ord() для используемого базового типа лежала в пределах от 0 до 255.
После того, как базовый тип задан, совокупность значений соответствующего множественного типа данных определяется автоматически. В нее входят все возможные множества, являющиеся произвольными комбинациями значений базового типа. Все эти множества являются отдельными значениями определенного множественного типа данных.
Описание множественного типа данных Паскаля
Type = set of
Пример множественного типа данных Паскаля
Type symbol= set of char;
Var letter, digits, sign: symbol;
Для того чтобы придать переменной множественного типа значение, используют конструктор множества – перечисление элементов множества через запятую в квадратных скобках. Например,
Конструктор множества может содержать диапазон значений базового типа. Тогда во множества включаются все элементы диапазона. Например,
digits:= [‘0’ .. ‘9’];
letter:= [‘a’ .. ‘z’];
Обе формы конструирования множеств могут сочетаться. Например,
letter:= [‘a’ .. ‘z’, ‘A’ .. ‘Z’];
Конструктор вида [] обозначает пустые множества.
В программе можно использовать множественны тип как константы, в этом случае их определяют следующим способом:
Const YesOrNo= [‘Y’, ‘y’, ‘N’, ‘n’];
Можно множественный тип определить как типизированную константу:
Const digits: set of char= [‘0’ .. ‘9’];
При описании множественного тип как констант допускается использование знака “+” (слияние множеств). Например,
Const Yes= [‘Y’, ‘y’]; No= [‘N’, ‘n’];
YesOrNo= Yes+ No;
Операции над множественными типами Паскаля
С множественными типами Паскаля можно выполнять действия объединения, исключения и пересечения.
Объединение множественных типов содержит элементы, которые принадлежат хотя бы одному множеству, при этом каждый элемент входит в объединение только один раз. Операция объединения множеств обозначается знаком ‘+’.
Пример множественных типов Паскаля
Возможно объединять множественные типы и отдельные элементы. Например,
small:= [‘c’ .. ‘z’];
small:= small + [‘a’] +[‘b’];
Исключение определяется как разность множественных типов, в котором из уменьшаемого исключаются элементы, входящие в вычитаемое. Если в вычитаемом есть элементы, отсутствующие в уменьшаемом, то они никак не влияют на результат. Операция исключения обозначается знаком ‘-‘.
Пример исключения множественных типов Паскаля
letter:= [‘a’ .. ‘z’];
glasn:= [‘a’, ‘e’, ‘o’, ‘u’, ‘i’, ‘y’];
soglasn:= letter-glasn;
Пресечение множественных типов– множества, содержащие элементы, одновременно входящие в оба множества. Операция пересечения множеств обозначается знаком ‘*’.
Пример пересечения множественных типов
Type chisla= set of byte;
Var z,x,y: chisla;
………..
x:= [0..150];
y:= [100..255];
z:= x*y
Операции отношения множественных типов Паскаля
Наряду с рассмотренными выше операциями, над значениями множественного типа определены и некоторые операции отношения. Операндами операций над множественными значениями в общем случае являются множественные выражения. Среди операций отношения над значениями множественного типа особое место занимает специальная операция проверки вхождения элемента во множества, обозначаемая служебным словом in. В отличие от остальных операций отношения, в которых значения обоих операндов относятся к одному и тому же множественному типу значений, в операции in первый операнд должен принадлежать базовому типу, а второй – множественному типу значений, построенному на основе этого базового типа. Результатом операции отношения, как обычно, является логическое значение (true или false).
‘a’ in glasn значение операции true;
‘o’ in soglasn значение операции false;
Операция сравнения на равенство множественных типов Паскаля. Множества считаются равными (эквивалентными), если все элементы одного множества присутствуют в другом и наоборот. Для операции сравнения на равенство или неравенство используются символы ‘=’ и ‘<>‘.
A:= [2,1,3];
D:= [1,3,2];
Тогда операция A=D имеет значение true, а операция A<>D имеет значение false.
Проверка включения. Одно множество считается включенным в другое (одно множество является подмножеством другого), если все его элементы содержатся во втором множестве. Обратное утверждение может быть и несправедливым. Операции проверки включения обозначаются ‘=’.
letter >= glasn;
soglan
Программирование
Исходники Pascal (127)
Справочник
Справочник по паскалю: директивы, функции, процедуры, операторы и модули по алфавиту
Типы данных
Множественный тип данных. Множество. Элемент множества. Способы задания множества. Объединение множеств. Разность множеств. Пересечение множеств
Множественный тип данных напоминает перечислимый тип данных. Вместе с тем, множество — набор элементов, не организованных в порядке следования. В математике множество — любая совокупность элементов произвольной природы. Понятие множества в программировании значительно уже математического понятия. Определение. Под множеством в Паскале понимается конечная совокупность элементов, принадлежащих некоторому базовому типу. В качестве базовых типов могут использоваться: перечислимые типы данных, символьный и байтовый типы или диапазонные типы на их основе. Такие ограничения связаны с формой представления множества в языке и объясняются тем, что функция Ord для элементов используемого базового типа должна быть в пределах от 0 до 255. Множество имеет зарезервированное слово set of и вводится следующим описанием
| Type < имя типа >= set of < имя базового типа >; Var < идентификатор. >:< имя типа >; |
Рассмотрите примеры описаний множеств:
| Type SetByte = set of byte; SetChisla = set of 10 .. 20; Symbol = set of char; Month = (January, February, March, April, May, June, July, August, September, October, November, December); Season = set of Month; Var Letter, Digits, Sign : Symbol; Winter, Spring, Summer, Autumn, Vacation, WarmSeason : Season; Index : SetChisla=[12, 15, 17]; Operation : set of (Plus, Minus, Mult, Divid); Param : set of 0..9=[0, 2, 4, 6, 8]; |
Для переменных типа множества в памяти отводится по 1 биту под каждое возможное значение базового типа. Так, под переменные Letter, Digits, Sign будет отведено по 256/8=32 байта. Для переменной Winter, базовый тип которой (Month) имеет 12 элементов, необходимо 2 байта, причем второй используется только наполовину. Если множество содержит какой-то элемент, то связанный с ним бит имеет значение 1, если нет — 0. Для того, чтобы дать переменной множества какое-то значение, используют либо конструктор множества — перечисление элементов множества через запятую в квадратных скобках:
| Sign:=[‘+’, ‘-‘]; Spring:=[March, April, May]; b:=[ ‘k’, ‘l’, ‘d’ ] |
либо определение через диапазон. В этом случае в множество включены все элементы диапазона.
| Digits:=[‘0’..’9′]; WarmSeason := [May .. September]; |
Обратите внимание, что в определении множества Digits использованы символы в таблице ASCII-кодов, а не целые числа. Обе формы конструирования могут сочетаться:
| Vacation:=[January, February, June .. August]; |
В программах множества часто используются как константы, в этом случае их можно определить следующим образом:
| Const YesOrNo = [‘Y’, ‘y’, ‘N’, ‘n’]; Const Const |
Объединение множеств (+)
Определение. Объединением двух множеств называется третье множество, включающее все элементы, которые принадлежат хотя бы одному из множеств-операндов, при этом каждый элемент входит в объединение множеств только один раз. Объединение множеств записывается как операция сложения.
| Type Symbol = set of char; Var SmallLatinLetter, CapitalLatinLetter, LatinLetter : Symbol; Begin . . . . . . SmallLatinLetter :=[‘a’..’z’]; CapitalLatinLetter := [‘A’..’Z’]; LatinLetter := SmallLatinLetter+CapitalLatinLetter; . . . . . . End. |
В операции объединения множеств могут участвовать и отдельные элементы множества. Например, допустима следующая запись, где два элемента и множество объединяются в новое множество:
| WarmSeason := May+Summer+September; |
или другая запись
которую можно применить для организации множества в цикле, если заменить множество [‘c’] переменной Sym того же типа, что и множество B, и считывать с клавиатуры данные в переменную Sym, объединяя ее затем с множеством В.
Разность множеств (-)
Определение. Разностью двух множеств является третье множество, которое содержит все элементы 1-го множества, не входящие во 2-е множество.
Если в вычитаемом множестве есть элементы, отсутствующие в уменьшаемом, они не влияют на результат.
| Summer := WarmSeason-Spring-Autumn; Summer := WarmSeason-May-September; |
Модуль System содержит процедуры для включения элемента в множество
| Include(Var S : set of T; Element : T); |
и исключения из множества
| Exclude(Var S : set of T; Element : T); |
где S — множество элементов типа Т, а Element — включаемый (или исключаемый) элемент. Эти функции отличаются от операций объединения и вычитания множеств только тем, что генерируют более эффективный код.
Пересечение множеств
Определение. Пересечением множеств называется множество, содержащее все элементы, одновременно входящие в оба множества-операнда. Операция обозначается знаком умножения.
| Summer := WarmSeason*Vacation; |
Теоретический материал (Паскаль)
Множественный тип данных. Множество. Элемент множества. Способы задания множества. Объединение множеств. Разность множеств. Пересечение множеств
Множественный тип данных напоминает перечислимый тип данных. Вместе с тем, множество — набор элементов, не организованных в порядке следования. В математике множество — любая совокупность элементов произвольной природы. Понятие множества в программировании значительно уже математического понятия. Определение. Под множеством в Паскале понимается конечная совокупность элементов, принадлежащих некоторому базовому типу. В качестве базовых типов могут использоваться: перечислимые типы данных, символьный и байтовый типы или диапазонные типы на их основе. Такие ограничения связаны с формой представления множества в языке и объясняются тем, что функция Ord для элементов используемого базового типа должна быть в пределах от 0 до 255. Множество имеет зарезервированное слово set of и вводится следующим описанием
| Type < имя типа >= set of < имя базового типа >; Var < идентификатор. >:< имя типа >; |
Рассмотрите примеры описаний множеств:
| Type SetByte = set of byte; SetChisla = set of 10 .. 20; Symbol = set of char; Month = (January, February, March, April, May, June, July, August, September, October, November, December); Season = set of Month; Var Letter, Digits, Sign : Symbol; Winter, Spring, Summer, Autumn, Vacation, WarmSeason : Season; Index : SetChisla=[12, 15, 17]; Operation : set of (Plus, Minus, Mult, Divid); Param : set of 0..9=[0, 2, 4, 6, 8]; |
Для переменных типа множества в памяти отводится по 1 биту под каждое возможное значение базового типа. Так, под переменные Letter, Digits, Sign будет отведено по 256/8=32 байта. Для переменной Winter, базовый тип которой (Month) имеет 12 элементов, необходимо 2 байта, причем второй используется только наполовину. Если множество содержит какой-то элемент, то связанный с ним бит имеет значение 1, если нет — 0. Для того, чтобы дать переменной множества какое-то значение, используют либо конструктор множества — перечисление элементов множества через запятую в квадратных скобках:
| Sign:=[‘+’, ‘-‘]; Spring:=[March, April, May]; b:=[ ‘k’, ‘l’, ‘d’ ] |
либо определение через диапазон. В этом случае в множество включены все элементы диапазона.
| Digits:=[‘0’..’9′]; WarmSeason := [May .. September]; |
Обратите внимание, что в определении множества Digits использованы символы в таблице ASCII-кодов, а не целые числа. Обе формы конструирования могут сочетаться:
| Vacation:=[January, February, June .. August]; |
В программах множества часто используются как константы, в этом случае их можно определить следующим образом:
| Const YesOrNo = [‘Y’, ‘y’, ‘N’, ‘n’]; Const Const |
Объединение множеств (+)
Определение. Объединением двух множеств называется третье множество, включающее все элементы, которые принадлежат хотя бы одному из множеств-операндов, при этом каждый элемент входит в объединение множеств только один раз. Объединение множеств записывается как операция сложения.
| Type Symbol = set of char; Var SmallLatinLetter, CapitalLatinLetter, LatinLetter : Symbol; Begin . . . . . . SmallLatinLetter :=[‘a’..’z’]; CapitalLatinLetter := [‘A’..’Z’]; LatinLetter := SmallLatinLetter+CapitalLatinLetter; . . . . . . End. |
В операции объединения множеств могут участвовать и отдельные элементы множества. Например, допустима следующая запись, где два элемента и множество объединяются в новое множество:
| WarmSeason := May+Summer+September; |
или другая запись
которую можно применить для организации множества в цикле, если заменить множество [‘c’] переменной Sym того же типа, что и множество B, и считывать с клавиатуры данные в переменную Sym, объединяя ее затем с множеством В.
Разность множеств (-)
Определение. Разностью двух множеств является третье множество, которое содержит все элементы 1-го множества, не входящие во 2-е множество.
Если в вычитаемом множестве есть элементы, отсутствующие в уменьшаемом, они не влияют на результат.
| Summer := WarmSeason-Spring-Autumn; Summer := WarmSeason-May-September; |
Модуль System содержит процедуры для включения элемента в множество
| Include(Var S : set of T; Element : T); |
и исключения из множества
| Exclude(Var S : set of T; Element : T); |
где S — множество элементов типа Т, а Element — включаемый (или исключаемый) элемент. Эти функции отличаются от операций объединения и вычитания множеств только тем, что генерируют более эффективный код.
Пересечение множеств
Определение. Пересечением множеств называется множество, содержащее все элементы, одновременно входящие в оба множества-операнда. Операция обозначается знаком умножения.
| Summer := WarmSeason*Vacation; |
Логические операции над множествами: проверка принадлежности элемента множеству, проверка включения элемента в множество, сравнение множеств
Определение. Множества считаются равными, если все элементы, содержащиеся в одном множестве, присутствуют в другом, и наоборот. В соответствии с этим правилом определяется результат операций сравнения «=» и «<>«. Например,
| If WarmSeason*Vacation=Summer Then Writeln (‘Правильно’); |
Задание. Сравните множества М1 и М2, пользуясь рисунками.
Проверка включения
Определение. Одно множество считается входящим в другое, если все элементы первого множества содержатся во втором, при этом обратное в общем случае может быть несправедливо. Операции проверки вхождения одного множества в другое записываются как » =»
| if S1 then writeln (‘S1 входит в S2’); if S1>=S2 then writeln (‘S2 входит в S1’); |
Задание. Подумайте, что напечатает оператор Write в каждом из случаев: 1.
| if Vacation>=Summer then writeln (‘Правильно’) else writeln (‘Неправильно’); |
| if Vacation then writeln (‘Правильно’) else writeln (‘Неправильно’); |
Проверка принадлежности
Операция проверки принадлежности элемента множеству записывается с использованием оператора in. Например, выражение
| May in WarmSeason |
имеет значение True. Использование множеств и операции in позволяет, в частности, сделать эффективнее проверку правильности вводимых символов. Например, для проверки допустимости введенного символа можно использовать следующее условие:
| (Reply=’y’) or (Reply=’Y’) or (Reply=’n’) or (Reply=’N’) |
Но если ввести множество
| Const AllowSymbol : set of char = [‘Y’, ‘y’, ‘N’, ‘n’]; |
проверяемое условие можно записать в более компактной форме:
| Reply in AllowSymbol |
Задание. Наберите рассмотренную программу, откомпилируйте ее. Проверьте работу программы, исполняя ее по шагам и наблюдая текущие значения переменных i, X, M в окне просмотра. Попробуйте задать значения числа большие 50, повторно задавать одинаковые значения Х и анализируйте значения множества М. Дополните программу выводом на экран содержимого полученного множества. Откомпилируйте программу.
Примеры решения задач на применение множеств
Пример 1. Описать множества гласных и согласных букв русского языка, определить количество гласных и согласных букв в предложении, введенном с клавиатуры. Зададим тип Letters — множество букв русского языка, затем опишем переменные этого типа: Glasn — множество гласных букв, Sogl — множество согласных букв. Вводимое с клавиатуры предложение опишем переменной Text типа String. Для указания номера символа в строке Text применим переменную i типа byte. Для подсчета количества гласных и согласных букв опишем переменные G и S. Проверку принадлежности символов, составляющих предложение, множеству гласных или согласных букв русского языка организуем с использованием оператора цикла For. Параметр цикла i, изменяясь от 1 до значения длины предложения, будет указывать порядковый номер символа в предложении. Принадлежность очередного символа предложения множеству гласных или согласных букв проверим с помощью операции in. Если выполняется условие Text[i] in Sogl, тогда увеличивается на 1 счетчик S. Если выполняется условие Text[i] in Glasn, тогда увеличивается на 1 счетчик G. Если не выполняется ни первое, ни второе условие, значит, очередной символ в предложении не является гласной или согласной буквой русского языка. Теперь рассмотрите текст программы:
| Program GlasnSogl; Type Letters = set of ‘A’..’я’; Var Glasn, Sogl : Letters; Text : String; i, G, S : byte; Begin Glasn := [‘A’, ‘а’, ‘Е’, ‘е’, ‘И’, ‘и’, ‘О’, ‘о’, ‘У’, ‘у’, ‘ы’,’Э’, ‘э’, ‘Ю’, ‘ю’, ‘Я’, ‘я’, ‘Ё’, ‘ё’]; Sogl := [‘Б’..’Д’, ‘б’..’д’, ‘Ж’, ‘ж’, ‘З’, ‘з’, ‘К’..’Н’, ‘к’..’н’, ‘П’..’Т’, ‘п’..’т’, ‘Ф’..’Щ’, ‘ф’..’щ’, ‘ь’, ‘ъ’]; Write(‘Введите предложение ‘); Readln(Text); G := 0; S := 0; For i := 1 to Length(Text) do Begin If Text[i] in Glasn Then G := G+1; If Text[i] in Sogl Then S := S+1; End; Write(‘В предложении » ‘, Text, ‘ » ‘, G, ‘ гласных и ‘, S, ‘ согласных букв’); End. |
Задание. Усовершенствуйте программу, дополните комментарием. Если у Вас возникла идея решения этой задачи с помощью другого алгоритма, — дерзайте. Пример 2. Поиск простых чисел с помощью решета Эратосфена в числовом промежутке [1 .. N]. В теме «Целочисленная арифметика» Вы решали задачи на поиск простых чисел в заданном диапазоне различными способами. Здесь мы рассмотрим ту же задачу, но применим для ее решения знания, полученные при изучении темы «Множества». Примечание. Вспомним, что простым числом называется число, не имеющее делителей, кроме единицы и самого себя. Идея метода «решета Эратосфена» заключается в следующем: сформируем множество М, в которое поместим все числа заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4, и так далее до целой части числа [N/2], кроме самих этих чисел. После такого «просеивания» в множестве М останутся только простые числа. Рассмотрите вариант решения этой задачи.
| Program Resheto; Var M : set of byte; i, k, N : Integer; Begin Writeln(‘Введите размер промежутка (до 255) ‘); Readln(N); M := [2..N]; For k := 2 to N div 2 do For i := 2 to N do If (i mod k=0) and (i<>k) Then M := M-[i]; For i := 1 to N do If i in M Then Write(i:3); Readln; End. |
- Как сформировано множество М?
- Как организован просмотр элементов этого множества?
- Как организован просмотр делителей?
- Как удаляется элемент множества?
- Как организован вывод «просеянного» множества?
Если Вы внимательно рассмотрели решение этой задачи и правильно ответили на вопросы, Вы должны были заметить, что алгоритм решения задачи можно улучшить.
Задание. Улучшите алгоритм решения предложенной задачи. Протестируйте программу и дополните ее комментариями.
Примечание. Если Вы затрудняетесь при выполнении задания, то вот Вам подсказки:
-
Например, вы знаете, что если из множества М удалены все элементы, делящиеся на 2, то нет смысла проверять, делятся ли оставшиеся числа на 4, 6, 8, 10, и т.д.
Пример 3. Разгадывание ребусов.
Каждая буква — это цифра, разным буквам соответствуют разные цифры. Необходимо заменить буквы цифрами так, чтобы получилось верное равенство. Найти все решения. Для решения этой задачи используется метод перебора с возвратом. Используем множество S1 для хранения цифр слова МУХА, причем будем вносить в него цифры последовательно, учитывая уже внесенные цифры. Начальное значение S1 — пустое множество. После выбора всех цифр первого слова создаем его числовой эквивалент и числовой образ слова СЛОН. Выделяем цифры СЛОНа (множество S2), и если слова состоят из разных цифр (то есть пересечение S1 и S2 пустое), и все цифры СЛОНа разные, то выводим решение на экран. Если же нет, то идет возврат — удаляем из множества S1 последнюю внесенную цифру и пытаемся выбрать еще одно значение. Таким образом, мы перебираем все возможные варианты и выводим на экран только те, которые удовлетворяют равенству.
Заметим, что значение буквы М в слове МУХА может иметь значения от 1 до 4, а буква А в этом же слове не может быть равна 0.
Рассмотрите решение задачи.
| Program Rebus; Type MN = set of 0..9; Var digit, m, u, h, a : 0..9; i, n1, n2 : Integer; S1, S2 : MN; f : boolean; Procedure Print(x, y : Integer); Begin write(x); write(‘ + ‘); write(x); write(‘ = ‘); writeln(y); writeln; End; Begin S1 := [ ]; for m := 1 to 4 do begin S1 := S1+[m]; for u := 0 to 9 do if Not(u in S1) then begin S1 := S1+[u]; for h := 0 to 9 do if Not (h in S1) then begin S1 := S1+[h]; for a := 1 to 9 do if Not (a in S1) then begin S1 := S1+[a]; n1 := 1000*m+100*u+10*h+a; n2 := 2*n1; f := true; S2 := [ ]; for i := 1 to 4 do begin digit := n2 mod 10; n2 := n2 div 10; f := f and not (digit in s2); S2 := [digit] + S2; end; if (S1*S2=[ ]) and f then Print (n1, 2 * n1); S1 := S1-[a]; end; S1 := S1-[h]; end; S1 := S1-[u]; end; S1 := S1-[m]; end; Readln; End. |
Задание. Решите один из ребусов:
- П Ч Ё Л К А x 7 = ЖЖЖЖЖЖ
- ТОРГ x Г = ГРОТ
- ЛАДЬЯ+ЛАДЬЯ = ФЕРЗЬ
- М3 = КУБ
- СМ3 = КУБИК
- МАТЕ * М = АТИКА
- ПРОП * О = РЦИЯ
- ПРОП : О = РЦИЯ
- (М + О + С +К + В + А)4 = МОСКВА
- ВЕТКА + ВЕТКА = ДЕРЕВО
- САР = АТОВ
- ПЛОМБА * 5 = АПЛОМБ
- НИКЕЛЬ * 6 = ЕЛЬНИК
- КВАНТ * 30 = ЖУРНАЛ
- КАПЛЯ + КАПЛЯ + КАПЛЯ + = ОЗЕРКО
- СОРОК * 5 = ДВЕСТИ
- SIX * TWO = TWELVE
- ДВЕСТИ * 5 = ТЫСЯЧА
- НАТАША + ТОНЯ = СЁСТРЫ
- БРА2 = БОМДОР
Пример 4. Рассмотрите специальную процедуру ввода положительных целых чисел, которая запрещает набор иных символов, кроме цифр, и ограничивает число используемых символов.
| Procedure ReadWord(Var Result : Word; x, y, MaxLength : byte); Const ValidSymbol : set of char=[‘0’..’9′,#8,#13]; Var Str : string; Code : integer; Key : char; Begin GoToXY(x, y); Str := »; repeat repeat |
В заголовке процедуры Result — возвращаемое число; MaxLength — максимальное число цифр в записи числа; х, у — координаты начальной позиции вывода. Процедура формирует текстовую строку Str, состоящую из цифр. При нажатии клавиши Enter строка преобразуется в целочисленную переменную.
В начале программы курсор направляется в заданную точку, и текстовой строке присваивается пустое значение. Далее начинается бесконечный цикл, заданный оператором Repeat . Until False. Выход из цикла происходит вместе с выходом из процедуры по команде Exit. «Бесконечность» цикла обеспечивает произвольное число повторов и исправлений при вводе числа.
Процедура реагирует только на нажатие цифровых клавиш, клавиш Enter и BackSpace. Назначение клавиш — традиционное: Enter используется для завершения процедуры, BackSpace — для стирания последнего введенного символа.
| repeat Key := ReadKey until Key in ValidSymbol; |
проверяет вводимые символы на допустимость. Множество допустимых символов ValidSymbol определено в процедуре как константа, оно включает цифровые символы и символы, соответствующие клавишам Enter и BackSpace. Первая имеет символьный код #13, вторая — #8.
Далее оператор Case производит выбор одного из трех направлений — обработка нажатой цифры, обработка клавиши BackSpace или обработка клавиши Enter. При нажатой цифре сначала проверяют, не достигло ли число цифр максимального значения. Число цифр определяется функцией Length, аргумент которой — редактируемая строка. Если длина уже достигла максимального значения, выдается звуковой сигнал. Если длина вводимой строки меньше максимальной, то в строку дописывается символ, и он же выводится на экран процедурой Write.
При нажатии клавиши BackSpace должен быть стерт последний введенный символ. Вначале производится проверка, есть ли в строке символы. Если строка пуста, подается звуковой сигнал, если нет — начинается удаление символа. Для этого строка уменьшается на один элемент процедурой Delete, курсор возвращается назад на одну позицию, на место стираемой цифры записывается символ пробела, затем курсор снова возвращается на позицию назад. Возврат курсора обеспечивается оператором GoToXY(WhereX-1, WhereY), который использует функции WhereX и WhereY для определения текущего положения курсора и уменьшает координату х на 1.
После нажатия Enter строка преобразуется в целочисленную переменную процедурой Val, и происходит выход из процедуры ReadWord по команде Exit.
В этой процедуре показано, что ввод данных и другие процедуры, связанные с работой оператора, должны, как правило, иметь защиту от ошибочных действий. В данном примере это обеспечивается тем, что процедура блокирует неправильные нажатия клавиш и ограничивает длину строки.
Поскольку все проверки усложняют программу, требование защиты от возможных ошибок программиста не является обязательным. Вопрос в том — надеется ли программист на свою аккуратность при использовании собственных процедур.
Задание*. Составьте программу для проверки входных данных другого типа.