Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Технология разработки алгоритмов

Опыт практической алгоритмизации и программирования привел к формированию неких общих принципов и методов проектирования, разработки и оформления алгоритмов.

Какими качествами должен обладать хороший алгоритм?

Прежде всего, от алгоритма требуется, чтобы он правильно решал поставленную задачу. Но не менее важно, какой ценой это достигается. Речь идет о разумности затрат на его создание. С этой точки зрения алгоритм должен быть легким для понимания, простым для доказательства правильности и удобным для модификации. В рамках такой идеологии и сформировался так называемый структурный подход к конструированию и оформлению алгоритмов, позволяющий уменьшить количество ошибок в алгоритмах, упрощающий их контроль и модификацию.

По своей сути структурный подход есть отказ от беспорядочного стиля в алгоритмизации и программировании (в частности, отказ от оператора goto) и определение ограниченного числа стандартных приемов построения легко читаемых алгоритмов и программ с ясно выраженной структурой. Теоретическим фундаментом этого подхода является теорема о структурировании, из которой следует, что алгоритм решения любой практически вычислимой задачи может быть представлен с использованием трех элементарных базисных управляющих структур: а) структуры следования или последовательности; б) структуры ветвления; в) структуры цикла с предусловием (рис. 9.7, соответственно а, б, в, где P – условие, S – оператор).

Рис. 9.7. Базисные управляющие структуры

Базисный набор управляющих структур является функционально полным, то есть с его помощью можно создать любой сколь угодно сложный алгоритм. Однако с целью создания более компактных и наглядных алгоритмов дополнительно используются следующие управляющие структуры: а) структура сокращенного ветвления; б) структура выбора; в) структура цикла с параметром; г) структура цикла с постусловием (рис. 9.8, соответственно а, б, в, г).

В разных языках программирования реализация базовых управляющих структур может быть различной. В языке Паскаль реализованы все рассмотренные структуры.

Рис. 9.8. Дополнительные управляющие структуры

Любой алгоритм может быть построен посредством композиции базисных и дополнительных структур:

- их последовательным соединением - образованием последовательных конструкций;

- их вложением друг в друга - образованием вложенных конструкций.

Например, алгоритм Евклида, описанный ранее, представляет собой комбинацию из трех управляющих структур: последовательности, цикла и ветвления (рис. 9.9).

Рис. 9.9. Алгоритм Евклида как композиция базисных структур

Каждая из структур может рассматриваться как один блок с одним входом и одним выходом. Таким образом, мы можем ввести преобразование любой структуры в функциональный блок. Тогда всякий алгоритм, составленный из стандартных структур, поддается последовательному преобразованию к единственному функциональному блоку и эта последовательность преобразований может быть использована как средство понимания алгоритма и доказательства его правильности. Обратная последовательность преобразований может быть использована в процессе проектирования алгоритма по нисходящей схеме с постепенным раскрытием единственного функционального блока в сложную структуру основных элементов. В области автоматизированной обработки данных такой подход называют нисходящим проектированием или проектированием «сверху вниз».

Разработка алгоритма по нисходящей схеме начинается с разбиения сложной исходной задачи на отдельные более простые подзадачи, решение которых может быть представлено в общей структуре алгоритма функционально независимыми блоками. Разработку логической структуры каждого такого блока и ее модификацию можно осуществлять независимо от остальных блоков. На первом этапе проекта раскрываются наиболее важные и существенные связи в исследуемой задаче, составляется укрупненная схема алгоритма, определяется функциональное назначение каждого блока, его входные и выходные данные. На последующих этапах проектирования уточняется логическая структура отдельных функциональных блоков общей схемы, строятся схемы алгоритмов выделенных ранее подзадач. Разработка алгоритма каждой подзадачи также может осуществляться в несколько этапов детализации. На каждом этапе проекта выполняются многократные проверки и исправления алгоритма. Подобный подход является рациональным, позволяет значительно ускорить процесс разработки сложных алгоритмов, и в значительной мере избежать ошибочных решений.

