К. Йенсен, Н. Вирт - Паскаль - Руководство для пользователя (1109480), страница 12
Текст из файла (страница 12)
Предположим, А и  — множественные выражения одного типа, а е — ординальное выражение базового типа,' 86 Рулоьпдстнп длл пользователе '3','К','1','й','й','О,','Р','О','й', Уене1з := (ч А','Е',' 1','О',О); Сспзепап(з := Ееееегз - Упне1з й44 := [2,3) <= ОрспОе Действия с множествами относительно быстрые и их можно использовать для исключения более сложных проверок.
Например, вместо проверки 11 (С(т = 'А') ог (Сй = 'Е*) ог (Сй = Т) от (Сй = *О') ог н (Сй = ТР) (йеп о можно написать более простую 11 СЬ (п ('А', *Е', Т, 'О', '(Г) (Леп о ргейгаа Сапнег(((при(,Оп(рис); ( Лрограмма 8,1 — Чтение последовательности цифр и преобразование их в целое. Знака нет. ) наг СЬ: Сйаг; 019гйз: зе( а( '0'..'9'; ИиаЬег: 1п(ейег; Ьей1п 0(йтез:= ('О'.. '9') (инициация значения множества ); Оеар(1приЬ, СЬ); ИиаЬег := 0; ьй1!е СЬ гп 0(агез Оа Ьей(п ИиаЬег := йиаЬег ' 10 ь Ога(СЬ) — Огй('0'); йггйе1п(0и(рит, йиаЬег); йеаа(1приЬ, СЬ) епв ( СЬ содержит символ, идущий за целым ) еп4 Дает в качестве результата: 4 43 492 4321 д Множественные типы а9, ргоБгав БеСОрегаС(апа(ОиСриС); ( Программа 8.2 — Пример операций над множествами.
) Суре Оауа = (Иоп, Тие, Иод, Тпи, Ег(, БаС, Бип); Иееп = зеС о1 Раух; иаг Еи11йееп, Иогй, Ггее: Иеей; Оау: Оауа; ргосебиге Спесй(й: Иееа); ( процедуры вводятся в гл. 11 ) иаг 0: Оауе; Ьеа(п !ог 0 := Коп Со Бип бо 11 0 1п й Спел йг(Се(ОисриС, 'х') е1ае Иг1Се(ОосриС, 'о'); Иг)се1п(ОисриС) епо' ( Спеси ); ЬеБ(п йогй:= Ц; Ггее := (); Еи11йеей := (Копь .Бип); Оау := Бас; Ггее:= 10ау) + Егее + )Бип); Спесй(ргее); Иота:= Еи11йеех — Ггее; Спесп(йогй); 11 Ггее <= Еи11йеей Спеп Иг(ее(рисрис, 'О'); 11 Еи11йееИ >= йоге Сйеп Иг(се(ОисриС, 'К'); 11 пеС (йагН >= Егее) Спел Иг(се(ОисриС, ' Ласй'),' 11 (Бас) <= Иота Спел Иг1Се(ОисриС, 'Гогаес СС('); Иг(ее1п(ОиериС) еаза Дает в качестве результата: ооооохх хххххоо ОК Ласп УО Руководство для кольвователл 8.3.
РАЗРАБОТКА ПРОГРАММ Программирование в смысле построения н формулирования алгоритмов, в общем, сложный процесс, требующий владения определеннымн приемами и умения учитывать многие детали. Только в редких случаях здесь существует одно-единственное «хорошее» решение. Обычно перед нами так много решений, что выбор оптимального требует основательного анализа не только возможных алгоритмов и машин, но даже и условий, в которых наиболее часто будет использоваться наша программа. Поэтому конструирование алгоритма должно состоять из последовательности обдумывания, исследования и принятия конструктивных решений. На ранних этапах лучше всего концентрировать внимание на глобальных проблемах и при первом наброске решения не останавливаться на деталях.
По мере продвижения процесса задачу можно разбивать на подзадачи, уделять больше внимания деталям определения задачи н особенностям используемых приемов программирования. Такой подход к программированию часТо называют структурным программированием [4[, нли программированием методом последовательных уточнений [2[. Ниже мы покажем процесс создания алгоритма на примере, взятом у Хоара из [4[. Мы его перескажем, естественно, используя понятия, присущие Паскалю. Нужно найти простые числа, лежащие в диапазоне 2..п, где п ) = 2.
После сравнения различных алгоритмов мы остановимся на «решете Эратосфена», ибо в этом алгоритме не используются ни умножение, ни деление. Сначала опишем алгоритм «словами»: 1. Поместим все числа между 2 и п в «решето». 2. Выберем и вынем из «решета» наименьшее нз оставшихся в нем чисел. 3. Поместим это число среди «простых» чисел.
4. Переберем и вынем из «решета» все числа, кратные данному. 5. Если «решето» не пустое, то повторим шаги 2 — 5. Хотя при выполнении программы в первую очередь проводится инициация переменных, тем не менее при разработке соответствующие операторы пишутся в последнюю очередь. Для того чтобы записать зти действия правильно, требуется исчерпывающее понимание алгоритма. Если нужно сохранять работоспособность программы, то при каждой ее модификации операторы инициации придется корректировать. К сожалению, даже коррекции не всегда достаточно. Для представления как «решета», так и множества простых чисел Хоар использует множества с элементами от 2 до п. Ниже д !Иназееетеенеие тиль 9! дается слегка видоизмененный «набросок» его программы: ргойгав Рг!ве!; ( П рограмма 8.3 — Использование для решета Эратосфена множеств ) сопзС И = 10000; Суре Раз!С!че = 1..йах1пС; чаг 5!ече, Рг!вез зеС о! 2..И; йехСРг[ве, Мч!С!р!е: Роз!С!че„ Ьей!и ( инициация ) 3!ече:= [2..И); Рглез := [); йехСРгппе ;= 2; гереаС (поиск очередного простого ] чЬ!1е поС [йехСРгле !и 31ече) 6о йехСРг!ве:= 5чсс[йехСРгле); Рг!вез := Ргхвез + [МехСРгле); Мч1С!р!е:= ИехСРгле; иЬ11е Ич1С!Р1е <= И 6о (исключение) Ьей!п 5!ече:= 3!ече — [Ич1С!р1е); .
Ич1С1р!е:= Ич1С!р!е + йехСРг1ве; еп6 чпС!1 5[ече = Ц еп6 . В качестве упражнения Хоар предлагает переписать программу так, чтобьг в множествах были только нечетные числа. Ниже приводится решение; обратите внимание на его связь с первым решением. ргойгав Рг1ве2; (Программа 8.4 — Использование для решета Эратосфена множеств; только нечетные числа.) сопзС И Ф 5000 ( й' = И 6!ч 2 ); Фуре Роз[С!че = 1..Мах1пС; 92 Руководство дол лохозоеоге»е хаг 3!ене, Рг!вез: зес а! 2..й; йехЬРг!ве, Ма!$!р!е, йе|Рг1|е: Раз!С!уе; Ьей!л ( инициация ) йене := [2..й]; Рг!вез := П; йех(Рг!ве := 2; гереет ( поиск очередного простого )' иь! 1е па+ (йехсРг!ве (п Я(еие) аа йехЬРг!ве := Басс(йехЬРг1|е); Рг1|ез:= Рг!|ез + [йехЬРг!ве); йенРг!ве := 2 о йехЬРг!ве — 1; Ма11!Р1е := йехЬРг!ве; кй1:е Ма1С!Р!е =- й аа ( исключение) Ьее!а о!еуе:= о!еуе — [Иа1$!Р1е); Ми!1!Р1е:= М|1$!Р1е + йехЬРг!ве; епа апЬ!1 Я!еуе = [) епа' .
Желательно, чтобы все основные операции с множествами выполнялись достаточно быстро. Многие создатели трансляторов ограничивают максимальный размер множеств размером слона соответствуюшей машины. В этом случае каждый элемент множества представляется одним разрядом -(О означает отсутствие, а 1— присутствие элемента в множестве.) Поэтому большинство реализаций не будет работать с множеством из !ОООО элементов. Это обстоятельство заставляет в программе 8.5 модифицировать представление данных. Большое множество можно представить как массив меньших множеств, каждое из которых «влезает» в несколько слов (количество слов зависит от реализации).
Новая программа основывается как на абстрактной модели уже на втором наброске. В ней и «решето» ($!ече), и простые числа (РНгпез) переопределяются как массивы множеств, а )Х[ех( представляется записью. ргайгев Рг!веЗ(0аараЬ); ( Программе 8.5 — Поиск простык чисел в диапазоне 3 .. 10000 с помощью решете, содержащею нечетные числе из этого диапазона.1 8. Множественные тины 93 сопзс ЗеСЗ(хе = !28 ( зависит от реализации ИахЕ1евепс = 127; Зесрагсз = 39 ( = 10000 6!ч Зесз(ге 6!ч 2 [; Суре Иаспга1 = О..Мах1пС; чаг З(ече, Рг[вез: аггау [О..ЗеСРагсз] о( зеС о1 О..йахЕ1евепС; йехСРг(ве: гесог6 РагС, Е1евепС: йасега1 еп6; Мо111р!е, ИеиРг1ве: Иасчга!; Р, й, Соопс: йаСчга1; ЕврСу: Воо!еап; ЬеВ[п ( инициация ) (ог Р := О Со ЗесрагСз 6о ЬеВ!и З[ече[Р] := [О ..
МахЕ!евепЦ; Рг!вез[Р] := Ц еп6; ' З(ече[0] := З1ече[0] — (0]; Еврсу := Га!зе; йехСРг!ве.рагС := 0; йехСРг[ве.Е1евепС := 1; и!СЬ йехСРг1ве 6о гереас (поиск очередного простого ] ий11е пос (Е1евепС Сп 3!ече["РагЦ) 6о Е1евепС := Зосс(Е1евепС); Рг[вез[РагЦ := Ргйвеь[РагЦ + [Е!евепЦ; йеиРг1ве := 2 " Е!евепС + 1; Ип)С[р1е := Е!евепС; Р: — РагС; иЬ11е Р <= ЗеСРагСз 6о ( е1ив!пасе ( ЬеВ[п З[ече[Р] := З!ече[Р] — [Ич111р1е]; Р:= Р + Рагс * 2; Мч111р1е := Ич111р1е + йеиРг!ве; иЬС 1е Ич1С1р1е > МахЕ!евепС 6о Ье01п Р:= Р + 1; Мо111р1е := Мч1С[р1е — ЗеСЗЕае еп6 Рв Руководство олл пользователя 0; О Ьо ЯеЬРагае оо := 0 Ьо ИахЕ)евепЬ до й )п Рг)веа[Р) ЬЬеп Ье8)п Иг)ее(Оиерио, 2 ' й + 1 + Р ' Бе($)ае ' 2:6); Соипа := Соипо + 1) )( (Соиле вод 8) = 0 Ьпеп Иг)ее)п(ОиериЬ) епд СоипС := (ог Р := )ог И )Р епд.
Дает в качестве результата: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 9871 9883 9887 9901 9907 9923 9929 9931 9941 9949 9967 9973 10007 10009 10037 10039 . 10061 10067 10069 10079 10091 10093 )0099 10103 10111 10133 10139 10141 10151 10159 10)63 10169 епо; т( 3)еуе[РагЬ) = П Ьпеп Ье8)п Евреу := Тгие; Е)евеп$ := 0 епе; вЬ)1е Евр)у апд (Раг) < ЗейРагеа) бо Ье8)п Раг) := Рагй + 1; Евр)у := 3)еме[РагЬ) = [] епо ипЬ)1 Евреу; ФАЙЛОВЪ|Е ТИПЫ Во многих случаях наипростейшим методом введения структуры является последовательное расположение. Среди профессионалов по обработке данных в этой ситуации обычно используется термин последовательный файл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
