Вспомогательные алгоритмы и процедуры

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

В качестве примера рассмотрим следующую задачу: требуется составить алгоритм вычисления степенной функции с целым показателем: y = x^k, где k – целое число, x¹0. В алгебре такая функция определена следующим образом:

Для данной задачи в качестве подзадачи можно рассматривать возведение числа в целую положительную степень.

Учитывая, что 1/x^-n =(1/x)^-n, запишем основной алгоритм решения этой задачи.

алг Степенная функция

цел n; вещ x, y;

начввод x, n

если n=0

тоy:=1

иначе если n>0

то СТЕПЕНЬ(x, n, y)

иначе СТЕПЕНЬ(1/x, -n, y)

кв

кв

вывод y

Кон

Здесь дважды присутствует команда обращения к вспомогательному алгоритму с именем СТЕПЕНЬ. Это алгоритм возведения вещественного основания в целую положительную степень путем его многократного перемножения. Величины, стоящие в скобках в команде обращения к вспомогательному алгоритму, называются фактическими параметрами.

В учебном алгоритмическом языке вспомогательные алгоритмы оформляются в виде процедур. Запишем на АЯ процедуру СТЕПЕНЬ.

процедура СТЕПЕНЬ(веща, цел k, вещ z)

цел i

нач z:=1; i:=1

пока i£k, повторять

нцz:=z´a

i:=i+1

кц

Кон

Заголовок вспомогательного алгоритма начинается со слова “процедура”, после которого следует имя процедуры и в скобках – список формальных параметров. В этом списке перечисляются переменные-аргументы и переменные-результаты с указанием их типов. Здесь a и k – формальные параметры-аргументы, z – параметр-результат. Следовательно, процедура СТЕПЕНЬ производит вычисления по формуле: z=a^k.

В основном алгоритме «Степенная функция» обращение к процедуре производится путем указания ее имени с последующим в скобках списком фактических параметров. Между формальными и фактическими параметрами процедуры должны выполняться следующие правила соответствия:

- по количеству (сколько формальных, столько и фактических параметров);

- по последовательности (первому формальному соответствует первый фактический параметр, второму – второй и т.д.);

- по типам (типы соответствующих формальных и фактических параметров должны совпадать).

Фактические параметры-аргументы могут быть выражениями соответствующего типа.

Обращение к процедуре инициирует следующие действия:

1) значения параметров-аргументов присваиваются соответствующим формальным параметрам;

2) выполняется тело процедуры (команды внутри процедуры);

3) значение результата передается соответствующему фактическому параметру, и происходит переход к выполнению следующей команды основного алгоритма.

В процедуре СТЕПЕНЬ нет команд ввода исходных данных и вывода результатов. Здесь присваивание начальных значений аргументам (a, n) производится через передачу параметров-аргументов. А присваивание результата переменной (y) происходит через передачу параметра-результата (z). Таким образом, передача значений параметров процедур – это третий способ присваивания (наряду с командой присваивания и командой ввод).

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

Упражнения

1. Даны декартовы координаты трех вершин треугольника на плоскости. Составить алгоритм определения площади треугольника.

2. Дана скорость ракеты при выходе за пределы атмосферы Земли. Составить алгоритм определения, как будет двигаться ракета после выключения двигателей? (Напомним величины трех космических скоростей: 7,5 км/сек; 11,2 км/сек; 16,4 км/сек).

3. Даны три положительных числа. Составить алгоритм, определяющий, могут ли они быть длинами сторон треугольника?

4. Пусть компьютер способен выполнять только две арифметические операции: сложения и вычитания. Составить алгоритмы:

а) умножения двух целых чисел;

б) целочисленного деления двух чисел;

в) получения остатка от целочисленного деления двух чисел.

5. Построить алгоритм решения биквадратного уравнения, используя как вспомогательный алгоритм решения квадратного уравнения.

6. Составить алгоритм нахождения НОД трех натуральных чисел, используя вспомогательный алгоритм нахождения НОД двух чисел.