Метод простой итерации (брал с методы)

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

Сумма бесконечного ряда

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

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

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

, (2)

где . (3)

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

Пример 1. Вычислить с погрешностью e =0,001 для заданного значения аргумента x значение функции sin(x) с помощью ее разложения в ряд:

,

где (2n – 1)! = 1×2×3××× (2n – 1).

Выразим вспомогательную функцию из выражения (3):

.

С ее помощью по формуле (2) будем определять очередное слагаемое t. Первый член ряда находим непосредственно из формулы для общего члена ряда, подставив в нее n = 1. Далее приведен алгоритм решения задачи.

Бесконечное произведение

Бесконечное произведение представляет собой произведение бесконечного числа сомножителей:

.

Если такое произведение стремится при i ®¥ к некоторому пределу P, то P называют значением бесконечного произведения. Если P конечно и отлично от нуля, то произведение называют сходящимся, в противном случае - расходящимся. Если бесконечное произведение сходится, то . Именно это обстоятельство можно использовать для прекращения циклических вычислений частичных произведений, а именно когда очередной сомножитель станет отличаться от 1 на величину меньше заданной погрешности e. Разберем правила решения данной задачи на конкретном примере.

БИЛЕТ №7

№7 1. Процедурный тип данных. Пример его использования

2. Сортировка символьных данных. Пример

Процедурный тип данных

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

Объявление процедурного типа похоже на заголовок подпрограммы (см. п. 10): пишется слово procedure или function, за которым в круглых скобках записывается список формальных параметров; для функции после списка формальных параметров через двоеточие указывается тип функции. В отличие от заголовка подпрограммы здесь не указывается имя подпрограммы.

Пример.

type

Proc1 = procedure; {процедура без параметров}

Proc2 = procedure(var X,Y: Integer);

{процедура с двумя параметрами-переменными целого типа}

Func1 = function(X: Real): Real;

{функция вещественного типа с одним параметром-значением}

Далее можно ввести переменные этих типов:

var

Р1: Proc1;

Р2: Proc2;

F1: Func1;

После этого процедурным переменным можно присваивать значения конкретных процедур и функций. Как и во всех других случаях, процедурная переменная и подпрограмма должны быть совместимы для присваивания (т. е. должны иметь одинаковое число формальных параметров, совпадающих по типам; функции, кроме того, должны иметь идентичный тип). |

Существует ряд правил использования подпрограмм в качестве процедурной переменной:

они должны компилироваться с ключом компилятора {$F+} или иметь директиву far для получения полного адреса подпрограмм;

они не должны быть стандартными процедурами и функциями;

они не должны объявляться внутри других процедур и функций;

они не должны быть типа inline или interrupt (пп. 10.5.5 и 10.5.6).

Пример.

{$F+}

procedure Swap (var A, B: Byte);

var

Temp: Byte;

begin

Temp:=A; A:=B; В:= Temp

end;

function Tan(Angle: Real): Real;

begin

Tan:=Sin(Angle) / Cos(Angle)

{проверка, что Cos(Angle)<>0, осуществляется в основной программе}

end;

{$F-}

В этом случае процедурным переменным, введенным ранее, можно присвоить значения:

Р2:= Swap;

Fl:= Tan;

а вызовы P2(I,J) и F1(X) эквивалентны соответственно Swap(I,J) и Таn(Х).

Так же как и указатель, процедурная переменная занимает 4 байта памяти, в которых помещается полный адрес подпрограммы (поэтому подпрограммы необходимо компилировать с ключом {$F+}).

 

Процедурные переменные можно использовать так же, как и переменные других типов: в выражениях (если эта переменная - функция), в виде оператора (если эта переменная - процедура), как компонента другой более сложной переменной, как передаваемый в подпрограмму параметр. Идея единства данных и подпрограмм получила дальнейшее развитие в объектно-ориентированном программировании - см. п. 14.

 

Сортировка символьных данных. Пример.

Сортировка пузырьковым методом

Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок.

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

{ сортировка пузырьковым методом}

procedure Bubble(var item: DataArray; count:integer);

var

i,j: integer;

x: DataItem;

begin

for i:= 2 to count do

begin

for j:= count downto i do

if item[j-1]>item[j] then

begin

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