В качестве примера рассмотрим задачу табулирования функции одной переменной, то есть вычисление значений функции у = f(x) для всех значений х, изменяющихся от х0 до хn с шагом hx, сокращенно:
x = С…0(hx) С…n.

Пусть

РіРґРµ

a, b, x0, hx, xn – исходные данные.

Процесс проектирования алгоритма табулирования функции у = f(x) показан на рис. 9.10, а. На первом уровне детализации схема отражает процесс табулирования функции в общем виде (блоки 1.1-1.5). Далее осуществляется детализация блока 1.4 в виде последовательности блоков 2.1-2.3 второго уровня. Функция z = z(x), входящая в определение исходной функции, представлена разветвляющейся структурой третьего уровня детализации (блоки 3.1-3.5).

Р°

Рис. 9.10. Нисходящая схема проектирования
алгоритма вычисления сложной функции

Подставляя вместо функциональных блоков, подвергнутых дальнейшей детализации, соответствующие структуры, получим окончательную схему алгоритма, изображенную на рис. 9.10, б.

Р±

Рис. 9.10. Окончание. Алгоритм вычисления сложной функции

Структуры алгоритмов

Алгоритмы линейной структуры

Реализуют линейные вычислительные процессы, в которых отдельные этапы вычислений должны выполняться последовательно друг за другом. Линейные алгоритмы содержат только команды обработки данных. При исполнении алгоритма команды выполняются в порядке их записи. Линейный алгоритм вычисления коэффициентов приведенного квадратного уравнения рассмотрен в предыдущем разделе (рис. 9.2). Для построения таких алгоритмов используется структура следования.

Ветвления

Вычислительные процессы, в которых в зависимости от тех или иных условий должны выполняться различные этапы вычислений, называются разветвляющимися. Для построения алгоритмов, реализующих такие вычислительные процессы, необходимы специальные команды (управляющие структуры), позволяющие управлять ходом выполнения алгоритма, а менно, осуществлять выбор одного из нескольких возможных действий. Основной такой конструкцией является структура простого ветвления, реализующая принятие двоичного, или дихотомического, решения. Примером алгоритма с простыми ветвлениями является рассмотренный ранее алгоритм выбора максимального числа. Рассмотрим алгоритмы с более сложными ветвлениями.

Пример 9.5. Вычислить значение функции, график которой изображен на рис. 9.11.

Рис. 9.11. График функции

Область определения функции разбивается на 4 участка, на каждом из которых значение функции определяется по различным формулам:

Для построения схемы алгоритма решения данной задачи используем вложенную конструкцию структур ветвления (СЂРёСЃ. 9.12). Проверяем заданные условия последовательно. Первым проверим условие x £ 0 Рё, если РѕРЅРѕ выполняется, то вычислим y:= –x. Если первое условие РЅРµ выполняется, то, следовательно, x > 0, Рё надо проверить следующее условие, x £ 3. Часть второго условия 0 < x можно РЅРµ проверять, так как, если дело дошло РґРѕ проверки этого условия, то заведомо 0 < x. Если условие x £ 3 выполняется, то вычислим y:= 0, иначе 3 < x, Рё проверяется условие x £ 5, проверка 3 < x исключается. Если действительно x £ 5, то вычисляем y:= x–3, Р° иначе 5 < x Рё вычисляем y:= 2, исключая проверку этого последнего условия. □

Рис. 9.12. Алгоритм вычисления значения функции
по заданному графику

Пример 9.6. Вычислить РєРѕСЂРЅРё квадратного уравнения ax2 + bx + c = 0, a ¹ 0, РІ области действительных чисел. Р’ зависимости РѕС‚ значения дискриминанта D = b2 - 4ac возможны три случая:

1) квадратное уравнение не имеет действительных корней, если D < 0;

2) квадратное уравнение имеет два действительных равных корня, если D = 0: x1 = x2 = -b/2a;

3) квадратное уравнение имеет два действительных различных корня, если D > 0:

Схема алгоритма приведена на рис. 9.13. Алгоритм содержит сложное ветвление, являющееся композицией двух простых ветвлений.

Рис. 9.13. Алгоритм решения квадратного уравнения

