Для чего нужны вспомогательные алгоритмы кратко
Обновлено: 03.07.2024
Перечень вопросов, рассматриваемых в теме: структурное программирование, подпрограммы, формальные параметры, фактические параметры, параметры-значения, параметры-переменные, процедуры, функции, рекурсия.
Глоссарий по теме: структурное программирование, подпрограммы, процедуры, функции, рекурсия.
Основная литература по теме урока:
Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2017
Дополнительная литература по теме урока:
- И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2012
- Андреева Е. В. Программирование — это так просто, программирование — это так сложно. Современный учебник программирования. — М.: МЦНМО, 2015
Теоретический материал для самостоятельного изучения
На одном из прошлых уроков мы упоминали теорему, суть которой заключается в том, что для любой логической задачи можно составить алгоритм, используя лишь три базовых структуры: следование, ветвление и повторение. Эта теорема является одним из ключевых положений структурного программирования, о котором мы с вами сегодня и будем говорить.
Основные принципы структурного программирования заключаются в том, что:
Давайте узнаем, что такое подпрограммы, какими они могут быть и как их использовать.
На прошлом уроке мы рассмотрели один из базовых алгоритмов обработки числовых данных — алгоритм нахождения НОД натуральных чисел.
Вернемся к нему для решения задачи нахождения НОД трех натуральных чисел a, b, c. Для решения воспользуемся следующим математическим фактом: если a, b, c — три натуральных числа, то НОД (a, b, c) = НОД (НОД (a, b), c). Иначе говоря, нужно найти НОД двух величин, а затем НОД полученного значения и третьего числа.
Аналогичным образом можно было решить задачу нахождения НОД четырех, пяти и т. д. чисел. Понятно, что при этом код программы увеличился бы за счет добавления однотипных блоков. А можно ли каким-либо образом сократить запись алгоритма? Давайте разберемся.
В программировании ситуация, когда приходится выполнять одни и те же действия, является весьма типичной. Мы имеем алгоритм, который предназначен для решения подзадачи, выделенной в основной задаче. Выписывать алгоритм для решения подзадачи каждый раз заново в том месте программы, где он встречается, нерационально. Язык программирования Паскаль позволяет выделить любой алгоритм, описывающий подзадачу, и записать его только один раз, дав ему имя, а уже затем использовать его столько раз, сколько необходимо. Такой алгоритм называется подпрограммой и располагается в разделе описания до основной программы.
Подпрограммы подразделяются на процедуры (procedure) и функции (function).
Описание процедуры в Паскале имеет следующий формат:
Оформим в нашем примере в качестве процедуры подпрограмму нахождения НОД двух натуральных чисел.
Теперь разберемся, какая служебная информация находится в круглых скобка рядом с именем процедуры.
Подпрограмма реализует некоторый частный алгоритм, который вызывается в основной программе. Для реализации алгоритма подпрограмме могут понадобиться некоторые данные из основной программы. Обработав эти данные, подпрограмма возвращает результат основной программе, если в этом есть необходимость. Передавать информацию из основной программы в подпрограмму и наоборот мы можем только через переменные, которые носят специальное название — параметры. Именно они и указываются в круглых скобках рядом с именем процедуры.
Переменные, указанные непосредственно в заголовке процедуры, называются формальными параметрами. То, что подставляется вместо них при вызове процедуры в основной программе, называется фактическими параметрами:
Квадратные скобки указывают на то, что список формальных параметров может отсутствовать, т.е. возможна процедура без параметров. Параметры могут быть параметрами-переменными и параметрами-значениями. Параметры-переменные записываются следующим образом:
Параметры-значения указываются так:
Чаще всего параметры-значения служат для работы с входной в процедуру информацией, а параметры-переменные — для работы с выходной информацией.
Вернемся к программе nod1. Наша процедура evklid должна получить на вход две переменные, найти для них НОД и передать его в основную программу. Получаем:
Теперь рассмотрим другой вариант программы, решающий ту же задачу. В ней используется процедура без параметров.
Чтобы разобраться в этом примере, введем одно важное понятие — область действия описания.
Областью действия описания любого программного объекта (переменной, типа, константы и т. д.) является тот блок, на который это описание распространяется. Если данный блок вложен в другой (подпрограмма), то присутствующие во вложенном блоке описания являются локальными. Они действуют только в пределах внутреннего блока. Описания же, расположенные во внешнем блоке, называются глобальными по отношению к внутреннему блоку. Если глобально описанный объект используется во внутреннем блоке, то на него распространяется внешнее (глобальное) описание.
В программе nod2 переменные x, y, nod1 являются локальными внутри процедуры; переменные a, b, c — глобальные. Однако внутри процедуры переменные a, b, c не используются. Связь между внешним блоком и процедурой осуществляется через параметры.
В программе nod2 все переменные являются глобальными. В процедуре evklid нет ни одной локальной переменной. Здесь обмен значениями между основной программой и процедурой осуществляется через глобальные переменные.
Теперь выясним, что такое подпрограмма-функция. Обычно функция используется в том случае, когда результатом работы подпрограммы должна быть скалярная (простая) величина. Тип результата называется типом функции.
Формат описания функции следующий:
Как и у процедуры, у функции служебная информация содержит список формальных параметров, среди которых могут присутствовать как параметры-значения, так и параметры-переменные. Все это — аргументы функции. Параметры могут вообще отсутствовать, если аргументы передаются глобально.
Программа решения рассмотренной выше задачи с использованием функции будет выглядеть следующим образом:
Сравнивая приведенные выше программы, можно сделать вывод, что программа nod4 имеет определенные преимущества перед другими. Функция позволяет получить результат путем выполнения одного оператора присваивания. Здесь также демонстрируется возможность того, что фактическим параметром при обращении к функции может быть эта же функция.
Среди всевозможных подпрограмм особый интерес представляют так называемые рекурсивные подпрограммы.
Рекурсивная подпрограмма (функция, процедура) — подпрограмма, содержащая в своем описании вызов самой себя.
Пример 1. Как известно, факториал натурального числа определяется следующим образом:
Иначе это можно записать так:
F(n)=F(n–1) · n при n > 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.
Подобные вычисления можно проводить в уме, а их результаты фиксировать в таблице:
И в завершение вспомним задачу вычисления НОД и модифицируем с использованием рекурсивной функции.
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Для чего нужны вспомогательные алгоритмы?
Ответ
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.
При построении новых алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо выполнение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
Вспомогательный алгоритм нужен тогда, когда в разных места алгоритма необходимо выполнить одну и ту же последовательность шагов обработки данных.
Вспомогательным алгоритмом называется алгоритм, целиком используемый в составе другого алгоритма.
При решении многих задач возникает необходимость в проведении одних и тех же вычислений на различных этапах выполнения программы при различных значениях данных. Повторение одной и той же последовательности действий может быть оформлено в виде подпрограммы (вспомогательного алгоритма). При этом повторяющиеся группы операторов записываются в подпрограмме по отношению к некоторым формальным параметрам, а в нужных местах основной программы обеспечивается лишь обращение к подпрограмме с указанием фактических параметров. Использование подпрограмм позволяет следовать принципам структурного программирования, т.е. разбивать сложную задачу на простые подзадачи, в результате основная программа собирается в виде обращения к подпрограммам.
В соответствии с методами структурного программирования построение программ производится методом постепенной детализации алгоритмов. Некоторые части алгоритма могут выделяться в виде вспомогательных алгоритмов, решающих вспомогательные подзадачи.
Вспомогательный алгоритм – алгоритм, который можно вызвать и использовать в других алгоритмах, указав только его имя.
Вспомогательные алгоритмы создаются, когда возникает необходимость разбиения задачи на ряд более простых задач или когда есть необходимость многократного использования одного и того же набора действий в одном или разных алгоритмах.
Рассмотрим пример, Вы хотите спеть песню, у которой три куплета и припев, исполняемый после каждого куплета. Алгоритм Ваших действий будет следующим:
1. Спеть 1-й куплет.
2. Спеть припев.
3. Спеть 2-й куплет.
4. Спеть припев.
5. Спеть 3-й куплет.
6. Спеть припев.
Действия, объединенные в пункт "спеть припев", трижды повторяются. Таким образом, этот алгоритм содержит набор повторяющихся одинаковых действий и в озникает необходимость многократного использования одного и того же набора действий (алгоритма), следовательно такой набор действий или алгоритм можно выделить в качестве самостоятельного фрагмента. Он становится вспомогательным алгоритмом.
Вспомогательный алгоритм – алгоритм, по которому решается некоторая подзадача из основной задачи и который, как правило, выполняется многократно. Алгоритм может содержать несколько вспомогательных алгоритмов.
Блок-схема вызова вспомогательного алгоритма
Вспомогательный алгоритм является аналогом языковой подпрограммы, обладает той же структурой, которой обладает весь алгоритм. Он имеет имя (заголовок) и может иметь параметры, которые называются формальными параметрами. Имя служит для того, чтобы отличить его от других алгоритмов, а формальные параметры, которые напоминают переменные математических функций, выполняют роль входных и выходных параметров.
Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан весь набор необходимых входных и выходных величин. Нередко один и тот же параметр может оказаться входным и выходным одновременно.
Например, на вход такого алгоритма может быть подана переменная для обработки, а на выходе процедуры он может предстать в измененном виде как выходной параметр.
Вспомогательные алгоритмы должны быть состыкованы между собой в процессе "сборки" основного алгоритма. Для этого используют имена (заголовки) вспомогательных алгоритмов; с их помощью вызывают этот алгоритм (обращаются к его работе) из других вспомогательных или основного алгоритмов.
Пример. Рассмотри алгоритм вычисления длин окружности для кругов различного радиуса с использованием вспомогательного алгоритма.
C=2*Pi*r, где C - длина окружности, Pi - математическая константа, r - радиус круга.
Алгоритм Dlina - вспомогательный алгоритм.
r, C - формальные параметры.
В данном видеоуроке рассматриваются вспомогательные алгоритмы и их применение. Это позволит учащимся продумывать нюансы программирования сложных алгоритмов. А также рассматриваются рекурсивные алгоритмы, их принцип работы и приводятся примеры их создания.
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.
Получите невероятные возможности
Конспект урока "Вспомогательные алгоритмы"
Раньше мы изучили метод последовательного конструирования алгоритмов, при котором алгоритм последовательно разбивается на подзадачи, пока все они не станут понятны исполнителю.
При конструировании алгоритмов вы уже наверняка сталкивались, с ситуацией, когда одна и та же последовательность действий выполнялась для различных данных в разных местах программы, то есть одну и ту же подзадачу решали несколько раз, так на пример в некоторых программах мы несколько раз выводили содержимое массива на экран. До этого, в таких случаях мы повторно записывали ту же последовательность команд, в результате чего наша программа становилась длиннее. А если вы допускали ошибки при написании программ, то наверняка заметили, что чем длиннее программа – тем сложнее в ней найти ошибку.
Но оказывается, что в таких случаях можно сократить текст программы, оформив соответствующие последовательности команд в виде вспомогательных алгоритмов, которые можно использовать многократно.
Вспомогательный алгоритм – это алгоритм, который целиком использован в составе другого алгоритма.
Ещё одной важной особенностью вспомогательных алгоритмов, является универсальность, то есть их можно использовать в совершенно разных программах, в которых они будут работать одинаково, то есть единожды написав, вспомогательный алгоритм вычисления площади треугольника, можно его использовать в любой, программе, в которой в ходе работы требуется вычислить площадь треугольника.
Задача: Робот находится в левой верхней клетке поля без стен. Нарисовать девять квадратов. Две на две клетки.
Очевидно, что при решении данной задачи мы будем повторять одну и ту же последовательность команд для рисования каждого квадрата. Следовательно, можно оформить её в качестве вспомогательного алгоритма, а также у нас есть три одинаковых ряда квадратов, последовательность команд для рисования которых можно так же оформить в виде вспомогательного алгоритма.
Для начала запишем последовательность команд для рисования квадрата в виде вспомогательного алгоритма, при этом условимся, что все квадраты будем рисовать, начиная с левой верхней клетки.
Вспомогательный алгоритм рисования квадрата
Так мы получили вспомогательный алгоритм для рисования квадрата. Теперь запишем вспомогательный алгоритм для рисования горизонтального ряда квадратов, назовём его ряд.
Чтобы нарисовать ряд квадратов, Робот должен нарисовать первый квадрат, для этого вызовем уже написанный алгоритм, записав его название. А затем нужно переместиться на позицию для рисования следующего квадрата. Для этого Робот должен трижды сместиться вправо, и один раз вверх. Далее нужно снова нарисовать квадрат и сместиться к следующему так же, как и до этого, трижды сместившись вправо и один раз вверх, и снова нарисовать квадрат.
Вспомогательный алгоритм рисования ряда квадратов
Запустим программу на выполнение. Девять квадратов изображены верно, следовательно, задача решена.
Результат работы программы
Изображение вспомогательного алгоритма на блок-схеме
Задача: У нас есть вспомогательный алгоритм factorial, который вычисляет значение факториала целого числа k. Составить блок-схему алгоритма вычисления значения выражения 1! + 2! + … + n!. Вспомним, что k! = 1 * 2 * … * k.
Блок-схема вспомогательного алгоритма
Блок-схема с использованием вспомогательного алгоритма
Рассмотрим, как работает вспомогательный алгоритм в составе основного. В начале выполняются команды основного алгоритма, идущие до вызова вспомогательного. Затем, когда доходит до выполнения вспомогательного алгоритма, его формальные параметры, в нашем случае k, заменяются параметрами из основного алгоритма. В нашем случае i. Далее выполняются команды вспомогательного алгоритма. Затем значения выходных параметров вспомогательного алгоритма, в нашем случае f подставляются в основной алгоритм, в нашем случае в переменную a. После чего далее выполняются команды основного алгоритма.
Через вспомогательные алгоритмы можно создавать так же рекурсивные алгоритмы. Рекурсивным алгоритмом называется алгоритм, который содержит ссылку на самого себя. Посмотрим для решения каких задач их можно применить.
Мы можем составить вспомогательный алгоритм для вычисления факториала, с использованием рекурсии, если примем во внимание формулу: n! = (n - 1)!. Важно при этом помнить, что 1! = 1. Блок-схема данного алгоритма будет выглядеть так.
Блок-схема рекурсивного алгоритма вычисления n!
Обратим внимание, что вспомогательный алгоритм содержит ветвление, при котором, если n > 1 – n! = (n - 1)!, а в случае если n = 1, то n! = 1. Также и в других рекурсивных алгоритмах, ссылка на алгоритм всегда указывается лишь в одной ветви условного оператора, иначе он будет вызывать сам себя бесконечно.
Задача: Робот находится в поле без стен, на определённом расстоянии от левого края. Он должен нарисовать уголок, то есть закрасить все клетки от своего текущего положения до левого края, а потом столько же клеток вниз.
Запишем рекурсивный вспомогательный алгоритм для рисования уголка. Назовём его угол. Он будет содержать условный оператор, условием которого будет если слева свободно, если данное условие выполняется, робот будет закрашивать клетку, в которой он находится и смещаться на одну клетку влево, после чего снова вызывать себя. После условного оператора будут содержаться команды, которые будут выполняться, когда робот дойдёт до стены. На каждом шаге Робот должен закрасить клетку, в которой он находится и сместиться на клетку вниз.
Рекурсивный алгоритм рисования уголка
Основной алгоритм будет содержать только одну команду - вызов вспомогательного алгоритма угол. Запустим программу на выполнение. Робот действительно изобразил уголок.
Рассмотрим подробнее, как работает данный алгоритм. Для примера возьмём случай, когда робот стоит в трёх клетках от левого края поля. При первом вызове вспомогательного алгоритма условие выполняется, следовательно, робот закрасит клетку в которой находится и сместиться на клетку влево, после чего снова вызовет вспомогательный алгоритм для рисования уголка, уже во второй раз. При втором вызове вспомогательного алгоритма робот снова закрасит клетку, в которой находится, сместиться на клетку влево, и вызовет себя уже в третий раз. При третьем вызове слева будет край поля, следовательно, условие выполняться не будет, и выполнятся только команды, которые идут после условного оператора, то есть робот закрасит клетку, в которой находится и сместится на клетку вниз. При третьем вызове вспомогательный алгоритм был завершён окончательно, а при первых двух – нет, следовательно, сейчас будет продолжено выполнение второго вызова вспомогательного алгоритма, то есть Робот снова закрасит клетку, в которой находится и сместиться вниз. Второй вызов вспомогательного алгоритма завершён, осталось выполнить до конца лишь первый вызов алгоритма. При этом Робот снова закрасит клетку, в которой находится, и сместиться на клетку вниз. Уголок готов.
Выполнение рекурсивного алгоритма, для удобства можно представить в виде стека, то есть коробки, у которой есть дно, но нет верхней крышки, в такую коробку объект можно положить лишь поверх остальных, точно так же и достать из коробки можно лишь верхний объект. То есть объект, который в коробку положили первым, достанут из коробки последним. Так же происходит при выполнении вспомогательного алгоритма угол, в нашем примере, в процессе выполнения первого вызова алгоритма, он был вызван второй раз, а в процессе выполнения второго вызова, в третий. После того, как было завершено выполнение третьего вызова, было продолжено выполнение второго, а после его завершения – первого.
При использовании рекурсивных алгоритмов важно помнить, что количество одновременных вызовов ограничено, поэтому, если рекурсию можно заменить циклом – лучше так и поступить.
Важно запомнить:
· Вспомогательным называется алгоритм, который целиком используется в составе другого алгоритма.
· Рекурсивный алгоритм – это алгоритм, в котором есть ссылка на самого себя.
· Исполнение рекурсивного алгоритма можно представить в виде стека.
· Если рекурсию можно заменить циклом – лучше так и поступить.
Мы научились применять вспомогательные и рекурсивные алгоритмы при решении задач.
Читайте также: