Вычисление рекуррентных последовательностей

Рекуррентная последовательность. Из курса математики известно понятие рекуррентной последовательности. Это понятие вводится так: пусть известно k чисел a1,..., аk. Эти числа являются первыми числами числовой последовательности. Следующие элементы данной последовательности вычисляются так:

 

Здесь F— функция от k аргументов. Формула вида

 

называется рекуррентной формулой. Величина k называется глубиной рекурсии.

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

Примерами рекуррентных последовательностей являются арифметическая (1) и геометрическая (2) прогрессии:

 

Рекуррентная формула для указанной арифметической прогрессии:

 

Рекуррентная формула для данной геометрической прогрессии:

 

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

 

Для геометрической прогрессии:

 

Следующая числовая последовательность известна в математике под названием чисел Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...

Начиная с третьего элемента каждое число равно сумме значений двух предыдущих, т. е. это рекуррентная последовательность с глубиной равной 2 (двухшаговая рекурсия). Опишем ее в ветвящейся форме:

 

Введение представления о рекуррентных последовательностях позволяет по-новому взглянуть на некоторые уже известные нам задачи. Например, факториал целого числа п! можно рассматривать как значение n-го элемента следующего ряда чисел:

 

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

 

Программирование вычислений рекуррентных последовательностей. С рекуррентными последовательностями связаны задачи такого рода:

1) вычислить заданный (n-й) элемент последовательности;

2) математически обработать определенную часть последовательности (например, вычислить сумму или произведение первых n членов);

3) подсчитать количество элементов на заданном отрезке последовательности, удовлетворяющих определенным свойствам;

4) определить номер первого элемента, удовлетворяющего определенному условию;

5) вычислить и сохранить в памяти заданное количество элементов последовательности.

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

Пример 1. Вычислить n-й элемент арифметической прогрессии (1).

Var M,I: 0..Maxint;

A: Real;

Begin

Write('N=');

ReadLn(N);

A:=l;

For I: =2 To N Do

A:=A+2;

WriteLn('A(',N:l,')=',A:6:0)

End.

Рекуррентная формула ai = ai-­1 + 2 перешла в оператор А:= А + 2.

Пример 2. Просуммировать первые п элементов геометрической прогрессии (2) (не пользуясь формулой для суммы первых n членов прогрессии).

Var N,1: 0..Maxint;

A,S: Real;

Begin

Write('N='); ReadLn(N);

A:=l;

S:=A;

For I: =2 To N Do

Begin

A:=2*A;

S:=S+A

End;

WriteLn('Сумма равна',S:6:0)

End.

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

Пример 3. Вывести на печать первые п (п ≥ 3) чисел Фибоначчи. Подсчитать, сколько среди них четных чисел.

Var N,I,K,F,F1,F2: 0..Maxint;

Begin

Fl:=l; F2:=l;

K:=0;

WriteLn('F(l)=',Fl,'F(2)=',F2);

For I:=3 To N Do

Begin

F:=F1+F2;

WriteLn('F(',I:l,')=',F);

If Not Odd(F) Then K:=K+1;

F1:=F2; F2:=F

End;

WriteLn('Количество четных чисел в последовательности равно',К)

End.

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

Пример 4. Для заданного вещественного х и малой величины ε (например, ε = 0,000001) вычислить сумму ряда

 

включив в нее только слагаемые, превышающие ε. Известно, что сумма такого бесконечного ряда имеет конечное значение, равное еx, где е = 2,71828... — основание натурального логарифма. Поскольку элементы этого ряда представляют собой убывающую последовательность чисел, стремящуюся к нулю, то суммирование нужно производить до первого слагаемого, по абсолютной величине не превышающего ε.

Если слагаемые в этом выражении обозначить следующим образом:

 

 

 

то обобщенная формула для i-го элемента будет следующей:

 

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

 

Используя обобщенную формулу, имеем:

 

Отсюда:

 

Действительно:

 

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

 

И наконец, приведем программу, решающую поставленную задачу.

