Перечисляемый тип данных

 

Этот тип данных получил название перечисляемого, потому что он задается в виде перечисления некоторых значений. Эти значения образуют упорядоченное множество и являются константами. Для объявления переменной список возможных значений, разделенных запятой, указывается в круглых скобках.

Например,

Var month:(january, february, march,

april, may,june, july, august,

september, october, november,

december);

Порядок элементов перечисляемого типа определяется порядком их следования в описании. Левый имеет минимальное значение (значение функции Ord для него равно 0), а правый − максимальное.

К переменным перечисляемого типа можно применять операции сравнения. Так, например, february<november.

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

 

§26. Описание переменных, констант и типов

Раздел описания констант

 

Константа − это величина, которая не изменяет своего значения в процессе выполнения программы. С константами мы уже встречались, так как в общем случае константой является любое целое или вещественное число, символ, идентификаторы false и true, а также идентификаторы, обозначающие значения переменных перечисляемого типа. Но константа может быть обозначена и именем. В этом случае она должна быть объявлена в разделе описания констант. Раздел описания констант начинается словомConst (от англ. constancy − постоянство).

Например,

Const N=25; K=38; D=(N+K) Div 2;

Letter='f'; M=5E15;

Здесь N, К, D − целочисленные константы, Letter − константа символьного типа, а М − константа вещественного типа. Следует отметить, что константа D принимает свое значение после вычисления выражения. В разделе описания констант можно ис­пользовать лишь некоторые стандартные функции, такие, как Abs, Chr, Pred, Succ, Odd, Ord.

Именование констант делает программу более удобной для понимания и внесения исправлений. При изменении констант достаточно будет изменить соответствующие значения в разделе описания констант.

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

Const N: Integer=15; ch: Char=#87;

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

Раздел описания типов

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

Тип данных определяет:

• формат представления данных в памяти ЭВМ;

• множество допустимых значений;

• множество допустимых операций.

Примечание. Следует отметить, что все типы данных изучались по этой схеме.

Все простые типы языка Паскаль можно разделить на стандартные и пользовательские. К стандартным типам относятся типы: Integer, Real, Char, Boolean, а также некоторые другие.

Пользовательские типы объявляются в разделе описания типов, который открывается словомType.

Пример

Type

week=(sunday, monday, tuesday,

wednesday, thursday, friday,

saturday);

work_week=monday..friday;

day=l..31;

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

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

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

 

§27. Преобразование типов.

Совместимость типов

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

Рассмотрим такую ситуацию. Пусть заданы типы Т1 и Т2, а также описаны переменные р1 и р2 следующим образом:

Var p1:T1; p2:T2;

Когда можно присвоить переменной р1 значения р2: р1:=р2? Чтобы ответить на этот вопрос, рассмотрим совместимость простых типов по присваиванию. Операция р1:=р2 является допустимой, если истинно одно из следующих утверждений:

• Т1 и Т2 − тождественные типы.

Типы являются тождественными, если они описаны одним и тем же идентификатором или происходят от одного и того же идентификатора.

Пример

TypeT1=Real; T2=Real; T3=T1;

T4=(red, green, blue, black, white);

T5=(red, green, blue, black,white);

T6=T4;

Здесь T1, Т2 и Т3 − тождественные типы, Т4, Т5 − не тождественные, поскольку (red, green, blue, black, white) не являются идентификаторами типа, Т4 и Т6 являются тождественными.

• Т2 является поддиапазоном типа Т1. Например, Type T1=Real; T2=Integer;

(множество целых чисел входит в диапазон вещественных чисел).

• T1 и Т2 являются отрезками одного и того же типа.

Например:

TypeT1=1..100; T2=-3..20;

week= (dl, d2, d3, d4, d5, d6, d7);

working_week=(d1..d5);

Совместимость по присваиванию станет более понятна, если вспомнить, что переменные в памяти занимают определенное число байт. Так, переменная типа Integer занимает 2 байта, типа Real − 6 байт. Переменной, которая занимает 6 байт, можно присвоить значение, занимающее 2 байта, а наоборот − не всегда.

Совместимость типов необходима также в выражениях и операциях сравнения.

Program Example_66;

Var a: Byte; b: Integer; c: Longint;

Begin

Writeln('Введите 2 числа:

Byte,Integer)');

Readln(a, b);

c:=a+b;

Writeln(c);

End.

Определить тип следующих выражений: a+b; a+b+c; a+b+c+x, если переменные описаны так:

Var a:Byte; b:Integer;

c:Longint; x:Real;

