Использование функций для структурирования алгоритмов

Функции позволяют разбивать алгоритм (программу) на отдельные блоки, или модули. Таким образом, модульное программирование обязано своим появлением именно функциям. Под модульным программированием подразумевается создание программ (алгоритмов) из самостоятельно отлаживаемых частей, которые в совокупности образуют единое приложение. Например, один модуль может отвечать за ввод данных, другой - реализовывать вывод данных на печать, а третий - обеспечивать сохранение данных на диске.

По сути, функция - это подпрограмма, которая может оперировать данными и возвращать значение.

Каждая функция имеет имя. Когда оно встречается в алгоритме (коде программы), управление переходит к телу функции. Этот процесс называется вызовом функции (или обращением к функции). По возвращении из функции выполнение алгоритма (программы) возобновляется со строки, следующей за той, где функция была вызвана.

Различают два вида функций: пользовательские и встроенные. Встроенные функции являются составной частью пакета компилятора и предоставляются фирмой-изготовителем. Пользовательские функции создаются самим программистом.

Возвращаемые значения, параметры и аргументы. Как уже было продемонстрировано ранее все функции возвращают значение. При обращении к функции она выполняет определенные действия, а затем в качестве результата возвращает значение. Оно называется возвращаемым значением, причем в языках программирования тип этого значения обязательно должен быть объявлен, например, целое, вещественное, логические и т.д.

Функции можно передать значения. Описание передаваемых значений называется списком параметров (формальные параметры).

Например, функция summa (арг цел I1, цел I2): рез цел - для псевдокода или, например, int summa (int I1, int I2) - для языка С++.

Это объявление означает, что функция summa () не только возвращает целое число (на это указывает ее тип данных int), но и получает два целочисленных значения I1 и I2 в качестве параметров.

Параметр описывает тип значения, которое будет передано функции при ее вызове. Фактические значения, передаваемые функции в момент ее вызова из основной программы, называются аргументами (или фактическими параметрами).

Например, P:=summa (5, 8) - для псевдокода или

int P = summa(5, 8) - для языка С++.

Здесь целочисленная переменная P инициализируется значением, возвращаемым функцией summa(), а в качестве аргументов этой функции передаются значения 5 и 8. Тип аргументов должен соответствовать объявленным типам параметров.

Для паримера, решим следующую задачу с использованием функции: даны два вещественных числа, являющихся величинами катетов некоторого прямоугольного треугольника. Вычислить длину гипотенузы этого треугольника.

Решение.Анализ задачи.

1. Формулы. Будем вычислять гипотенузу по формуле Пифагора

(1)

2. Входные данные. Из формулы (1) следует, что входными данными

являются длины катетов x и y.

3. Выходные данные (результат). Результатом работы алгоритма является вычисленное значение гипотенузы z.

Проектирование алгоритма.

Применим проектирование сверху вниз.

1) Напишем входные данные и результат в явном виде.

2) Алгоритм расчета результата выделим в отдельный алгоритм. Этот отдельный алгоритм представляет функцию. В главном алгоритме не нужно описывать, как функция будет вычислять значение гипотенузы. Это внутреннее дело функции, она - «черный ящик» для главного алгоритма. На схеме главного алгоритма вызов функции обозначается прямоугольником с двойными боковыми сторонами (см. рис. 11.10-а). Вместо этого прямоугольника и подставляется алгоритм функции
(см. рис. 11.10-б). Функция реализует формулу Пифагора (1).

Рис. 11.10. Схема алгоритма вычисления гипотинузы прямоугльного треугольника по известным катетеам с использованием функции (подпрограммы)

Рассмотрим другую задачу:найти сумму первых n натуральных чисел.

Решение.

Анализ задачи.

1. Формулы. Нужно найти сумму n чисел 1 + 2 + 3 + … + n. (2)

2. Входные данные. Из суммы (2) следует, что входным данным является количество первых натуральных чисел n.

3. Выходные данные (результат). Результатом работы алгоритма является вывод суммы (2).

Проектирование алгоритма:

1) напишем входные данные в явном виде;

2) выведем сообщение о величине суммы;