Var A,X,S,Eps: Real;

I: Integer;

Begin

Write('X ='); ReadLn(X);

Write('Epsilon ='); ReadLn(Eps);

A:=l; S:=0; I:=0;

While Abs(A)>Eps Do

Begin

S:=S+A;

I:=I+1;

A:=A*X/I

End;

WriteLn('Сумма ряда равна', S:10:4)

End.

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

Каждое повторное выполнение цикла в этой программе приближает значение S к искомому (уточняет значащие цифры в его записи). Такой вычислительный процесс в математике называется итерационным процессом. Соответственно, циклы, реализующие итерационный вычислительный процесс, называются итерационными циклами. Для их организации используются операторы While или Repeat.

Пример 5. Для заданного натурального N и вещественного х (х > 0) вычислить значение выражения:

 

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

 

Отсюда видна связь:

 

Теперь поставленная задача решается очень просто:

Var A,X: Real; I,N: Integer;

Begin

Write('X='); ReadLn(X);

Write('N='); ReadLn(N);

A:= Sqrt(X);

For I:=2 To N Do

A:=Sqrt(X+A);

WriteLn('Ответ:',А)

End.

К решению всех перечисленных выше задач можно подойти иначе.

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

Сделаем это для общего случая, определив арифметическую прогрессию с первым членом а0 и разностью d:

Соответствующая подпрограмма-функция выглядит так:

Function Progres(АО,D: Real;I: Integer): Real;

Begin

If I=1

Then Progres:=AO

Else Progres:=Progres(A0,D,I-1)+D

End;

 

Следующая программа выводит на экран первые 20 чисел Фибоначчи, значения которых вычисляет рекурсивная функция Fibon.

Var К: Byte;

Function Fibon(N: Integer): Integer;

Begin

If (N=1) Or (N=2)

Then Fibon:=1

Else Fibon:=Fibon(N-1)+Fibon(N-2)

End;

Begin

For K:=l To 20 Do WriteLn(Fibon(K))

End.

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

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

Пример 6. В ходе лечебного голодания масса пациента за 30 дней снизилась с 96 до 70 кг. Было установлено, что ежедневные потери массы пропорциональны массе тела. Вычислить, чему была равна масса пациента через k дней после начала голодания для k = 1, 2,..., 29.

Обозначим массу пациента в i-й день через рi (i = 0, 1, 2,..., 30). Из условия задачи известно, что р0 = 96 кг, p30 = 70 кг.

Пусть К— коэффициент пропорциональности убывания массы за один день. Тогда

 

Получаем последовательность, описываемую следующей рекуррентной формулой:

 

Однако нам неизвестен коэффициент К. Его можно найти, используя условие p30 = 70.

Для этого будем делать обратные подстановки:

 

Далее программирование становится тривиальным.

Var I: Byte; P,Q: Real;

Begin

P:=96;

Q:=Exp(l/30*Ln(70/96));

For I:=l To 29 Do

Begin

P:=Q*P;

WriteLn(I,'-й день-',Р:5:3,'кг')

End

End.

Основные понятия и средства компьютерной графики в Турбо Паскале

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

Начиная с четвертой версии Турбо Паскаля для IBM PC появилась мощная графическая библиотека, организованная в модуль Graph. В приложении 2 в справочной форме дано описание основных компонент этого модуля. В рассмотренных ниже примерах программ используется модуль Graph. Для его подключения в начале программы необходимо написать строку:

Uses Graph;

Графические режимы экрана отличаются:

• размером графической сетки (M x N, где М — число точек по горизонтали, N — число точек по вертикали);

• цветностью (число воспроизводимых на экране цветов).

 

Для установки графического режима экрана существуют соответствующие процедуры. В модуле Graph процедура установки графического режима экрана имеет следующий заголовок:

Procedure InitGraph(Var Driver,Mode: Integer; Path: String);

