В этой теме мы с вами рассмотрим методы декомпозиции. То есть мы будем учиться разбивать одну большую задачу на несколько отдельных, помельче. Небольшую самостоятельную задачу обычно гораздо легче решить. В этой теме мы познакомимся со способом записи таких подзадач на языке Паскаль.
Конструирование алгоритма «сверху вниз»
При конструировании достаточно сложного алгоритма логично разбивать его на ряд более йростых задач. Построение алгоритма идет «сверху вниз». Сначала строится основной алгоритм. В нем записываются обращения к вспомогательным алгоритмам, которые позволят решить отдельные, более простые задачи (подзадачи 1-го уровня). Если есть необходимость, осуществляют дальнейшую детализацию, и подзадача разбивается на еще более простые задачи (подзадачи 2-го уровня). Вспомогательные алгоритмы для решения подзадач последнего уровня не содержат обращений к другим вспомогательным алгоритмам (рис. 9.1).
Рис. 9.1. Схема алгоритма, построенного по принципу «сверху вниз»
Итак, вспомогательным алгоритмом называется алгоритм решения некоторой задачи, являющейся подчиненной по отношению к исходной (основной) задаче. При реализации таких алгоритмов на языке Паскаль их оформляют в виде процедур или функций. Согласно концепции структурного программирования, вспомогательный алгоритм должен: - иметь имя, по которому его можно вызвать из других алгоритмов; - возвращать управление тому алгоритму, из которого он был вызван. После того как завершится выполнение вспомогательного алгоритма, вызвавший его алгоритм должен продолжить работу с той точки, в которой он был прерван; - иметь возможность вызывать другие алгоритмы; - иметь достаточно малые размеры.
Практическая задача с использованием вспомогательных алгоритмов
Задача: выполнить с массивом действия, которые были предложены в заданиях 8.3, 8.4:
а) заполнить одномерный целочисленный массив из 10 элементов случайными числами от -20 до +20; б) вывести массив на экран в виде строки чисел; в) подсчитать сумму элементов массива; г) поменять местами элементы массива следующим образом: 1-й элемент— со 2-м, 3-й — с 4-м, 5-й — с б-м, 7-й — с 8-м, 9-й - с 10-м; д) вывести измененный массив на экран.
Разобьем основной алгоритм на подзадачи в порядке их перечисления в задании (рис. 9.2).
Рис. 9.2. Блок-схема алгоритма решения задачи из примера 9.1
Обратим внимание: пункты б) и д) выполняют одинаковое действие — вывод массива на экран. Поэтому оформим их в виде отдельного фрагмента программы под некоторым именем, а в нужных местах вызовем этот фрагмент по его имени. Такой фрагмент называется процедурой.
Процедура оформляется по тем же правилам, что и программа. Пункты а) и г) оформим также в виде процедур. Пункт в) — вычисление суммы элементов массива — оформим отдельным фрагментом, но с возвращением результата вычисления. Такой фрагмент называется функцией. В отличие от процедуры, из функции всегда возвращается результат в виде переменной, тип которой указывается в заголовке функции (см. пример 9.1).
Такая организация программы по блокам вспомогательных алгоритмов (процедурам и функциям) придает ей логичную структуру и делает ее более удобной для дальнейшего использования.
Процедуры и функции в программе оформляют в виде отдельных блоков, каждый из которых начинается специальным словом (procedure или function соответственно). Эти блоки должны располагаться в тексте программы перед оператором begin, начинающим основную программу. В каждом блоке процедуры или функции может находиться свой раздел описания переменных (var) и должна быть пара операторов begin ... end, между которыми пишется текст процедуры (или функции).
Внимательно читайте комментарии к программе!
Пример 9.1. Демонстрация процедур и функций на примере работы с одномерным массивом
Задание 9.1. Написать программу, в которой выполняется:
а) ввод одномерного массива А из 14 чисел (положительных и отрицательных); б) вывод массива на экран; в) сдвиг всех элементов массива на одну позицию влево (рис. 9.3); первый элемент встает на место последнего (см. блок-схему алгоритма на рис. 9.4); г) вывод массива на экран; д) подсчет количества положительных элементов. Все пункты оформить как процедуры или функции.
Пример работы с функцией: поиск максимального элемента
Пример 9.2: Программа поиска максимального элемента в массиве
Задание 9.2. Написать программу, в которой для массива из 20 элементов, заполненного случайными числами и i -20 до +20, 20 раз выполняется следующая процедура: слева направо по порядку сравниваются все соседние элементы и, если первый элемент в паре оказался больше второго, элементы меняются местами. В конце процедуры массив выводится на экран в строку. Таким образом, результатом программы должны быть 20 строк, в каждой из которых большие элементы массива постепенно «сдвигаются» вправо, а меньшие — влево.
Выводы
1. При решении сложной задачи разумно ее разбивать на подзадачи. При реализации на языке Паскаль каждая такая подзадача (блок) оформляется в виде функции или процедуры. 2. Процедуры и функции оформляются вне тела программы. Они начинают работать только при вызове из тела программы или из другого блока (функции, процедуры). 3. Результат работы функции возвращается через ее имя. 4. Различают глобальные и локальные переменные. 5. Глобальные переменные действуют в теле программы и в любом из ее блоков (функциях, процедурах). 6. Локальные переменные действуют только внутри блока, в котором они описаны.
Контрольные вопросы
1. Зачем нужно создавать процедуры и функции? 2. Чем отличаются функции от процедур? 3. Зачем нужны локальные переменные? 4. Если локальная и глобальная переменные имеют одинаковые имена, то к какой переменной будет идти обращение?