Рљ операндам вещественного типа РЅРµ следует применять операцию отношения В«=В» (равно), условие может РЅРµ выполняться РёР·-Р·Р° неточного представления вещественных чисел РІ памяти Р­Р’Рњ Рё неизбежных ошибок округления РїСЂРё вычислениях. Р’ алгоритме отношение D = 0 заменено отношением |D| < e, РіРґРµ e – допустимая погрешность округления. □

Пример 9.7. Даны три числа а, b, с. Определить, имеется ли среди них хотя бы одна пара взаимно-обратных чисел.

Числа Р±СѓРґСѓС‚ взаимно-обратными, если РёС… произведение равно единице. Р’ алгоритме производятся попарные проверки данных чисел. Если искомая пара найдена, выдается ответ «Да». Если же РЅРё РѕРґРЅР° проверка РЅРµ выявит пары взаимно-обратных чисел, выдается ответ «Нет». Алгоритм изображен РЅР° СЂРёСЃ. 9.14, Р°. Этот алгоритм верно решает задачу, РЅРѕ РЅРµ является структурным. Алгоритм легко преобразовать Рє структурному РІРёРґСѓ, если продублировать блок печати «Да» Рё вывести РїСЂРё этом найденные числа (СЂРёСЃ. 9.14, Р±). Дублирование блоков – распространенный прием приведения алгоритмов СЃ ветвлениями Рє структурному РІРёРґСѓ. Можно применить РґСЂСѓРіРѕР№ СЃРїРѕСЃРѕР± - введение сложных условий (СЂРёСЃ. 9.14, РІ). □

Рис. 9.14. Алгоритм поиска взаимно-обратных чисел

Циклы

Вычислительные процессы с многократным повторением однотипных вычислений/действий для различных значений входящих величин/данных называются циклическими, повторяемые участки вычислений – циклами, изменяющиеся в цикле величины – переменными цикла. Для организации циклов в алгоритмах необходимо предусмотреть (рис. 9.15):

- подготовку цикла – задание начальных значений переменным цикла перед первым его выполнением;

- тело цикла – вычислении/действия, повторяемые в цикле для различных значений переменных цикла;

- модификацию/изменение значений переменных цикла перед каждым новым его повторением;

- управление циклом – проверку условия продолжения/окончания цикла и переход на повторение цикла или его окончание.

Рис. 9.15. Общие схемы циклического алгоритма

В зависимости от того, где осуществляется проверка условия продолжения или окончания цикла, последний относят к виду:

- цикла с предусловием, когда цикл начинается с проверки условия продолжения цикла (рис. 9.15, а);

- цикла с постусловием, когда условие проверяется после выполнения тела цикла (рис. 9.15, б).

Наиболее наглядным примером циклического вычислительного процесса является задача табулирования функции: вычисления значений функции y = f(x) для значений аргумента x, изменяющихся от начального x0 до конечного xn с постоянным шагом hx (рис. 9.16). Здесь многократно повторяемые действия (тело цикла) – это вычисление значения функции f(x) для очередного значения аргумента x и вывод полученного результата на печать; переменная цикла – переменная x. Цикл выполняется для значений x, равных x0, x0 + hx, x0 + 2hx, ..., xn. Для модификации переменной x в цикле её значение надо увеличивать на значение шага: x := x + hx. Для управления циклом можно использовать структуру цикла как с предусловием, где x <= xn – условие продолжения цикла (рис. 9.16, а), так и с постусловием, где x > xn – условие окончания цикла (рис. 9.16, б).

Рис. 9.16. Общие схемы алгоритма табулирования функции

Алгоритмы табулирования функции с пред- и постусловием дают, вообще говоря, одинаковый результат. Но тело цикла с предусловием в определенной ситуации может не выполниться ни разу, а тело цикла с постусловием обязательно выполняется хотя бы один раз.

Рассмотрим случай, когда нижняя граница x0 переменной x превышает верхнюю xn. В этой ситуации цикл не должен выполняться ни разу. Поэтому в задаче табулирования функции лучше использовать цикл с предусловием, цикл же с постусловием может дать неверный результат. Приведем пример целесообразного использования цикла с постусловием.