Выражение справа в операторе присваивания вычисляется независимо от размера или типа переменной слева. Число 32867 не входит в диапазон допустимых значений типа Integer, именно вследствие этого мы получаем неправильный результат. Чтобы этого не случилось, нужно преобразовать переменные к более "вместительному" типу.

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

<идентификатор типа>(переменная).

Чтобы получить правильный результат, нужно записать следующий оператор:

c:=Longint(a)+Longint(b);

или:

c:=a+Longint(b);

Для преобразования типов используются также следующие функции:

Round(от англ. round − круглый, округлять) − округление числа до ближайшего целого

Trunc (от англ. truncate − урезать) − отбрасывание дробной части числа.

Int (от англ. integer – целый) − целая часть вещественного числа.

Frac(от англ. fraction − дробь) − дробная часть вещественного числа.

Low (от англ. low − низкий) − наименьшее значение данного порядкового или перечисляемого типа.

High (от англ. high − высокий, верх) − наибольшее значение данного порядкового или перечисляемого типа.

Пример 1

"Вечный календарь". Известно, что если дата лежит в диапазоне от 1582 до 4902 г., номер дня недели (номер воскресенья - 0, понедельника − 1,…, субботы − 6) равен остатку от деления на 7 значения выражения [2.6m-0.2]+d+y+[y/4]+[c/4]-2c

Здесь d − номер дня в месяце (1, 2, ...); m − номер месяца в году, нумерация начинается с марта (у марта − номер 1, у апреля − номер 2, ..., у декабря − номер 10, январь и февраль считаются месяцами с номерами 11 и 12 предыдущего года); у− две младшие цифры года; с − две старшие цифры года; [х] обозначает целую часть числа х.

Вычислить количество пятниц, приходящихся на 13−е число в XX столетии.

Решение

Program Example_67;

Type month=(marth, april, may, june,

july, august, September,

october, november, december,

january, february);

day=1..31;

year=1582..4902;

week=(sunday, monday, tuesday,

wednesday, thursday,

friday, saturday) ;

Consth=20;

d: day=13;

d_w: week= friday;

Var k:Integer;

{для подсчета кол-ва пятниц}

у: year; Mod_y: 0..99; int_y: 15..49;

m: month;

n:-50..1000;

Begin

k:=0;

For y:=(h-1)*100 To h*100-1 Do

{просмотрим все годы столетия}

For m:=marth To february Do

{просмотрим все месяцы года}

Begin

Mod_y:=y mod 100;

{найдем две последние цифры года}

int_y:=y div 100;

{найдем две первые цифры года}

n:=trunc(2.6*(Ord(m)+1)*0.2)+d+mod_y+

trunc(mod_y/4)+ trunc(int_y/4)-2*int_y;

If n mod 7=0rd(d_w) Then Inc(k);

End;

Writeln('количество пятниц,

приходящихся на ',d,' число в ',h,

' столетии равно ', k);

End.

При решении этой задачи нам понадобилось выполнить преобразование типов.

 

Пример 2

Найти k−е простое число в арифметической прогрессии 11, 21, 31, 41, 51, 61,…

Решение

Для решения поставленной задачи необходимо просматривать числа последовательности и проверять каждое из них на простоту. Поскольку нам неизвестно, сколько членов последовательности необходимо просмотреть, мы должны просматривать последовательность до тех пор, пока не найдем k−е простое число. Для этого воспользуемся циклом с условием:

Program Example_68;

Var k: Integer;

n, p, d: Longint:

Begin

Writeln('введите номер числа');

Readln(k);

n:=0; p:=1;

While n<k Do

Begin

Inc(p, 10); d:=2;

While (p mod d<>0) and (d<sqrt(p)) Do

Inc(d);

If d>=sqrt(p) Then Inc(n);

End;

Writeln(p);

Readln;

End.

В этом решении мы смогли записать условие d<sqrt(p), так как типы Integer и Real совместимы.

Пример 3

Вычислить сумму значений 1/n⁵ в прямом и обратном порядке.

Решение.

Перед вычислением четвертой степени значения целой (типа Word) переменной k ее значение присваивается вещественной переменной x. Это делается для того, чтобы избежать переполнения. Ведь диапазон значений вещественных переменных значительно больше, чем диапазон значений целых переменных типа Word.

Program Example_69;

uses Crt;

var x, summa, ammus: real;

k: word;

Begin

ClrScr;

Writeln('1/n^5, 1 to 1000');

{суммирование в прямом порядке}

Summa:=0.0;

for k:=1 to 1000 do

Begin

