|
|
Учебник для 9 класса Информатика и ИКТ§ 3.5. Конструирование алгоритмовКлючевые слова:
3.5.1. Последовательное построение алгоритмаСуществуют различные методы конструирования (разработки, построения) алгоритмов. Мы познакомимся с одним из них — методом последовательного построения (уточнения) алгоритма. Иначе он называется методом разработки «сверху вниз», нисходящим методом или методом пошаговой детализации. Процесс последовательного построения алгоритма выглядит следующим образом. На первом шаге мы считаем, что перед нами совершенный исполнитель, который «всё знает и всё умеет». Поэтому достаточно определить исходные данные и результаты алгоритма, а сам алгоритм представить в виде единого предписания — постановки задачи (рис. 3.13).
Рис. 3.13. Если исполнитель не обучен исполнять заданное предписание, то необходимо представить это предписание в виде совокупности более простых предписании (команд). Для этого:
Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю. Объединяя полученные предписания в единую совокупность выполняемых в определённой последовательности команд, получаем требуемый алгоритм решения исходной задачи. 3.5.2. Разработка алгоритма методом последовательного уточнения для исполнителя РоботИзвестно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Составим алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.
Представим план действий Робота следующими укрупнёнными шагами (модулями):
Детализируем каждый из пяти модулей.
Полностью программа управления Роботом выглядит так:
3.5.3. Вспомогательные алгоритмыПри построении новых алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо выполнение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 3.14), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — входные данные и результаты.
Рис. 3.14. Вспомогательный алгоритм делает структуру алгоритма более понятной. Пример 1. Построим алгоритм вычисления степени у = ах, где х — целое число, а ≠ 0. По определению степени с целым показателем:
Исходя из определения и учитывая, что
можно записать:
Ранее мы уже рассматривали алгоритм возведения произвольного вещественного числа в натуральную степень (§ 3.4, пример 19). Обозначим этот алгоритм st(a, n, у) и воспользуемся им в качестве вспомогательного алгоритма. Решение задачи вычисления степени у = аx, где х — целое число, а ≠ 0, представим блок-схемой:
Этот алгоритм является основным по отношению к вызываемому в нем вспомогательному алгоритму. Напомним, что параметрами используемого вспомогательного алгоритма были величины а, n, у. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать. Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 3.15):
Рис. 3.15.
Рассмотрим несколько примеров рекурсивных алгоритмов. Пример 2. Алгоритм вычисления степени с натуральным показателем n для любого вещественного числа а можно представить в виде рекурсивного.
Пример 3. Рекурсивный алгоритм положен в основу эффективного решения головоломки «Ханойская башня».
Интерактивная игра «HanoiSetup» (http://files.school-collection. edu.ru/) поможет вам вспомнить условие и алгоритм решения головоломки. Пример 4. Рассмотрим алгоритм построения геометрической фигуры, которая называется снежинкой Коха. Шаг процедуры построения состоит в замене средней трети каждого из имеющихся отрезков двумя новыми той же длины, как показано на рисунке.
С каждым шагом фигура становится всё причудливее. Граница снежинки Коха — положение кривой после выполнения бесконечного числа шагов. Попробуйте подсчитать, сколько рёбер в границе снежинки Коха после четвёртого шага; после пятого шага.
Самое главноеОдин из основных методов конструирования алгоритмов — метод последовательного построения алгоритма. Его суть состоит в том, что: исходная задача разбивается на несколько частей, каждая из которых проще всей задачи, и решение каждой части формулируется в отдельной команде; если получаются команды, выходящие за пределы возможностей исполнителя, то они представляются в виде совокупности ещё более простых предписаний. Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю. Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма. Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным. Вопросы и задания
|
|
|