Подпрограммы. Локальные и глобальные переменные

Будем называть процедуры и функции подпрограммами, так как они входят внутрь программы.

 

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

Исследуем взаимодействие подпрограмм в такой программе. Для этого рассмотрим глупую простую "сложную" программу А, вся задача которой - выполнить по порядку следующие вещи:

1) присвоить значение 5 переменной х,

2) затем вызвать процедуру В, зачем-то возводящую 10 в квадрат и печатающую текст "Результат равен ",

3) и наконец, напечатать значение х:

VAR x,y: Integer;

PROCEDURE B; BEGIN y:=10*10; Write('Результат равен ') END;

Begin

x:=5;

B;

WriteLn(x);

End.

Очевидно, программа напечатает Результат равен 5.

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

Сами подпрограммы тоже достаточно велики, и каждая из них может использовать десятки переменных. При этом возникает опасность, что автор какой-нибудь подпрограммы случайно использует внутри подпрограммы для ее нужд имя переменной, используемой в другой подпрограмме или в общей программе для других нужд, и таким образом испортит ее значение. Пусть, например, в нашей процедуре В ее автор опрометчиво присвоил бы значение 10*10 переменной с именем х. Тогда программа выглядела бы так:

VAR x,y: Integer;

PROCEDURE B; BEGIN x:=10*10; Write('Результат равен ') END;

Begin

x:=5;

B;

WriteLn(x);

END.

Очевидно, данная программа напечатала бы Результат равен 100.

 

Для защиты от таких ошибок руководитель проекта должен внимательно следить, чтобы разные подпрограммы не использовали переменных с одинаковыми именами. Но для больших программ этот контроль очень трудоемок и неудобен. Вместо этого в современных языках программирования разработан механизм локальных переменных. Локальная переменная- это переменная, описанная не в главной программе, а внутри подпрограммы. Если программист В знает, что его число 10*10 нигде, кроме как в процедуре В, не нужно, он описывает соответствующую переменную х внутри процедуры В, ничуть не заботясь, что переменные с таким же именем встречаются в других местах программы:

VAR x: Integer;

PROCEDURE B;

VAR x: Integer;

BEGIN x:=10*10; Write('Результат равен ') END;

Begin

x:=5;

B;

WriteLn(x);

END.

Данная программа напечатает Результат равен 5. Произойдет это вот по какой причине: Переменные, описанные внутри и снаружи подпрограммы, компилятор считает разными переменными, даже если они имеют одинаковые имена. Переменная х, описанная в программе, это совсем другая переменная, чем х, описанная в подпрограмме, и помещаются эти переменные в разных местах памяти. Поэтому и не могут друг друга испортить. Вы можете вообразить, что это переменные с разными именами xглоб и xлок.

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

Переменная, описанная в главной программе, называется глобальной переменной. Она видна отовсюду в программе и внутри подпрограмм и каждая подпрограмма программы может ее испортить. Но когда подпрограмма натыкается на переменную x, описанную внутри самой этой подпрограммы, то она работает только с ней и не трогает переменную x, описанную снаружи.

Рассмотрим еще один пример:

VAR x,z: Integer;

PROCEDURE B;

VAR x,y: Integer;

BEGIN

x:=20; y:=30; z:=40

END;

Begin

x:=1; z:=2;

B;

WriteLn(x,' ',z)

END.

Программа напечатает 1 40. Пояснение: Оператор WriteLn(x,z) находится снаружи процедуры В, и поэтому локальная переменная х=20, описанная внутри В, из него не видна. Зато прекрасно видна глобальная переменная х=1, которую он и печатает. Переменная же z не описана внутри В, поэтому она глобальна, и оператор z:=40 с полным правом меняет ее значение с 2 на 40.

Для полной ясности приведу порядок работы компьютера с этой программой:

1) В сегменте данных оперативной памяти компилятор отводит место под Х глобальное и Z глобальное.

2) Программа начинает выполняться с присвоения значений Х глобальное = 1 и Z глобальное = 2.

