Н. Джехани - Язык Ада (1988) (1160771), страница 16
Текст из файла (страница 16)
Быстрая сортировка Задача состоит в сортировке массива, описанной в предыдущем примере сортировки вставками, но на этот раз используется метод быстрой сортировки [НОА621. Быстрая сортировка в среднем более эффективна, нежели сортировка вставками [КМ3731". "Среднее время выполнения быстрой сортировки имеет величину порядка Гч Рой ГЧ, в то время как сортировка вставками — порядка Ф. и наихудшем случае оба алгоритма имеют величину поряд- Гланд 1 уг Ро'. Быстрая сортировка (А, Ь, (1) Р>.
1! О ин эл мент 1!>еп д е ппй; е(й!! Два элемента Феп Упорядочить их е(я!! Более чем два элемента Феп Разбить А на части так') ь [Один элемент в середине) (В данном случае по крайней мере поодному элемент> на каждую часть) где й †ирои>вольн величина и>массива А — 1 представляет собой указатель слева направо — Я представляет собой указатель справа налево Быстрая сортировка (А, 1., !); — левой части, которая содержит элементы < = К Быстрая сортировка (А, 1, ٠— правой части„ которая содержит элементы > = К вЂ” значения элементов, если они существуют, с индексами — большими, чем ), но меньшими, чем 1, равны К и — их не нужно сортировать, поскольку они уже находятся — на правильных местах еид 1! Разбиение массива А на левую часть, содержащую элементы, меньшие или равные К (произвольному значению из массива А), и правую часть, содержащую элементы, большие или равные К, основано на следующем алгоритме.
Просматриваем А слева (чтобы определить левую часть) до тех пор, пока не будет найден элемент, больший или равный К. Затем просматриваем А справа (чтобы определить правую часть) до тех пор, пока не будет найден элемент, меньший или равный К. Обменяем А(1) и А(1) так, чтобы они принадлежали правильному разбиению. Затем указатели сдвигаются на один шаг, т. е. 1 увеличивается на 1, а ! уменьшается на 1.
Если указатели не пересеклись, то просмотр возобновляется. Просмотры никогда не повторяются, поскольку разбиение, полученное при первом просмотре, предотвращает второй просмотр. Первоначально правая часть не содержит элементов, а просмотр левой части прекращается при нахождении значения К среди элементов массива А. Выбор К среди значений А и использование слабых неравенств (т.
е. <и> вместо <и> соответственно) гарантирует завершение обоих просмотров на элементе К или ранее. >> Необходимо, чтобы каждая часть содержала по крайней мере олин элемент для обеспечения выхода иэ рекурсии. уз две влив В конце просмотра, когда 1 равно Я, после обмена элементами" и изменения 1 и Я состояние массива А соответствует первому из показанных ранее разбиений.
С другой стороны, для 1, равного Я вЂ” 1, мы приходим ко второму разбиению (при этом в каждом разбиении содержится по одному элементу, которые необходимо поменять местами). Алгоритм разбиения массива описан операционно, т. е. путем задания этапов реализации. Альтернативный способ описания алгоритма, содержащего цикл, заключается в задании инварианта цикла и описании процесса обмена элементами в цикле для достижения поставленной цели.
Подходящий инвариант цикла для алгоритма разбиения следующий: А(Ь.. 1 — 1) ( К и А(Х + 1. Л5) > К Инвариант можно представить графически так ( ' 1 Цикл должен увеличивать 1 и уменьшать 1, сохраняя истинность инварианта. Такое описание разбиения более простое для понимания, чем операционное, запутанное детальным описанием реализации алгоритма.
Более того, описание, использующее инвариант цикла, более гибкое, чем операционное описание, поскольку программисту предоставляется свобода при реализации этого алгоритма и он может выбрать любой способ, согласующийся с инвариантом циклаз). Алгоритм, заданный шагом Рг, далее детализируется следующим образом: Рз. Логические выражения Один элемент и Два элемента детализируются так: Ы вЂ” Ь= О и 13 — 1. = 1 Оператор Упорядочить их детализируется так: 11 А(()) ( = А(1.) (йеп оу((АР(А(Ь), А(Ц)); епд !1 Логическое выражение Более чем два элемента детализируется так: 13 — 1.
> 1 Оператор Разбить А на части детализируется так: К: = А((О + Ь)/2); — К вЂ” средний элемент 1:=Ь; 1:=15; — А(1...1 — 1) ( гс и А(1 + 1. Л1) > К вЂ” это инвариант цикла эч)111е 1( = 31оор Увеличить левую часть, увеличив 1 Увеличить правую часть, уменьшив 1 " Если 1 равно 1, то никакие обмены не производятся, поскольку А(1) и А(1) это разные названия одного и того же элемента. 2) Более детальное обсужление использования инвариантов при разработке программ и рассуждения о никпак приведены в книге Дэвида Гриса «тье Бс)енсе ог Ргокгатгл(пк» [Ггк1811.
74 Глава г Расположить элементы так, чтобы инвариант цикла сохранился епд !оор; Рэ Оператор Увеличить левую часть... детализируется так: ггЫ!е А(1) < К !оор 1:=1+1; еЫ !оор; — А(1) > К Оператор Увеличить правую часть... детализируется так: ггЫ!е А(1) > К!оор Л:= э — 1; епб !оор; — А(Я) < К Оператор Расположить элементы... детализируется так: Ы'1< =Яйеп Я%АР(А(1), А(Ю)); 1:=1+ 1; Ю:= э — 1; епг! Ы; Используемая здесь процедура БчгАР определена ранее. Собрав все шаги детализации вместе, получаем окончательную версию программы: ргосег!пге ОО(СКБОКТ (А:!п оа! ЧЕСТОК) !в Ь: сопагап! А'КАХОЕ: = А'ЯКУТ; О: сопв1ап! А'КАХОЕ: = А'ЬАЯТ; 1, э:А'КАХОЕ; — 1 и Ю могут принимать только — те значения, которые соответствуют — правильным индексам А К:Н.ОАТ; (эеК!и И О вЂ” Ь=О гаев пп11 е!зЫ !.1 — Ь = 1 Феп Ы А(Ы) < А(1.) !пеп о ггАР(А(Ь) „А(0)); еЫ И; е!зЫ 0 — 1. > 1 !!геп К: = А((О + Ь)/2); 1:= Ь; Л:=(); — Разбиение массива с использованием К гг!г!1е 1 < = Л!оор пЫ!е А(1) < К !оор 1:=1+ 1; епп 1оор; щЫ!е А(э) > К 1оор э:= э — 1; Вве ение епй 1оор; И 1 < = 1 1(зеп Я%АР(А(1), А(1)); 1:=1+1; 1:= 3 — 1;" епй И; епг) 1оор; О(ЛСКБОКТ(А(Ь..
))); — отметим использование отрезка. Новая копия — элементов не порождается для отрезка. О)ЛСКБОКТ(А(1. Ы)); епй И епй ОШСКЯОКР Первые два случая в главном операторе Ы процедуры Я(ЛСКБОКТ можно объединить в один: И О вЂ” 1. < = 1 гаев И А(Щ < А(Ь) 1)геп В%АР (А(Ь), А(~1)); епй И; е!яИ... Память, используемую при быстрой сортировке во время рекурсии, можно уменьшить за счет сортировки сначала меньшего из двух отрезков А(Ь..Я) и А(1. Л3), а затем большего отрезка. 1.10.6. Умножение матриц Напишем процедуру МАТ М(ЗЬТ перемножения матриц А и В и заносящую результат в третью матрицу С.
Каждая матрица — это неограниченный тип гуре МАТК1Х 1я аггау (1ХТЕОЕКгапяе < >, 1ХТЕОЕКгапяе < >) о1 РЬОАТ; При умножении двух матриц, скажем А и В, число столбцов в матрице А должно равняться числу строк в матрице В. Число строк в матрице, содержащей результат, должно равняться числу строк в А, а число столбцов в ней должно равняться числу столбцов в В. Для упрощения программирования предположим, что соответствующие подтнлы индексов матриц А, В и результирующей матрицы совпадают. Начальная детализация для умножения матриц следующая: Ро.' Проверить правильность границ для умножения матриц 1ог 1(пА'КАХОЕ(1)1оор 1ог 1 ш В' КАХОЕ(2)!оор Вычислить С(1, 3) = 2', А(1, К) х В(К, 1); К~А'яхново) епй 1оор; епб 1оор; 76 Глава 1 Детализируя Ро, получаем следующую процедуру на языке Ада: ргосейпге МАТ М1Л.Т(А, В:!пМАТК1Х; С: ов!МАТК1Х)!з (гей(п !1 А'ЯКУТ(1)/ = С'НКЯТ(1) ог А'ЬАЯТ(1) /= С'ЬАБТ(!) ог А'ЯКУТ(2) /= В'ЯКУТ(1) ог А'ЬАБТ(2)/= В'ЬАЯТ(1) ог В'ЯКУТ(2) /= С'НКВТ(2) ог В'ЬАБТ(2) /= С'ЬАБТ(2) Феп пизе ЕККОК; — возбуждается исключение, — которое будет обсуждаться позже — в главе об исключениях епп !1; 1ог 1 !п А'КА(чОЕ(!)!оор 1ог Ю !п В'КА)чОЕ(2) 1оор С(1, 5):= О.О; !ог К !п А'КАХОЕ(2)!оор С(1, Ю):= С(1, 1) + А(1, К) х В(К, 1); епй !оор; епй 1оор; епй 1оор; епй МАТ М\ЛТ; Если в задании границ матриц присутствует ошибка, то подпрограмма МАТ М1Л.Т возбуждает исключение ЕККОК и завершается.
Обработка этой ошибки должна производиться там, откуда вызывается МАТ-М!Л.Т. Используя МАТ-М1Л.Т, операцию умножения х легко совместить для умножения матриц: !ппсйоп "я" (А, Вйп МАТК1Х) гегпгп МАТК1Х !з С:МАТК1Х (А'ЯКУТ(!) .. А 'ЬАЯТ(1), В 'НКБТ(2) .. В 'ЬАБТ(2)); Ьея!п МАТ М()ЬТ(А, В, С); гегпгп С; епй 1.10.7. Схема Горнера Прямое вычисление полинома А(х) = а„х" + а„~х" ' е ... + а~х + ае требует по крайней мере 2п умножений, тогда как при использовании схемы Горнера требуется только и умножений [АНО75). Схема Горнера зацает следуюшую схему вычислений: А(х) = (...((а„х + а„ ,)х + а з)х + ...
+ а~)х + ае. Вычисление полинома по схеме Горнера реализовано функцией Ез/АЬ РОЬг', где тип СОЕРР описан следующим образом: Гуре СОЕРР В аггау (1ХТЕОЕК гапяе < >) о1 НОАТ', Вев ение 77 Массив А, являющийся формальным параметром, содержит коэффициенты поли- нома а„, а„ь ..., а1 в элементах А(п), А(п — 1), ..., А(0). Ч вЂ” это то значение, для которого необходимо вычислять полипом: 1ппс!!оп ЕЧА! Р01Х(А:!п СОЕРР; Ч:!п Н.ОАТ) ге!нгп Н.ОАТ !я ЯЗМ: Н.ОАТ; )ген!п Я)М: = А(А'ЬАБТ): 1ог 1 ш гегегзе А'Р!КБТ..А'ЬАЕТ вЂ” 1!оор — отметим использование гегегзе Я)М: = Я)М е Ч + А(1); ецио !оор; ге!пгп Я)М; епо ЕЧАЬ Р01Х; Глава 2 Еще о типж ~3] В языке Ада для повышения удобочитаемости программ, обнаружения ошибок и генерации кода требуется, чтобы типы объектов были явно определены. Языку Ада присуща также большая строгость при обработке типов, что повышает надежность программ.
Все объекты должны быть использованы в соответствии с их типами. Язык Ада содержит разнообразные типы и механизмы определения типов, что позволяет программисту определять типы, необходимые для применения. Например: ° типы с плавающей точкой могут быть определены в рамках ограничений конкретной реализации с любой желаемой точностью; ° именуемые типы могут быть параметризованы; ° набор значений, связанный с существующим типом, можно ограничить так, что ошибочное использование значения, не входящего в ограниченный набор, будет обнаружено автоматически. ° некоторый новый тип может быть определен как имеющий значения и операции, аналогичные существующему типу.
Этот новый тип, однако, отличается от существующего, свойства которого он наследует. Таким образом, значение, представляющее возраст человека, нельзя небрежно присвоить переменной, представляющей номер карточки социального обеспечения человека. 2.1. Строгая типизация Язык Ада строго типизирован. Концепция строгой типизации была впервые реализована в языке программирования Паскаль. После разработки языка Паскаль тенденция строгой типизации была развита в языках программирования, таких как Евклид, Модула, Клу, Меса и, наконец, Ада. В контексте обсуждения в данной книге будет использовано определение, приведенное ниже.
Определение. Язык является строго типизированным [РЕ1)82), если: 1) каждый объект в языке принадлежит точно одному типу; 2) тип есть синтаксическое свойство, т. е. тип выражения можно определить из синтаксиса программьзп; 3) преобразование типа происходит путем преобразования значения одного типа в другой; неявное преобразование не будет иметь места, если рассматривать представление значения как значение другого типа. В языке Фортран, например, рассмотрение представления некоторого значения как элемента другого типа является возможным благодаря оператору эквивалентности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
