Практика программирования (Бейсик, Си, Паскаль)
         

Дерево решений


В начале XX в. многие американские фермеры увлекались игрой в "15", за решение которой предлагался весьма солидный приз. На квадратном поле размером 4x4 размещались 15 фишек с числовыми номерами 1, 2, ..., 15.

Наличие одного свободного поля позволяло передвигать фишки по горизонтали и вертикали с целью их сортировки по возрастанию номеров. Позиция, за которую предлагалось вознаграждение в размере $100000, содержала единственное нарушение порядка — фишки с номерами 14 и 15 были переставлены местами. Позднее было доказано, что из этой позиции невозможно перейти к полностью упорядоченной последовательности фишек. Так что призовой комитет ничем не рисковал.

Более того, оказалось, что все позиции фишек делятся на две категории. Если суммарное количество нарушений порядка в исходной позиции было четным, то полная сортировка фишек возможна. И тогда единственный смысл игры (исключая простое времяпрепровождение) заключался в достижении полностью упорядоченной расстановки за минимальное количество ходов. Для определенности под ходом мы будем подразумевать перемещение одной фишки на свободное место (в реальной игре прибегают к одновременному сдвигу двух или трех фишек, расположенных в одной строке или одном столбце).

С целью сокращения количества переборов мы продемонстрируем аналогичную игру на поле размером 2x3, где расположены фишки с буквами А, В, С, I, S. Цель игры — за минимальное число ходов перевести заданную исходную позицию в позицию BASIC:


Идея решения этой задачи заключается в построении полного дерева решений, в верхушке которого располагается целевая позиция BASIC. Каждый последующий уровень дерева образуют позиции, полученные из предыдущей вершины за один ход. С целью удобства ввода начальной позиции и последующего отображения ходов пустая клетка у нас будет представлена символом "*".

В нашей игре начало дерева может выглядеть следующим образом:


Естественно, что в очередной вершине дерева должна находиться позиция, не повторяющая предыдущие позиции. Так как общее количество перестановок из шести элементов равно 6!=720, то общее количество вершин в нашем дереве не будет превосходить эту границу. Более того, задача симметрична и из целевой позиции BASIC* можно будет породить ровно 359 новых вершин.




Для хранения дерева допустимых позиций используем два массива — массив строк tree, обеспечивающий хранение 360 шестисимвольных значений позиций, и числовой массив ind[360], в элементах которого будут фиксироваться индексы породивших строк. В нашем примере начальное заполнение массивов tree и ind может выглядеть следующим образом (табл. 6.1):

Таблица 6.1. Начальное заполнение массивов tree и ind



Индекс строки

 Значение строки

 Ссылка на породившую строку
0

 BASIC*

 -1
1

 BAIC*S

 0
2

 BASI*C

 0
3

 B*AICS

 1
4

 B*SIAC

 2
5

 BASIC

 2
6

 BCAI*S

 3
После того как построение полного дерева приводимых решений будет завершено, поиск оптимальной цепочки перестановок сводится к довольно простой процедуре. Сначала надо проверить, содержится ли исходная позиция среди вершин дерева. Если ее там нет, то заданная позиция не может быть сведена к позиции BASIC*. Если заданная позиция обнаружена в k-й вершине, то для восстановления цепочки переходов используем массив индексов породивших строк:

k1 = ind[k] - индекс предыдущей вершины, определяющей 1-й ход;

k2 = ind[k1l] - индекс вершины, определяющей 2-й ход;

k3 = ind[k2] - индекс вершины, определяющей 3-й ход;

....................................................

И это построение надо продолжать до тех пор, пока мы не встретим целевую вершину, у которой нет продолжения (ее индекс равен —1).

Совет 1 (общий)

Для построения дерева решений можно воспользоваться самым простым перебором: если пустая клетка находится на пересечении i-й строки и j-ro столбца, то теоретически с ней могут поменяться местами символы с индексами (i-l, j), (i+1, j), (i, j-1), (i, j + 1). На самом деле допустимых перемещений не четыре, а три или два, в зависимости от положения пустой клетки. Следовательно, в процедуре change придется позаботиться о проверке на принадлежность границам матрицы каждого кандидата на перемещение. И включать в дерево решений мы будем только те позиции, которые еще не встречались.



