Рекурсии Turbo Pascal Рекурсия Pascal-Паскаль
Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.
Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит.
Пример.
Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».
Построим последовательность чисел следующим образом: возьмем целое число 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.
Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.
Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение.
Пример рекурсивного алгоритма
N! = ( N-1)!* N, если N=0, то N!= 1
Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же, другая часть – через иные понятия.
Пример рекурсивного алгоритма
2n= 2 n-1*2, если n=0, то 2 n= 1
Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие процедуры).
Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.
Все сказанное о процедурах целиком относится и к функциям.
Записи Turbo Pascal
Записи в Паскале – фиксированное число элементов одного или нескольких типов, то есть в отличие от массивов, в которых содержатся элементы одного типа, в записях могут содержаться элементы как одного, так и разных типов. Тема, например, сведения о книгах имеет структуру: автор, название книги, издательство, год издания, её цена. Первые три элемента относится к строковому типу данных, четвертый к целому, а цена - к вещественному типу. Элементами записей могут быть базовые типы, переменные, массивы, указатели, записи и т.д. Элементы записи вместе с их описанием называются полями записи. Над элементами записи можно выполнять действия, допустимые для данных этого типа.
Все записи должны быть описаны в разделе TYPE . Описание записи начинается со служебного слова RECORD заканчивается END, между которыми указывается список имен и типов полей, выбранных пользователем. Все идентификаторы полей в записи должны быть различными. Например, запись Воок можно описать следующим типом card:
TYPE card = record Author : string [15]; Title: string [20]; Firm: string[10]; year : integer ; cena : real End; VAR Book : card;
Тип записи (например, card) вводит только шаблон записи и с его именем не связан никакой конкретный обьект. Обращение к полю выполняется с помощью составного имени (селектора записи), которое состоит из : Имя_записи . имя_элемента
Например, присвоить значения элементам записи Author и Title можно так: Book.author:=’Довгаль С.И.’; Book.title:=’Турбо Паскаль V 7.0’;
Ввод цены книги с клавиатуры : readln (Book.cena);
Для упрощения и сокращения записи составных имен используется оператор присоединения WITH. Имя записи выносится в заголовок оператора присоединения, а в блоке используются только имена полей записи. Общий вид оператора присоединения: WITH имя записи DO оператор;
Предыдущие операторы можно записать проще:
With Book do begin author:=’Довгаль С.И.’; title:=’Турбо Паскаль V 7.0’; readln (cena); end;
Пример: Из ведомости 3-х студентов с их оценками ( порядковый номер, Ф.И.О. и три оценки) определить количество отличников и средний бал каждого студента.
Program Spic; Type wed = record {Тип wed включает 3 поля: n, fio, bal} n : integer ; fio : string[40] ; bal : array [1..3] of integer {Поле bal – массив из 3 оценок } end; Var spisok : wed ; {Запись spicok типа wed} i, j, kol, s : integer; sr : real; Begin kol:=0; {kol- количество отличников} With spisok do {with присоединяет имя записи spisok ко всем } For i:=1 to 3 do { полям внутри цикла For по i } begin n:=i; Write (' Vvedite FIO # ', i ,' '); Readln (fio); s:=0; For j:= 1 to 3 do begin write ( 'Vvedite ocenky: ' ); readln ( bal [j] ); s := s+ bal [j]; end; if s=15 then kol:=kol+1; {подсчет количества отличников} sr := s/3; writeln ( fio, ', Sredniy bal = ', sr:4:1); end; writeln ( ' Kolichestvo otlichnikov = ', kol ); readln; end.