Н. Джехани - Язык Ада (1988) (1160771), страница 43
Текст из файла (страница 43)
Например, функция ОКЕАТЕК ТНАХ, описанная как Рдпсбоп ОКЕАТЕК ТНАХ(А, В: ЕМРЬОг'ЕЕ) гегнгв ВОО1.ЕАХ 1я Ьеяш гегогн А.11) ) В Н); епо ОКЕАТЕК ТНАХ; используется в качестве фактического параметра настройки при конкретизации ЕМРЬОУЕЕ ЯОКТ2: ргосеовге ЕМРЬОг'ЕЕ ВОКТ2!я пеэг 1ХБЕКТ10Х БОКТ 0(ЕМРЬО г'ЕЕ, ЕМРЬО>г'ЕЕ АККАДА, ОКЕАТЕК ТНАХ); Типы формальных параметров и тип результата операции «»> в настраиваемой процедуре 1ХБЕКТ1ОХ ЯОКТ О должны, конечно, согласовываться с типами параметров и результатом функции ОКЕАТЕК ТНАХ. Настраиваемая процедура 1ХБЕКТ1ОХ БОКТ О производит сортировку в соответствии с настраиваемой операцией «»>, обычный смысл которой «больше, чем». Если Х и г' являются элементами отсортируемого массива и Х ) У вЂ” истинно, то в отсортированном массиве элемент Х появится после У.
Таким образом, массив будет отсортирован в возрастающем порядке. Используя операцию «<» в настраиваемой процедуре 1ХВЕКТ10Х ВОКТ О, получим конкретизацию, в которой все элементы массива сортируются в убывающем порядке Например, следующая конкретизация ОЕСКЕАБ1ХО ВООЬЕАХ БОКТ будет упорядочивать элементы логического массива в убывающем порядке: ргосейвге РЕСКЕА81ХО В001.ЕАХ БОКТ 1в пем 1ХБЕКТ1ОХ БОКТ О(ВООЬЕАХ, В001.ЕАХ АККАДА, "< "); 6.7.3. Вычисление интеграла по правилу трапеций Напишем функцию 1ХТЕОКАТЕ О, которая вычисляет определенный интеграл от функции Е действительное - действительное в пределах от а до Ь -ь 1 ~ 1(х) > ь используя правило трапеций.
Необходимо предусмотреть возможность конкретизации настраиваемой функции 1ХТЕОКАТЕ О для различных функций Ь Правило трапеций позволяет вычислять приближенное значение интеграла от функции в пределах от а до Ь как площадь трапеции с основанием Ь вЂ” а и высотами 1(а) и 1(Ь). Это приближение можно сделать более точным, разделив отрезок [а, Ь] на два равных отрезка и сложив плошади полученных трапеций. Каждый из полученных отрезков затем снова делится на две равные части и т. д. 214 Глава б 1(Ь) ь к Рис.
6л. Вычисление интеграла от функции й используя один интеРвал. г(ь) а «+ь «+аь Рис. бдк Вычисление интеграла от функции 0 используя п интервалов. Приближенное значение интеграла 1, от функции 1 в пределах от а до Ь, используя разбиение отрезка на и частей, вычисляется по формуле 1„= Ь | — + 1(а + Ь) + 1(а + 2Ь) + ... + 1(а + (и — 1)Ь) + — ), г' 1(а) ((Ь) ~ 2 2 )' где Ь вЂ” длина и-го отрезка, которая находится как Ь = (Ь вЂ” а)/и. Процесс деления отрезка повторяется до тех пор, пока два последовательных приближения интеграла функции от (, вычисляемые по методу трапеций, не будут различаться по абсолютной величине меньше чем на ЕРБ (ЕРБ > 0) — требуемое правило останова. 1 1 1 1 ! 1 1 1 1 1 1 1 1 1 1 1 1 1 ! 1 1 1 1 1 1 1 1 1 1 1 1 — « — е 1 1 1 1 1 1 1 ! 1 1 1 1 «+(«-нь Ь к 21$ Иасг иваеыые ио ии Алгоритм вычисления интеграла методом трапеций можно абстрактно описать как: ХЕ% АРРКОХ: 0; Р)Х1БНЕР: ГА1.БЕ; аЬВе по! Г1Х1БНЕ1) 1оор РКЕЧ10ЫБ АРРКОХ: ХЕ% АРРРсОХ; Вычислить ХЕЧ/ АРР)сОХ Г1Х1БНЕР: пЬз (ХЕ% АРР)сОХ вЂ” РКЕЧ100Б АРРКОХ) < ЕРБ; Разделить каждый интервал на две равных части еаа 1оор; Спецификация настраиваемой функции 1ХТЕОКАТЕ О имеет вид аевег!е (уре КЕАЬ (а йй!(а < >; згИЬ (пас((ов Р(Х: !в КЕАЬ) ге!агп КЕАЬ; -- функция Р задается при конкретизации (ппе(!ов 1ХТЕОКАТЕ О(А, В, ЕРБ: !в КЕАЬ) геава 1сЕАЬ; Тело настраиваемой функции 1ХТЕОКАТЕ С имеет вид йас(!ов 1ХТЕО)сАТЕ О(А, В, ЕРБ: Ы КЕАЬ) геапв )сЕАЬ Ы ХЕ% АРРКОХ: КЕАЬ: 0.0; -- случайное начальное значение РКЕЧ100Б АРРКОХ: КЕАЬ; Р(Х1БНЕВч ВОО1.ЕАХ: РАЬБЕ; -- для входа в цикл -- число интервалов -- размер интервала -- временная переменная Х 1ХТЕОЕВ(10.0 ' ( — А)) + 1: -- Х должно быть таким, чтобы размер интервала был — относительно мал; преобразование вешественного значения — в целое выполняется с округлением Н: ( — А)/КЕАЬ(Х); -- начальный размер интервала аЫ)е по! Р(Х1БНЕР 1оор РКЕЧ101Ж АРРКОХ; ХЕЧ/ АРРКОХ; — вычисление ХЕЧ/ АРРКОХ ЯЗМ: Р(А)/2.0; 1ог 1 Ьг 1..Х-1 !оор БЫМ: Я)М+ Р(А+ КЕАЬ(1) я Н); епй 1оор; Я)М: Я)М + Р(В)/2.0; ХЕЧ/ АРРРсОХ: Я5М я Н; Р)Х1БНЕР: аЬя (ХЕЧг' АРРКОХ вЂ” РКЕЧ100Б АРРКОХ) < ЕРБ; Х: Х ° 2; - - число интервалов для следуюшего приближения Глава в гзб Н:-НУ го; -- размер интервала для следующего приближения епо 1оор; геФогп ХЕНЧ АРРКОХ; епй 1ХТЕбКАТЕ б; Функция 1ХТЕСКАТЕ С работает неверно, если первое же приближение интеграла Р удовлетворяет условию останова, так как ХЕ% АРРКОХ присвоено произвольное начальное значение 0.0.
Эту задачу можно разрешить, если заставить программу принудительно делать по меньшей мере два вычисления или же инициализировать ХЕ% АРРКОХ приближением интеграла вместо произвольной величины: ХЕ'1гг' АРРКОХ: КЕАЬ: (Р(А) + Р(В))/2.0; -- площадь под кривой представляется как одна -- большая трапеция, т. е. Х = 1 6.7.4. Множества В данном примере для реализации множеств используется настраиваемый пакет БЕТ С. Каждая конкретизация БЕТ С создает новое множество. Определяются операции добавления и удаления элемента множества, объединения и разности двух множеств, а также определения, пусто ли множество, и получения пустого множества (пц11). Тип БЕТ описан как личный тип, так что множества могут присваиваться объектам типа БЕТ и сравниваться на равенство и неравенство.
Спецификация пакета БЕТ С следующая: яепепс Фуре Е1.ЕМ Фв (< >); -- любой дискретный тип рас!Фане БЕТ б !в Фуре БЕТ!в рпгаге; ргосе)пге АР!)(Б: ш овФ БЕТ; Е: !и ЕЬЕМ); ргосеФ!цге КЕМОЧЕ(Б: !и оиФ БЕТ; Е: !и Е1.ЕМ); уписФ!ои ЕМРТУ(Б: Фп БЕТ) гегвгп В001.ЕАХ; уцисйои "+" (Х, У: 1п БЕТ) гегпгп БЕТ; — — объединение множеств Йшсвоп "-"(Х, У:!и БЕТ) ге!игл БЕТ; -- разность множеств; возвращает множество, содержащее все -- элементы Х,кроме тех, которые присутствуют в У Йвсбоп Х()ЬЬ БЕТ гегогп БЕТ; рпгаФе Фуре БЕТ АККАДА Фв аггау(ЕЬЕМ) о( ВООЬЕАХ; Фуре БЕТ Фв гесоп! А: БЕТ АККАУ: (ЕЬЕМ > РАЬБЕ); Наст аиааемые модули епд гесогд; -- при создании множеств им будут присваиваться значения -- пустых множеств (пц11).
Только именуемый тип может -- иметь начальное значение по умолчанию. Это значение при-- сваивается всем объектам этого типа. Поэтому логический -- массив А, реализующий множество, окаймлен записью. -- Значение по умолчанию может быть подавлено явной -- инициализацией епд БЕТ О; Реализация этого пакета приведена ниже: расйпие Ьоду БЕТ О $е ргоседаге АРР(Б: ш оп! БЕТ; Е: $а ЕЬЕМ) 1е Ье)$)а Б.А(Е): ТКЫЕ; ев$ АРР; ргоседаге КЕМОЧЕ(Б: $и оп! БЕТ; Е: ги Е1.ЕМ) Ь Ьеяю Б.А(Е): РА1.БЕ; евд К.ЕМОЧЕ; йюсбои ЕМРТУ(Б: $в БЕТ) геаиа ВООЬЕАг( !а Ьеи)в 1ог 1 !п Е1.ЕМ !вор $$ Б.А(1) гйеп ге!игл РА1.БЕ; еад $$; ев$ Ьор; геаиа ТРЕШЕ; епд ЕМРТУ; йюе$$ов "+"(Х, У: ш БЕТ) геюгв БЕТ 1в КЕЯЛ.Т: БЕТ; -- начальное значение КЕЯЛ.Т вЂ” пустое множество Ье$$$а $ог 1 $и Е1.ЕМ !оор КЕБ1)ЬТ.А(1): Х.А(1) ог У.АИ); евд !оор; геиив КЕБ)Л.Т; ев1 "+"; йюсйоп "-"(Х, У: ш БЕТ) геаиа БЕТ $а КЕЯ)ЬТ: БЕТ; й?В Глава 6 Ьея(п Раг 1 в ЕЬЕМ!вор КЕЯЛ.Т.А(1): Х.А(1) ав1 пв! 'г.А(1); ев1 !оор; ге!пгп КЕБ(Л,Т; 1 е Рапсйоп Х()ЬЬ БЕТ гешгп БЕТ 1я КЕЯЛ.Т: БЕТ; Ьей!п гегвгп КЕЯЛ.Т; -- пусто по определению епа Х()ЬЬ БЕТ; епй БЕТ О; Приведем несколько примеров использования пакета БЕТ О: расйайе 1ХТ БЕТ 1а пезг БЕТ О(БМА1 ЫХТ); расйайе СНАК БЕТ !в пезг БЕТ О(СНАКАСТЕК); А, Рк 1ХТ БЕТ.БЕТ; Х, У: СНАК БЕТ.БЕТ; Реализация множеств с использованием логических значений для указания присутствия или отсутствия элемента во множестве делает операции над множествами быстрыми.
Тем не менее такая реализация не является эффективной с точки зрения использования памяти, особенно если число элементов во множестве в данный момент времени мало по сравнению с максимальным числом возможных элементов, которые могут присутствовать во множестве. Как же реализовать множества, чтобы память использовалась эффективно? Исследование этой проблемы предоставляется читателю. Указание: реализовать множество как список. Сравнить это решение с реализацией множества в виде логического массива по скорости выполнения операций и использованной для элементов множества памяти. Существуют ли еще более удобные структуры данных, отличные от описанных выше, которые требовали бы меньше памяти, чем логические массивы, а работали бы быстрее, чем при использовании списков? 6.7.5. Операции над массивами Настраиваемые модули в языке программирования Ада можно использовать для определения классов операций.
Примеры таких операций приводятся для одномерных и двумерных массивов. б.7.5.1. Одномерный массив Этот пример иллюстрирует тот факт, что различные операции над одномерными массивами, такие как вычисление максимального элемента или нахождение произведения всех элементов массива, могут быть опеределены и записаны как одна настраиваемая функция ЧЕСТОК ОРЕКАТ1ОХ. Этот пример также иллюстрирует универсальность и мощность настраиваемых модулей языка Ада. 219 Нас анвавмыв мо аа Предположим, что ЧЕСТОК ОРЕКАТ10Х конкретизируется как функция ТНЕТА ЧЕСТОК для операции 9, ТНЕТА ЧЕСТОК (А) вычисляет значение а,разд ра„ где а; — элементы массива А".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
