Рекуррентный способ последовательности пример

Рекуррентные соотношения и уравнения

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

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

• Метод производящих функций
• Метод характеристического уравнения

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

Метод производящих функций

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ <0>= …, \\ a_ <1>= …, \\ a_ = …, \\ … \\ a_ = …, n\geqslant k$$
2. Домножить каждую строчку на $z$ в соответствующей степени $z^ \cdot a_$ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_^ <\infty>a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
3. Решить полученное уравнение относительно $G(z)$.
4. Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:

1. Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f \to \\ \to p_ a_ + p_a_ + . + p_n a_n =0. $$
2. Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_ \lambda^ + p_\lambda^ + . + p_\lambda + p_n =0. $$
3. Выписать согласно полученным корням $\lambda_1, . \lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 \lambda_1^n +. +C_k \lambda_k^n \, \mbox < для случая различных простых корней>, $$ $$ C_1 \lambda_1^n + C_2 n\lambda_1^n +. +C_m n^m \lambda_1^n+. +C_k \lambda_k^n \mbox < для случая корня >\, \lambda_1 \, < кратности >\, m. $$
4. Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ — многочлен от $n$).
5. Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
6. Подставить начальные условия $a_0, a_1, . a_$ и получить значения констант $C_1, . C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$

Числа Фибоначчи растут быстро: $f_<10>=55$, $f_<20>=6765$, а $f_<100>=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$\begin 1\cdot f_0 &= &0\cdot 1,\\ z\cdot f_1 &= &1\cdot z,\\ z\cdot f_n & = &(f_+f_)\cdot z^n, \quad n\geq2.\\ \end $$

Складываем все строчки:

На третьем шаге алгоритма приводим все суммы к замкнутому виду:

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

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

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

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

Аналогично (но с делением на $z_2$) действуем со второй дробью:

Преобразуем данное выражение, используя то, что

$$1/z_1=-z_2, \quad 1/z_2 = -z_1, \quad z_1-z_2=\sqrt <5>$$ $$f_n=\frac<1><\sqrt<5>>\left( \biggl( \frac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \frac<1-\sqrt<5>> <2>\biggr)^n \right). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_+f_$, и найдем его корни:

Тогда общее решение однородного рекуррентного уравнения имеет вид:

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

Решая систему, найдем

Итоговое выражение для последовательности чисел Фибоначчи:

Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$ с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность $$, удовлетворяющую рекуррентному соотношению $a_ + 4 a_ + 3 a_ = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Источник

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

Определение возвратной последовательности

Характеристическое уравнение

Общее решение рекуррентного уравнения 2-го порядка

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

Примеры с решениями

Определение возвратной последовательности

в каждой из которых символами b₁ и q обозначены заданные числа – первый член и знаменатель прогрессии.

Определение . Пусть k – натуральное число. Возвратной (рекуррентной) последовательностью порядка k называют последовательность, для задания которой требуется задать первые её k членов, т.е. числа

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

– заданные числа ( коэффициенты рекуррентной формулы ).

Замечание 1 . Числа

называют начальными условиями .

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

Для задания таких последовательностей требуется задать их первые два члена, то есть вещественные числа x₁ и x₂ , а остальные члены последовательности

xn = q1 xn – 1 + q2 xn – 2 , n > 2 ,

(1)

Характеристическое уравнение

Для того, чтобы получить характеристическое уравнение возвратной последовательности (1), будем искать такие числа λ , при которых последовательность вида

xn = λ n

(2)

удовлетворяет рекуррентной формуле (1).

xn – 1 = λ n – 1 , xn – 2 = λ n – 2 ,

(3)

то при подстановке формул (2) и (3) в формулу (1) возникает уравнение

которое удобно переписать в виде

λ n – q1 λ n – 1 – – q2 λ n – 2 = 0 .

(4)

Если теперь уравнение (4) разделить на λ n–2 , то мы получим квадратное уравнение относительно λ вида:

которое и называют характеристическим уравнением .

Общее решение рекуррентного уравнения второго порядка

В случае, когда характеристическое уравнение имеет два различных вещественных корня λ₁ и λ₂ , каждая из последовательностей

и

удовлетворяет рекуррентной формуле (1), поэтому для любых чисел c₁ и c₂ последовательность с общим членом

также удовлетворяет рекуррентной формуле (1).

Числа c₁ и c₂ называют произвольными постоянными .

В случае, когда характеристическое уравнение имеет два совпавших вещественных корня λ₁ = λ₂ , непосредственная проверка показывает, что каждая из последовательностей

и

удовлетворяет рекуррентной формуле (1), поэтому для любых чисел c₁ и c₂ последовательность с общим членом

также удовлетворяет рекуррентной формуле (1).

В случае, когда характеристическое уравнение имеет два комплексно-сопряженных корня λ_{1, 2} = α ± i β, каждая из последовательностей

удовлетворяет рекуррентной формуле (1), поэтому для любых чисел c₁ и c₂ последовательность с общим членом

также удовлетворяет рекуррентной формуле (1).

Ряд примеров, в которых выводятся формулы общего члена возвратных последовательностей, разобран в разделе «Возвратные последовательности: вывод формулы общего члена» нашего справочника.

Источник

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

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

Пример

Примером рекуррентно заданной последовательности является последовательность чисел Фибоначчи — 1, 1, 2, 3, 5, 8, 13, . , в которой каждое последующее число, начиная с третьего, является суммой двух предыдущих: 2 = 1 + 1; 3 = 2 + 1 и так далее. Данную последовательность можно задать рекуррентно:

Пример

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

Решение. Найдем третий член заданной последовательности:

Аналогично находим далее, что

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

Дата добавления: 2015-09-10 ; просмотров: 6 | Нарушение авторских прав

Источник

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

Рекуррентная последовательность. Из курса математики известно понятие рекуррентной последовательности. Это понятие вводится так: пусть известно 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).

For I: =2 To N Do

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

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

For I: =2 To N Do

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Var A,X,S,Eps: Real;

While Abs(A)>Eps Do

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Function Fibon(N: Integer): Integer;

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

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

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

Пример 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;

For I:=l To 29 Do

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

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

Начиная с четвертой версии Турбо Паскаля для 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).

Var Driver,Mode: Integer;

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

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

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

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

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

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

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

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

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

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

‘IBM PC — computer’,

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

Var Name: String[20]

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

Var slovo: String

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

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

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

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

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

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

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

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

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

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

‘cosmi’ ‘PASCAL’ 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 в одну строку.

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

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

‘test-5’ Length(S) 6

Функция 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. Следующая программа получает из слова «ВЕЛИЧИНА» слово «НАЛИЧИЕ»:

Var S11,S12: String[10];

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

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

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

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

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

If (S[I]>=’0′) And (S[i] — это выражение любого порядкового типа; — постоянная величина того же типа, что и селектор; — любой простой или составной оператор.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: 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

For J:=l To JMax Do

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

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

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

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

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

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

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

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

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

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

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

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

For I:=2 To 12 Do

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

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

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

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

Источник