end;

end;

end; {конец сортировки пузырьковым методом}

В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.

Сортировка пузырьковым методом имеет два цикла. Поскольку число элементов массива задается переменной "count", внешний цикл вызывает просмотр массива count - 1 раз. Это обеспечивает нахождение каждого элемента в своей позиций после завершения процедуры. Внутренний цикл предназначен для фактического выполнения операций сравнения и обмена.

Эта версия сортировки пузырьковым методом может сортировать символьный массив в порядке возрастания значений элементов. Например, следующая короткая программа сортирует строку, которая считывается с дискового файла "test.dat". Эта же программа может использоваться с другими подпрограммами сортировки, которые приводятся в этой главе.

program SortDriver;

{эта программа будет считывать 80 или меньше символов

дискового файла "test.dat", отсортирует их и

выдаст pезультат на экран дисплея }

type

DataItem = char;

DataArray = array [1..80] of char;

var

test: DataArray;

t, t2: integer;

testfile: file of char;

{ сортировка пузырьковым методом}

procedure Bubble(var item: DataArray; count:integer);

var

i,j: integer;

x: DataItem;

begin

for i:= 2 to count do

begin

for j:= count downto i do

if item[j-1]>item[j] then

begin

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

end;

end;

end;

 

begin

Assign(testfile, 'test.dat');

Reset(testfile);

t:= 1;

 

{ считывание символов,которые будут сортироваться.}

 

while not Eof(testfile) do begin

read(testfile, test[t]);

t:= t+1;

end;

t:= t-2; {скорректировать число считанных элементов }

 

Bubble(test, t); { сортировать массив }

 

{ выдать отсортированный массив символов }

for t2:= 1 to t do write(test[t2]);

WriteLn;

end.

 

Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab":

 

- исходное положение: d c a b;

- первый проход: a d c b;

- второй проход: a b d c;

- третий проход: a b c d.

При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/ 2 (n**2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу.

Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n**2-n), а для наихудшего случая будет равно 3/2 (n**2-n) раз. Вывод этих формул выходит за пределы этой книги. Можно заметить, что по мере ухудшения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива.

Например, если не учитывать время операций обмена, выполняемых для перестановки неупорядоченных элементов, то тогда при выполнении одной операции сравнения в течение 0,001 секунд сортировка десяти элементов займет 0,05 секунд, сортировка ста элементов займет пять секунд, а сортировка 1000 элементов займет 500 секунд. Сортировка 100 000 элементов (такой размер имеет небольшой телефонный справочник) потребовала бы 5000000 секунд или около 1400 часов (т.е. два месяца непрерывной работы).

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

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

Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

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

procedure Shaker(var item: DataArray; count:integer);

var

j, k, l, r: integer;

x: DataItem;

begin

l:= 2; r:= count; k:= count;

repeat

for j:= r downto l do

if item[j-1] then

begin { обмен }

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

k:= j;

end;

 

l:= k+1;

 

for j:= l to r do

if item[j-1]>item[j] then

begin { обмен }

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

k:= j;

end;

 

r:= k-1;

until l>r

end; { конец челночной сортировки }

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

БИЛЕТ №8

1. Нетипизированные параметры подпрограмм. Явное приведение типа

2. Операторы циклов с постусловием и предусловием. Пример

Нетипизированные параметры

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

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

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

1Автоопределенное преобразование типов;

2 Наложенное описание переменной определенного типа.

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

Procedure Proc (Var: а);

b: = Integer (a) + 10;

Для наложения переменной определенного типа используют описание с absolute, например:

Procedure Proc (Var: а);

Var r: real absolute a;

При этом переменная r оказывается в памяти размещенной в том же месте, что и нетипизированный параметр а, и, соответственно, любое изменение r приведет к изменению а.

2.2 Цикл с постусловием “Repeat Untill” цикл повторяется до тех пор пока не будет выполнено условие… и цикл While do повторяется До тех пор пока выполняется условие.

 

 

БИЛЕТ №9

1. Структурограмма как способ записи алгоритма

2. Логический тип и операции с ним

Существуют еще формы записи, которые можно отнести к графическим.

Одной из таких форм является построение структурограмм.

 

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

 

Рассмотрите блок-схему и структурограмму алгоритма.