x:=k;

summa:=summa+1.0/(x*Sqr(Sqr(x)));

end;

{суммирование в обратном порядке}

ammus:=0.0;

for k:=1000 downto 1 do

Begin

x:=k;

ammus:=ammus+1.0/(x*Sqr(Sqr(x)));

end;

Writeln('Прямая сумма=', summa);

Writeln('Обратная сумма', ammus);

Writeln('Разность=', summa-ammus);

Readln;

End.

 

ПРОЦЕДУРЫ

 

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

В Паскале имеются два вида подпрограмм − процедуры и функции. Их структура очень похожа на структуру основной программы.

Описание процедуры

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

Procedure Имя [Список формальных

параметров];

Описательная часть

Begin

Тело процедуры

End;

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

Фактические параметры − это параметры, кото­рые передаются процедуре при ее вызове.

Количество и типы формальных и фактичес­ких параметров должны в точности совпадать.

Формальные параметры описываются в заголовке процедуры и определяют тип и место подстановки фак­тических параметров, формальные параметры делятся на два вида: параметры−переменные и параметры−значения.

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

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

Все переменные программы делятся на глобальные и локальные. Глобальные переменные объявляются в разделе описаний основной программы. Локальные пе­ременныеобъявляются в процедурах и функциях. Та­ким образом, локальные переменные "живут" только во время работы подпрограммы.

Пример 1

Составить программу для вычисления aⁿ: целые чис­ла a и n (n≥0) вводятся с клавиатуры.

Решение

Составим процедуру для вычисления степени целого числа.

Procedure Degree(x,у: Integer;

Var st: Longint);

Var i:Integer; {описательная часть}

Begin {тело процедуры}

st:=1;

For i:=1 To у Do st:=st*x;

End;

Первая строчка описания − это заголовок процеду­ры, который начинается со словаProcedure. Процеду­ра названа именем Degree. В скобках записан список формальных параметров, то есть, перечислены переменные с указанием их типа. Мы используем три параметра: пер­вый − основание степени, то есть число, которое надо воз­вести в степень; второй − показатель степени, третий − результат. Первые два формальных параметра − парамет­ры-значения, третий − параметр-переменная, и перед ним указано словоVar. Все они описаны как целые (х и у − переменные типа Integer, a st − типа Longint, так как степенная функция быстро возрастает).

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

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

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

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

Program Example_70;

Var a, n: Integer;

s: Longint;

Procedure Degree(x,y: Integer;

Var st: Longint);

Var i:Integer;

Begin

st:=1;

For i:=1 To у Do st:=st*x;

End;

Begin{основная программа}

