Существуют различные методы конструирования (разработки, построения) алгоритмов. Мы познакомимся с одним из них — методом последовательного построения (уточнения) алгоритма. Иначе он называется методом разработки «сверху вниз», нисходящим методом илиметодом пошаговой детализации.
Процесс последовательного построения алгоритма выглядит следующим образом.
На первом шагемы считаем, что перед нами совершенный исполнитель, который всё знает и всё умеет. Поэтому достаточно определить исходные данные и результаты алгоритма, а сам алгоритм представить в виде единого предписания — постановки задачи.
Если исполнитель не обучен исполнять заданное предписание, то необходимо представить это предписание в виде совокупности более простых предписаний (команд). Для этого:
задачу разбивают на несколько частей, каждая из которых проще всей задачи;
решение каждой части задачи формулируют в отдельной команде, которая также может выходить за рамки системы команд исполнителя;
при наличии в алгоритме предписаний, выходящих за пределы возможностей исполнителя, такие предписания вновь представляются в виде совокупности ещё более простых предписаний.
Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю. Объединяя полученные предписания в единую совокупность выполняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи.
Разработка алгоритма методом последовательного уточнения для исполнителя Робот
Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закреплена.
Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.
Представим план действий Робота следующими укрупнёнными шагами (модулями):
Детализируем каждый из пяти модулей.
1. Чтобы закрасить все клетки коридора, находящиеся левее Робота, прикажем Роботу шагнуть влево и выполнить цикл ПОКА:
Под управлением этого алгоритма Робот закрасит все клетки коридора, находящиеся левее от него, и окажется на клетке рядом с левой границей коридора.
2. Командой вправо вернём Робота в коридор. Наша задача — вернуть Робота в исходную точку. Эта точка имеет единственный отличительный признак — она не закрашена. Поэтому пока занимаемая Роботом клетка оказывается закрашенной, будем перемещать его вправо.
Под управлением этого алгоритма Робот окажется в исходной точке.
3. Выполнив команду вправо, Робот пройдёт исходную клетку и займёт клетку правее исходной. Теперь можно закрашивать клетки коридора, расположенные правее исходной.
4. Так как, выполнив предыдущий алгоритм Робот оказался правее коридора, командой «влево» вернём его в коридор. Возвращение в исходную точку обеспечивается алгоритмом:
5. По команде «закрасить» Робот закрашивает исходную точку.
Вспомогательные алгоритмы
При построении новых алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо выполнение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
Вспомогательный алгоритм— алгоритм, целиком используемый в составе другого алгоритма.
При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс», внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — входные данные и результаты.
Вспомогательный алгоритм делает структуру алгоритма более понятной.
Построим алгоритм вычисления степени y=ax, где x — целое число, a≠0.
По определению степени с целым показателем.
a0=1,a≠0;a−n=1an,a≠0,n∈N.
Исходя из определения и учитывая, что 1a−x=(1a)−x, можно записать: y=⎧⎩⎨⎪⎪⎪⎪⎪⎪1 при x=0ax при x>0(1a)−x при x<0.
Решение задачи вычисления степени y=ax, где x — целое число, a≠0, представим блок-схемой:
Этот алгоритм является основным по отношению к вызываемому в нём вспомогательному алгоритму.
Напомним, что параметрами используемого вспомогательного алгоритма были величины a,n,y. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т.е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.
Команда вызова вспомогательного алгоритма исполняется следующим образом:
Формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
Для заданных входных данных исполняются команды вспомогательного алгоритма:
Полученные результаты присваиваются переменным с именами фактических результатов;
Осуществляется переход к следующей команде основного алгоритма.
Рекурсия
Рекурсией называется ситуация, когда подпрограмма вызывает сама себя.
Большинство современных языков высокого уровня поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом.
Пример:
Рекурсивный алгоритм положен в основу эффективного решения головоломки «Ханойская башня».
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Пример:
Кривая Коха— фрактальная кривая, описанная в 1904 году шведским математиком Хельге фон Кохом.
Три копии кривой Коха, построенные (остриями наружу) на сторонах правильного треугольника, образуют замкнутую кривую бесконечной длины, называемую снежинкой Коха.
С каждым шагом фигура становится всё причудливее.
Рекомендованный список литературы
Босова Л.Л. Информатика — Учебник для 8 класса. – М.: БИНОМ. Лаборатория знаний
Did you find apk for android? You can find new Free Android Games and apps.