Здесь целая переменная Driver определяет тип графического драйвера; целая переменная Mode задает режим работы графического драйвера; Path — выражение типа String, содержащее маршрут поиска файла графического драйвера.

Список констант модуля Graph, определяющих типы драйверов и режимы, приведен в табл. П2.1 приложения 2.

Вот пример программы, инициализирующей графический режим VGAHi для работы с драйвером VGA (монитор типа VGA).

 

Uses Graph;

Var Driver,Mode: Integer;

Begin

Driver: = VGA;{драйвер}

Mode: = VGAHi;(режим работы}

InitGraph(Driver,Mode,'C:\TP\BGI');

 

Здесь указывается, что файл egavga.bgi с драйвером для VGA-монитора находится в каталоге C:\TP\BGI. Режим VGAHi соответствует графической сетке 640 х 480 с палитрой из 16 цветов.

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

Driver:=Detect;

InitGraph(Driver,Mode,'C:\TP\BGI');

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

В модуле Graph процедура возвращения в текстовый режим имеет заголовок:

Procedure CloseGraph;

Строковый тип данных

Теперь мы познакомимся с типом данных, который относится к числу структурированных. Это строковый тип данных (строка). Следует заметить, что строковый тип данных есть в Турбо Паскале и отсутствует в стандартном Паскале.

Строка — это последовательность символов. Каждый символ занимает 1 байт памяти (код ASCII). Количество символов в строке называется ее длиной. Длина строки может находиться в диапазоне от 0 до 255. Строковые величины могут быть константами и переменными.

Строковая константа есть последовательность символов, заключенная в апострофы. Например:

'Язык программирования ПАСКАЛЬ',

'IBM PC — computer',

'33-45-12'.

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

Var <идентификатор>: String[<максимальная длина строки>]

Например:

Var Name: String[20]

Параметр длины может и не указываться в описании. В таком случае подразумевается, что он равен максимальной величине — 255. Например:

Var slovo: String

Строковая переменная занимает в памяти на 1 байт больше, чем указанная в описании длина. Дело в том, что один (нулевой) байт содержит значение текущей длины строки. Если строковой переменной не присвоено никакого значения, то ее текущая длина равна нулю. По мере заполнения строки символами ее текущая длина возрастает, но она не должна превышать максимальной по описанию величины.

Символы внутри строки индексируются (нумеруются) от единицы. Каждый отдельный символ идентифицируется именем строки с индексом, заключенным в квадратные скобки. Например:

Name[5], Name[i], slovo[k+1].

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

Тип String и стандартный тип char совместимы. Строки и символы могут употребляться в одних и тех же выражениях.

Строковые выражения строятся из строковых констант, переменных, функций и знаков операций. Над строковыми данными допустимы операции сцепления и операции отношения.

Операция сцепления (+) применяется для соединения нескольких строк в одну результирующую строку. Сцеплять можно как строковые константы, так и переменные.

Например:

'ЭВМ'+'IВМ'+'РС'.

В результате получится строка:

'ЭВМ IBM PC'.

Длина результирующей строки не должна превышать 255. Операции отношения =, <

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

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

Пример:

Выражение Результат

'cosmi'<'cosm2' True

'pascal'>'PASCAL' True

'Ключ_'<>'Ключ' True

'MS DOS'='MS DOS' True

Функция Copy (S, Poz, N) выделяет из строки s подстроку длиной в N символов, начиная с позиции Poz.N и Poz — целочисленные выражения.

Пример:

Значение S Выражение Результат

'ABCDEFG' Copy(S,2,3) 'BCD'

'ABCDEFG' Copy(S,4,4) 'DEFG'

Функция Concat (Sl, S2,..., SN) выполняет сцепление (конкатенацию) строк S1,...,SN в одну строку.

Пример:

Выражение Результат

Concat('АА','XX','Y') 'AAXXY'

Функция Length (S) определяет текущую длину строки S. Результат — значение целого типа.

Пример:

Значение S Выражение Результат

'test-5' Length(S) 6

'(А+В)*С' Length(S) 7