Пример 9.8. Составим алгоритм вычисления суммы всех целых чисел, вводимых с терминала до тех пор, пока не будет введен нуль.

Накопление СЃСѓРјРјС‹ S будем осуществлять РІ цикле путем прибавления очередного введенного числа k Рє СЃСѓРјРјРµ всех предыдущих: S := S + k. Перед началом цикла значение переменной S обнулим: S := 0. Проверка условия окончания цикла возможна лишь после РІРІРѕРґР° хотя Р±С‹ РѕРґРЅРѕРіРѕ числа, поэтому лучше использовать цикл СЃ постусловием. Алгоритм вычисления РёСЃРєРѕРјРѕР№ СЃСѓРјРјС‹ представлен РЅР° СЂРёСЃ. 9.17. □

Рис. 9.17. Алгоритм вычисления суммы вводимых чисел

Помимо циклов с пред- и постусловием принято различать циклы с заранее неизвестным и известным числом повторений. Примером цикла первого типа могут служить алгоритм вычисления суммы (пример 9.8) и алгоритм Евклида. Примером цикла второго типа – алгоритм табулирования функции, где число повторений цикла Nx определяется как

Nx = [(xn – x0)/hx] + 1,

где квадратные скобки [ ] означают целую часть числа.

В циклах с известным числом повторений всегда можно выделить переменную, определяющую число повторений цикла, значение которой изменяется по заданному закону, например, от начального до конечного с постоянным шагом. Такая переменная используется для управления циклом: в условии окончания цикла осуществляется сравнение текущего значения переменной с заданным порогом. Эту переменную именуют параметром цикла, а сам цикл - циклом с параметром.

Для схемного представления цикла с параметром используют специальную управ ляющую структуру с блоком модификации (рис. 9.18), где указывают закон изменения параметра цикла. Например, в задаче табулирования функции y = f(x) параметром цикла является переменная x, закон изменения которой можно представить в виде x = x0 (hx) xn.

Схема цикла с параметром для табулирования функции одной переменной приведена на рис. 9.18. На схеме вход 1 в блок i – первоначальный вход в цикл, вход 2 – очередное повторение цикла, выход 3 – окончание цикла.

Рис. 9.18. Схема цикла с параметром

Блок модификации включает в себя подготовку цикла (x := x0), изменение параметра цикла при его очередном повторении (x := x + hx), управление циклом – проверку условия его продолжения (x < xn) и переход на продолжение или окончание цикла. При этом явно выделено тело цикла. Проверка условия x < xn проводится перед каждым, в том числе первым, выполнением цикла, как в цикле с предусловием. И если начальное значение параметра цикла больше конечного, то цикл не выполняется ни разу.

Для записи цикла с параметром в языках программирования существует специальный оператор – оператор цикла с параметром.

Пример 9.9. Составим алгоритм табулирования сложной функции, приведенный на рис. 9.10, используя структуру цикла с параметром. Алгоритм представлен на рис. 9.19. Тело цикла в этом алгоритме представляет собой композицию двух вложенных структур ветвления и структуры следования.

Р’ схеме алгоритма РІ качестве параметра цикла может выступать переменная любого типа. РџСЂРё реализации этой структуры РІ различных языках программирования синтаксис оператора цикла СЃ параметром может РЅРµ допускать использование параметра цикла вещественного типа, как, например, РІ языке Паскаль. РўРѕРіРґР° необходимо введение дополнительной переменной целого типа, определяющей количество значений x, y Рё используемой РІ качестве параметра цикла. □

Рис. 9.19. Алгоритм табулирования сложной функции

Пример 9.10. Вычислить степень Y = an действительного числа a СЃ натуральным показателем n. Воспользоваться для вычислений следующей формулой: an = a × a × вЂ¦× a – n раз.

Компактно произведение может быть записано в виде

Для вычисления Y организуем цикл СЃ параметром i, РІ котором будем накапливать РёСЃРєРѕРјРѕРµ произведение РїРѕ следующему правилу: РґРѕ начала цикла положим Y = 1, Р° РІ цикле будем домножать n раз накопленное ранее произведение РЅР° a, то есть Y := YВ·a. Алгоритм представлен РЅР° СЂРёСЃ. 9.20. □

