ээээээ ээээээээээээээээ

6 рекурсия

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

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

Пример.Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

Пример программы с использованием рекурсии

Program Arsac; Var first: word;

Procedure posledov (i: word); Begin

Writeln (i);

If i=1 then exit;

If odd(i) then posledov(3*i+1) else posledov(i div 2); End;

Begin

Write (‘ введите первое значение ’); readln (first);

Posledov (first);

Readln ;

End.

Виды рекурсий

1.Простая а) Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией. б) Если в процедуре рекурсивный вызов не является завершающей инструкцией, то такая рекурсия называется вложенной.

2.Сложная или косвенная :Функция A вызывает функцию B, а функция B — функцию A.

Рекурсия и цикл Что такое цикл?

Цикл – разновидность управляющей конструкции. Управляет она, очевидно, выполнением кода (как например,

конструкция if (условие) [then] оператор, где оператор выполняется, только если условие истинно).

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

На псевдокоде цикл с предусловием обычно обозначается так: while (условие) do{оператор1; оператор2; … } Здесь в круглых скобках записано условие цикла, а в фигурных – тело цикла. Например, так можно распечатать все числа от nдо 1:

while (n > 0) do{// на каждом шаге цикла проверяем, не стало ли n

<= 0, т.е. не выполнилось ли условие выхода из цикла print(n);// печатаем текущее значение n n = n — 1;// уменьшаем значение n, чтобы оно в конце концов стало меньше 0 и мы вышли из цикла }

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

При чем здесь рекурсия?

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

dec_print(n) {if (n > 0) then { // проверка условия, как в циклеprint(n); // печать очередного значения n dec_print(n-1); // вызов функции от следующего значения n } }

На каждом шаге рекурсии проверяется условие n > 0. Если оно не выполнится, ничего больше происходить не будет, т.к. нет

ветки else, точно так же, как и в цикле. Если же оно истинно, будут выполнены операторы во вторых фигурных скобках: сначала напечатано очередное значение n, а потом вызвана та же функция от уменьшенного значения n – последнее равносильно выполнению оператора n = n — 1; в цикле и переходу к следующему шагу. Этот вызов функции снова запустит выполнение аналогичных действий: сначала проверка истинности условия, а

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

Теперь попробуем задать такое преобразование в общем виде. Цикл с предусловием, как сказано выше, имеет следующий вид: while (условие) do{оператор1; оператор2; … }

Его можно заменить такой рекурсивной функцией:

cycle(...) { // параметры зависят от того, что происходит в циклеif (условие) then {// проверка такого же условия, как в циклеоператор1; // операторы из тела циклаоператор2; … cycle(...); // рекурсивный вызов функции } }

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

30.Реализация цикла с параметром в ЯП

Цикл – это многократно повторяющиеся фрагменты программ. Алгоритм циклической структуры – это алгоритм,

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

Формат записи:

1. For P:=Pn to Pk do OP;

2. For P:=Pk downto Pn do OP;

где: For - для;to – до;downto – уменьшая до;do – выполнить;OP

– тело цикла; оператор (простой или составной); P - параметр цикла, переменная порядкового типа; Pn, Pk – начальное и конечное значение параметра. Работа оператора: Вычисляется начальное значение параметра цикла Pn и присваивается параметру P. Проверяется условие P?Pk, и если оно Trueвыполняются операторы тела цикла OP . После чего наращивается значение P на единицу и опять проверяется условие P?Pk . Если условие False осуществляется выход из цикла. В операторе с downto шаг изменения параметра цикла равен –1. Примеры записи:

For i:=1 to n do n:=sqr(i)+1;

For s:=’A’ to ‘Z’ do R:=R+ord(s)/127;

For L:=False to True do H:= (False or L) And Not (L);

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

где: C=2,7; a=0.5; t=0,1; 0<n<10; Dn=1.

Program Ex_3; Uses crt;

Var y, C, a, t :real; n :integer; Begin

clrscr;

Writeln('Введите C, a, t'); Read(C, a, n); Writeln('Результат:'); Writeln(‘n’:5,’y’:15);

For n:=1 to 10 do Begin y:=C*exp(a*t)*cos(n*t);

Writeln(n:4,’ ‘:5, y:10); end; End.

12)Строковый (литерный).

К базовым, с некоторой натяжкой, можно отнести тип данных «строка».

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

Из-за возможности доопределения, некоторые авторы учебников строковый тип данных к базовым не относят.

Вместе со знаками в памяти хранится длина строки, чтобы выводить не все 256 знаков. В языке pascal для хранения длины строки используется элемент набора с номером 0. В этот байт записывается число от 0 до 255.

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

Тип строка в языке pascal отмечается словом string, в языке basic, после имени переменной пишут знак доллара ’$’, в некоторых версиях вместо знака доллара используется знак «солнышко» - круг поверх косого креста.

0	1	2	3	4	5	6	...	255
	б	у	к	в	ы
код 5		код б		код у		код к		код в	код ы

Первый знак строки занимает 1 байт, второй – второй, ...

Нулевой байт хранит длину строки.

pascal basic

var s:string;

s$=”буквы”

begin s:=’буквы’; end. (s¤=”буквы”)

К операциям преобразования строк относим:

Выделение части строки (с указанного места указанной длины).

Конкатенация, соединение (склейка) двух строк в одну. (Часто операция обозначается знаком ‘+’ между аргументами.)

Удаление части строки.

Вставка одной строки внутрь другой.

Не реализованные в некотором языке операции вполне заменимы набором имеющихся.

Например, удалить часть строки можно путем склейки кусочка слева и кусочка справа. Средняя часть будет потеряна.

BASIC PASCAL

выполняем вырезку из строки =mid$(s$,m,l) =copy(s,m,l)

=left$(s,l)
=right$(s,l)
склеиваем две строки	=s1$+s2$	=concat(s1,s2)
удаляем часть строки	delete(s,m,l)

вставляем строку в строку	insert(p,s,m)
замена фрагмента строки	mid$(a$,m,x)=

О строке можно извлечь информацию:

Число – длину строки.

Номер места, начиная с которого одна строка находится внутри другой (поиск подстроки в строке).

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

BASIC	PASCAL
определяем длину строки		=len(s$)	=length(s)
ищем подстроку в строке		=instr(s$,p$)	=pos(p,s)
преобразуем число в строку =str$(x)			str(n,s)
=bin$(x)
=oct$(x)
=hex$(s)
преобразуем строку в число =val(x$)			val(s,n,c)

15. Указатели. Выделение и возвращение памяти. ДИНАМИЧЕСКАЯ ПАМЯТЬ

Динамическая память -- это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кбайт), стека (обычно 16 Кбайт) и собственно тела программы. Размер динамической памяти можно варьировать в

широких пределах. По умолчанию этот размер определяется всей доступной памятью ПК и, как правило, составляет не менее 200...300 Кбайт. АДРЕСА И УКАЗАТЕЛИ Оперативная память ПК представляет собой совокупность элементарных ячеек для хранения информации -- байтов, каждый из которых имеет собственный номер. Эти номера называются адресами, они позволяют обращаться к любому байту памяти. .Указатель -- это переменная, которая в качестве своего значения содержит адрес байта памяти. В ПК адреса задаются совокупностью двух шестнадцатиразрядных слов, которые называются сегментом и смещением. Сегмент -- это участок памяти, имеющий длину 65536 байт (64 Кбайт) и начинающийся с физического адреса, кратного 16 (т.е. 0, 16, 32, 48 и т.д.). Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу. Адресное пространство ПК составляет 1 Мбайт (речь идет о так называемой стандартной памяти ПК; на современных компьютерах с процессорами 80386 и выше адресное пространство составляет 4 Гбайт, однако в Турбо Паскале нет средств, поддерживающих работу с дополнительной памятью; при использовании среды Borland Pascal with Objects 7.0 такая возможность имеется). Для адресации в пределах 1 Мбайта нужно 20 двоичных разрядов, которые получаются из двух шестнадцатиразрядных слов (сегмента и смещения) следующим образом: содержимое сегмента смещается влево на 4 разряда, освободившиеся правые разряды заполняются нулями, результат складывается с содержимым смещения.

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

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

Таким образом, по своей внутренней структуре любой указатель представляет собой совокупность двух слов (данных типа WORD), трактуемых как сегмент и смещение. С помощью указателей можно размещать в динамической памяти любой из известных в Турбо Паскале типов данных. Лишь некоторые из них (BYTE, CHAR, SHORTINT, BOOLEAN) занимают во внутреннем представлении один байт, остальные -- несколько смежных. Поэтому на самом деле указатель адресует лишь первый байт данных.ВЫДЕЛЕНИЕ И ОСВОБОЖДЕНИЕ ДИНАМИЧЕСКОЙ ПАМЯТИ Вся динамическая память в Турбо Паскале рассматривается как сплошной массив байтов, который называется кучей. Физически куча располагается в старших адресах сразу за областью памяти, которую занимает тело программы. Начало кучи хранится в стандартной

переменной HEAPORG, конец - в переменной HEAPEND. Текущую границу незанятой динамической памяти указывает

указатель HEAPPTR.

Расположение кучи в памяти ПК

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

var