Функция Pos (Sl, S2) обнаруживает первое появление в строке S2 подстроки Sl. Результат — целое число, равное номеру позиции, где находится первый символ подстроки S1.

Если в строке S2 подстроки Sl не обнаружено, то результат равен 0.

Пример:

Значение S2 Выражение Результат

'abcdef Pos('cd',S2) 3

'abcdcdef Pos('cd',S2) 3

'abcdef Pos('k',S2) 0

Процедура Delete (S, Poz, N) выполняет удаление N символов из строки S, начиная с позиции Poz.

Пример:

Исходное значение S Оператор Конечное значение S

'abcdefg' Delete(S,3,2) 'abefg'

'abcdefg' Delete (S,2,6) 'a'

В результате выполнения процедуры уменьшается текущая длина строки в переменной S.

Процедура Insert(Sl,S2,Poz) выполняет вставку строки S1 в строку S2, начиная с позиции Poz.

Пример:

Начальное S2 Оператор Конечное S2

'ЭВМ PC' Insert('IBM-',S2, 5) 'ЭВМ IBM-PC'

'Рис.2' Insert('N',S2,6) 'Рис. N2'

Пример 1. Следующая программа получает из слова «ВЕЛИЧИНА» слово «НАЛИЧИЕ»:

Program Slovo_1;

Var S11,S12: String[10];

Begin

S11:='ВЕЛИЧИНА';

S12:=Copy(S11,7,2)+Copy(S11,3,4)+S11[2];

WriteLn(S12)

End.

Пример 2. Составим программу, которая формирует символьную строку, состоящую из n звездочек (n — целое число, 1 ≤ n ≤ 255).

Program Stars;

Var A: String;

N,I: Byte;

Begin

Write('Введите число звездочек');

ReadLn(N);

A:=';

For I:=1 To N Do

A:=A+'*';

WriteLn(A)

End.

Здесь строковой переменной а вначале присваивается значение пустой строки (' '). Затем к ней присоединяются звездочки.

Пример 3. В символьной строке подсчитать количество цифр, предшествующих первому символу!.

Program С;

Var S: String;

К,I: Byte;

Begin

WriteLn(«Введите строку»);

ReadLn(S);

K:=0;

I:=l;

While (K»Length(S)) And (S[I]<>'!') Do

Begin

If (S[I]>='0') And (S[i]<='9')

Then K:=K+1;

I:=I+1

End;

WriteLn ('Количество цифр до символа «!» равно',К)

End.

В этой программе переменная К играет роль счетчика цифр, а переменная I — роль параметра цикла. Цикл закончит выполнение при первом же выходе на символ! или, если в строке такого символа нет, при выходе на конец строки. Символ S[I] является цифрой, если истинно отношение: 0

Пример 4. Дана символьная строка, которая имеет следующий вид:

'а

b ='

На месте а и b стоят десятичные цифры; значком

обозначен один из знаков операций: +, -, *. Иначе говоря, записано арифметическое выражение с двумя однозначными числами и знак равенства, например '5+7 ='. Нужно, чтобы машина вычислила это выражение и после знака равенства вывела результат. Операция деления не рассматривается для того, чтобы иметь дело только с целыми числами.

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

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

Program Interpretator;

Var Str: String[4];

А, В: 0..9;

С: -100..100;

Begin

{ввод исходной строки}

WriteLn('Введите выражение!');

WriteLn;

Read(Str);

{преобразование цифровых символов в числа}

A:=Ord(Str[l])-Ord('0');

B:=Ord(Str[3])-Ord('0');

(выполнение арифметической операции)

Case Str[2] Of

'+': С:=А+В;

'-': С:=А-В;

'*': С:=А*В

End;

{вывод результата}

WriteLn(С:2)

End.

В этой программе появился новый для нас оператор. Он называется оператором выбора. Формат этого оператора описывается синтаксической диаграммой (рис. 33).

 

