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

Вычисление предела последовательности является типичной задачей на использование итерационного цикла.

Пример 24.

Последовательность {X_n} определена следующим образом:

Найти предел последовательности {X_n}, принимая за него такое Х_n, при котором

|X_n – X_n-1| < ε.

Таблица имен

Магемат. величина	Обозначение в программе	Содержательный смысл	Тип переменной
n	N	Номер итерации	integer
Xn-1	XI	Член последовательности X с номером n-1	real
Хn	X	Член последовательности X с номером n	real
ε	E	Требуемая точность расчетов	real

 

PROGRAM PR24;

VAR

X, X1, E: REAL;

N: INTEGER;

BEGIN

WRITELN('BBEДИTE E');

READLN(E);

N:= 1;

X:= 1;

REPEAT

X1:= X;

X:= (N * N +2)/(3*N * N – N +1);

N:=N+ 1;

UNTIL ABS(X – X1) <E;

WRITELN('Предел последовательности равен', X:12:8)

END.

 

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

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

Есть определенные признаки, которые помогают выявить наличие рекуррентных формул. К таким признакам относятся выражения (-1)ⁿ, Xⁿ, n! и подобные этим выражения, присутствующие в формуле общего члена бесконечного ряда. Часто рекуррентная формула для бесконечного ряда находится путем деления соседних членов ряда друг на друга.

Пример 25.

Вычислить . Вычисление ряда окончить при выполнении условия: .

Для решения этой задачи необходимо использовать рекуррентную формулу. А найти ее можно следующим способом. Сделаем преобразование исходного ряда в следующий вид:

Тогда условие окончания вычислений будет выглядеть так | A_i | < ε. Это условие либо выполнится для некоторого i = n и вычислительный процесс будет завершен, либо не выполнится. Во втором случае используют термин «зависание программы». Оператор ЭВМ искусственно останавливает программу и выясняет причину зависания: неправильные исходные данные, например комбинация X и ε, или допущена ошибка в тексте программы, а может быть получена неправильная рекуррентная формула, или другая причина имеет место.

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

Эти формулы и будут исходными для нашей задачи. На этом первый этап подготовки бесконечного ряда к нахождению его суммы Y с погрешностью ε на компьютере завершается. Если рекуррентную формулу найти невозможно или нет в этом необходимости, то можно ограничиться только приведенными выше преобразованиями.

Но в нашем случае нужен второй этап преобразования, а именно, нахождение рекуррентной формулы. Для этого поделим два соседних члена А_i, А_i-1 (Иногда, с точки зрения математических преобразований проще будет разделить А_i+1 на А_i, что эквивалентно):

Отсюда находим рекуррентную формулу:

Таблица имен

Математ. величина	Обозначение в программе	Содержательный смысл	Тип переменной
i	I	Номер итерации	integer
X	X	Параметр бесконечного ряда	real
Y	Y	Искомая сумма	real
Ai	А	Член последовательности А с номером i	real
ε	Е	Требуемая точность расчетов	real

 

PROGRAM PR25;

VAR

Y, Е, А, X: REAL;

I: INTEGER;

BEGIN

WRITELN('Введите X, E');

READLN(X, E);

I:= 1;

A:= -X*X/2;

Y:=A;

WHILE ABS(A) >= E

DO BEGIN

I:= I+1;

A:= -X*X/2/I/(2*I - 1)*A;

Y:= Y + A;

END;

WRITELN('Y=', Y:10:6)

END.

 

Вложенные итерационные циклы

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

WHILE… DO WHILE… DO…

WHILE… DO REPEAT… … UNTIL…

REPEAT … REPEAT … UNTIL… UNTIL…

REPEAT … WHILE … DO … … UNTIL…

 

Пример 26.

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

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

Таблица 19

Идентификатор	Содержательный смысл	Тип переменной
А	Число букв в новом слове	INTEGER
В	Число букв в самом длинном слове	INTEGER
С	Число слов	INTEGER
F	Последний символ, введенный с клавиатуры	CHAR

В программе используется три счетчика А, В, С и переменная F для чтения из входного файла INPUT текущего символа (литеры). Алгоритм содержит два итерационных цикла. Внешний цикл с постусловием используется для подсчета числа слов в предложении С, а также для выявления самого длинного слова (формирование значения переменной В). Внутренний цикл обеспечивает чтение очередной литеры F, отделяет русские буква от знаков препинания и латинских букв, определяет конец слова и подсчитывает количество букв А в текущем слове. Концом слова считается пробел или точка.

PROGRAM PR26;

VAR

А, В, С: INTEGER;

F: CHAR;

BEGIN

WRITELN ('Введите слова, разделенные пробелами.');

WRITELN ('В конце предложения поставьте точку.');

В:= 0;

С:= 0;

REPEAT

A:= 0;

F:= '*';

WHILE (F <> '') AND (F <> '.') { Конец слова}

DO BEGIN READ(F);

IF (('A'<=F) AND (F<='Я')) OR ((('a'оF) AND (F<='n')) OR (('p'<=F) AND (F<='я')))

THEN A:= A + 1

END;

С:= С + 1; { Новое слово}

IF В < A THEN В:= А

