рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Множества

Множества - раздел Транспорт, От автора Понятие Множества В Паскале Очень Близко К Математиче...

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

Set Of тип

где тип - базовый для этого множества тип, т.е. тип элементов множества. Базовый тип должен быть порядковым типом мощностью не более 256 (т.е. допускающим не более 256 различных значений), причем порядковые номера (вспомним функцию Ord) наименьшего и наибольшего значений должны лежать на отрезке [0,255]. Таким образом, базовым типом для множества могут быть: тип Char, тип Boolean, типByte и все производные от Byte интервальные типы. Размер множества можно определить по формуле размер= (мощность-1)Div 8+1, т.е. множества - довольно компактные объекты, самое большое множество имеет размер 32 байта. Неименованные константы типа “множество” записываются в виде:

[ подмножество , подмножество, ...]

где подмножество - это либо отдельное значение, либо диапазон, диапазон записывается как начальное значение.. конечное значение . Любое из значений может быть как константой, так и выражением соответствующего типа. Запишем, например, константу-множество, содержащую числа 0, 1, 2, 3, 4, 8, 12, 13, 14, 15, 16, 22 : [0,1,2,3,4,6,12,13,14,15,16,22],или [0..4,6,12..16,22], или [0..2,3..4,6..6,12,13..16,22],или[22,13..15,1..6,0,12,16];все эти константы полностью эквивалентны, порядок записи элементов совершенно безразличен. Допускаются пустые множества, они записываются так [ ]. Опишем несколько переменных и типизированных констант:

 

Type MySet = Set Of 0..99;

Var a : Set Of Char;

b : MySet;

Const c : MySet = [];

d : Set Of Char = ['А'..'Я'];

e : Set Of Boolean = [False];

 

К множествам применимы следующие операции :

- множеству можно присвоить множество того же типа;

- операция “объединение” +

- операция “дополнение” -

- операция “пересечение” *

- операция “эквивалентность” =

- операция “неэквивалентность” <>

- операция “включение” <= и >=

Последние три операции дают значение логического типа - True или False. Пусть множествоA=[1..20] , B=[2..9,15..20], C=[3..22], тогда A+B=[1..20], A+C=[1..22], A-C=[1,2], C-A=[21,22], A*B=[1..20], A*C=[3..20], B*C=[3..9,15..20], A=B =False , A<>C =True , B<=A =True, A>=C =False .

Существует еще одна операция, связанная с множествами, - операция In (“принадлежит”), она применяется к скалярной величине и множеству

выражение In множество

Здесь выражение - любое выражение базового для данного множества типа, результат операции - True, если такой элемент есть в множестве, и False в противном случае. Для множеств определены две стандартные процедуры:

Include( множество , выражение )

Exclude( множество , выражение )

Процедура Include добавляет элемент, равный значению выражения в множество, а процедура Exclude удаляет такой элемент из множества.

Теперь, когда мы знаем все возможности множеств, запишем программу, находящую все простые числа на отрезке [1,255] :

 

{программа использует алгоритм "решето Эратосфена"}

Type NumSet = Set Of 1..255;

Const N : NumSet=[2..255]; { исключили 1 как не являющуюся простым числом }

Var

MaxDivider,d : Byte;

k : Word;

Begin

MaxDivider:=Round(Sqrt(255));

d:=2;

While d<=MaxDivider Do Begin

k:=2*d;

While k<=255 Do Begin

Exclude(N,k);

Inc(k,d);

End;

Inc(d);

End;

WriteLn('Простые числа :');

For k:=1 To 255 Do

If k In N Then WriteLn(k:4);

End.

 

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

 

Type Letters = Set Of Char;

Const

Lat = ['a'..'z','A'..'Z'];

Rus = ['а'..'п','р'..'я','А'..'Я'];

Var c : Char;

Const

RSum : Word=0;

LSum : Word=0;

Begin

Write('Введите массив символов, затем нажмите Enter ');

Repeat

Read(c);

If c In Lat Then Inc(LSum)

Else

If c In Rus Then Inc(RSum);

Until c=#13;

WriteLn('Латинских букв ',LSum,' русских букв ',RSum);

End.

 

Обратите внимание, что в этом алгоритме нет необходимости заранее знать, сколько символов содержится в массиве (более того, в программе никакого массива и нет!), достаточно лишь помнить, что клавиша Enter генерирует символы #13 и #10.

Решим еще одну, более интересную задачу, в которой использование множества исключительно эффективно: определить, есть ли в последовательности символов хотя бы два одинаковых.

 

Type CharSet = Set Of Char;

Var

M : CharSet;

c : Char;

Begin

M:=[];

While Not EoLn Do Begin

Read(c);

If c In M Then Begin

WriteLn(‘Есть два символа ‘,c);

Halt(0);

End;

Include(M,c);

End;

WriteLn(‘Нет одинаковых символов’);

End.

– Конец работы –

