Индукция. Рекурсия. Стек

END.

BEGIN

END.

BEGIN

Параметры-значения и параметры-переменные

END.

BEGIN

a[1]:=10; a[2]:=20;

b[1]:=40; b[2]:=50;

WriteLn (sum(a),' ',sum(b));

Начиная вычислять функцию sum(a), Паскаль подставляет в ячейки для элементов массива c значения элементов массива a. Начиная же вычислять функцию sum(b), Паскаль подставляет в ячейки для элементов массива c значения элементов массива b.

В заголовке функции неправильно было бы писать

function sum (c: array [1..2] of Integer):Integer.

Необходимо было сначала определить тип массива в разделе TYPE, а затем использовать это определение и в описании a и b, и в заголовке функции. Таково требование синтаксиса Паскаля.

Задание 122. В школе два класса. В каждом - 5 учеников. Каждый ученик получил отметку на экзамене по физике. Определить, какой из двух классов учится ровнее (будем считать, что ровнее учится тот класс, в котором разница между самой высокой и самой низкой отметкой меньше).

Указание: Создать функции min(c:vector), max(c:vector) и raznitsa(c:vector).

Многие процедуры не только рисуют или звучат, но и, подобно функциям, вычисляют что-нибудь полезное. Например, процедура B из следующей программы увеличивает глобальную переменную x на значение параметра y.

VAR x: Integer;

PROCEDURE B (y:Integer);

BEGIN x:=x+y END;

x:=1000;

B(1);

WriteLn(x)

Будет напечатано число 1001.

Однако руководители проектов не любят, когда в подпрограммах встречаются имена глобальных переменных. Мало ли - руководителю придет в голову изменить имя глобальной переменной, и что тогда - переписывать все подпрограммы? Поэтому придумали использовать так называемые параметры-переменные. Вот та же программа с их использованием:

VAR x: Integer;

PROCEDURE B (y:Integer; var c:Integer);

BEGIN c:=c+y END;

x:=1000;

B(1, x);

WriteLn(x)

Здесь y - хорошо знакомый нам параметр. Называется он параметр-значение. При начале выполнения подпрограммы для параметра-значения выделяется место в стеке и туда посылается значение соответствующего фактического параметра (1).

c - незнакомый нам параметр-переменная, отличающийся от параметра-значения словом var. При начале выполнения подпрограммы для параметра-переменной никакого места в стеке не выделяется, а выделяется в стеке место только для адреса соответствующего фактического параметра. Подпрограмма через этот адрес работает непосредственно с переменной, являющейся фактическим параметром (x). Получается, что слово var «снимает защиту» со своего фактического параметра и вы вполне можете нечаянно его испортить.

Вопрос: имеет ли смысл писать B(1, 1000)? Ответ: не имеет, так как подпрограмма не будет знать, какой переменной присваивать результат 1001. Естественно, Паскаль выдаст сообщение об ошибке.

Задание 123: На двух станциях (A и B) в течение года измерялась температура. Соответственно созданы два массива чисел длиной 365. Затем оказалось, что на станции A термометр все время показывал температуру на 2 градуса выше настоящей, а на станции B - на 3 градуса ниже. Написать процедуру с двумя параметрами, которая исправляет исходный массив. Один формальный параметр - величина поправки, другой - параметр-переменная - массив температур.

Начну с классического примера о факториале. Факториалом целого положительного числа N называется произведение всех целых чисел от 1 до N. Например, факториал пяти равен 1*2*3*4*5, то есть 120. Факториал единицы считается равным 1.

Все понятно. Однако, существует еще один, совершенно ужасный способ объяснения, что такое факториал. Вот он:

“Факториал единицы равен 1. Факториал любого целого положительного числа N, большего единицы, равен числу N, умноженному на факториал числа N-1 .”

Если вам уже все ясно, значит вы - математический талант. Для нормальных людей поясню. Чтобы последнее предложение было понятнее, возьмем какое-нибудь конкретное N, например, 100. Тогда это предложение будет звучать так: Факториал числа 100 равен числу 100, умноженному на факториал числа 99.

Ну и что? И как же отсюда узнать, чему равен какой-нибудь конкретный факториал, скажем, факториал трех? Будем рассуждать совершенно чудовищным образом:

Смотрю в определение: Факториал трех равен 3 умножить на факториал двух. Не знаю, сколько это. Спускаюсь на ступеньку ниже.

Смотрю в определение: Факториал двух равен 2 умножить на факториал единицы. Не знаю, сколько это. Спускаюсь еще на ступеньку.

Смотрю в определение: Факториал единицы равен 1. Вот - впервые конкретное число. Значит можно подниматься.

Поднимаюсь на одну ступеньку. Факториал двух равен 2 умножить на 1, то есть 2.

Поднимаюсь еще на ступеньку. Факториал трех равен 3 умножить на 2, то есть 6. Задача решена.

Рассуждая таким образом, можно вычислить факториал любого числа. Способ рассуждения называется рекурсивным, а способ объяснения называется индуктивным.

Какое отношение все это имеет к компьютерам? Дело в том, что рекурсивный способ рассуждений реализован во многих языках программирования, в том числе - и в Паскале. Значит, этим языкам должен быть понятен и индуктивный способ написания программ.

Обозначим кратко факториал числа N, как Factorial(N), и снова повторим наш индуктивный способ объяснения:

“Если N=1, то Factorial(N) = 1.

Если N>1, то Factorial(N) вычисляется умножением N на Factorial(N-1).”

В соответствии с этим объяснением напишем на Паскале функцию Factorial для вычисления факториала:

FUNCTION Factorial(N: Byte): LongInt;

Дата добавления: 2014-12-27