Совет 2 (общий)

Для удобства манипуляций со значениями вершин их целесообразно рассматривать и как одномерные строки, и как двумерные массивы 2x3, каждый элемент которых представлен соответствующим символом. Первое удобно для организации сравнения позиций, а второе—для перестановки фишек. Связь между одномерным индексом k и парой двумерных индексов (i,j) осуществляется по формулам:

k = i * 3 + j. i = k div 3. j = k mod 3.



Следует не забывать, что приведенные формулы справедливы, если индексы в массивах отсчитываются от 0, например так, как это делается в Си. Однако в строках Бейсика и Паскаля индексы символов отсчитываются от 1. Поэтому в соответствующих фрагментах программ введена соответствующая коррекция значения одномерного индекса k.

Совет 3 (общий)

Для более четкой организации структуры программы выделим следующие программные единицы:

level — процедура, порождающая новые вершины в дереве решений из позиции с индексом from;

change (il, jl) —процедура, осуществляющая обмен символа с указанными индексами, и символа "*", расположенного в позиции (i, j). Если новая позиция допустима и она еще не содержится в дереве решения, то процедура change присоединяет новую позицию к дереву решений и увеличивает значение счетчика вершин птах;

poisk — процедура, осуществляющая поиск исходной позиции роs 0 в дереве решений. Если исходная позиция найдена среди приводимых вершин, то процедура poisk осуществляет раскрутку цепочки ходов до главной вершины дерева;

print_tab(s) —процедура отображения очередного хода, представленного строкой s, в форме таблички размером 2x3. Координаты левого верхнего угла таблички на экране представлены глобальными переменными (х0, у0).

Программа 6_01.bas

DECLARE SUB change (il AS INTEGER, j1 AS INTEGER)

DECLARE SUB printTAB (s AS STRING)

DECLARE SUB level ()

DECLARE SUB poisk ()

REM Дерево решений BASIC

DEFINT A-Z

DIM SHARED x0 AS INTEGER, y0 AS INTEGER, nmax AS INTEGER, k AS INTEGER

DIM SHARED from AS INTEGER



DIM SHARED tree(360) AS STRING * 6, ind(360) AS INTEGER, pos0 AS STRING * 6

nmax = 1: x0 = 1: y0 -= 2

tree(0) = "BASIC*"

ind(0) = -1

CLS

INPUT "Введите строку с исходной позицией - ", pos0

FOR from = 0 TO nmax - 1:

level NEXT from poisk END

SUB change (il AS INTEGER, jl AS INTEGER)

DIM n AS INTEGER, kl AS INTEGER, tmp AS STRING, str2 AS STRING

IF (il < 0) OR (il > 1) OR (jl < 0) OR (jl > 2) THEN EXIT SUB

kl = il * 3 + jl + 1

str2 = tree(from)

tmp = MID$(str2, k, 1)

MID$(str2, k, 1) =MID$(str2, kl, 1)

MID$(str2, kl, 1) = tmp

FOR n = 0 TO nmax - 1

IF str2 = tree(n) THEN EXIT SUB

NEXT n

ind(nmax) = from

tree(nmax) = str2

nmax = nmax + 1 END SUB

SUB level

FOR k = 1 TO 6

IF MID$(tree(from), k, 1) = "*" THEN EXIT FOR

NEXT k

i = (k - 1} \ 3 ' номер строки

j = (k - 1) MOD 3' номер столбца

CALL change(i - 1, j)

CALL change(i + 1, j )

CALL change(i, j - 1)

CALL change(i, j + 1)

END SUB

SUB poisk

FOR q = 0 TO nmax - 1

IF pos0 = tree(q) THEN GOTO m

NEXT q

PRINT "Эта позиция не сводится к требуемой"

EXIT SUB

m:

CALL printTAB(tree(q))

q = ind(q)

IF q >= 0 THEN GOTO m

END SUB

SUB printTAB (s AS STRING)

LOCATE y0, x0: PRINT "+-+-+-+"

LOCATE y0 + 1, x0: PRINT " | ";

MID$(s, 1, 1);