Writeln('Введите два числа –

основание и показатель степени');

Readln(a,n);

Degree(а,n,s); {обращение к процедуре}

Writeln('Результат ',s);

Readln;

End.

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

Пример 2

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

Решение

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

Procedure Swap (Var х, у:Integer);

Var z: Integer;

Begin

z:=x; x:=y; y:=z;

End;

Процедура называется Swap. У нее имеется два фор­мальных параметра, которые являются параметрами переменными, так как необходимо поменять значения переменных и запомнить изменения. Эти параметры яв­ляются результатами выполнения процедуры.

В процедуре описана переменная z, которая исполь­зуется как промежуточная.

Вся программа имеет вид:

Program Example_71;

Var a, b: Integer;

Procedure Swap(Varx, y: Integer);

Var z: Integer;

Begin

z:=x; x:=y; y:=z;

End;

Begin

Writeln('Введите значения

переменных а и b');

Readln(а, b);

Swap(a, b); {обращение к процедуре}

Writeln('а= ', а, ' b= ',b);

{вывод новых значений}

Readln;

End.

Пример 3

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

ProgramExample_72;

uses crt;

Var choice: integer;

Procedure Menu;

Begin

Writeln('1. Преобразовать часы, минуты

и секунды в секунды');

Writeln('2. Преобразовать секунды в часы,

минуты и секунды');

Writeln('3. Завершить работу');

Writeln;

Writeln(' введите номер (1-3);

End;

Procedure second_to_time;

Var total_seconds: longint;

hours, minutes, seconds: longint;

temp: Longint;

Begin

ClrScr;

Writeln('Введите суммарное количество

секунд:');

Readln(total_seconds);

Writeln;

temp:=total_seconds div 60;

seconds:=total_seconds mod 60;

hours:=temp div 60;

minutes:=temp mod 60;

Writeln;

Writeln (total_seconds, ' секунд - это');

Writeln;

Writeln(hours, 'часов,' ,minutes,

' минут, ',seconds, ' секунд');

Writeln;

Writeln('для продолжения работы

нажмите <Enter>');

Readln;

end;

Proceduretime_to_seconds;

Var total_seconds: longint;

hours, minutes, seconds: longint;

Begin

ClrScr;

Writeln('Введите часы: ');

Readln(hours);

Writeln;

Writeln('Введите минуты');

Readln(minutes);

Writeln;

Writeln('Введите секунды:');

Readln(seconds);

Writeln;

total_seconds:=hours*3600+

+minutes*60+seconds;

Writeln;

Writeln(hours, ' часов,', minutes,

' минут, ', seconds, ' секунд – это ',

total_seconds, ' секунд');

Writeln;

Writeln('Для продолжения работы нажмите

<Enter>');

Readln;

End;

Begin

choice:=0

While choice<>3 do

Begin

ClrScr;

Menu;

readln(choice);

case choice of

1: time_to_seconds;

2: seconds_to_time;

End; {case}

End; {while}

End.

 

ФУНКЦИИ

 

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

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

Таким образом, общий вид описания функции сле­дующий:

Function Имя[(Список формальных

параметров)]: Тип

результата;

Описательная часть

Begin

Тело функции, в котором обязательно

должно быть присваивание

Имя функции:=значение

End;

Пример 1

Составить программу, подсчитывающую число соче­таний без повторения из n элементов по k.

Число сочетаний без повторения вычисляется по формуле:

Обозначим через n и k переменные для хранения введенных чисел; c − переменную для хранения ре­зультата.

Чтобы подсчитать количество сочетаний без повто­рения, необходимо вычислить n!, (n-k)!, k!

Опишем функцию для вычисления факториала чис­ла

n(n!= 1•2•...•n).

Function factorial(n:Integer):Longint;

{заголовок функции}

Var i: Integer; {описательная часть}

rez: Longint;

Begin {тело функции}

rez:=1;

For i:=1 To n Do rez:=rez*i;

factorial:=rez;

{присваивание значения имени функции}

End;

Первая строчка в описании функции − это ее заголо­вок. Служебное словоFunction (функция) указывает на то, что именем factorial названа функция. В скоб­ках записан список формальных параметров функции, состо­ящий из одной переменной целого типа. Далее в заголовке указан тип значения функции. В данном примере резуль­тат функции factorial − длинное целое число.

За заголовком функции следует описательная часть функции, которая, как и у программы, может состоять из разделов описания переменных, констант, типов. В данном примере имеется только раздел описания пере­менных. В нем описаны переменные i (счетчик цикла) и rez (для накопления значения факториала).

Далее идет раздел операторов (тело функции). Ре­зультат присваивается имени функции, таким образом функция получает свое значение.

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

Program Example_73;

Var n, k: Integer;

a1, a2, a3, c: Longint;

Function factorial (n:Integer): Longint;

Var i: Integer;

rez: Longint;

Begin

rez:=1;

For i:=1 To n Do rez:=rez*i;

factorial:=rez;

End;

Begin

Writeln('Ввод n и k:');

Readln(n,k) ;

a1:=factorial(n); {вычисление n!}

a2:=factorial(k); {вычисление k!}

a3:=factorial(n-k);{вычисление(n-k)!}

c:=a1 div (a2*a3) ; {результат}

Writeln(c);

Readln;

End.

 

Пусть n=5, k=3. Когда в программе встречается оператор a1:=factorial(n), выполняются следующие действия:

¨ выделяется память для переменных, описанных в функции factorial;

¨ формальному параметру присваивается значение фактического: n:=n (n=5);

¨ выполняется функция, вычисляется факториал числа 5;

¨ значение функции передается в место обращения к этой функции, то есть присваивается переменной а1.

В операторах a2:=factorial(k) и a3:factorial(n-k) еще дважды вызывается функция factorial с пара­метрами k=3 и n-k=2. Всего в программе имеется 3 обращения к функции factorial, столько же раз выполняются и описанные выше действия.

Еще раз подчеркнем, что функция − это самостоя­тельная часть программы, имеющая собственные пере­менные, которым отводится отдельное место в памяти ЭВМ. Этим объясняется тот факт, что переменные с одинаковыми именами, используемые в функции и в ос­новной программе, являются разными (в рассмотрен­ном примере - переменная n основной программы и параметр n функции). При выполнении программы машина "не путает" имена этих переменных, так как области их действия не совпадают.

Это особенно важно при написании больших про­грамм.

Пример 2

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

Решение

Мы уже решали похожую задачу, только в ней не требовалось написать функцию.

Надо выделять последнюю цифру числа до тех пор, пока число не станет равным нулю. При этом каждый раз счетчик увеличивается на 1 (начальное значение счет­чика − 0).

Function Quantity(x: Longint): Byte;

Var k: Byte;

Begin

k:=0;

While x <> 0 Do

Begin

Inc(k) ;

x:=x div 10;

End;

Quantity:=k;

End;

В заголовке функции указано ее имя − Quantity. Функции передается только один параметр − целое число, количество цифр которого надо найти. Результат − тоже целое число. В разделе переменных описана перемен­ная k − счетчик цифр. В теле функции с помощью цикла While выполняются указанные выше действия (увели­чивается значение счетчика и удаляется последняя цифра).

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

Program Example_74;

Var n1, n2: Longint;

k1, k2: Byte;

Function Quantity(x: Longint): Byte;

Var k: Byte;

Begin

k:=0;

While x<>0 Do

Begin

Inc(k) ;

x:=x div 10;

End;

Quantity:=k;

End;

Begin

Writeln('Введите два числа');

Readln(n1, n2);

k1:=Quantity(n1);

{количество цифр первого числа}

k2:=Quantity(n2);

{количество цифр второго числа}

If k1=k2 Then

Writeln('Одинаковое количество цифр')

Else If k1>k2 Then

Writeln('В первом числе цифр больше')

Else

Writeln('Во втором числе цифр

больше');

Readln;

End.

Пример 3

Составьте программу решения неравенства bⁿ≤a≤bⁿ⁺¹ относительно n при условии a≥1, b>1.

Решение

Неравенство решается перебором значений n, метод решения реализован в функции largest_power, аргументами которой являются значения a и b.

program Example_75;

functionlargest_power(a, b: longint):word;

var n: word;

x: longint;

Begin

x:=b; n:=0;

while x<=a do

Begin

x:=b*x; inc(n);

end; {while}

largest_power:=n;

end;{function}

Begin

writeln('3^n<=10000<3^(n+1)');

writeln('n=', largest_power (10000, 3));

write('Нажмите <Enter>');

readln;

End.

Обратите внимание на то, как вызывается функция: writeln('n=', largest_power(10000, 3)). Внутри выражения функция вызывается следующим образом:

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

Примеры рекурсивного

Программирования

 

Алгоритм, который в процессе работы обращает­ся сам к себе, называется рекурсивным. Для иллюст­рации понятия рекурсия часто приводят пример с те­левизором, на экране которого изображен этот же телевизор, на экране второго − опять телевизор и так далее.

Можно разбить все рекурсивные задачи на 4 вида.

Задачи с рекурсивной

Формулировкой

 

Некоторые объекты являются рекурсивными по оп­ределению, поэтому рекурсивные алгоритмы их получе­ния буквально повторяют соответствующие определения.

Пример

Вычисление факториала натурального числа. Для того чтобы вычислить N!, надо значение (N-1)! умножить на N, при этом 1!=1. В общем виде это можно записать так:

1 при N=1;

N!=

N(N-1)! при N>1.

Для вычисления факториала опишем функцию.

ProgramExample_76;

Function factorial (n: Integer):

Longint;

Begin

if n=1 Then factorial:=1

Else factorial:=n*factorial(n-1);

End;

Рассмотрим последовательность вызовов этой функ­ции для n=5.Первый вызов функции происходит в основной программе a:=factorial(5). Отметим, что при каждом обращении к функции будет создаваться свой набор локальных переменных (в данном случае в функции factorial имеется всего одна локальная переменная n). Для каждой локальной переменной на время работы функции выделяется память. После завер­шения работы функции эта память освобождается и пе­ременные удаляются.

Так как n≠1, то управление передается на ветку Else и функции factorial присваивается значение n*factorial(n-1), то есть 5*factorial(4). Про­исходит второй вызов функции factorial, с парамет­ром 4. Этот процесс повторяется до тех пор, пока значе­ние параметра не станет равным 1. Тогда n=1, а поэто­му значение функции factorial=1. Таким образом, n=1 − это условие окончания рекурсии. Управление пе­редается в точку вызова, то есть в предыдущую функцию для n=2 factorial:=n*factorial(n-1), значит, factorial: =2*1, следовательно, factorial(2)=2. Возвращаемся назад, поднимаясь "вверх" по цепочке ре­курсивных вызовов. Таким образом, получаем значение factorial(5)=120, это значение и присваивается пе­ременной а.

 

Задачи, из постановки