3) Вызывается процедура В. При этом в стеке оперативной памяти отводится место под Х локальное и У локальное.

4) Присваиваются значения Х локальное = 20, У локальное = 30 и Z глобальное = 40.

5) Программа выходит из процедуры В. При этом исчезают переменные Х локальное = 20 и У локальное = 30.

6) Компьютер печатает Х глобальное = 1 и Z глобальное = 40.

 

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

Массивы как параметры

Параметрами подпрограмм могут быть переменные не только простых, но и сложных типов, таких как массивы, записи, множества. Рассмотрим для иллюстрации пример с массивами.

Задача: Имеется два массива, по два числа в каждом. Напечатать сумму элементов каждого массива. Использовать функцию sum, единственным параметром которой является имя суммируемого массива.

Программа:

TYPE vector = array [1..2] of Integer;

VAR a,b: vector;

FUNCTION sum (c:vector):Integer;

BEGIN sum:=c[1]+c[2] END;

BEGIN

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

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

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

END.

Начиная вычислять функцию 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;

BEGIN

x:=1000;

B(1);

WriteLn(x)

END.

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

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

VAR x: Integer;

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

BEGIN c:=c+y END;

BEGIN

x:=1000;

B(1, x);

WriteLn(x)

END.

Здесь 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;

BEGIN

if N=1 then Factorial:=1;

if N>1 then Factorial:=N* Factorial(N-1)

END;

BEGIN

WriteLn(Factorial(3))

END.

Обратите внимание, что в программе нигде не употребляется оператор цикла. Вся соль программы в том, что функция Factorial вместо этого включает в себя вызов самой себя - Factorial(N-1).

 

Что же происходит в компьютере во время выполнения программы? Механизм происходящего в точности соответствует нашему рассуждению по рекурсии.

 

Все начинается с того, что Паскаль пробует выполнить строку WriteLn(Factorial(3)). Для этого он вызывает функцию Factorial. Выполнение подпрограммы начинается с того, что в стеке отводится место для всех формальных параметров и локальных переменных, а значит и для нашего формального параметра N. Затем фактический параметр 3 подставляется на место формального параметра N, то есть в стек в ячейку N посылается 3. Затем выполняется тело функции. Так как 3>1, то Паскаль пытается выполнить умножение 3* Factorial(3-1) и сталкивается с необходимостью знать значение функции Factorial(2), для чего вызывает ее, то есть отправляется ее выполнять, недовыполнив Factorial(3), но предварительно запомнив, куда возвращаться.

 

Спускаюсь на ступеньку ниже. В соседнем месте стека отводится место для N. Это уже другое N, путать их нельзя. В эту ячейку N посылается 2. Затем выполняется тело функции. Пусть вас не смущает, что Паскаль второй раз выполняет тело функции, не закончив его выполнять в первый раз. Так как 2>1, то Паскаль пытается выполнить умножение 2* Factorial(2-1) и сталкивается с необходимостью знать значение функции Factorial(1), для чего вызывает ее.

 

Спускаюсь еще на ступеньку. В соседнем месте стека отводится место еще для одного N. В эту ячейку N посылается 1. Затем выполняется тело функции. Так как 1=1, то Паскаль вычисляет Factorial:=1. Вот - впервые конкретное число. Затем Паскаль пытается выполнить следующую строку if N>1 then Factorial:=N* Factorial(N-1). Поскольку нельзя сказать, что 1>1, то выполнение тела функции закончено. Значит можно подниматься.

 

Поднимаюсь на одну ступеньку. Паскаль возвращается внутрь тела функции (той, где N=2) и успешно выполняет умножение - Factorial:=2*1=2.

 

Поднимаюсь еще на ступеньку. Паскаль возвращается внутрь тела функции (той, где N=3) и успешно выполняет умножение - Factorial:=3*2=6. Задача решена.

 

После выхода из подпрограммы место в стеке освобождается.

 

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