Эта тема принадлежит разделу:

От автора

B r... Теперь мы можем присвоить переменным их значения...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Множества

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

От автора
Первое издание этой книги вышло в свет в 1997 году и довольно быстро стало библиографической редкостью. Автор несколько неожиданно для себя обнаружил, что книга пользуется черезвычайно высоким спро

Round(x) - округленное до целого вещественное число, преобразованное к типуLongInt
6. Sqr(x) - квадрат числа 7. Sqrt(x) - квадратный корень 8. Exp(x) - экспонента 9. Ln

Символьный тип данных
Для хранения символьной информации в Паскале предусмотрен специальный тип данных Char. Допустимы переменные, нетипизированные и типизированные константы такого типа. Данные типа

Caseвыражение Of
список значений : оператор/блок .................................. список значений: оператор/блок

Процедуры и функции. Сфера действия описаний
В языке Паскаль (как вы уже поняли из предыдущего материала) существуют понятия процедуры и функции. Процедуры и функции можно определить как замкнут

Открытые массивы и нетипизированные параметры
Из предыдущего раздела мы узнали, что параметры подпрограмм описываются как [Var] имя : имя типа , это правда, но не вся правда - существует еще два

Графические средства языка Паскаль
Монитор персонального компьютера может работать в двух режимах - текстовом и графическом. Все, что мы делали до сих пор, мы делали в текстовом режиме. Текстовый экран содержит 2000 знако

Особенности вещественных вычислений
В отличие от целочисленных выражений, которые всегда вычисляются точно, вещественные выражения дают приближенный результат и вещественные переменные содержат приближенные значения. Это обстоятельст

Case тип Of
константа 1 : (описание поля); константа 2 : (описание поля); .....................

Модуль Crt
Crt - еще один стандартный модуль Паскаля, в котором содержатся разнообразные средства консольного ввода-вывода (то есть ввода с клавиатуры и вывода на текстовый экран). Процедуры

Var TextAttr : Byte
В ней содержится текущий цвет фона и цвет символов, используемые при выводе на экран процедурами Write иWriteLn. Изменив эту переменную, вы задаете новый

Другие средства обработки файлов и модуль DOS
Для того чтобы определить, есть ли на диске файл с заданным именем, удобно использовать уже известную нам стандартную функцию IOResult , которая возвращает ноль при успешном завершении последней оп

Type SearchRec=Record
Fill : Array[1..21] of Byte; Attr : Byte; Time : LongInt; Size : LongInt; Name : Stri

Процедурные типы
Язык Паскаль позволяет использовать в программе данные типа “процедура” или типа “функция”. Такие данные можно передавать как аргументы подпрограмм, можно описывать и использовать массивы процедур

Указатели и динамическая память
Указателями называются переменные и константы, значениями которых являются адреса. Различаются два вида указателей - обобщенные указатели и

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

Открытые строки
  Открытыми строками, или длинными строками, или C-строками, называются символьные последовательности длиной до 65535 символов, ограниченные справа нуль-символ

Использование командной строки и вызов внешних программ
Паскаль позволяет передавать информацию в программу при ее запуске через командную строку. Для этого служат две стандартные функции -ParamCount и ParamStr.

Обработка программных прерываний
Программное прерывание - это ситуация, возникающая, когда дальнейшее выполнение программы невозможно. Например, деление на ноль, переполнение, ошибка Range check error, обращение по неверному адрес

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

Type имя типа=Object
описание полей описание методов End; Поля объектов описываются так же, как поля записей, а описание метода - это заголовок процедуры или функции. Сами методы распол

Рекурсия и динамическое программирование
В этом и всех последующих разделах речь пойдет уже не о языке программирования Паскаль, а о задачах, которые вы можете решать с помощью этого языка, о наиболее интересных и полезных алгоритмах и пр

Рекурсия и стек отложенных заданий
Рекурсивные алгоритмы далеко не всегда неэффективны, как можно подумать, прочитав предыдущий раздел. Во многих задачах рекурсивные процедуры и функции очень полезны, кроме того, они исключительно п

Стеки и очереди
Значение стека как структуры данных в программировании не исчерпывается лишь стеком отложенных заданий. В этом разделе мы решим с помощью стека задачу о вычислении значения арифметического выражени

Комбинаторные алгоритмы
В этом разделе мы рассмотрим три наиболее важные задачи комбинаторики: нахождение всех подмножеств множества из n элементов; нахождение всех выборок по m элементов из n элементов и нахождение всех

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

Упорядоченные бинарные деревья и приоритетные очереди
Упорядоченным бинарным деревом, или бинарным деревом поиска, называют дерево, в любой части которого элементы левого поддерева меньше корневого элеме

Алгоритмы сортировки
В этом разделе мы рассмотрим различные алгоритмы решения задачи сортировки. Задача сортировки ставится следующим образом: дана последовательность записей R1,R

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги