Билет 4

Задание 1:

Семакин – стр. 39-48; задачник №1 – 10-26.

Задание № 2:

Вопросы:

1. Какую роль в компьютерных программах играют процедуры и функции? В чем их различия?

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

1. Процедуры и функции представляют собой относительно самостоятельные фрагменты программы, оформ­ленные особым образом и снабженные именем. Упоминание этого имени в тексте программы называется вы­зовом процедуры (функции). Отличие функции от процедуры заключается в том, что результатом исполне­ния операторов, образующих тело функции, всегда является некоторое единственное значение или указатель, поэтому обращение к функции можно использовать в соответствующих выражениях наряду с переменными и константами. Условимся далее называть процедуру или функцию общим именем «подпрограмма», если только для излагаемого материала указанное отличие не имеет значения. Подпрограммы представляют собой инструмент, с помощью которого любая программа может быть разбита на ряд в известной степени незави­симых друг от друга частей. Такое разбиение необходимо по двум причинам. Во-первых, это средство эконо­мии памяти: каждая подпрограмма существует в программе в единственном экземпляре, в то время как об­ращаться к ней можно многократно из разных точек программы. При вызове подпрограммы активизируется последовательность образующих ее операторов, а с помощью передаваемых подпрограмме параметров нуж­ным образом модифицируется реализуемый в ней алгоритм.

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

Описать подпрограмму - это значит указать ее заголовок и тело. В заголовке объявляются имя подпрограммы и формальные параметры, если они есть. Для функции, кроме того, указывается тип возвращаемого ею ре­зультата. За заголовком следует тело подпрограммы, которое, подобно программе, состоит из раздела описа­ний и раздела исполняемых операторов. В разделе описаний подпрограммы могут встретиться описания под­программ низшего уровня, в тех - описания других подпрограмм и т.д.

Описание и вызов. В Паскале подпрограммы называются процедурами и функ­циями и описываются в разделе с тем же названием.

Процедура имеет такую же структуру, как и программа, но с двумя отличиями:

• заголовок процедуры имеет другой синтаксис и включает служебное слово procedure;

• описание процедуры заканчивается точкой с запятой (а не точкой).

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

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

procedure <имя> (<список описаний формальных параметров>) Описание формальных параметров может иметь вид

<список имен>: <тип> или var <список имен>: <тип>

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

Оператор вызова процедуры имеет вид

<имя процедуры> (<список выражений>);

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

Параметры-переменные следует использовать для представления результатов процедуры.

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

Функция - это подпрограмма, определяющая единственное скалярное, вещественное или строковое значение. Отличия подпрограммы-функции от процедуры:

• заголовок функции начинается со служебного слова function и заканчивается указанием типа значения функции:

function <имя> (список описаний формальных параметров): <тип>;

• раздел операторов функции должен содержать хотя бы один оператор при­бивания имени функции;

• обращение к функции - не оператор, а выражение вида

<имя функции> (<список фактических параметров>). Функции (и процедуры) могут использовать свое имя в собствен­ном описании,

т.е. могут быть рекурсивными.

Пример: составим программу, которая для заданных четырех натуральных чисел а, Ь, с, d напечатает наибольшие об­щие делители первой и второй пар чисел и

сравнит их по величине.

В программе определим рекурсивную функцию nod(x,y) по формулам

Применяя эти формулы к числам 21 и 15, последовательно находим nod(21,15) = nod(6,15) = nod(15,6) = nod(3,6) = nod(6,3) = nod(0,3) = nod(3,0) = 3.

Программа 19

program four;

var a,b,c,d,m,n:integer;

function nod(x,у: integer) '.integer;

var h:integer;

begin

if y=0 then h:=x

else if x<y then h:=nod(y,x) else h:=nod(x mod у, у); nod:=h end; begin

writeln('введите 4 натуральных числа¹)»

read(a,b,c,d); writeln;

m:=nod(a,b); n:=nod(c,d);

writeln ('нодС, a, ', ',b, ') = ',m);

writeln('нод(',c,',',d,')=',n);

if m>n then writeln('первый > второго')

else if m<n then writeln(' первый < второго')

else writeln('нод пар равны') end.

2. Рекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Рассмотрим классический пример - вычис­ление факториала (пример 18). Программа вводит с клавиатуры целое число N и выводит на экран значение N!, которое вычисляется с помощью рекурсивной функции РАС. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении

чисел с плавающей запятой, либо нажать Ctrl-Z и Enter. При выполнении правильно организованной рекур­сивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В примере 8.5 решение при N = 0 тривиально и используется для остановки рекурсии. Пример 8.5

Program Factorial;

{$S+} {Включаем контроль переполнения стека}

var

n: Integer;

Function Facfn: Integer): Real;

{Рекурсивная функция, вычисляющая n! }

begin {Fac}

if n < 0 then

WriteLn ('Ошибка в задании N')

else

if n = 0 then

Fac:= 1

else Fac:= n * Fac(n-l)

end {Fac};

{---------------}

begin {main} repeat

ReadLn (n);

WriteLn ('n!= ',Fac(n))

until EOF

end {main}.

Изучая в предыдущем разделе язык Паскаль, мы уже использовали понятие ре­курсии. Однако оно столь важно и прин­ципиально, что с ним следует познакомиться детальнее.

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

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

procedure RETR; begin

инициализация начального хода repeat выбор очередного хода

if подходит then его запись; if решение не полное then RETR;

if неудача then стирание хода и возврат на предыдущий until удача or нет хода end.

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

Программа 39

program tur;

var i, j, ii, jj, n, nn: integer; q: boolean;

dx, dy:array[1..8] of integer; h: array[1..8,1..8] of integer; (*рекурсивная процедура - попытка сделать ход*) procedure try(i,x,у:integer; var q:boolean);

var k, u, v: integer; ql: boolean; begin

k:=0; repeat k:=k+l; ql:=false; u:=x+dx[k]; v:=y+dy[k];

if { (K=u)and(u<=n)and(K=v)and(v<=n)) and(h[u, v]=0)

then begin h[u,v]:=i;

(*для отладки и наблюдения процесса поиска с возвратом*) for ii:=l to n do begin for jj:= 1 to n do

write(h[ii,jj]:5); writeln; end; readln;

if i<nn then begin try(i+l,u,v,ql); if not(ql) then h[u,v]:=0 else ql:=true; end

else ql:=true end;

until (ql) or (k=8); q:=ql;

end; (*конец процедуры*) begin

dx[l]:=2; dx[2]:=l; dx[3]:=-l; dx[4]:=-2; dx[5]:=-2;

dx[6]:=-l; dx[7]:=l; dx[8]:=2; dy[l]:=1; dy[2]:=2;

dy[3]:=2; dy[4]:=1; dy[5]:—1; dy[6]:=-2;

dy[7]:=-2; dy[8]:—1;

write('введи n: '); readln(n);

for i:=l to n do for j:=l to n do h[i,j]:=O;

write('введи i,j: '); readln(i,j); nn:=n*n;

h[i, j]:=1; try (2, i, j,q);

if q then begin

for i:=l to n do begin

for j:= 1 to n do write(h[i,j]:5); writeln; end; end

else writeln('нет маршрута¹); readln end.