1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 32
Текст из файла (страница 32)
Задача, тем самым, делится на последовательность двух: редукции и извлечения ответа из величины х. При атом используется процедура нахождения остатка. Итак (2) ТЕЛО НОД: ( цел проц ОСТ (А, В); знач А, В; цел А, В; ТЕЛО ОСТ; РЕДУКЦИЯ(4(; г: =х) прим ТЕЛО ОСТ/А, В/ состоит из одного оператора присваивания, использующего целое деление.
Итак (3) ТЕЛО ОСТ: ОСТ: = А — (А —: В) хВ драм РЕДУКЦИЯ /х, у/. Очевидно, что редукция носит повторный характер. На каждом шаге редукции х и у заменяются соответственно ОСТ(у, х) и х, а повторение контролируется значением величины и = ОСТ (х, у). Итак (4) РЕДУКЦИЯ: (цел и; для и: = ОСТ (у, х) пока и Ф О цикл ЗАМЕНА ) (5) ЗАМЕНА: (у: = х; х: = и) Для того чтобы собрать программу из структурных формул, нужно произвести систематические подстановки структурной формулы для'задачи в другую структурную формулу, в которой зта задача упоминается в качестве подзадачи. Имена задач, остающиеся в программе в качестве меток, не обязательны и могут быть выброшены, так как структурированная программа не содержит операторов перехода.
Некоторые метки в собранной программе оставлять все же полезно для того, чтобы сохранить в ней смысловые спорные точки. Ниже показана результирующая программа нахождении наибольшего общего делителя. проц НОД (х, у, г); знач х, у; цел х, у, г; начало цел проц ОСТ (А, В); знач А, В; цел А, В ОСТ: = А — (А — 'В) х В; В 4.3.
ОБЩАЯ ОРГАНИЗАЦИЯ ЭКОНОМИИ ПАМЯТИ РЕДУКЦИЯ: начало цел и; длн и: = ОСТ (х, у) пока и ~ О цикл начало у: = х; х: = и конец; конец: ЛОЛУЧЕУХИЕ: г: = х конец $4.3. Общая организация экономии памяти Весь последний текст главы будет выглядеть наподобие только что приведенного демонстрационного примера. Возможно, что читать его будет не трудно, но очень скучно. Чтение можно будет сделать более медленным, но и гораздо более интересным, если попытаться самому структурировать программу экономии памяти, испольвуя текст главы для контроля. Читатель может быть уверен, что это будет соревнование с автором (при условии, конечно, полноценного знания предыдущих глав и некоторого навыка в алголе) почти.на равных, так как для автора написание этой главы было его первым упранвнением в структурированном программировании, а сама програм)ва приведена именно в том виде, в каком она получалась (не считая, естественно, переписываний, вызванных замеченными ошибками).
Зкономия памяти в операторной схеме прим Мы начинаем с' уточнения объектов задачи. В соответствии со скааанным во вступлении к этой главе мы будем представлять элементарные абстрактные объекты, главньгм образом, натуральными числами, их множества — отрезками натурального ряда, а подмножества — логическими шкаламн. Для того чтобы задать множество операторов, нам достаточно укаэать цел и — число операторов. Управляющий граф мы будем изображать, матрицей смежности цел массив С[1: и, 1: и), в которой С(у, у! равен 1, еслиу-й оператор является преемником 1-го оператора, и О в противном случае.
Такое представление удобно для построения транзитивных замыканий, так как в-я строка матрицы С вЂ” это множество преемников оператора в, а у-й столбец — множество предшественников оператора у. Множества аргументов' и результатов в сумме обраэуют множество полюсов. Поскольку нам приходится работать, как вообще с полюсамн, так и, в частности, с аргументами и результатами, нам будет удобнее рассматривать множество полюсов как отрезок натурального ряда от 1 до р + д, где цел р — число аргументов, а цел д — число результатов.
В этом случае 1-й результат изображается числом р + в. Распределение полюсов прн этом естественно изображается вектором цел массив У(1: р + д), 152 Гл. 4. Ркализхция где т'[/1 — оператор, сопоставленный 1-му полюсу. Вектор цел массив Ь[1: р + о[ задаст распределение памяти, если считать, что Ь[11 — это величина, сопоставленная 1-му полюсу. Для заданной таким образом операторной схемы мы будем искать цел массив Ь1 И: р + д) — новое, по возможности экономное распределение памяти.
Программу Экономии Памяти в Операторной Схеме мы будем строить в виде. описания процедуры ЭПОС с перечисленными формальными параметрами. Итак (1) проц ЭПОС (и, С, р, о, У, Ь, Ь1); значи, С, р, д, У, Ь; цел и, р, д; цел массивы С, У, Ь, Ь1; ТЕЛО ЭПОС прим ТЕЛО ЭПОС/и, С, р, о, [г, Ь, Ь1/. Узловым моментом экрпомни памяти является построение информационного графа, а более точно — его областей действия. Фактически результатом построения областей действия будет цел 1 — число. областей действия и каноническое распределение памяти цел массив ЬК И: р + о[, в котором всем полюсам, относящимся к 1-й области действия, будет сопоставлена величина 1.
Экономия памяти будет производиться на основе канонического распределения. Итак (2) ТЕЛО ЭПОС: (цел 1; цел массив ЬК [1: р + о1; КАНОНИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ /7/; ЭКОНОМИЯ ПАМЯТИ) прим ЭКОНОМИЯ ПАМЯТИ /и, С, р, д, $', 1, ЬК, Ь1/. Мы. хотим прежде всего структурировать нашу программу выделением крупных разделов, которые образуют в свою очередь содержание параграфов данной главы. ЭКОНОМИЯ ПАМЯТИ естественно расчленяется на получение графа несовместимости и на его последующую раскраску, которая и задаст нужное распределение памяти. Аналогично графу переходов мы зададим граф несовместимости его матрицей смежности цел массив (/[1: 1, 1: 11, в которой О[1, /1 = 1, если 1-я и /-я области несовместимы, и (/[/, /] = 0 в противном случае.
Очевидно, что матрица П вЂ” симметрична. Итак (3) ЭКОНОМИЯ ПАМЯТИ: (цел массив ПИ: 1, 1: 11; ПОЛУЧЕНИЕ ГРАФА НЕСОВМЕСТИМОСТИ /49/; РАСКРАСКА И ОКОНЧАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ) прим РАСКРАСКА И ОКОНЧАТЕЛЬНОЕ РАСПРЕ/ДЕЛЕНИЕ /р, д, 1, ЬК, О, Ь1/. Структурирование задачи подсказывается ее названием. Раскраску вершин графа (/ с учетом уже имеющихся примеров представления отображений проще. всего представить вектором цел массив О[1: 11, где О[1)в краска, сопоставленная 1-й вершине графа несовместимости..
1 «л. кАноническое РАспРвделение пАмяти 153 При атом предполагается, что множество использованных красок, как и ранее, представлено отрезком натурального ряда. Итак (4) РАСКРАСКА И ОКОНЧАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ: (цел массив О[1: 1]; РАСКРАСКА/75/; ОКОНЧАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ) прим ОКОНЧАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ /р, о, ЬК, О, Ь1/. Мы доведем до конца заключительную часть программы, чтобы потом сконцентрировать внимание на главных подзадачах. Для получения экономного окончательного распределения памяти нам нужно для каждого полюса найти краску, сопоставленную его области действия, и сопоставить ее сав«ему полюсу. Итак (5) ОКОНЧАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ: (цел у; для/: = 1 шаг 1 до р + о цикл СВОЯ КРАСКА /-МУ ПОЛЮСУ) прим СВОЯ КРАСКА /-МУ ПОЛЮСУ /у, ЬК, О, Ь1/.
Нам нужно определить значение Ь1[/]. ЬК[/] дает нам номер области действия, к которой относится у-й полюс. Так как Ч[11— это краска, сопоставленная 1-й облйсти действия, то искомая краска равна Ч [ЬК [/] ]. Итак (6) СВОЯ КРАСКА /-МУ ПОЛЮСУ: Ь1[/]: = О[ЬК[/]] Итак, мы выделили три крупные подзадачи, которымн н будем заниматься до конца главы. Это КАНОНИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ, ПОЛУЧЕНИЕ ГРАФА НЕСОВМЕСТИМОСТИ и РАСКРАСКА. 4 4.4. Каноническое распределение памяти прим КАНОНИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ /[2)п, С, р, д, У, Ь, 1, ЬК/ начинается с того, что согласно $ 3.1 каждый полюс'считается принадлежащим «своей собственной» компоненте свяаности информационного графа.
Другнмн словами, происходит максимальная расклейка распределения памяти, задающая начальное значение вектора, ЬК. После етого производится непосредственное построение областей действия. Итак (7) КАНОНИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ: (РАСКЛЕЙКА ПОЛЮСОВ; ПОСТРОЕНИЕ ОБЛАСТЕЙ ДЕЙСТВИЯ /9/) прим РАСКЛЕЙКА ПОЛЮСОВ'/р, д, ЬК/ очевидно решается итерацией сопоставления 1-му полюсу (1 1,..., р + о) величины 1. Итал ГЛ. 4.
РЕАЛИЗАЦИЯ (8) РАСКЛЕЙКА ПОЛЮСОВ: (цел 1; для 1: = 1 шаг 1 до р + д цикл ЬКП): = 1) прим ПОСТРОЕНИЕ ОБЛАСТЕЙ ДЕЙСТВИЯ /(7) п, С, р, д, У, Ь, 1, 1 К/ должно построить не только каноническое распределение памяти ЬК, но и подсчитать число областей действия й Итак (9) ПОСТРОЕНИЕ ОБЛАСТЕЙ ДЕЙСТВИЯ: (НАХОЖДЕНИЕ ЬК/11/; ПОДСЧЕТ ЧИСЛА ОБЛАСТЕЙ) прим ПОДСЧЕТ ЧИСЛА ОБЛАСТЕЙ /ЬК, В. По правилу слияния текущих областей действия мы всегда оставляем в схеме величину с меньшим покером. Это позволяет нам определить число областей взятием максимального злемента вектора ЬК.
Итак (10) ПОДСЧЕТ ЧИСЛА ОБЛАСТЕЙ: (1: = 0; (цел 1; для 1: = 1 шаг 1 до р + Ч цикл если ЬКП) ) 1 то й = ЬКП))) прим НАХОЖДЕНИЕ ЬК/(9) п, С, р, е, )/, Ь, ЬК/ согласно з ЗА есть итерация построения ограниченного транзитивного образа оператора для кан;дого результата схемы, в процессе построения которого будет в нужных случаях происходить слияние текущих компонент связности. Итак (11) НАХОЖДЕНИЕ ЬК: (цел 1; для 1: = 1 шаг 1 до д цикл ТРАНЗАМ 1-ГО РЕЗУЛЬТАТА) прим ТРАНЗАМ 1-ГО РЕЗУЛЬТАТА /и, С, р, е, $', Ь, ЬК, 1/. Построение ограннченнога транзнтивного образа требует перед выполнением основного итерационного цикла движения по дугам графа определенной подготовительной работы.
Нам надо будет задать начальные значения стартового и пополняемого множеств 3 и Т, а также построить ограничивающее множество В. Для слияния текущих областей действия пам нужно по ходу дела фиксировать моменты достижения операторов, воспринимающих величину, сопоставленную 1-му результату. Эти операторы образуют «аргументное» множество А. Все эти множества мы представим в виде логических шкал длины и. Необходимость ввести эти множества очевидна и лежит, так сказать, на поверхности. Предстоящий шаг структурирования задачи дзег нам, однако, хороший материал для понимания того, что беаошибочное структурирование и своевременное введение новых объектов требует поистине полноты знания задачи и четкого представления, как будет протекать работа во вяутреняих слоях программы. В данном случае речь идет о механизме слияния текущих коьшонент связности прн попадании во время построения транзитивного замыкания на оператор из аргументного мно- ' % «А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