PRINT "|"; MID$(s, 2, 1);

PRINT "|"; MID$(s, 3, 1); "I" LOCATE y0 + 2, x0:

PRINT "+-+-+-+" LOCATE y0 + 3, x0: PRINT "|"; MID$(s, 4, 1);

PRINT "|"; MID$(s, 5, 1);

PRINT "|"; MID$(s, 6, 1); " |" LOCATE y0 + 4, x0:

PRINT "+-+-+-+" x0 = x0 + 10

IF x0 = 81 THEN y0 = y0 + 5: x0 = 1

END SUB

Программа 6_01.с

#include <stdio.h>

#include <conio.h>

#include <string.h>

void level();

void change(int il, int J12);

void poisk(};

void print_tab(char* s);

char tree[360][7];

char pos0[7];

int ind[360];

int i,j,k,nmax=l;



int x0=l,y0=2;

int from;

void main() {

strcpy(&tree[0][0],"BASIC*");

ind[0]=-l;

clrscr();

printf("Введите строку с исходной позицией - ");

scanf("%s",pos0);

for(from=0; from<nmax; from++) level();

poisk () ;

getch ();

}

//---------------------------------

void level() {

for{k=0; k<6; k++)

if(tree[from][k]=='*')break;

i=k/3; //номер строки

j=k%3; //номер столбца

change (i-1,j);

change(i+1,j);

change(i,j-1);

change(i,j+1); }

//-------------------------------------

void change(int i1, int j1) { char tmp,str2[7];

int n,kl;

if(il<0 || i1>l || jl<0 | | jl>2) return;

kl=il*3+jl;

strcpy(str2, (char*)street from][0]);

tmp=str2[k]; str2[k]=str2[kl]; str2[kl]=tmp;

for(n=0; n<nmax; n++)

if(strcmp(str2,(char*)&tree[n][0])==0) return;

ind[nmax] =f rom;

strcpy((char*)stree[n] [0] , str2);

nmax++;

}

//--------------------------------------

void poisk() { char *p;

p=Stree[0][0] ;

for(int q=0; q<nmax; q++)

if(strcmp(pos0,p+q*7)==0) goto m;

printf("\ n Эта позиция не сводится к требуемой");

return;

m:

print_tab(p+q*7) ;

q=ind[q];

if(q>=0) goto m;

return;

}

//-------------------------------------------

void print_tab(char* s) { char top[]= "+-+-+-+";

charmid[]= "+-+-+-+";

char bottom[]="+-+-+-+";

gotoxy(x0,y0);

printf("%s",top);

gotoxy(x0,y0+l) ;

printf("|%c|%c!%c|",s [0],s [1],s [2]);

gotoxy(x0,y0+2);

printf("%s", mid);

gotoxy(x0,y0+3);

printf(";%ci%ci%c!",s[3],s[4],s[5]);

gotoxy(x0,y0+4);

printf("%s",bottom);

x0=x0+10;

if(x0==81){y0=y0+5;x0=l;} }

Программа 6_01.pas

program basic; uses Crt;

var

tree:array [0..359] of string[6];

pos0:string[6];

ind:array [0..359] of integer;

x0,y0,i,j,k,nmax,from:integer;

procedure print_tab(s:string);

begin

gotoxy(x0,y0);

write{'+-+-+-+' );

gotoxy(x0,y0+1);

write {' |',s[l],'|',s[2],'|',s[3],'|');



gotoxy(x0,y0+2);

write('|-+-+-|');

gotoxy(x0,y0+3);

write('!',s[4],'|',s[5],'|',s[6],'| ');

gotoxy(x0,y0+4);

write('+-+-+-+');

x0:=x0+10;

if(x0=81)then begin y0:=y0+5;

x0:=l;

end;

end;

procedure poisk;

var

q:integer;

label m; begin

for q:=0 to nmax-1 do

if pos0=tree[q] then goto m;

write(' Эта позиция не сводится к требуемой');

readln;

exit;

m:

print_tab(tree[q]};

q:=ind[q];

if q>=0 then goto m;

end;

procedure change(il,jl:integer);

var

tmp:char;

str2:string[6];

n,kl:integer; begin