Пример 9.11. Вычислим сумму квадратов всех целых чисел из заданного интервала [m, n]. В компактной форме записи:

Для вычисления указанной СЃСѓРјРјС‹ организуем цикл СЃ параметром, РІ котором будем n раз вычислять значение очередного слагаемого y := i2 Рё накапливать РёСЃРєРѕРјСѓСЋ СЃСѓРјРјСѓ S := S + y. До начала цикла положим S := 0. Алгоритм приведен РЅР° СЂРёСЃ. 9.21. □

Рис. 9.20. Алгоритм вычисления конечного произведения Рис. 9.21. Алгоритм вычисления конечной суммы

Пример 9.12. Определим, какое количество точек (x, y) из заданного множества x = x0 + ihx; y = y0 + ihy; i = 0, 1, ..., 20, находится в каждой из заштрихованных областей D1 и D2, включая их границы (рис. 9.22).

Пример иллюстрирует цикл с несколькими переменными цикла. Число анализируемых точек определяется количеством значений переменной i. Организуем цикл с параметром i, в котором будем изменять значения переменных x, y и для каждой очередной пары (x, y) проверять условия её принадлежности к одной из заданных областей.

Рис. 9.22. Области определения

Условие попадания точки (x, y) РІ область D1 – окружность радиусом 2 СЃ центром РІ точке (5, 4): (x - 5)2 + (y - 4)2 £ 4.

Условие попадания точки (x, y) РІ область D2 – окружность радиусом 3 СЃ центром РІ точке (-5, -4): (x + 5)2 + (y + 4)2 £ 9.

Для проверки условий Рё подсчета количества KolD1, KolD2 точек, попавших РІ каждую РёР· областей, используем структуры сокращенного ветвления. Перед циклом надо задать переменным РёС… начальные значения (СЂРёСЃ. 9.23). □

Итерационные циклы

Среди циклов с неизвестным числом повторений большое место занимают циклы, в которых в процессе повторения тела цикла образуется последовательность значений a1, a2, ..., an, ..., сходящаяся к некоторому пределу a:

Каждое новое значение an в такой последовательности является более точным приближением к искомому результату a. Циклы, реализующие такую последовательность приближений/итераций, называют итерационными.

В итерационных циклах условие окончания цикла основывается на свойстве безграничного приближения значений an к искомому пределу с увеличением n. Итерационный цикл заканчивают, если для некоторого значения n выполняется условие

|an – an–1| £ e,

где e – допустимая погрешность вычислений. При этом результат отождествляют со значением an, то есть считают, что an = a.

Рис. 9.23. Алгоритм подсчета числа точек,
принадлежащих заданным областям

Пример 9.13. Составим алгоритм вычисления с заданной погрешностью e, используя следующее рекуррентное соотношение:

yn = yn-1 - (x/yn-1 - yn-1)/2; y1 = x/2.

Условием окончания данного итерационного цикла будет условие |yn – yn–1| £ e. Для его проверки необходимо иметь РґРІР° приближения: текущее yn Рё предыдущее yn-1. Алгоритм можно упростить, если ввести вспомогательную переменную d = yn - yn-1 = (x/yn-1 - yn-1)/2 Рё использовать ее РІ условии окончания цикла: | d | £ e. Для проверки такого условия достаточно иметь лишь РѕРґРЅРѕ приближение, которое обозначим через y.

Алгоритм вычисления квадратного РєРѕСЂРЅСЏ представлен РЅР° СЂРёСЃ. 9.23. Для организации итерационного процесса использована структура цикла СЃ постусловием. □

Рис. 9.23. Алгоритм вычисления квадратного корня

Вложенные циклы

В практике алгоритмизации часто встречаются задачи, при решении которых необходимо проектировать алгоритмы с несколькими циклами. Если в теле цикла содержится один или несколько других циклов, то такие циклы называют вложенными. Цикл, содержащий в себе другой цикл, называют внешним. Цикл, содержащийся в теле другого цикла, называют внутренним.