Здесь <селектор> — это выражение любого порядкового типа; <константа> — постоянная величина того же типа, что и селектор; <оператор> — любой простой или составной оператор.

Выполнение оператора выбора происходит так: вычисляется выражение-селектор; затем в списках констант ищется такое значение, которое совпадает с полученным значением селектора; далее исполняется оператор, помеченный данной константой. Если такой константы не найдено, то происходит переход к выполнению оператора, следующего после оператора выбора.

В приведенной выше программе роль селектора играет символьная величина Str[2]. Если она равна +, то выполнится оператор c:=a+b; если равна -, то выполнится оператор с:=а-b; если равна *, выполнится оператор с:=а*b. Для любых других значений Str[2] не выполнится ни один из операторов присваивания, и значение переменной С останется неопределенным.

Приведенное выше описание оператора выбора соответствует стандарту Паскаля. В Турбо Паскале допустимо использование в операторе Case альтернативной ветви после служебного слова Else. Вот пример для той же задачи. Если мы хотим, что-. бы в случае неверного символа в Str[2] выдавалось сообщение об этом, нужно программировать так:

Case Str[2] Of

'+': С:=А+В;

'-': С:=А-В;

'*': С:=А*В

Else WriteLn("неверный знак операции')

End;

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

После ввода строки цифровые символы переводятся в соответствующие десятичные числа. Затем интерпретируется знак операции. В зависимости от знака выполняется одно из трех арифметических действий. Далее результат выводится на экран после символа =.

 

 

Табличные данные и массивы

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

 

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

{Тi}, i=1,...,12.

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

 

Теперь представьте, что нам требуется собрать информацию о среднемесячных температурах за 10 лет, например с 1981 по 1990 г. Очевидно, что для этого удобна прямоугольная таблица, в которой столбцы соответствуют годам, а строки — месяцам.

 

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

Для значений, хранящихся в такой таблице, удобно использовать двухиндексные обозначения. Например, H1981,2 обозначает температуру в феврале 1981 г. и т.п. А вся совокупность данных, составляющих таблицу, обозначается так:

{Hi,j}, i=1981..1990; j=1..12

Обработка подобных данных производится с использованием двухиндексных величин. Например, средняя температура марта за 10 лет вычисляется по формуле:

 

А значение средней температуры за весь-десятилетний период вычисляется так:

 

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

T[1],T[5],T[i],H[1981,9],H[i,j] и т.п.

Массив, хранящий линейную таблицу, называется одномерным, прямоугольную таблицу — двумерным.

Тип элементов массива называется его базовым типом. Очевидно, что для рассмотренных массивов температур базовым типом является вещественный (Real).

Описание массивов. Переменная регулярного типа описывается в разделе описания переменных в следующей форме:

Var <идентификатор>: Array[<тип индекса>] Of <тип компонент>

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

Var Т: Array[1..12] Of Real;

Описание массива определяет, во-первых, размещение массива в памяти, во-вторых, правила его дальнейшего употребления в программе. Последовательные элементы массива располагаются в последовательных ячейках памяти (T[1], T[2] и т. д.), причем значения индекса не должны выходить из диапазона 1... 12. В качестве индекса может употребляться любое выражение соответствующего типа. Например, Т[i+j], Т[m div 2].

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

Var H: Аггау[1981..1990]. Of Array[1..12] Of Real;

Вот примеры обозначения некоторых элементов этого массива:

Н[1981][1]; Н[1985][10]; Н[1990][12]

Однако чаще употребляется другая, эквивалентная форма обозначения элементов двумерного массива:

Н[1981,1]; Н[1985,10]; Н[1990,12]

Переменная H[1981] обозначает всю первую строку таблицы, т.е. весь массив температур за 1981 г.

Другим вариантом, эквивалентным приведенному выше описанию, является следующий:

Type Month=Array[1..12] Of Real;

Year=Array [1981..1990] Of Month;

Var H: Year;

Наиболее краткий вариант описания данного массива такой:

Var H: Array[1981..1990,1..12] Of Real;

По аналогии с математикой одномерные числовые массивы часто называют векторами, а двумерные — матрицами.

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

Const Imax=10; Jmax=20;

Var Mas: Array[1..Imax,1..Jmax] Of Integer;

Теперь для изменения размеров массива Mas и всех операторов программы, связанных с этими размерами, достаточно отредактировать только одну строку в программе — раздел констант.

Действия над массивом как единым целым. Такие действия допустимы лишь в двух случаях:

• присваивание значений одного массива другому;

• операции отношения «равно», «не равно».

В обоих случаях массивы должны иметь одинаковые типы (тип индексов и тип элементов).

Следующий фрагмент программы организует построчный вывод матрицы на экран:

For I:=1 То IMax Do

Begin

For J:=l To JMax Do

Write(Mas[I,J]:6);

WriteLn

End;

После печати очередной строки матрицы оператор WriteLn без параметров переведет курсор в начало новой строки. Следует заметить, что в последнем примере матрица на экране будет получена в естественной форме прямоугольной таблицы, если JMax не превышает 12 (сами подумайте почему).

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

Пример 1. Вернемся к массиву среднемесячных температур T[1.. 12]. Требуется вычислить среднегодовую температуру, а также ежемесячные отклонения от этой величины.

Program Example;

Const N = 12;

Type Vec=Array [1..N] Of Real;

Var T,Dt: Vec;

St: Real;

I: Integer;

Begin (Ввод исходных данных)

WriteLn('Вводите таблицу температур');

For I:=l To N Do

Begin

Write(I: 2,':');

ReadLn(T[I])

End;

{Вычисление средней температуры}

St:=0;

For I:=1 To N Do

St:=St+T[I];

St:=St/N;

(Вычисление таблицы отклонений от среднего}

For I:=1 To N Do

Dt[I]:=T[I]-St;

{Вывод результатов}

WriteLn('Средняя температура равна',St:6:2);

WriteLn;

WriteLn('Отклонения от средней температуры:');

For I:=l To N Do

WriteLn(1:1,':',Dt[I]:6:2)

End.

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

Пример 2. Выбор максимального элемента

Пусть из рассмотренного выше массива температур требуется отобрать самую высокую температуру и номер месяца, ей соответствующего. Идея алгоритма решения этой задачи: чтобы получить максимальную температуру в вещественной переменной TMах, сначала в нее заносится первое значение массива T[1]. Затем поочередно сравнивается значение TMах с остальными элементами массива температур, и каждое значение большее, чем TMах, присваивается этой переменной. Для получения номера самого теплого месяца в целой переменной NumMax в нее следует каждый раз засылать номер элемента массива температур одновременно с занесением в TMах его значения.

ТМах:=Т[1];

NumMax:=1;

For I:=2 To 12 Do

If T[I]>Tmax

Then

Begin

TMax:=T[I];

NumMax:=1

End;

Заметим, что если в массиве температур несколько значений, равных максимальному, то в NumMax будет получен первый номер из этих элементов. Чтобы получить последнюю дату, нужно в операторе If заменить знак отношения > на >=.

Пример 3. Сортировка массива. В одномерном массиве Х из N элементов требуется произвести перестановку значений так, чтобы они расположились по возрастанию, т.е. Х1 ≤ Х2 ≤... ≤ ХN.

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

Идея: производится последовательное упорядочивание смежных пар элементов массива: Х1 и X2, Х2 и Х3,.... ХN-1 и ХN. В итоге максимальное значение переместится в ХN. Затем ту же процедуру повторяют до XN-1 и т.д., вплоть до цепочки из двух элементов Х1 и X2. Такой алгоритм будет иметь структуру двух вложенных циклов с внутренним циклом — переменной (сокращающейся) длины.

For I:=1 То N-l Do

For K:=l To N-I Do

If Х[К]>Х [K+l]

Then

Begin

А:=Х[К];

Х[К]:=Х[К+1];

Х[К+1]:=А

End;