if (i1<0)or (i1>l)or(j1<0)or(j1>2) then exit;

kl:=il*3+jl+l;

str2 : =tree.[ from] ;

tmp:=str2[k] ;

str2[k]:=str2[kl];

str2[kl]:=tmp;

for n:=0 to nmax-1 do

if str2=tree[n] then exit;

ind[nmax]:=from;

tree[nmax]:=str2;

inc(nmax); end;

procedure level; begin

for k:=l to 6 do

if tree[from] [k] = '*' then break;

i:=(k-l) div 3; {номер строки}

j:=(k-l) mod 3; {номер столбца}

change(i-1,j};

change(i+1,j);

change(i,j-1);

change(i,j+1);

end;

begin

nmax:=l;

x0:=l; y0:=2;

tree[0]:='BASIC*';

ind[0]:=-1;

clrscr;

write('Введите строку с исходной позицией');

read(pos0);

for from:=0 to 359 do level;

poisk;

readln;

end.


в предыдущих разделах должны были


Подпрограммы (процедуры) и функции

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

Во-первых, упрощается логика программ за счет вынесения многочисленных деталей за рамки основного алгоритма. Появляется возможность конструировать программу "сверху — вниз", составляя ее по началу из пустых блоков (заглушек), о которых известно только их функциональное назначение. Потом каждый из блоков детализируется, разбиваясь на более мелкие программные единицы и т. д. Подпрограммы, текст которых обычно не превышает одну-две страницы, гораздо легче анализировать и отлаживать. Во-вторых, выделение подпрограмм позволяет уменьшить общий объем программы особенно в тех случаях, когда к ним приходится многократно обращаться из разных точек. Наконец, многие подпрограммы могут быть использованы повторно при решении других задач.

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

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

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

Текст программы на алгоритмическом языке, оформленный в виде дискового файла с соответствующим расширением (bas, с, срр, pas), принято называть исходным модулем. В решении задачи может принимать участие один или несколько исходных модулей. В системе QBasic такие модули сменяют друг друга в оперативной памяти с помощью оператора CHAIN. Система Turbo С (Borland C++) позволяет разбить текст исходной программы на несколько программных файлов, которые могут быть протранслированы автономно и объединены между собой с помощью специального сборочного файла — проекта. В системе Turbo Pascal отдельные подпрограммы могут быть вынесены в специальным образом оформленные модули, начинающиеся с оператора unit и подключаемые к тексту исходной программы по директиве Uses.


Результатом трансляции (компиляции) каждого программного файла в системе Turbo С является объектный модуль — дисковый файл с расширением obj. В составе одного объектного модуля может находиться как головная функция, так и любое количество подчиненных ей пользовательских функций. С помощью сервисной программы tlib.exe объектные модули могут быть помещены в библиотеку — дисковый файл с расширением lib. Любая компонента библиотеки может быть использована при сборке готовой к исполнению программы.

Модули Паскаля, начинающиеся с оператора unit, после компиляции превращаются в дисковые файлы с расширением tpu (от Turbo Pascal Unit) и играют роль, аналогичную библиотекам объектных модулей на языке Си.

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



Оформление и вызов программных единиц в системе QBasic


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

Описанию внутренней функции с именем, обязательно начинающимся с символов "FN", предшествует заголовок вида:

DEF FNs1s2...[(аргументы)]

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

FNs1s2. . . = выражение

Признаком конца описания внутренней функции является оператор END DEF. В теле внутренней функции может находиться оператор EXIT DBF, обеспечивающий досрочное завершение вычислений при выполнении определенных условий.

Внутренняя функция, алгоритм вычисления которой сводится к единственному выражению, описывается одним оператором, после которого завершение END DEF не требуется:

DEF FNs1s2. . . [(аргументы)]=выражение

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

DEF FNd=SQR((X1-X2)^2+(Y1-Y2)^2+(Z1-Z2)^2)

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