Выполняются вложенные циклы следующим образом. Сначала при фиксированных начальных значениях переменных внешнего цикла полностью выполнится внутренний цикл и его переменные «пробегут» все свои значения. Затем переменные внешнего цикла примут следующие значения и, если условие окончания внешнего цикла не будет достигнуто, снова полностью выполнится внутренний цикл и его переменные опять «пробегут» все свои значения и т. д. до тех пор, пока не выполнится условие окончания внешнего цикла.

Пример 9.14. Составим алгоритм табулирования сложной функции двух переменных:

для x = x0(hx) xn и y = y0(hy) yn.

Вычисление значений функции z для всех различных пар (x, y) необходимо организовать следующим образом. Вначале при фиксированном значении одного из аргументов, например, при x = x0, вычислить значения z для всех заданных y: y0, y0 + hy, y0 + 2hy, ..., yn. Затем, изменив значение x на x0 + hx, вновь перейти к полному циклу изменения переменной y. Данные действия повторить для всех x: x0, x0 + hx, x0 + 2hx, ..., xn.

Для записи алгоритма необходима структура вложенных циклов, например, с параметром: внешнего – с параметром x и внутреннего – с параметром y. В данной задаче внешний и внутренний циклы можно поменять местами, при этом изменится только порядок изменения аргументов.

Общее количество значений z равно Nz = NxּNy, РіРґРµ

Nx = [(xn – x0)/hx] + 1, Ny = [(yn – y0)/hy] + 1.

Алгоритм табулирования функции, выполненный по технологии нисходящего проектирования, представлен на рис. 9.25.

Рис. 9.25. Алгоритм табулирования функции двух переменных

РќР° первом этапе составлена укрупненная схема решения задачи СЃ выделением операции РІРІРѕРґР° исходных данных Рё структуры вложенных циклов. РќР° втором этапе раскрывается тело внутреннего цикла как композиция структур ветвления. □

Пример 9.15. Найти совершенное число в интервале [2, n]. Совершенное число равно сумме всех своих делителей, включая единицу. Например, 28 – совершенное число, так как 28 = 1 + 2 + 4 + 7 + 14.

В алгоритме для каждого целого k из заданного интервала будем определять сумму S всех его делителей и сравнивать значения S и k. Если они равны, то анализируемое k есть искомое совершенное число, надо его вывести и закончить поиск, в противном случае, перейти к следующему целому числу из заданного интервала.

Для реализации такого алгоритма необходима структура вложенных циклов: внешнего, для просмотра заданного интервала, и внутреннего, для вычисления суммы (рис. 9.26, а). Построенный алгоритм не является структурированным. Рассмотрим один из способов приведения циклического алгоритма к структурному виду. Внешний цикл имеет два условия окончания: исчерпание всех целых чисел из заданного интервала и выполнение равенства k = S. В зависимости от того, какое условие привело к окончанию цикла, необходимо предпринять различные действия. Объединим оба условия окончания цикла в одно: k > n или k = S. Для принятия окончательного решения после завершения цикла проверим, какое же условие привело к его окончанию (рис. 9.26, б).

Рис. 9.26. Алгоритм поиска совершенного числа

Можно структурировать алгоритм иначе: в цикле с параметром k ввести дополнительную переменную Pr, установив до цикла Pr = 0. Как только совершенное число будет найдено, присвоить Pr значение этого числа. Окончательное решение в этом случае принимается уже на основании анализа признака Pr.

Структура внутреннего цикла для вычисления СЃСѓРјРјС‹ S раскрывается РЅР° втором этапе детализации алгоритма. Поскольку РІСЃРµ числа делятся РЅР° единицу, то сначала устанавливается S = 1. Р’ цикле СЃ параметром i, изменяющимся РѕС‚ 2 РґРѕ [k/2], суммируются РІСЃРµ делители числа k. Р’ интервале РѕС‚ [k/2]+1 РґРѕ k–1 РЅРµ может быть делителей числа k. □

Вспомогательные алгоритмы

