Что такое вспомогательный алгоритм процедура
Что такое вспомогательный алгоритм процедура
Вспомогательные алгоритмы создаются, когда возникает необходимость разбиения задачи на ряд более простых задач или когда есть необходимость многократного использования одного и того же набора действий в одном или разных алгоритмах.
1. Спеть 1-й куплет.
2. Спеть припев.
3. Спеть 2-й куплет.
4. Спеть припев.
5. Спеть 3-й куплет.
6. Спеть припев.
Действия, объединенные в пункт «спеть припев», трижды повторяются. Таким образом, этот алгоритм содержит набор повторяющихся одинаковых действий.
Пример 2: Рассмотрим следующую задачу. Пусть требуется составить программу, по которой Кенгуренок напишет на экране четырехзначное число 1919.
В таком случае программа решения поставленной задачи разделяется на основную программу (основной алгоритм) и процедуры (вспомогательные алгоритмы). Каждая процедура должна иметь свое уникальное имя.
Ее формат, т.е. общий вид, следующий:
Метод последовательной детализации
Использованный нами подход облегчает программирование сложных задач. Задача разбивается на более простые подзадачи. Решение каждой оформляется в виде вспомогательного алгоритма, а основной алгоритм организует связку между ними.
Метод программирования, при котором сначала пишется основная программа, в ней записываются обращения к пока еще не составленным подпрограммам, а потом описываются эти подпрограммы, называется методом последовательной (пошаговой) детализации . Причем количество шагов детализации может быть гораздо большим, чем в нашем примере, поскольку сами подпрограммы могут содержать внутри себя обращения к другим подпрограммам.
Сборочный метод
Возможен и другой подход к построению сложных программ: первоначально оставляется множество подпрограмм, которые могут понадобиться при решении задачи, а затем пишется основная программа, содержащая обращения к ним. Подпрограммы могут быть объединены в библиотеку подпрограмм и сохранены в долговременной памяти компьютера. Такую библиотеку можно постепенно пополнять новыми подпрограммами.
Например, если для управления графическим исполнителем создать библиотеку процедур рисования всех букв и цифр, то программа получения любого текста будет состоять из команд обращения к библиотечным процедурам.
Информатика. 10 класс (Повышенный уровень)
§ 7. Понятие вспомогательного алгоритма
7.1. Вспомогательные алгоритмы
Вспомогательный алгоритм — алгоритм, который можно использовать в других алгоритмах, указав его имя и, если необходимо, значения параметров. Вспомогательный алгоритм, записанный на языке программирования, называют подпрограммой.
Основные преимущества использования подпрограмм:
1. Разбиение комплексной программной задачи на простые шаги (декомпозиция). Это позволяет распределить решение одной задачи между различными людьми.
2. Уменьшение повторяющегося кода.
3. Многократное использование кода в других программах, в том числе и другими программистами.
4. Сокрытие деталей реализации от пользователей подпрограммы.
Перед тем как использовать функцию, ее нужно описать. Описание функции включает объявление и определение функции.
Объявление функции (пример 7.1) включает в себя заголовок функции, заканчивающийся точкой с запятой и включающий:
Функции могут быть с параметрами или без параметров. Если функция не имеет параметров, то наличие круглых скобок после имени функции обязательно.
Определение функции состоит из заголовка функции (без точки с запятой) и тела функции, заключенного в фигурные скобки. В нем содержатся команды языка, реализующие вспомогательный алгоритм (пример 7.2).
При вызове функции (пример 7.3) указывается ее имя и параметры, необходимые для вычислений. Эти параметры называют фактическими параметрами.
В описании функции задается список формальных параметров. Каждый параметр, описанный в этом списке, является локальным по отношению к описываемой функции, т. е. на него можно ссылаться по его имени из данной подпрограммы, но не из основной программы или другой функции.
Переменные, значения которых должны быть известны во всех функциях, являются глобальными и описываются до описания функций. Если переменная описана между описаниями функций, то ее значение будет глобальным для всех функций, описанных ниже, но неизвестным для функций, описанных выше.
Необходимость оптимизации программ по объему занимаемой памяти привела к появлению подпрограмм. Подпрограммы позволили не повторять в программе идентичные блоки кода, а описывать их однократно и вызывать по мере необходимости.
Использование подпрограмм позволяет повысить надежность кода программы. Подпрограммы обычно имеют небольшой размер, поэтому найти и исправить в них ошибки проще, нежели в большой программе.
Использование подпрограмм гарантирует относительную автономность модификации программы: если нужно что-либо изменить в программе, переделывать придется не всю программу, а только некоторые подпрограммы.
Пример 7.1. Объявление функций.
int kol _ cifr ( int n );
double plos_treug ( double a, double h );
Что такое вспомогательный алгоритм процедура
Пример 1. Предположим, что в нескольких местах программы требуется выводить на экран сообщение об ошибке: Ошибка программы. Это можно сделать, например, так:
вывод «Ошибка программы» write (‘Ошибка программы’);
Конечно, можно вставить этот оператор вывода везде, где нужно вывести сообщение об ошибке. Но тут есть две сложности. Во-первых, при этом строка-сообщение будет храниться в памяти много раз. Во-вторых, если мы задумаем поменять текст сообщения, нужно будет искать эти операторы вывода по всей программе. Для таких случаев в языках программирования предусмотрены процедуры — вспомогательные алгоритмы, которые выполняют некоторые действия.
1.2. Определение ВА
Можно ли взять определения из предыдущего пункта из теории за 5-9 класс?
1.3. Оформление процедур
в школьном алгоритмическом языке и в Паскале
вывод ‘Ошибка программы’
writeln(‘ Ошибка программы ‘)
В школьном алгоритмическом языке процедура оформляется точно так же, как и основной алгоритм, но размещается после основной программы.
Как мы видели, использование процедур сокращает код, если какие-то операции выполняются несколько раз в разных местах программы. Кроме того, иногда большую программу разбивают на несколько процедур для удобства, оформляя в виде процедур отдельные этапы сложного алгоритма. Такой подход делает всю программу более понятной.
1.4. Процедура с параметрами
Процедура Error при каждом вызове делает одно и то же. Более интересны процедуры, которым можно передавать параметры (аргументы) — дополнительные данные, которые изменяют выполняемые действия.
Предположим, что в программе требуется многократно выводить на экран запись целого числа (0..255) в 8-битном двоичном коде. Старшая цифра в такой записи — это частное от деления числа на 128. Далее возьмём остаток от этого деления и разделим на 64 — получается вторая цифра и т. д. Алгоритм, решающий эту задачу для переменной п, можно записать так:
Писать такой цикл каждый раз, когда нужно вывести двоичное число, очень утомительно. Кроме того, легко сделать ошибку или опечатку, которую будет сложно найти. Поэтому лучше оформить этот вспомогательный алгоритм в виде процедуры. Но этой процедуре нужно передать значение параметра — число для перевода в двоичную систему. Программа получается такой:
алг printBin (цел n 0)
Основная программа содержит всего одну команду — вызов процедуры printBin для значения 99. В заголовке процедуры в скобках записывают тип и внутреннее имя параметра (т. е. имя, по которому к нему можно обращаться в процедуре). Значение параметра, переданное из вызывающей программы в процедуру (в этом примере — число 99), обычно называют аргументом.
В школьном алгоритмическом языке запрещено изменять параметры процедуры внутри процедуры, поэтому мы назвали параметр п0, а в начале процедуры скопировали его значение в переменную п.
Параметров может быть несколько, в этом случае они перечисляются в заголовке процедуры через запятую (в школьном алгоритмическом языке) или точку с запятой (в Паскале). Например, процедуру, которая выводит экран среднее арифметическое двух целых чисел, можно записать так:
procedure printSred (a: integer; b: integer);
Если несколько параметров одного типа стоят в списке один за другим, их можно определить списком:
procedure printSred(a, b: integer);
Напишем процедуру, которая меняет местами значения двух переменных. Проще всего для этого использовать третью переменную (пока напишем программу только на Паскале):
procedure Swap(a, b: integer);
После запуска этой программы обнаружится, что значения переменных х и у остались прежними: на экран будет выведено: 2 3. Дело в том, что эта процедура работает с копиями переданных ей параметров. Это значит, что процедура Swap создаёт в памяти временные локальные переменные с именами а и b и копирует в них переданные значения переменных х и у основной программы. Поэтому и все перестановки в нашей программе были сделаны именно с копиями, а значения переменных х и у не изменились. Такая передача параметров называется передачей по значению.
Чтобы решить проблему, нужно явно сказать, чтобы процедура работала с теми же ячейками памяти, что и основная программа. Для этого в Паскале в заголовке процедуры перед именем изменяемого параметра пишут ключевое слово var :
procedure Swap ([ var la, b: integer);
Теперь процедура решает поставленную задачу: на выходе мы увидим: 3 2, что и требовалось. В подобных случаях говорят, что параметры передаются по ссылке, а не по значению. Это означает, что фактически в процедуру передаётся адрес переменной и можно изменять значение этой переменной, записывая новые данные по этому адресу.
В школьном алгоритмическом языке все параметры делятся на аргументы (исходные данные, обозначаются арг) и результаты (ключевое слово рез, эти значения процедура передаёт вызывающей программе). По умолчанию (если не указано иначе) все параметры считаются аргументами. Поэтому два следующих заголовка равносильны:
В нашем случае параметры процедуры одновременно являются и аргументами, и результатами, поэтому их нужно объявлять с помощью ключевого слова аргрез. Приведём полную программу:
Информатика. 11 класс
Конспект урока
Информатика, 11 класс. Урок № 4.
Тема — Вспомогательные алгоритмы и подпрограммы: правила описания и использования подпрограмм
Перечень вопросов, рассматриваемых в теме: структурное программирование, подпрограммы, формальные параметры, фактические параметры, параметры-значения, параметры-переменные, процедуры, функции, рекурсия.
Глоссарий по теме: структурное программирование, подпрограммы, процедуры, функции, рекурсия.
Основная литература по теме урока:
Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2017
Дополнительная литература по теме урока:
— И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2012
— Андреева Е. В. Программирование — это так просто, программирование — это так сложно. Современный учебник программирования. — М.: МЦНМО, 2015
— Молчанова С. И. Основы программирования. Турбо-Паскаль 7.0 для школьников и абитуриентов. — М.: «Аквариум»; ООО «Фирма «Издательство АСТ», 1999
Теоретический материал для самостоятельного изучения
На одном из прошлых уроков мы упоминали теорему, суть которой заключается в том, что для любой логической задачи можно составить алгоритм, используя лишь три базовых структуры: следование, ветвление и повторение. Эта теорема является одним из ключевых положений структурного программирования, о котором мы с вами сегодня и будем говорить.
Основные принципы структурного программирования заключаются в том, что:
Давайте узнаем, что такое подпрограммы, какими они могут быть и как их использовать.
На прошлом уроке мы рассмотрели один из базовых алгоритмов обработки числовых данных — алгоритм нахождения НОД натуральных чисел.
Вернемся к нему для решения задачи нахождения НОД трех натуральных чисел a, b, c. Для решения воспользуемся следующим математическим фактом: если a, b, c — три натуральных числа, то НОД (a, b, c) = НОД (НОД (a, b), c). Иначе говоря, нужно найти НОД двух величин, а затем НОД полученного значения и третьего числа.
Аналогичным образом можно было решить задачу нахождения НОД четырех, пяти и т. д. чисел. Понятно, что при этом код программы увеличился бы за счет добавления однотипных блоков. А можно ли каким-либо образом сократить запись алгоритма? Давайте разберемся.
В программировании ситуация, когда приходится выполнять одни и те же действия, является весьма типичной. Мы имеем алгоритм, который предназначен для решения подзадачи, выделенной в основной задаче. Выписывать алгоритм для решения подзадачи каждый раз заново в том месте программы, где он встречается, нерационально. Язык программирования Паскаль позволяет выделить любой алгоритм, описывающий подзадачу, и записать его только один раз, дав ему имя, а уже затем использовать его столько раз, сколько необходимо. Такой алгоритм называется подпрограммой и располагается в разделе описания до основной программы.
Подпрограммы подразделяются на процедуры (procedure) и функции (function).
Описание процедуры в Паскале имеет следующий формат:
Оформим в нашем примере в качестве процедуры подпрограмму нахождения НОД двух натуральных чисел.
Теперь разберемся, какая служебная информация находится в круглых скобка рядом с именем процедуры.
Подпрограмма реализует некоторый частный алгоритм, который вызывается в основной программе. Для реализации алгоритма подпрограмме могут понадобиться некоторые данные из основной программы. Обработав эти данные, подпрограмма возвращает результат основной программе, если в этом есть необходимость. Передавать информацию из основной программы в подпрограмму и наоборот мы можем только через переменные, которые носят специальное название — параметры. Именно они и указываются в круглых скобках рядом с именем процедуры.
Переменные, указанные непосредственно в заголовке процедуры, называются формальными параметрами. То, что подставляется вместо них при вызове процедуры в основной программе, называется фактическими параметрами:
Квадратные скобки указывают на то, что список формальных параметров может отсутствовать, т.е. возможна процедура без параметров. Параметры могут быть параметрами-переменными и параметрами-значениями. Параметры-переменные записываются следующим образом:
Параметры-значения указываются так:
Чаще всего параметры-значения служат для работы с входной в процедуру информацией, а параметры-переменные — для работы с выходной информацией.
Вернемся к программе nod1. Наша процедура evklid должна получить на вход две переменные, найти для них НОД и передать его в основную программу. Получаем:
Здесь мы замечаем, что наша процедура evklid дважды вызывается одинаковым образом. Но это нарушает саму идею решения и может привести к неверному ответу. Чтобы исправить эту ошибку, введем формальные параметры, имена которых отличны от фактических:
Теперь рассмотрим другой вариант программы, решающий ту же задачу. В ней используется процедура без параметров.
Чтобы разобраться в этом примере, введем одно важное понятие — область действия описания.
Областью действия описания любого программного объекта (переменной, типа, константы и т. д.) является тот блок, на который это описание распространяется. Если данный блок вложен в другой (подпрограмма), то присутствующие во вложенном блоке описания являются локальными. Они действуют только в пределах внутреннего блока. Описания же, расположенные во внешнем блоке, называются глобальными по отношению к внутреннему блоку. Если глобально описанный объект используется во внутреннем блоке, то на него распространяется внешнее (глобальное) описание.
В программе nod2 переменные x, y, nod1 являются локальными внутри процедуры; переменные a, b, c — глобальные. Однако внутри процедуры переменные a, b, c не используются. Связь между внешним блоком и процедурой осуществляется через параметры.
В программе nod2 все переменные являются глобальными. В процедуре evklid нет ни одной локальной переменной. Здесь обмен значениями между основной программой и процедурой осуществляется через глобальные переменные.
Теперь выясним, что такое подпрограмма-функция. Обычно функция используется в том случае, когда результатом работы подпрограммы должна быть скалярная (простая) величина. Тип результата называется типом функции.
Формат описания функции следующий:
Как и у процедуры, у функции служебная информация содержит список формальных параметров, среди которых могут присутствовать как параметры-значения, так и параметры-переменные. Все это — аргументы функции. Параметры могут вообще отсутствовать, если аргументы передаются глобально.
Программа решения рассмотренной выше задачи с использованием функции будет выглядеть следующим образом:
Сравнивая приведенные выше программы, можно сделать вывод, что программа nod4 имеет определенные преимущества перед другими. Функция позволяет получить результат путем выполнения одного оператора присваивания. Здесь также демонстрируется возможность того, что фактическим параметром при обращении к функции может быть эта же функция.
Среди всевозможных подпрограмм особый интерес представляют так называемые рекурсивные подпрограммы.
Рекурсивная подпрограмма (функция, процедура) — подпрограмма, содержащая в своем описании вызов самой себя.
Пример 1. Как известно, факториал натурального числа определяется следующим образом:
Иначе это можно записать так:
В определении факториала через рекурсию имеется условие n ≤ 1, при достижении которого вызов рекурсии прекращается. Такое условие (оно называется граничным) в рекурсивном определении должно присутствовать обязательно!
Пример 2. Алгоритм вычисления функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n)=F(n–1) +3· F(n–2) при n > 2.
Требуется выяснить, чему равно значение функции F(7).
По условию, F(1) = F(2) = 1.
F(3) = F(2) + 3 · F(1) = 1 + 3 · 1 = 4.
F(4) = F(3) + 3 · F(2) = 4 + 3 · 1 = 7.
F(5) = F(4) + 3 · F(3) = 7 + 3 · 4 = 19.
F(6) = F(5) + 3 · F(4) = 19 + 3 · 7 = 40.
F(7) = F(6) + 3 · F(5) = 40 + 3 · 19 = 97.
Подобные вычисления можно проводить в уме, а их результаты фиксировать в таблице:
И в завершение вспомним задачу вычисления НОД и модифицируем с использованием рекурсивной функции.
Применение рекурсивных методов для решения вычислительных задач не всегда эффективно. В большинстве случаев для решения той же задачи можно построить оптимальный не рекурсивный алгоритм. В то же время существуют задачи не вычислительного содержания, решить которые без использования рекурсии оказывается крайне проблематичным. К числу таких задач относится, например, известная головоломка под названием «Ханойские башни», с которой вы можете познакомиться в дополнительном материале.
Что такое вспомогательный алгоритм процедура
¾ Рисование числа 1919 Семакин 9
Данная задача естественным образом выводит на идею вспомогательного алгоритма. Задание следующее: составить алгоритм рисования числа «1919». Учитель может поступить следующим образом: предложить ученикам написать алгоритм прежними средствами, т. е. используя только три основные команды: шаг, поворот, прыжок. Такое задание, очевидно, не вызовет энтузиазма учеников, поскольку принцип им уже понятен, а писать длинный линейный алгоритм довольно скучно. В этой ситуации вполне возможно самостоятельное «открытие» учениками идеи вспомогательного алгоритма. Обратив внимание на то, что в рисунке дважды присутствуют цифры «1» и «9», ученики могут прийти к идее отдельного описания алгоритмов рисования этих цифр, а затем использования их для получения четырехзначного числа «1919». После обсуждения этой идеи учитель вводит понятие вспомогательного алгоритма и объясняет, как производится его описание и использование. На языке Кенгуренка вспомогательный алгоритм называется процедурой.
Умение использовать вспомогательные алгоритмы необходимо вырабатывать у учеников как можно раньше, уже на примерах линейных алгоритмов. Важнейший прием алгоритмизации и программирования — декомпозиция задачи, т.е. выделение в исходной задаче некоторых более простых подзадач. Алгоритмы решения таких подзадач называются вспомогательными алгоритмами, а реализующие их программы — подпрограммами (процедурами). Таким образом, решение исходной задачи разбивается на несколько алгоритмов: основной алгоритм и вспомогательные алгоритмы. Как правило, в основном алгоритме происходит многократное обращение к вспомогательному алгоритму.
ШАГ ШАГ ПОВОРОТ ШАГ ШАГ ШАГ ШАГ
ШАГ ПОВОРОТ ШАГ ШАГ ПОВОРОТ ШАГ ШАГ ПОВОРОТ
Дано: Исполнитель в т.А
Надо: воспроизвести образец
¾ Алгоритм «Обязанности» Гейн
Представьте себе, что вы находитесь в летнем лагере труда и отдыха, вас назначили дежурным по столовой и вы хотите продумать порядок своих действий. Некоторые обязанности дежурного придётся в течение дня исполнять несколько раз. Например:
Убрать со столов посуду. Вытереть столы. Расставить стулья. Уйти.
Эту последовательность действий предстоит выполнить три раза за дежурство: после завтрака, обеда и ужина. Назовём соответствующий алгоритм «Обязанности», а при написании распорядка дня заменим эти четыре действия одной командой:
Исполнить алгоритм Обязанности.
Тогда распорядок дежурства по столовой примет такой вид:
Прийти в столовую в 7.00.
Накрыть столы к завтраку.
Дождаться окончания завтрака.
Исполнить алгоритм Обязанности.
Прийти в столовую в 13.00.
Накрыть столы к обеду.
Дождаться окончания обеда.
Исполнить алгоритм Обязанности.
Прийти в столовую в 18.00.
Накрыть столы к ужину.
Дождаться окончания ужина.
Исполнить алгоритм Обязанности.
Подобным образом поступают часто, когда при составлении алгоритма возникает необходимость многократного использования одного и того же набора действий. Этот набор действий выделяют в качестве самостоятельного алгоритма и дают ему имя. С этого момента появляется возможность его использования в других алгоритмах, т. е. он становится вспомогательным алгоритмом.
¾ Подготовка реферата макарова 8-9
Представьте себе, что вам предстоит подготовить реферат по какому-либо предмету. При работе над рефератом на компьюте ре часто приходится редактировать текст: исправлять ошибки, копировать и удалять фрагменты текста и т. д. Надеемся, что вы уже знакомы с технологией работой над текстовым документом и его редактирование не вызывает у вас вопросов.
Любая из выполняемых при редактировании операций (ко пирование, вырезание, удаление фрагмента текста и т. д.) пред ставляет собой определенную последовательность действий, то есть алгоритм. Содержание этих алгоритмов благодаря час тому их использованию уже не вызывает вопросов. Стоит понять, что необходимо использовать определенную операцию, например копирование, как руки сами воспроизводят соответ ствующий алгоритм. Таким образом, мозг человека хранит огромное количество ранее определенных алгоритмов, которые используются по мере необходимости при решении различных задач.
Алгоритм, из которого производится вызов вспомогательного алгоритма, получил название основного алгоритма.
¾ Алгоритм «Набор текста песен» макарова 8-9
Например, для набора текста песни, содержащей три куплета с припевом, можно воспользоваться основным алгоритмом под названием * Набор текста песни».
Алгоритм «Набор текста песни»
1. Набрать название песни.
2. Набрать первый куплет.
4. Набрать второй куплет.
5. Скопировать припев.
6. Набрать третий куплет.
7. Скопировать припев. Конец алгоритма
В этом алгоритме многократно встречается слово Скопировать смысл которого вам понятен, так как был определен на начальном этапе обучения технологии работы с текстом.
Здесь слово скопировать является именем алгоритма, определенного ранее, то есть вспомогательного алгоритма. Слово «припев» обозначает конкретный объект, над которым нужно произвести действие копирования.
Рассмотрим, что представляет собой алгоритм копирования, который является вспомогательным по отношению к основному алгоритму «Набор текста песни». Назовем такой вспомогательный алгоритм «Скопировать (объект копирования)».
Алгоритм «Скопировать (объект копирования)»
2. Выбрать команду Правка/Копировать.
3. Указать щелчком мыши место вставки.
4. Выбрать команду Правка/Вставить.
При записи данного вспомогательного алгоритма мы указали его имя и в скобках — название параметра, с которым алгоритм работает. В данном случае параметр один — объект копирования. У параметра «объект копирования» могут быть разные значения. При наборе песни в качестве объекта копирования будет использоваться припев. При рисовании в качестве объекта копирования будет использоваться заранее созданный графический элемент. При создании формулы в качестве объекта копирования может использоваться, например, функция или ранее созданное простое математическое выражение.
После выполнения вспомогательного алгоритма вы возвращаетесь в основной алгоритм для его продолжения.
Вспомогательные алгоритмы используются для решения сложных задач, так как любую сложную задачу можно разбить на более простые и каждую из них оформить в виде вспомогательного алгоритма. В общем случае во вспомогательном алгоритме может быть несколько параметров.
Создание вспомогательных алгоритмов можно поручить разным разработчикам. Разбиение сложного алгоритма на простые части, которые оформляются как вспомогательные, делает его более наглядным и понятным.
¾ Рисование слова «МИР»с помощью исполнителя Чертежник Кушниренко
Составив три алгоритма для рисования букв М, И, Р, можно не только последовательно приказывать ЭВМ выполнять эти алгоритмы, но и задать порядок их выполнения в виде алгоритма:
надо нарисовано слово МИР, перо поднято и расположено в конце слова (начале следующей буквы)
Строки «буква М», «буква И», «буква Р» в записи алгоритма «МИР» —это команды алгоритмического языка, которые означают соответственно
выполнить алгоритм с именем «буква М»,
выполнить алгоритм с именем «буква И»,
выполнить алгоритм с именем «буква Р».
Если теперь поместить в ЭВМ алгоритм «МИР» и алгоритмы «буква М», «буква И», «буква Р» (см. АН), а затем приказать ЭВМ выполнить алгоритм «МИР», то ЭВМ автоматически выполнит сначала алгоритм «буква М», потом — «буква И» и наконец—»буква Р».
ПОНЯТИЯ ОСНОВНОГО И ВСПОМОГАТЕЛЬНОГО АЛГОРИТМОВ.
ВЫЗОВ ВСПОМОГАТЕЛЬНОГО АЛГОРИТМА
Алгоритмы «буква М», «буква И» и «буква Р» в этом примере называются вспомогательными для основного алгоритма «МИР».
ОДИН И ТОТ ЖЕ АЛГОРИТМ МОЖЕТ ВЫСТУПАТЬ
И В РОЛИ ВСПОМОГАТЕЛЬНОГО, И В РОЛИ ОСНОВНОГО
Алгоритм «МИР» ( All ) сам может быть использован как вспомогательный. Например, мы можем составить следующий алгоритм для рисования лозунга «МИРУ МИР»:
дано п epo поднято
надо | нарисован лозунг «МИРУ МИР», перо поднято и расположено в конце лозунга (в начале следующей буквы)
сместиться на вектор (3, 0) |пропуск между словами МИР
В этом примере алгоритм «МИР» является вспомогательным по отношению к алгоритму «МИРУ МИР» и основным по отношению к алгоритму «буква М».
¾ Алгоритм проезда по большому городу Каймин
Решение новых задач мы всегда пытаемся свести к решению уже известных, а решение сложных задач — к решению более простых подзадач. Соответственно в алгоритмах решения сложных задач для решения подзадач могут выделяться вспомогательные алгоритмы, которые служат для их решения. Каждый такой вспомогательный алгоритм описывает способ решения некоторой вспомогательной задачи или даже общий способ решения некоторого класса вспомогательных подзадач.
Типичный пример — алгоритм проезда по большому городу. Рассмотрим задачу проезда в Москве от аэродрома Внуково до Красной площади. Один из способов можно описать следующим алгоритмом с использованием вспомогательных алгоритмов:
¾ Алгоритм рисования индекса 660000 Босова 7
Пример 1. Составить алгоритм рисования почтового индекса города Красноярска — 660000.
Для решения основной задачи (рисования почтового индекса 660000) достаточно «научить» Чертежника рисовать цифру 6 и цифру 0. Для этого алгоритм рисования цифры нужно предварительно оформить в виде процедуры (вспомогательного алгоритма).
1.2. Определения ВА, предлагаемые авторами учебников
1. Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав его имя и, если имеются, значения параметров. Макарова 8-9
2. Алгоритм, по которому решается некоторая подзадача из основной задачи и который, как правило, выполняется многократно, называется вспомогательным алгоритмом.
Вспомогательный алгоритм – это алгоритм решения некоторой подзадачи исходной (основной) задачи. Вспомогательный алгоритм, записанный на языке программирования, называется подпрограммой или процедурой. семакин
3. Вспомогательный алгоритм – алгоритм, целиком используемый в составе другого алгоритма. Босова, Ершов
4. Вспомогательный алгоритм – это набор действий, многократно использующихся в алгоритме, выделенных в качестве самостоятельного алгоритма и имеющих имя. Гейн
6. Для решения каждой подзадачи составляют свою программу на языке программирования, которая называется вспомогательной программой (подпрограммой). Быкадоров 15п 9
7. Вспомогательным называется алгоритм, снабженный таким заголовком, который позволяет вызывать этот алгоритм из других алгоритмов. Любой алгоритм можно сделать вспомогательным: надо лишь снабдить его соответствующим заголовком (т.е. указать название, аргументы и результаты). ВА – мощное и удобное средство, облегчающее решение трудных задач.
8. (Вспомогательные) подпрограммы предназначены для сокращения записи часто встречающихся формул и алгоритмов, текстуально совпадающих или имеющих одну и ту же структуру. Бауэр Гооз
1.3. Обращение к ВА (описание ВА)Босова 9 Семакин 161
1.3.1. Заголовок ВА. Гейн 8
Когда при составлении алгоритма возникает необходимость многократного использования одного и того же набора действий. Этот набор действий выделяют в качестве самостоятельного алгоритма и дают ему имя. С этого момента появляется возможность его использования в других алгоритмах, т. е. он становится вспомогательным алгоритмом.
1.3.2. Команда вызова ВА Босова 9 Гейн.
Набор команд, из которых состоит вспомогательный алгоритм, заменяют одной командой, которая называется командой вызова вспомогательного алгоритма.
Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 2.4):
1. формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2. для заданных входных данных исполняются команды вспомогательного алгоритма;
3. полученные результаты присваиваются переменным с именами фактических результатов;
4. осуществляется переход к следующей команде основного алгоритма.
Босова информатика 9
1.3.3. Общая форма записи ВА:
Записывая вспомогательный алгоритм, кроме названия, следует указывать переменные, служащие аргументами и результатами. Гейн 8
Для различения переменных одинаково обозначенных в основном и вспомогательном алгоритмах договариваются считать, что все обозначения из вспомогательного алгоритма действительны только в пределах этого алгоритма.
1.3.4. Типы переменных
· переменная вещественного типа;
· переменная целого типа;
· передача данных во вспомогательный алгоритм
Есть много различных формальных исполнителей алгоритмов, которые умеют работать с числовыми переменными. Все они оперируют с числами примерно одинаково.
Каждый исполнитель алгоритмов характеризуется прежде всего набором своих допустимых действий. Надо лишь прояснить одно обстоятельство, связанное с тем, что переменные могут принимать не только значение, равное натуральному числу, но и другие значения.
Вспомним, как записывают числа на уроках математики.
Алгоритмы выполнения действий над числами сильно зависят от того, как эти числа записаны. Например, десятичные дроби складываются совсем не так, как обыкновенные. Поэтому формальный исполнитель должен знать, с числами какого вида он будет иметь дело.
В алгоритме редко присутствует запись самих чисел. Обычно в нём фигурируют переменные, которые, словно пустая тара, всегда готовы принять в себя числа на временное хранение. Но никто не хранит подсолнечное масло в бумажных пакетах или сахар в сетках. Каждому виду продукта — свой тип тары. Так же и с переменными: каждому виду чисел — свой тип переменных.
Если формальный исполнитель имеет дело только с одним видом чисел, то можно не указывать тип переменных — и так всё понятно. Обычно исполнители могут работать с не
сколькими видами чисел. Наиболее распространённые из них — это целые числа и вещественные числа (их ещё называют действительными). Поэтому и переменные бывают нескольких типов. Прежде всего используются целые и вещественные переменные.
Приступая к написанию программы, мы обязаны сообщить исполнителю, каков тип используемых в ней переменных. Эту информацию записывают с помощью специальной конструкции, называемой объявлением переменных.
Объявление переменных может, например, выглядеть так:
Переменные объявляются до фигурных скобок, ограничивающих тело алгоритма, программы или подпрограммы. Например:
Стандартные слова вещ и цел, как обычно, подчёркиваются.
Напомним, что переменные в основном алгоритме и во вспомогательном алгоритме могут иметь одинаковые имена. И они вполне могут быть разного типа. Основной алгоритм и вспомогательный алгоритм могли составлять разные люди, и они не обязаны знать или заранее согласовывать, как будут называться переменные в основном алгоритме, откуда будет поставляться информация во вспомогательный алгоритм и как будут именоваться аргументы и результаты вспомогательного алгоритма.
Например, в уже знакомом вам алгоритме нахождения разложения на простые множители переменные можно описать следующим образом:
(*п — исходное число, т — наименьший простой множитель числа п*)
Алгоритм Разложение на простые множители цел: п, т;
(*3десь т — исходное число, an — наименьший простой множитель числа п*)
< Сообщить «Разложения не существует»;
< Вызвать Простой множитель (т, п);
Переменные, фигурирующие в заголовке вспомогательного алгоритма, называют формальными параметрами — они всего лишь сообщают пользователю вспомогательным алгоритмом, сколько переменных требуется для передачи исходных данных и результатов. Разрабатывая алгоритм, полезно прокомментировать, какая именно информация должна храниться в каждой переменной.
Имена переменных (неважно, аргументы это или результаты), которые фигурируют в операторе Вызвать, являются фактическими параметрами. Правила присваивания значений формальным параметрам очень просты.
Перед началом выполнения подпрограммы:
¾ если в подпрограмме есть аргументы, то берётся первая переменная в операторе Вызвать; её содержимое (т. е. значение) присваивается первой переменной после слова арг в заголовке соответствующей подпрограммы;
¾ если в подпрограмме есть второй аргумент, то берётся вторая переменная в операторе Вызвать; её содержимое присваивается второй переменной после слова арг в заголовке соответствующей подпрограммы;
¾ если в подпрограмме есть третий аргумент, то третья переменная присваивается третьей переменной и т. д.
После окончания работы подпрограммы:
¾ если в подпрограмме есть результаты, то берётся первая переменная после слова рез в заголовке соответствующей подпрограммы; её содержимое присваивается следующей переменной, которая осталась после присваивания значений аргументам в операторе Вызвать;
¾ если есть еще результаты, то их значения присваиваются соответствующим переменным.
Количество переменных и их тип в операторе Вызвать должны совпадать с количеством переменных и их типом в заголовке соответствующей подпрограммы.
Таким образом, переменные вася и киса, объявленные дважды в примере описания переменных, именуют совсем разные переменные. Это просто тёзки, имеющие (как и у людей) одно имя. Поскольку мы не видим, как выглядит оператор Вызвать, то очень может быть, что содержимое васи из программы вовсе и не соответствует васе из подпрограммы, как могли некоторые из вас ожидать. Ну а раз переменные разные, ничто не мешает им иметь и разные типы.
Но переменные можно объявить в основном алгоритме, работать с ними во вспомогательном алгоритме. Такие переменные называются глобальными переменными. Например, в алгоритме разложения на простые множители переменные можно описать так:
Делать пока («не делится на т)
Алгоритм Разложение на простые множители
< Сообщить «Разложения не существует»;
< Вызвать Простой множитель (р);
Теперь во вспомогательном алгоритме нет аргументов, есть только результаты. Переменная п здесь является глобальной, она используется как в основном, так и во вспомогательном алгоритме. А переменная т — локальная, она может использоваться только во вспомогательном алгоритме.
Мы могли бы отказаться от описания результатов вспомогательного алгоритма и сделать две глобальные переменные — п и т. Может показаться, что так значительно проще — описывать переменные только в основном алгоритме и ни о чём не думать. Но в этом случае вспомогательный алгоритм теряет всю свою привлекательность. Сложный алгоритм может быть собран из различных вспомогательных алгоритмов, как домик из кубиков. Но это можно легко сделать только в том случае, если вспомогательные алгоритмы не используют глобальных переменных. Ведь может случиться так, что в разных вспомогательных алгоритмах используются переменные с одинаковыми именами или вспомогательный алгоритм может содержать очень большое количество глобальных переменных.
Использование параметров во вспомогательном алгоритме помогает не вникать в то, из чего состоит тело этого вспомогательного алгоритма, а использовать его как уже готовый блок для строительства новых алгоритмов.
алгоритма с указанием
2.3. Блок «предопределённый процесс»
При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 2.3), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — входные данные и результаты.
Фактические параметры указываются в этом блоке, а формальные параметры — в начальном блоке вспомогательного алгоритма.
Вспомогательный алгоритм делает структуру алгоритма более понятной.
Для передачи информации во вспомогательный алгоритм и получения его результатов в команде вызова вспомогательного алгоритма указываются фактические параметры — имена переменных основного алгоритма или арифметические выражения