Все программные единицы в Си носят название функций и разницу в оформлении настоящих подпрограмм и настоящих функций можно обнаружить по типу возвращаемого значения. Если в качестве указания типа использовано служебное слово void, то перед нами типичная подпрограмма (в терминах Си — функция, не возвращающая значение). Перед заголовком объявляемой функции всегда присутствует либо стандартный тип, либо описатель типа с последующей звездочкой. Последнее означает, что функция возвращает указатель на данное соответствующего типа. В частности, допускается, что таковым указателем может быть "void *" В самом общем виде заголовок функции выглядит следующим образом:

void имя_функции([параметры])

ИЛИ

тип имя_функции([параметры])

ИЛИ

тип * имя_функции([параметры])

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

int sign(int x)

{

/* Определение знака целого числа */

if(x<0) return -1;

if(x>0) return 1;

return 0; }

В отличие от Бейсика и Паскаля функции Си, не имеющие параметров, всегда сопровождаются пустыми круглыми скобками. Например — cirscr ().

Головная программа на Си представлена функцией main, которая может иметь до трех параметров, связанных с извлечением аргументов из командной строки. Чаще всего эта функция не имеет параметров и не возвращает значение:

void main(void)

К функции-подпрограмме в Си обращаются, указав ее имя со списком фактических параметров:

имя_функции(фактические параметры);

Функция, возвращающая значение, может использоваться как операнд в выражении соответствующего типа:

int qq;

qq=getch(); /*ожидание ввода кода символа с клавиатуры*/

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

sin(0.5);

Системная функция в данном случае проработает, но эффекта от такого вызова никто не заметит. Разве что немного увеличится время работы программы. А в случае с функцией getch игнорирование результата позволяет зафиксировать момент, когда пользователь нажал какую-то клавишу.




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

Внешняя функция начинается с заголовка:

FUNCTION имя_функции[(аргументы)][STATIC]

Добавка STATIC требует, чтобы значения всех локальных переменных после очередного обращения к функции были сохранены и моглиут быть использованы при последующем обращении к функции. Если по условиям задачи необходимо сохранять значения только некоторых локальных переменных, то слово STATIC может быть использовано в теле функции при объявлении соответствующих переменных:

STATIC Q1 AS INTEGER, F AS DOUBLE

В теле функции, состоящем из обычных операторов, обязательно должно присутствовать присвоение:

имя_функции = выражение

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

Признаком конца описания внешней функции является оператор END FUNCTION. Для досрочного выхода из подпрограммы вычисления функции используется оператор EXIT FUNCTION.