При нисходящем проектировании алгоритма решения сложной задачи исходную задачу разбивают на более простые подзадачи. Каждой такой подзадаче соответствует функционально законченная часть алгоритма. Если оформить эту часть алгоритма в виде самостоятельной алгоритмической единицы со своими входными и выходными данными и, таким образом, что к ней будут возможны многократные обращения (ссылки) из основного алгоритма, то такую алгоритмическую единицу можно назвать вспомогательным или подчиненным алгоритмом (в программировании – подпрограмма).

Если для какой-то подзадачи уже известен алгоритм ее решения, то он может быть включен в состав вновь разрабатываемого алгоритма в качестве вспомогательного.

Если в алгоритме или в разных алгоритмах встречаются фрагменты, одинаковые по выполняемым действиям и различающиеся только значениями обрабатываемых данных, то такого рода фрагменты могут быть оформлены в виде отдельного алгоритма. В соответствующих местах основного алгоритма будут осуществляться лишь обращения к ним. Это позволяет сократить объем и улучшить структуру всего алгоритма в целом.

При использовании вспомогательных алгоритмов возникают вопросы их оформления (таким образом, чтобы в дальнейшем можно было ссылаться на них из других алгоритмов) и техники включения в основные алгоритмы в процессе исполнения последних.

В схемах алгоритмов полная формализация в оформлении подчиненных алгоритмов не производится. Однако установлены некоторые общие правила их оформления. Для подчиненного алгоритма определяется его имя, входные и выходные данные. В блок-схеме в блоке начала указывается имя алгоритма и имена его входных величин – исходных данных, а в блоке конца указываются имена выходных величин – результатов. Переменные, перечисленные в блоках начала и конца, называются формальными параметрами. Их введение необходимо для того, чтобы при многократных вызовах подчиненного алгоритма можно было задавать различные значения исходных данных, а после его исполнения воспользоваться полученными результатами.

В качестве примера рассмотрим алгоритм вычисления степени y := an с натуральным показателем n (см. рис. 9.20). Оформим его как вспомогательный алгоритм. На рис. 9.27 приведена схема вспомогательного алгоритма, его имя – Step, его входные параметры – n, a, выходной параметр – y.

Рис. 9.27. Вспомогательный алгоритм вычисления степени

Вызов вспомогательного алгоритма (ссылка из основного алгоритма) осуществляется с помощью специального блока (см. табл. 9.2). В блоке вызова вспомогательного алгоритма указываются его имя и список фактических параметров: конкретных значений и имен исходных данных и имен вычисляемых результатов, которые должны быть подставлены вместо формальных параметров при исполнении вспомогательного алгоритма. Количество и порядок формальных и фактических параметров должны совпадать.

Далее рассмотрим алгоритм вычисления степени z = xk, x ¹ 0, СЃ целым показателем k, пользуясь следующим определением:

Алгоритм вычисления z = xk построим, используя вспомогательный алгоритм Step вычисления степени с натуральным показателем. Схема алгоритма приведена на рис. 9.28.

Ссылка на вспомогательный алгоритм Step производится дважды: с фактическими параметрами k, x, z при k > 0 и с фактическими параметрами -k, 1/x, z при k < 0. Исполняется вспомогательный алгоритм Step один раз в зависимости от введенного в основной программе значения k.

После выполнения совокупности действий, предусмотренных в Step, осуществляется возврат в основной алгоритм к блоку вывода, следующему за блоком обращения к вспомогательному алгоритму.

Рис. 9.28. Алгоритм вычисления степени с целым показателем

Очень важно понимать суть и механизм замены формальных параметров фактическими. Формальные параметры – это переменные, формально присутствующие во вспомогательном алгоритме и определяющие тип и место подстановки фактических параметров. Фактические параметры – это реальные величины основного алгоритма (константы, переменные, выражения), заменяющие при вызове вспомогательного алгоритма его формальные параметры. Над этими величинами и производятся действия, предусмотренные командами вспомогательного алгоритма. Замена формальных параметров фактическими осуществляется по порядку их следования, число и тип формальных и фактических параметров должны совпадать.


567891011121314151617181920

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...