3) алгоритм вычисления суммы S первых n натуральных чисел выделим в отдельный модуль (см. рис. 11.6). В этом модуле используем цикл для накопления суммы в сумматоре S. Для этого заметим, что текущее слагаемое суммы (2) имеет вид i. Тогда сумму можно накопить в сумматоре, если:

· в начале присвоить ему начальное значение S = 0;

· далее прибавлять к сумматору в цикле переменную i, изменяя ее от 1 до n.

Результат проектирования представлен на рис. 11.11.

Рис. 11.11. Вычисление суммы первых n натуральных чисел

Функция может вызывать саму себя - это свойство называется рекурсией. Когда функция вызывает саму себя, речь идет о прямой рекурсии. Если же функция вызывает другую функцию, которая затем вызывает первую, то в этом случае имеет место косвенная рекурсия.

Некоторые задачи лучше всего решаются именно с посощью рекурсии. Так, рекурсия полезна в тех случаях, когда над данными выполняется определенная процедура, а затем эта же процедура выполняется над полученным результатом.

Чтобы продемонстрировать решение задачи при помощи рекурсии, рассмотрим ряд Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 . . .

Каждое число ряда (после второго) представляет собой сумму двух чисел, стоящих впереди. Задача может заключаться в вычислении, наример 15 члена ряда Фибоначи. В общем случае n-е число ранво сумме n-2-го и
n-1-го чисел, при условии, что n>2.

Для рекурсивных функций необходимо задать условие прекращения рекурсии. Обязательно должно произойти событие, способное заставить программу (алгоритм) остановить рекурсию, иначе она никогда не завершится. В ряду Фибоначчи условием выхода является событие n £ 2, когда это условие истино следует прекратить работу рекурсии.

Вербальное описание алгоритма.

1. Запросить у пользователя какой член в ряду Фибоначчи следует вычислить.

2. Вызвать функцию fibon(), в качестве аргумента которой передать заданный пользователем fibon(), порядковый номер члена ряда Фибоначчи;

3. В теле функции fibon() выполнить анализ поступившего аргумента n. Если n £ 2, то заврешить работу функции и возвратить значение равное 1. В противном случае функция fibon() вызывает сама себя, передавая в качестве аргумента значение n-2, затем снова вызывает сама себя, передавая в качестве аргумента значение n-1, а после следует сложить полученные из функции значения: fibon(n-2) + fibon(n-1) - это и будет искомый результат.

Реализация задачи на псевдокоде.

Алгоритм 4

алг Расчет n-го члена ряда Фибоначчи

нач

вывод (“Введите какой номер члена ряда Фибоначчи следует вычислить”)

ввод (n)

Fn:= fibon(n)

вывод (n,“-ый член ряда Фибоначчи равен ”, Fn)

кон

функция fibon (аргцел n): резцел

Нач

если n<=2 то fibon:=1

иначе fibon:=fibon(n-2)+fibon(n-1)

Все

Кон

Вопросы и задания для самопроверки

1. Какие этапы решения задачи на ЭВМ можно выделить? Охарактеризуйте их.

2. Кто участвует в решении задачи на ЭВМ и на каких этапах?

3. Перечислите и охарактеризуйте основные методы технологии программирования.

4. Какие этапы можно выделить при создании программы?

5. В чем отличие между отладкой и тестированием программы?

6. Какие методы тестирования вы знаете?

7. Определите понятия полиморфизм, инкапсуляция и наследование.

8. Перечислите базовые алгоритмические структуры.

9. Какие виды циклов вам известны?

10. Опишите работу команды «выбор» на псевдокоде.

11. Опишите работу команды «ветвление» на псевдокоде.

12. Нарисуйте схему алгоритма нахождения суммы n четных натуральных чисел. Как будет выглядеть этот алгоритм на псевдокоде?

13. Нарисуйте схему алгоритма нахождения произведения . Как будет выглядеть этот алгоритм на псевдокоде?

14. Перепишите алгоритм из задания 13, используя функцию для нахождения произведения.

15. Напишите пример алгоритма, реализующего линейный поиск, поиск делением пополам.

16. Напишите пример алгоритма, реализующего сортировку массива с помощью прямого выбора, с помощью обменов.

17. Дайте определения понятиям: «функция», «рекурсия».

18. Как описывается функция на алгоритмическом языке. Приведите пример.