UNTIL F='.'; { Конец предложения }

WRITELN ('Наибольшее число букв в слове =', В);

WRITELN ('Число слов в предложении =', С)

END.

В этой программе оператор READ использован для ввода потока символов произвольной длины. Реализован логический вложенный цикл, в котором применяются как оператор постусловия REPEAT для анализа конца предложения, так и оператор предусловия WHILE для выделения слов в предложении.

 

Программирование данных

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

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

 

 

Таблица 19

Типы данных языка Паскаль

Скалярные (простые)

Указатель

Структурированные

Вещественные

Порядковые

Целые (перечислимые)

Литерный

Логический

Пользова-тельские

Расширенное

Двойное вещественное

Вещественное

Короткое вещественное

Длинное целое

Целое

Слово

Короткое целое

Байт

Интервальный

Перечислимый

Файл данных

Текстовый файл

Множество

Строка

Запись

Массив

extended

double

real

single

longint

integer

word

shortint

byte

char

boolean

Имя типа задается программистом

pointer

file

text

set

string

record

array

 

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

 

3.1. Конструирование простых пользовательских типов

Данные простого типа (константы, переменные, выражения) имеют только одно значение, поэтому этот тип часто называют скалярным. К стандартным скалярным типам относятся следующие наиболее известные и часто употребляемые типы: REAL, INTEGER, BOOLEAN, CHAR. Последние три типа содержат ограниченное число значений, поэтому их называют стандартными перечисляемыми типами. Вещественные типы данных, в том числе и REAL, к перечисляемым типам не относятся. Пользователь на базе стандартных перечисляемых типов может создать свои пользовательские типы. Различают два простых пользовательских типа данных:
пользовательские перечисляемые типы и интервальные (иногда говорят ограниченные) типы данных.

Пользовательские перечисляемые типы

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

TYPE <имя типа> = (значение 1, значение 2,..., значение N);

При этом понимают, что «значение i » — это идентификатор элемента с номером i.

Допускается неявное определение перечисляемого типа непосредственно в разделе VAR:

VAR <список переменных>: (значение 1, значение 2,значение N);

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

TYPE G = (С, О, N, F);

VAR Gl, G2: G;

Данные указанных типов можно использовать в операторах FOR и CASE, в функциях SUCC, PRED и ORD. К сожалению, в стандартных процедурах READ, READLN, WRITE, WRITELN эти данные не поддерживаются. Наиболее часто данные пользовательских перечисляемых типов используются при конструировании сложных типов данных (индексы массивов, указателей и т.д.).

Пример 27.

Для заданного года вычислить количество дней.

PROGRAM PR27;

TYPE MONTH - (JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT,NOV, DEC);

{Пользовательский перечисляемый тип данных}

VAR

S, YEAR: INTEGER;

MEC: MONTH;

BEGIN

WRITELN ('ВВЕДИТЕ ГОД');

READ (YEAR);

S:= 0;

FOR MEC:= JAN TO DEC { Просмотр всех месяцев по порядку }

DO CASE MEC OF

APR, JUN, SEP, NOV: S:= S+30; { Список месяцев, содержащих 30 дней}

FEB: IF (YEAR MOD 4 = 0) AND (YEAR MOD 100 <> 0) OR (YEAR MOD 400 = 0)

THEN S:= S+29 {Апрель, високосный год}

ELSE {IF } S:= S+28; { Апрель, не високосный год }

ELSE {CASE}S:=S+31

END; {CASE}

WRITELN ('ЧИСЛО ДНЕЙ:', S)

END.

Перечисляемые типы характеризуются упорядоченностью значений (элементов) этого типа. Существует порядковый номер для каждого идентификатора. Первый в списке идентификатор имеет номер 0, второй 1 и т.д. Исключение составляет тип INTEGER, где номер совпадает с числом. В пользовательском перечисляемом типе номера присваиваются в порядке перечисления идентификаторов при определении типа слева – направо, сверху – вниз. Оператор FOR осуществляет последовательный перебор значений порядковых элементов в соответствии с их упорядоченностью.

На перечисляемых типах данных (стандартных и пользовательских) определены встроенные функции SUCC, PRED, ORD (таблица 11).

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

JAN < FEB < MAR <... < DEC, (тип пользователя – MONTH);

FALSE < TRUE, (тип – BOOLEAN);

-32768 < -32767 <... < 32767, (тип – INTEGER);

'a' < 'b' < 'c' <... < 'z', (тип – CHAR).

Допустимо использовать отношения <, >, =, <>, <=, >= для сравнения переменных, выражений или констант одного перечисляемого типа. Примеры: ' а ' < ' b ' — имеет значение TRUE;
MAR > DEC — имеет значение FALSE.

Интервальные типы

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

TYPE <Имя типа> = <Левая граница>.. <Правая граница>;

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

Примеры задания интервальных типов:

TYPE

DAY = (SU, МО, TU, WE, ТН, FR, SA);

WORK_DAY = МО.. FR; { Интервальный пользовательский тип}

YEAR = 1900.. 2000; { Интервальные типы}

LAT_ALFABETH = 'А'.. 'Z'; {Стандартные типы}

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