Теперь поговорим о переполнении стека. Размер стека в Паскале не превышает 64K. В нашем случае в стеке одновременно хранилось три копии формальных параметров и локальных переменных. Если бы мы вычисляли факториал десяти, то копий было бы десять. В более сложных, чем факториал, задачах стек может легко переполниться, о чем Паскаль сообщает, когда уже поздно.

Чем хорош рекурсивный стиль программирования? В нашей программе о факториале мы как бы и не программировали вовсе, а просто обяснили компьютеру, что такое факториал. Как бы перешли на новый уровень общения с компьютером: вместо программирования - постановка задачи.

Чем плох рекурсивный стиль программирования? Если мы для решения той же задачи напишем программу не с рекурсией, а с обычным циклом, то такая программа будет выполняться быстрее и потребует меньше памяти.

 

Задание 124: Напишите рекурсивную функцию fib для вычисления чисел Фибоначчи.

Сортировка

Пусть имеется ряд чисел: 8 2 5 4. Под сортировкой понимают их упорядочивание по возрастанию (2 4 5 8) или убыванию (8 5 4 2). Сортировать можно и символы (по алфавиту или коду ASCII) и строки (как слова в словаре).

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

 

Задача: Задан массив из 100 произвольных положительных чисел. Отсортировать его по возрастанию.

Если мы не можем сходу запрограммировать задачу, нужно подробно представить себе, в каком порядке мы решали бы ее вручную, без компьютера. Как бы мы сами сортировали 100 чисел? Мы бы запаслись пустым листом бумаги из 100 клеток. Затем нашли бы в исходном массиве максимальное число и записали его в самую правую клетку, а в исходном массиве на его месте записали бы число, меньшее самого маленького в массиве (в нашем случае подойдет 0). Затем нашли бы в изменившемся исходном массиве новое максимальное число и записали его на второе справа место. И так далее.

Вот программа для 10 чисел:

CONST N = 10;

TYPE vector = array [1..N] of Word;

CONST massiv_ishodn: vector =(3,8,4,7,20,2,30,5,6,9); {Это исходный массив}

VAR massiv_rezult: vector; {Это наш пустой лист бумаги}

i: Word;

FUNCTION maximum (m:vector; N:Word; var Nomer_max: Word):Word; {Это вспомогательная функция для поиска максимума в массиве}

VAR i,max:Word;

BEGIN

max:=m[1]; Nomer_max:=1; {Это порядковый номер максимального элемента }

for i:=2 to N do if max<m[i] then begin max:=m[i]; Nomer_max:=i end;

maximum:=max

END;

PROCEDURE sortirovka (mass_ish:vector; N:Word; var mass_rez:vector); {Основная процедура сортировки}

VAR i, Nom_max:Word;

BEGIN

for i:=1 to N do begin

mass_rez[N+1-i]:=maximum(mass_ish, N, Nom_max);

mass_ish[Nom_max]:=0

end {for};

END;

BEGIN

sortirovka (massiv_ishodn, N, massiv_rezult);

for i:=1 to N do Write (massiv_rezult[i],' '); {Распечатываем отсортированный массив}

END.

Функция maximum, кроме того, что сама имеет значение максимального элемента массива, выдает еще порядковый номер максимального элемента - Nomer_max. Это называется побочным эффектом функции.

 

Методов сортировки много. Приведенный метод - самый примитивный. Мало того, что нам пришлось расходовать память на второй массив, для выполнения сортировки массива из 100 элементов понадобилось бы около 100*100=10000 операций сравнения элементов массива между собой.

Существуют методы гораздо более эффективные. Приведу один из них - метод пузырька. Представьте себе тонкую вертикальную трубку с водой. Запустим снизу пузырек воздуха. Он поднимется до самого верха. Затем пустим еще один. Он поднимется наверх и остановится сразу же под первым. Затем запустим третий и так далее все сто пузырьков.

А теперь представим, что это не трубка, а наш исходный массив, а вместо пузырьков поднимаются максимальные элементы.

