Работа стека представлена на следующей схеме:

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

Данная функция явно носит рекурсивный характер, исходя из ее определения: Xn = 1, если n = 0;

Xn = (Xn-1)*X, если n > 1.

function POWER(FACTOR:real; EXPONENT:integer): REAL;

begin

if EXPONENT < 0

then POWER:=1/POWER(FACTOR,abs(EXPONENT))

else if EXPONENT > 0

then POWER:= FACTOR*POWER(FACTOR,EXPONENT-1)

ELSE POWER:=1

end;

ЗАМЕЧАНИЕ. Помимо рекурсивных функций в языке Паскаль можно определять по тому же принципу и рекурсивные процедуры. Подробно о них будет сказано в следующих разделах, а пока покажем, как рекурсивная функция может быть переделана в рекурсивную процедуру на примере вычисления факториала:

procedure FACTORIAL(VALUE:integer; var F: integer);

begin

iF VALUE=0 then F:=1

else begin FACTORIAL(VALUE-1,F);

F:=F*VALUE

end;

end;

Здесь уже, в отличие от функции FACTORIAL, для вычисления N! необходимо вызвать эту процедуру с помощью оператора процедуры FACTORIAL(N,FN), где FN - переменная для возвращения из процедуры значения N!.

6. МАССИВЫ. ДАННЫЕ ТИПА ARRAY

Скалярный тип - простой тип данных. Скалярное данное неделимо. Массивы - это структурированные типы данных. Массив состоит из нескольких элементов. Ко всему массиву можно обращаться по его имени. Можно обращаться к его элементу, но для этого надо задать индекс (индексы). Массивы бывают одномерные и многомерные. Для объявления массива необходимо задать типы его индексов и компонент.

Тип компонент массива - это просто тип данных, ассоциированный с каждой компонентой массива. Тип компонент может быть любым REAL, INTEGER, CHAR, BOOLEAN, перечислимым, интервальным. В качестве компоненты массива может быть взят и тип массив.

Тип индекса должен быть одним из упорядоченных типов, т.е. любым скалярным типом, кроме REAL: INTEGER, CHAR, интервальный, перечислимый. Тип индекса определяет границы изменения индекса. Если сделана попытка использовать несуществующую компоненту, то возникает ошибка (ошибка неверного индекса).

6.1 Одномерные массивы

а) с помощью служебного слова TYPE описывается тип массива, а затем с помощью VAR вводится переменная этого типа;

б) с помощью слова VAR сразу описывается переменная типа массив;

Например, объявление массива из 100 элементов типа REAL можно осуществить следующими двумя способами:

а) type R100 = array[1..100] of real;

var A: R100;

б) var A: array[1..100] of real.

Здесь задан массив с именем "А" и его элементы имеют имена: А[1],..., A[100]. Чаще всего для типа индекса используют интервальный тип на основе типов INTEGER и CHAR. Однако можно в качестве индексов брать перечислимый тип.

ПРИМЕР 1. Подсчет числа вхождений букв в текст определенной длины

program COUNTER;

var COUNT: array['a'..'z'] of integer;

CH: char; N: integer;

begin

for CH:= 'a' to 'z' do

COUNT [CH]:= 0; N:= 0;

repeat

read(CH); N:= N+1;

if (CH >= 'a') and (CH <= 'z') then

COUNT [CH]:= COUNT [CH]+1;

until CH = '.';

for CH:= 'a' to 'z' do

writeln(CH, COUNT [CH]:10, COUNT [CH]*100/N:10:2);

end.

ПОЯСНЕНИЕ. В этом примере тип индекса есть интервальный тип на базе типа CHAR, а тип компонент есть целое число. Таким образом, элементы массива - числа, а их индексы - буквы, т.е. число элементов массива равно 26 (число букв латинского алфавита). Рассмотрим теперь случай, когда тип индекса задан перечислимым типом, а компоненты массива представлены компонентами интервального типа на базе типа INTEGER.

ПРИМЕР 2. Присваивание переменной с именем месяца числа дней этого месяца

program NUMBRDAY;

type MONAT = (JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG,

SEP, OKT, NOV, DEC);

var DAY: array [MONAT] of 28..31; T: MONAT;

begin

for T:= JAN to DEC do

case T of

JAN, MAR, MAY, JUL, AUG, OKT, DEC: DAY[T]:= 31;

APR, JUN, SEP, NOV: DAY[T]:= 30;

FEB: DAY[T]:= 28;

end;

end.

6.2 Многомерные массивы

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

Например, таблица символов M x N, где M - число строк и N - число столбцов, может быть описана:

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

type LINE = array[1..N] of char;

STOLB = array[1..M] of LINE;

var TAB: STOLB.

Здесь TAB[I] - переменная типа LINE, а TAB[I][J] - переменная

типа CHAR.

Эти два вида определения массивов задают и два способа обращения к элементам массива: TAB[I,J] - в первом случае и TAB[I][J] - во втором.

Вполне очевидно, что сказанное выше для двумерного массива распространяется и на массивы большей размерности. Например, описание VAR CUBE: ARRAY[1..M, 1..N, 1..K] OF INTEGER определяет задание трехмерного массива целых чисел.

6.3 Способы работы с массивами

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39