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

 

В команде вызова вспомогательного алгоритма на месте его результатов указываются имена величин основного алгоритма, в которых должны оказаться вычисленные значения. Например, если нам надо в основном алгоритме "вычисление" найти гипотенузу х прямоугольного треугольника с катетами р - 1 и р + 1, то достаточно написать вызов вспомогательного алгоритма "гипотенуза" (А56):

 

алг вычисление

нач вещ р, х

…

гипотенуза (р - 1, р + 1, х)

…

Кон

Пусть к моменту выполнения этого вызова величина р имеет значение 7 (рис. 63).

 

 

Рис. 63

 

Встретив вызов "гипотенуза (р - 1, р + 1, х)", компьютер вычислит значения р-1 и р+1 передаст их алгоритму "гипотенуза" в качестве значений аргументов а и b. Значение х в этот момент не вычисляется, так как х соответствует результату вспомогательного алгоритма.

Затем начинается выполнение вспомогательного алгоритма "гипотенуза". Выделяется память алгоритма, в ней создаются ячейки для аргументов а, b и результата с, аргументы получают значения, переданные из основного алгоритма (рис. 64).

 

Рис. 64

 

В памяти компьютера при этом будет одновременно храниться информация, относящаяся и к алгоритму "вычисление", и к алгоритму "гипотенуза". Далее ЭВМ выполнит алгоритм "гипотенуза" и вычислит значение величины-результата с (рис. 65).

 

Рис. 65

 

Встретив строчку кон, компьютер передаст значение результата в основной алгоритм и завершит работу алгоритма "гипотенуза", освободив его память. В основном алгоритме значение результата записывается в ячейку величины, указанной в команде вызова, т. е. в х (рис. 66). После этого компьютер продолжает выполнять алгоритм "вычисление".

 

Рис. 66

 

Общие правила выполнения команды вызова вспомогательного алгоритма

 

1. Выполняя команду вызова вспомогательного алгоритма, компьютер вычисляет значения аргументов и передает их вспомогательному алгоритму в том порядке, в котором они записаны в команде вызова. После этого выполнение основного алгоритма приостанавливается.

2. Перед началом выполнения вспомогательного алгоритма компьютер отводит для него место в памяти. Аргументы получают значения, переданные из основного алгоритма.

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

4. После окончания вспомогательного алгоритма все, что с ним связано, стирается из памяти компьютера. (Если алгоритм вызывается еще раз, то все начинается сначала: компьютер снова отводит место в памяти, присваивает значения аргументам и т. д.)

5. Продолжается выполнение основного алгоритма.

 

17.4. Алгоритм с результатами при управлении Роботом

	А57

алг средний уровень радиации в коридоре (рез вещ г)

дано | Робот в левой клетке коридора, уходящего вправо

надо | r = средний уровень радиации в коридоре, Робот

| вышел из коридора вправо

нач цел n, вещ S

n:= 0; S:= 0

нц пока снизу стена

n:= n + 1; S:= S + радиация

вправо

кц

утв | n = длина коридора, S = суммарная радиация

r:= S /n

Кон

 

Алгоритм Евклида

 

Рассмотрим такую задачу: найти наибольший общий делитель двух натуральных чисел. Один из способов решения этой задачи был предложен древнегреческим математиком Евклидом, жившим более двух тысяч лет назад. Суть метода Евклида в следующем: большее из двух чисел надо заменить разностью этих чисел. При этом все общие делители, а значит, и наибольший из них, сохраняются. Если проделать эту операцию несколько раз, то, в конце концов, числа станут равны друг другу и полученное значение будет искомым.

 

 

Запишем алгоритм Евклида на алгоритмическом языке.

А58

алг Евклид (арг цел а, b, рез цел d)

дано а > 0 и b > 0

надо | d = НОД (а, b)

начцел m, n | дополнительные величины нужны, чтобы не менять

| значения аргументов

m:= а; n:= b

нц пока m<> n

утв | инвариант цикла: НОД (m, n) = НОД (а, b)

если m > n

то m := m – n

иначе n := n – m

Все

кц

утв m = n | НОД (m, n) = НОД (а, b)

d := m

Кон

Докажем правильность этого алгоритма. Рассмотрим инвариант цикла. Ясно, что он справедлив при первом выполнении цикла — в этот момент значения т и п совпадают со значениями а и b.

Предположим, что при некотором выполнении цикла инвариант справедлив. Пусть в этот момент т > п. Тогда выполнится команда m:= m - n и величина т получит новое значение. При этом все общие делители т и п остаются прежними, так как если т и п делятся на х, то т - п также делится на х. Аналогично сохраняются все делители, если п > т.

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

Условие, записанное после цикла, следует из инварианта цикла и условия окончания цикла (т = п). Из чего очевидно вытекает НОД (а,b) = т.

Осталось доказать, что выполнение цикла завершится. Для этого заметим, что при каждом выполнении цикла большее из чисел т и п уменьшается, но при этом они остаются положительными. Ясно, что это не может продолжаться бесконечно долго, следовательно, выполнение цикла когда-нибудь завершится.