Вот алгоритм: Сравним первый элемент массива со вторым, и если второй больше, то ничего не делаем, а если первый больше, то меняем местами первый и второй элементы. В этом вся соль метода. Затем повторяем это со вторым и третьим элементами. Если третий больше, то ничего не делаем, а если второй больше, то меняем местами второй и третий элементы. Затем повторяем все это с третьим и четвертым элементами и так далее. Таким образом, максимальный элемент, как пузырек, поднимется у нас до самого верха.

Теперь, когда мы знаем, что элемент номер 100 у нас самый большой, нам предстоит решить задачу сортировки для массива из 99 элементов. Запускаем второй пузырек и так далее.

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

Вот программа:

CONST N = 10;

TYPE vector = array [1..N] of Word;

CONST massiv: vector =(3,8,4,7,20,2,30,5,6,9);

VAR i: Word;

PROCEDURE puziryok (var mass:vector; Razmer:Word);

VAR i,m,c:Word;

BEGIN

for m:=Razmer downto 2 do begin {Всего пузырьков – 9}

for i:=1 to m-1 do begin {i увеличивается – пузырек ползет вверх}

if mass[i]>mass[i+1] then begin {Стоит ли обмениваться значениями}

c:=mass[i]; {Три оператора для обмена значений двух элементов с помощью}

mass[i]:= mass[i+1]; {транзитного элемента c}

mass[i+1]:=c

end {if}

end {for};

end {for};

END;

BEGIN

puziryok (massiv,N);

for i:=1 to N do Write (massiv[i],' '); {Распечатываем отсортированный массив}

END.

Задание 125: Отсортируйте по убыванию двумерный массив. Я имею в виду вот что:

a[1,1] >= a[1,2] >= … >= a[1,N] >=

>= a[2,1] >= a[2,2] >= …>= a[2,N] >=

>= a[3,1] >= a[3,2] >= …

 

Глава 14. Строгости Паскаля

«Сердцем» этой главы является параграф «Синтаксические диаграммы», так как там материал о грамматике Паскаля представлен в наиболее строгом и упорядоченном виде. Так что после прочтения многих параграфов из этой главы стоит заглянуть в «Синтаксические диаграммы», чтобы окончательно разложить все по полочкам.

Структура программы

Самая маленькая программа на Паскале имеет такой вид:

BEGIN END.

Она, естественно, ничего не делает. Если мы хотим заставить программу что-то делать, то все операторы, приказывающие выполнять нужные нам действия, мы должны записать между BEGIN и END. Например:

BEGIN WriteLn(1993); WriteLn(1994) END.

Обычно программа содержит переменные, константы, обращения к подпрограммам и прочие элементы. Все они должны быть описаны выше BEGIN. Например:

CONST k = 10;

VAR a: Real;

BEGIN

a:=5;

WriteLn(a+k)

END.

Таким образом, программа на Паскале состоит из двух и только двух разделов:

1) выше BEGIN расположен раздел описаний,

2) ниже BEGIN расположен раздел выполняемых операторов.

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

 

Приведем полный список служебных слов, после которых задаются описания:

· Переменные описываются после служебного слова VAR

· Метки описываются после служебного слова LABEL

· Константы описываются после служебного слова CONST

· Процедуры описываются после служебного слова PROCEDURE

· Функции описываются после служебного слова FUNCTION

· Новые типы, определяемые программистом,

описываются после служебного слова TYPE

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

И наконец, программа может иметь заголовок, который состоит из служебного слова PROGRAM и в простейшем случае имени программы.

Пример программы:

PROGRAM Divan;

USES Crt,Graph;

Label met1,met2;

Const k = 100;

S = 'Хорошо!';

TYPE Kniga = array [1..k] of String;

Tablitsa = array [0..20,1..10] of Integer;

Minuta = 0..60;

VAR x,y: Real;

Uspevaemost: Tablitsa;

PROCEDURE Torpeda......

FUNCTION Invers......

Begin

.......

End.