В ы с ш е е п р о ф е с с и о н а л ь н о е о б р а з о в а н и е информатика и программироВание осноВы информатики
жүктеу/скачать 4,7 Mb. Pdf көрінісі
|
1 Основы информатики
| 9.6.6. вспомогательные алгоритмы
При нисходящем проектировании алгоритма решения сложной задачи исходную задачу разбивают на более простые подзадачи. Каж- дой такой подзадаче соответствует функционально законченная часть алгоритма. Если оформить эту часть алгоритма в виде самостоятельной алго- ритмической единицы со своими входными и выходными данными и таким образом, что к ней будут возможны многократные обращения (ссылки) из основного алгоритма, то такую алгоритмическую едини- цу можно назвать вспомогательным или подчиненным алгоритмом (в программировании — подпрограмма). Если для какой-то подзадачи уже известен алгоритм ее решения, то он может быть включен в состав вновь разрабатываемого алгорит- ма в качестве вспомогательного. Если в алгоритме или в разных алгоритмах встречаются фрагмен- ты, одинаковые по выполняемым действиям и различающиеся толь- ко значениями обрабатываемых данных, то такого рода фрагменты могут быть оформлены в виде отдельного алгоритма. В соответствую- щих местах основного алгоритма будут осуществляться лишь обра- щения к ним. Это позволяет сократить объем и улучшить структуру всего алгоритма в целом. При использовании вспомогательных алгоритмов возникают во- просы их оформления (таким образом, чтобы в дальнейшем можно было ссылаться на них из других алгоритмов) и техники включения в основные алгоритмы в процессе исполнения последних. В схемах алгоритмов полная формализация в оформлении под- чиненных алгоритмов не производится. Однако установлены неко- торые общие правила их оформления. Для подчиненного алгоритма определяется его имя, входные и выходные данные. В блок-схеме в блоке начала указывается имя алгоритма и имена его входных вели- чин — исходных данных, а в блоке конца указываются имена выход- ных величин — результатов. Переменные, перечисленные в блоках начала и конца, называются формальными параметрами. Их введение необходимо для того, чтобы при многократных вызовах подчинен- ного алгоритма можно было задавать различные значения исходных данных, а после его исполнения воспользоваться полученными ре- зультатами. В качестве примера рассмотрим алгоритм вычисления степени y : = a n с натуральным показателем n (см. рис. 9.20). Оформим его как вспомогательный алгоритм. На рис. 9.27 приведена схема вспомога- 145 тельного алгоритма: его имя — Step, его вход- ные параметры — n, a, выходной параметр — y. Вызов вспомогательного алгоритма (ссыл- ка из основного алгоритма) осуществляется с помощью специального блока (см. табл. 9.2). В блоке вызова вспомогательного алгоритма указываются его имя и список фактических параметров: конкретных значений и имен ис- ходных данных и имен вычисляемых резуль- татов, которые должны быть подставлены вместо формальных параметров при исполне- нии вспомогательного алгоритма. Количество и порядок формальных и фактических пара- метров должны совпадать. Рис. 9.27. Вспомогательный алгоритм вычисления степени Рис. 9.28. Алгоритм вычисления степени с целым показателем Далее рассмотрим алгоритм вычисления степени z = x k , x ≠ 0 с целым показателем k, пользуясь следующим определением: x k x k x k k k k = = > < - 1 0 0 1 0 , ; , ; / , . если если если Алгоритм вычисления z = x k построим, используя вспомогатель- ный алгоритм Step вычисления степени с натуральным показателем. Схема алгоритма приведена на рис. 9.28. Ссылка на вспомогательный алгоритм Step производится дважды: с фактическими параметрами k, x, z при k > 0 и с фактическими параметрами -k, 1/x, z при k < 0. Исполняется вспомогательный алгоритм Step один раз в зависимости от введенного в основной про- грамме значения k. После выполнения совокупности действий, предусмотренных в Step, осуществляется возврат в основной алгоритм к блоку вывода, следующему за блоком обращения к вспомогательному алгоритму. Очень важно понимать суть и механизм замены формальных па- раметров фактическими. Формальные параметры — это перемен- ные, формально присутствующие во вспомогательном алгоритме и определяющие тип и место подстановки фактических параметров. Фактические параметры — это реальные величины основного ал- горитма (константы, переменные, выражения), заменяющие при вызове вспомогательного алгоритма его формальные параметры. Над этими величинами и производятся действия, предусмотренные ко- мандами вспомогательного алгоритма. Замена формальных параме- тров фактическими осуществляется по порядку их следования, число и тип формальных и фактических параметров должны совпадать. |