Тип внутренней или внешней функции определяется специальным символом, завершающим имя функции (% — короткий целый, & — длинный целый, ! — короткий вещественный, # — длинный вещественный, $ -строковый). Если имя функции завершается любым другим символом, то по умолчанию функции присваивается короткий вещественный тип.

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

Внутренняя подпрограмма, входящая в текст головной программы, обязательно должна начинаться с метки, на которую передается управление оператором GOSUB. Работа внутренней подпрограммы завершается оператором RETURN, после чего продолжается работа основной программы с оператора, следующего за GOSUB. В отличие от обычных подпрограмм у внутренней подпрограммы отсутствуют параметры, и она может оперировать только с переменными основной программы. Логически внутренние подпрограммы повторяют структуру подпрограмм в машинных кодах. К внутренней подпрограмме может обратиться только ее владелец.

Внешняя подпрограмма начинается с заголовка:

SUB имя-подпрограммы[(параметры)][STATIC]

Тело внешней подпрофаммы завершается оператором END SUB. Для досрочного прекращения работы программы используется оператор EXIT SUB.

К внешней подпрофамме можно обратиться из любой профаммной единицы двумя способами, особой разницы между которыми нет:

имя_подпрограммы [фактические параметры]

ИЛИ

CALL имя_подпрограммы[(фактические параметры)]





Как дань своему прототипу, — алгоритмическому языку АЛГОЛ, — Паскаль называет свои подпрограммы процедурами и начинает их описание со строки вида:

procedure имя_процедуры[(параметры)];

Тело процедуры на Паскале в точности повторяет структуру головной программы. В нем могут присутствовать разделы описания меток (label), констант (const), типов данных (type), переменных (var) и других процедур и функций, входящих в состав данной процедуры. Наличие вложенных процедур и функций отличает Паскаль и от Си, и от Бейсика. Собственно вычислительная часть тела процедуры начинается со служебного слова begin и заканчивается соответствующим end, после которого, в отличие от головной программы, следует не точка, а точка с запятой.

Фрагмент программы от заголовка процедуры до завершающей операторной скобки end принято называть блоком. Для Паскаля характерна возможность использования вложенных блоков, с каждым из которых можно связать натуральное число, соответствующее уровню вложения. Так, например, в блок А могут быть вложены два последовательных блока первого уровня — блоки в и с. Если же блок с вложен в блок в, входящий в свою очередь в блок А, то блок с уже имеет уровень два по отношению к блоку А. В теле любого блока могут содержаться обращения к вложенным блокам своего первого уровня или к последовательным блокам такого же уровня. Блок не имеет права напрямую обратиться к своим процедурам второго или более высокого уровня вложенности.

Если процедура А обращается к процедуре в, то описание процедуры в должно предшествовать описанию процедуры А. Однако, если программа включает рекурсивную цепочку из двух или более процедур, одна из них должна объявляться (но не описываться) первой с добавкой forward. Соответствующее объявление носит название опережающего (forward — впереди бегущий футболист, нападающий):

procedure имя_процедуры[(параметры)]; forward;

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




Для обращения к процедуре достаточно задать ее имя с последующим набором фактических параметров.

Описание функции отличается только тем, что ее заголовок начинается со служебного слова function и заканчивается указанием типа функции.

function имя_функции[(параметры)]:тип;

Тело функции отличается от тела подпрограммы только наличием оператора присваивания:

имя_функции:=выражение;

Досрочный выход из тела функции или тела процедуры осуществляется по оператору exit.

Головная программа на Паскале выступает в роли контейнера, содержащего все свои функции и процедуры. Первым оператором головной программы может быть не обязательная строка:

program имя_программы;

Собственно тело головной программы начинается с операторной скобки begin, расположенной вслед за последним объявлением, и завершается закрывающей операторной скобкой end с последующей точкой.




Оформление модулей на Паскале


В отличие от головной программы с ее первым необязательным оператором, модуль обязан начинаться со следующего заголовка:

Unit имя_модуля;

Если в качестве имени паскалевской программы может выступать любой идентификатор, в том числе и достаточно длинный, то именем модуля может быть только имя файла, допустимое в операционной системе MS-DOS. Это связано с тем, что при некоторых обстоятельствах (например, если пользователь вместо режима compile выбрал режим Make или Build) система программирования Turbo Pascal вынуждена заново оттранслировать пользовательские модули. И тогда она пытается открыть дисковые файлы, имена которых совпадают с именами обновляемых модулей.

Второе отличие модуля от головной программы заключается в структуре модуля, содержащего от одной до трех частей, начинающихся служебными словами interface, implementation И begin. Интерфейсная часть, следующая за словом interface, состоит из описания типов данных, констант и переменных, а также заголовков функций и процедур, доступных любой программе, использующей данный модуль.

Вслед за служебным словом implementation начинается раздел описания всех процедур и функций, включенных в состав модуля. Среди них, естественно, должны присутствовать все процедуры и функции, упомянутые в интерфейсной части. Однако, кроме них, в состав модуля могут входить любые процедуры и функции внутреннего пользования, доступные только внутри данного модуля. Об их существовании внешний пользователь не обязан знать. Если после завершения исполнительного раздела (implementation) встречается операторная скобка begin, то за ней следует так называемая инициирующая часть модуля. Эта часть содержит обычные операторы, выполняемые непосредственно перед стартом головной программы. Как и программа, модуль завершается операторной скобкой end с последующей точкой.

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

Unit Calendar interface type

Days=(Mon,Tue,Wed,Thu,Fri,Sat,Sun);

WorkingDays=Mon..Fri;

Months=(Jan,Feb,Mar,Apr,May,June,

July,Aug,Sept,Oct,Nov,Decem);

Summer=June..Aug;

Autumn=Sep.. Nov;

Spring=Mar..May;

DayNo=l..31;

YearNo=1900..2119;

Date=record Day:DayNo;

Month:Months;

Year:YearNo; end;

implementation end.

Модуль, содержащий только инициирующую часть, может произвести какие-то первоначальные действия — открыть временный файл, проверить принтер и т. п.



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


Для обеспечения максимальной независимости программных единиц во всех алгоритмических языках принято стандартное правило — данные, объявленные внутри программной единицы, являются собственностью этой программной единицы и образуют так называемый набор локальных данных. В QBasic и Си область действия локальных данных распространяется только на подпрограмму (функцию), в которой эти данные объявлены. Поэтому, несмотря на совпадение имен переменных, используемых в разных программных единицах, между такими переменными ничего общего нет. Это развязывает руки создателям программ, т. к. позволяет им не вникать в детали чужих программ, которые они собираются использовать. Наличие вложенных блоков в программах на Паскале немного модифицирует этот стандарт. Здесь действуют права наследования — любой внутренний блок имеет право использовать данные, объявленные во внешнем по отношению к нему блоке. Но если во внутреннем блоке объявляется переменная с таким же именем, как и во внешнем блоке, для нее выделяется новая ячейка оперативной памяти при одновременном сохранении значения переменной внешнего блока.

В связи с описанным разграничением данных возникает вопрос о механизмах взаимодействия программных единиц, одна из которых обращается к другой. Таких механизмов, в общем-то, два — передача данных через параметры и совместное использование общих (глобальных) переменных.

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

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




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

Как определить или задать тип параметра в подпрограммах и функциях на Бейсике? Обратите внимание на заголовок подпрограммы или функции. Имя каждого формального параметра либо сопровождается специальным знаком (% — короткий целый, & — длинный целый, ! — короткий вещественный, # -длинный вещественный, $ — строковый), либо за ним следует описатель типа вида AS type. В качестве описателя типа параметра может быть использовано одно из служебных слов INTEGER, LONG, SINGLE, DOUBLE или STRING.

Если параметром является массив, то, независимо от его размерности, вслед за именем располагаются пустые скобки. Для определения минимального и максимального значения индекса по каждому измерению фактического массива, который подпрограмма получит во время работы, следует использовать функции LBOUND и UBOUND. Первым аргументом таких функций является имя формального массива (а во время выполнения вместо него будет подставлено имя фактического массива), а вторым — порядковый номер индекса для многомерных массивов. Если формальный параметр А представлен одномерным массивом, то обращения LBOUND(A, 1) и LBOUND (А) эквивалентны.

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


В отличие от этого в системах компилирующего типа, к которым относятся и Turbo С, и Turbo Pascal, ситуация с формальными параметрами процедур и функций определена более жестко. В качестве любого конкретного пара-

метра можно передать либо адрес соответствующего фактического аргумента, либо его значение. Для параметров, принимающих только адреса, в Си используются указатели, а в Паскале — аргументы, снабженные описателем var. Все остальные параметры передаются только по значению. Чтобы предотвратить изменение фактического параметра, переданного по адресу, в списке аргументов перед описанием соответствующего формального параметра должно находиться служебное слово const.

Кроме аппарата параметров, программные единицы могут совместно использовать значения общих (глобальных переменных).

В QBasic объявление глобальных переменных, доступных в любой внешней подпрограмме или внешней функции, сопровождается добавкой SHARED (дословно - "совместно используемый"):

DIM SHARED A(20)
AS INTEGER, D
AS SINGLE
COMMON
SHARED A(20)
AS INTEGER, D
AS SINGLE

Последнее объявление означает, что общие переменные (массив А и одиночная переменная о) будут доступны не только всем подпрограммам и функциям данного программного файла, но и другим Бейсик-программам, загружаемым в память по оператору CHAIN.

В программных файлах Си переменные, объявленные за пределами всех функций, считаются глобальными по отношению к функциям этого файла и могут использоваться в теле любой функции без каких-либо дополнительных указаний. Но если в теле функции объявлена переменная с таким же именем, то зона ее влияния локализована в данной функции и глобальная переменная с аналогичным именем здесь уже не действует. Если же задача собирается из нескольких программных файлов, общие для всех функций переменные целесообразно выделить в отдельный программный файл. В функциях, где предполагается их использование, такие переменные должны объявляться с описателем extern (внешний):

extern int a[20]; extern float d;

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