1611678431-0e68e83522cb9d960ac896aa5d90854d (826635), страница 9
Текст из файла (страница 9)
Например, [1, 2, 3] и [3, 2, 1] — это эквивалентные множества.Каждый элемент в множестве учитывается только один раз. Поэтомумножество [1, 2, 3, 4, 2, 3, 4, 5] эквивалентно [1..5].Переменныемножественноготипаописываютсятак:Var <идентификатор> : set of <базовый тип>;Например:Var A, D : Set Of Byte;B : Set Of 'a'..'z';C : Set Of Boolean;Нельзя вводить значения во множественную переменную процедуройввода и выводить процедурой вывода.Множественная переменная может получить конкретное значение только врезультатевыполненияоператораприсваивания:<множественная переменная> := <множественное выражение>;Например:A : = [50, 100, 150, 200];B : = ['m', 'n', 'k']; C : = [True, False];D : = A;Кроме того, выражения могут включать в себя операции над множествами.Операции над множествамиОбъединением двух множеств A и B называется множество, состоящее изэлементов, входящих хотя бы в одно из множеств A или B.
Знак операцииобъединения в Паскале «+».Примеры:1) [1, 2, 3, 4] + [3, 4, 5, 6] => [1, 2, 3, 4, 5, 6]2) []+[‘a’..’z’]+[‘A’..’E’, ‘k’] => [‘A’..’E’, ‘a’..’z’]3) [5<4, true and false] + [true] => [false, true]Пересечением двух множеств A и B называется множество, состоящее изэлементов, одновременно входящих во множество A и во множество B.Знак операции пересечения в Паскале «*»Примеры:1) [1, 2, 3, 4] * [3, 4, 5, 6] => [3, 4]2) [‘a’..’z’]*[‘A’..’E’, ‘k’] => [‘k’]3) [5<4, true and false] * [true] => []Разностью двух множеств A и B называется множество, состоящее изэлементов множества A, не входящих во множество B.Примеры:1a)1b)2a)2b)3a)3b)[1, 2, 3, 4] - [3, 4, 5, 6] => [1, 2][3, 4, 5, 6] - [1, 2, 3, 4] => [5, 6][‘a’..’z’]-[‘A’..’E’, ‘k’] => [‘a’..’j’, ‘i’..’z’][‘A’..’E’, ‘k’] - [‘a’..’z’] => [‘A’..’E’][5<4, true and false] - [true] => [false][true] - [5<4, true and false] => [true]Операция вхождения.
Это операция, устанавливающая связь междумножеством и скалярной величиной, тип которой совпадает с базовым типоммножества. Если x — такая скалярная величина, а M — множество, то операциявхождения записывается так: x in M.Результат — логическая величина true, если значение x входит вмножество M, и false — в противном случае.Например, 4 in [3, 4, 7, 9] –– true, 5 in [3, 4, 7, 9] –– false.Используя данную операцию, можно не только работать с элементамимножества, но и, даже если в решении задачи явно не используются множества,некоторые логические выражения можно записать более лаконично.1) Натуральное число n является двухзначным.
Вместо выражения (n >=10) and (n <=99) можно записать n in [10..99].2) Символ c является русской буквой. Вместо выражения (c >= ‘А’) and (c<= ‘Я’) or (c>=‘а’) and (c<=‘п’) or (c>=‘р’) and (c<=‘я’) пишем c in [‘А’.. ‘Я’,‘а’.. ‘п’, ‘р’.. ‘я’] и т.д.Добавить новый элемент в множество можно с использованием операцииобъединения. Например, a:= a+[5] Для этих же целей в Turbo Pascal 7.0предназначена процедура Include:include (M, A) M – множество, A –переменная того же типа, что и элементы множества M. Тот же пример можнозаписать так: Include (a, 5)Исключить элемент из множества можно с помощью операции «разностьмножеств».
Например, a:= a-[5] Для этих же целей в Turbo Pascal 7.0предназначена процедура Exclude:exclude (M, A) M – множество, A –переменная того же типа, что и элементы множества M. Тот же пример можнозаписать так: Exclude (a, 5)Рассмотрим несколько примеров использования множеств при решениизадач.Задача 1. В городе имеется n высших учебных заведений, которыепроизводят закупку компьютерной техники. Есть шесть компьютерных фирм:«Диалог», «Avicom», «Нэта», «Сервер», «Декада», «Dega.ru». Ответить наследующиевопросы:1) в каких фирмах закупка производилась каждым из вузов?2) в каких фирмах закупка производилась хотя бы одним из вузов?3) в каких фирмах ни один из вузов не закупал компьютеры?Решим задачу с использованием множеств.
Для удобства дальнейшихманипуляций в порядке следования занумеруем компьютерные фирмы, начинаяс единицы. Занесём информации о месте закупок компьютеров каждым из вузовв отдельное множество.Ответ на первый вопрос можно получить, выполнив пересечение всехтаких множеств.Ответ на второй вопрос – результат объединения множеств.И, наконец, на последний – разность множества всех фирм и множествафирм, где хотя бы один вуз делал покупки.program ex_set_1;type firma = set of 1..6;v = array[0..20] of firma;const f: array [1..6] of string[10] ='Декада', 'Dega.ru');('Диалог', 'Avicom', 'Нэта', 'Сервер',{процедура ввода информации о закупке компьютеров в очередной фирме}procedure vvod(var a: firma);var i: byte; ans: 0..1;begina:= [];for i := 1 to 6 dobeginWrite('Вуз покупал компьютеры в фирме ', f[i], ' (1 - да, 0 - нет)?'); ReadLn(ans);if ans = 1 then a:=a+[i]end;end;{процедура вывода элементов массива, номера которых содержатся в множестве}procedure Print(a : firma);var i: byte;beginfor i := 1 to 6 doif i in a then write(f[i]:10);writelnend;{Процедура, дающая ответ на первый вопрос}procedure Rez1(a: v; n : byte; var b : firma);var i : byte;beginb := [1..6];for i := 0 to n-1 dob := b * a[i];end;{Процедура, дающая ответ на второй вопрос}procedure Rez2(a: v; n : byte; var b : firma);var i : byte;beginb := [];for i := 0 to n-1 dob := b + a[i];end;var a: v; n, i : byte; c : firma;beginwrite('Сколько вузов делали закупку? ');readln(n);for i := 0 to n-1 do vvod(a[i]);Rez1(a, n, c);writeln('Каждый из вузов закупил компьютеры в фирмах: ');Print(c);Rez2(a, n, c);writeln('Хотя бы один из вузов закупил компьютеры в фирмах: ');Print(c);writeln('Ни один из вузов не закупил компьютеры в фирмах: ');Print([1..6]-c);end.Задача 2.
Сгенерировать n множеств (нумерацию начать с 1). Вывестиэлементы, которые входят во все множества с номерами, кратными трём, но невходят в первое множество.program ex_set_2;type mn = set of byte;v = array[1..30] of mn;{процедура ввода информации в очередное множество}procedure vvod(var a: mn);var i, n, vsp: byte;begina:= [];n := 1 +random(200);for i := 1 to n dobeginvsp:= random(256);a:=a+[vsp]end;end;{процедура вывода элементов множества}procedure Print(a : mn);var i: byte;beginfor i := 0 to 255 doif i in a then write(i:4);writelnend;{Процедура, дающая ответ на вопрос}procedure Rez(a: v; n : byte; var b : mn);var i : byte;beginb := [0..255];i:= 3;while i <= n dobeginb := b * a[i];i := i + 3end;b := b - a[1]end;var a: v; n, i : byte; c : mn;beginrandomize;write('Сколько множеств? ');for i := 1 to n dobegin vvod(a[i]);print (a[i])readln(n);end;Rez(a, n, c);Print(c);end.Задача 3.
Дана строка. Сохранить в ней только первые вхождениясимволов, удалив все остальные.program ex_set_3;var m : set of char;s : string; i : byte;beginwrite('Введите строку: ');readln(s);m :=[];i := 1;while i <= length(s) doif s[i] in m then delete(s, i, 1)else begin m:=m+[s[i]]; i := i + 1 end;writeln(s)end.23. Понятие частичной правильности. Метод промежуточных утверждений для простых Паскальпрограмм2.3.4 Метод промежуточных утвержденийПусть -- некоторая последовательность операторов, аи-- некоторыеутверждения о значениях переменных, используемых в P соответственно вначальном и конечном состояниях выполнения P .аназывается предусловием,-- постусловием дляГоворят, что является частично правильной относительно ее спецификации,заданной в виде утвержденийи(или, что то же самое, обладаетсвойством частичной правильности {}P{}), если для любых начальныхзначений переменных, относительно которых справедливо , выполнениедействия (если оно определено) дает такие конечные значения переменных,для которых истинно утверждение.
Примеры свойств:,,для любыхи.Заметим, что частичная правильность ничего не говорит о завершаемостиТак, например, в последнем свойстве оператор не применим, еслисумма.превышает MaxInt.Свойство правильности программы относительно внешней ее спецификации,заданной в виде утвержденийи, означает справедливость свойствачастичной правильности {}, а такжесвойства завершаемости программы -- нормального завершения выполненияпрограммы на любом начальном состоянии, удовлетворяющемутверждению.Идея метода промежуточных утверждений для доказательства частичнойправильности Паскаль-программ состоит в построении исчисления свойствчастичной правильности программ и их частей, аксиомами в которомвыступают свойства элементарных операторов (операторов присваивания ипустых операторов), а правила вывода связаны с другими конструкциями языкаи позволяют выводить свойства этих конструкций из свойств составляющих егокомпонент или операторов присваивания (как это имеет место для операторовввода-вывода).При этом ход построения доказательства заданного свойства частичнойправильности всей Zonnon-программы (или ее части) может состоять впоследовательном применении правил вывода свойств, сводящих исходноесвойство к некоторым свойствам образующих ее частей -- в конечном счете кгруппе свойств частичной правильности составляющих ее операторовприсваивания, либо в его выводе из свойств операторов присваивания.
Цель -построить вывод заданного свойства частичной правильности. В этомдоказательстве (выводе) могут использоваться также все традиционныеаксиомы и правила вывода соответствующего логического исчисления и тойобласти (например, арифметики), к которой относится задача, решаемаяпрограммой.Семантика пустого оператораоператора: {}{описывается очевидной аксиомой пустого} для любого утвержденияВ соответствии с семантикой оператора присваиванияимеемследующую аксиому оператора присваивания: {любая пара утверждений таких, чтоиз}, гдеи---- утверждение, получающеесяподстановкой выражения вместо вхождения переменнойНапример,справедливы свойства:.Следующие два правила завершают построение исчисления свойств Zonnonпрограмм, использующих лишь уже рассмотренные конструкции языка; вдальнейшем они будут дополнены правилами и для других конструкций.Правило вывода следствий формулируется следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
