Билет№45 Двумерные (многомерные массивы). Индексация. Исполбзование процедур. Задача: о МиниМаксе(матрица как массив строк) №45 обработка двухмерных массивов

Пример(МиниМакс). В матрице A (размерности m  n) найти минимальное значение среди максимальных эл-

-тов строк. Исходные данные и результаты расположены в файлах.

{ Пример : нахождение "минимаксного" элемента матрицы }

{ Дано: (1) Натуральные n и m : 1..10 }

{ (2) матрица A размера n*m с вещественными элементами }

{ Получить: индексы i и j элемента матрицы A, такого, что}

{ a[i,j]=(MIN k : 1..n: (MAX l : 1..m : a[k,l])), }

{ т.е. a[i,j] - минимальный из максимальных элементов строк матрицы}

{ ======================================= }

const first = 1; nml = 10;

type index = first..nml; Row = array [index] of Real;

Matr = array [index] of Row;

var fin, fout : Text; a : Matr; { двухмерный массив 10 * 10 в памяти }

n, m, i, j : index; { реальное число: строк - n, столбцов - m }

{------------------------------------------------------------------}

procedure InMatrOut ( n, m : index; var a : Matr );

{входные аргументы: n,m ; результат (выходной параметр): a}

{ ввод матрицы из файла fin, вывод в файл fout - глобальные: fin, fout}

var i, j : index; elem : Real;

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

procedure InRowOut ( k : index; var str : array of Real );

{ ввод и вывод строки матрицы : str -строка, k - ее длина }

{ входной аргумент: k ; результат (выходной параметр): str}

{ ввод из fin, вывод в fout - глобальные: fin, fout}

var j : index; elem : Real;

begin

for j:=1 to k do

begin

Read( fin, elem ); Write( fout, elem : 6 : 2, ' ');

str[j-1] := elem {str-открытый массив (индексация с 0 ) }

end; {j}

ReadLn ( fin );

WriteLn( fout )

end; { конец внутренней процедуры InRowOut }

{...........................................................}

begin { InMatrOut }

for i := 1 to n do { обработка матрицы по строкам }

InRowOut( m, a[i] ); { ввод и вывод i-й строки }

ReadLn ( fin );

WriteLn( fout )

end; { InMatrOut }

{------------------------------------------------------------------}

function ArgMaxInRow( m: index; var str: array of Real ): index;

{ входные аргументы: m - индекс последнего эл-та в A,}

{ str- открытый массив (индексация с 0 ),}

{ результат: значение функции ArgMaxInRow .}

{ Поиск argMax - индекса максимального элемента}

{ из str[0..m-first], т.е. str[argMax] = ( MAX k:0..m-first : str[k])}

type index0 = 0..nml-first; { новая индексация параметра-массива str }

var argMax, i : index0;

begin { ArgMaxInRow }

argMax := 0;

for i := 1 to m-first do

{m-first - новая индексация последнего эл-та A в str }

{ inv: str[argMax] = ( MAX k:0..i : str[k] ) }

if str[i] > str[argMax] then argMax := i;

{ необходимо вернуться к исходной индексации }

ArgMaxInRow := argMax+first {возврат к исходной индексации }

end; { ArgMaxInRow }

{------------------------------------------------------------------}

procedure MinMax( n, m : index; var a : Matr; var i, j : index);

{входные аргументы: n, m, a; результат (выходной параметр): i,j}

{ a[i,j]=(MIN k:1..n: (MAX l:1..m : a[k,l])), }

{ т.е. a[i,j] - минимальный из максимальных эл-тов строк матрицы }

var i1, j1 : index;

begin { MinMax }

i := 1; j := ArgMaxInRow( m, a[i]); { a[i,j] - текущий "минимакс"}

for i1 := 2 to n do

begin

j1 := ArgMaxInRow( m, a[i1]);

if a[i1,j1] < a[i,j] then begin i := i1; j := j1 end

{ a[i,j]=(MIN k:1..i1: (MAX l:1..m : a[k,l]))}

end {for}

end; { MinMax }

{------------------------------------------------------------------}

begin { main }

Assign( fin, 'inmatr1.dat'); Reset( fin );

Assign(fout, 'outmatr1.dat'); ReWrite( fout );

ReadLn( fin, n, m ); ReadLn( fin );

WriteLn( fout, ' *** матрица A (', n:1, '*', m:1, ') ***');

InMatrOut( n, m, a );

MinMax( n, m, a, i, j );

WriteLn( fout, ' Р Е З У Л Ь Т А Т : ');

WriteLn( fout, '"минимакс" матрицы');

WriteLn( fout, 'a [',i:1,',',j:1,']=',a[i,j]:6:2);

Close(fin); Close(fout)

end.

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

Входной файл inmatr1.dat:												Выходной файл outmatr1.dat:
4	5		:	n,		M						*** матрица A (4*5)***
======================строка												1.00	2.00	0.05	4.00	5.00
1.	2.	.5	4.		5.	6.	7.	8.	9.	10.	: 1	0.10	0.20	0.50	0.40	0.30
.1	.2	.5	.4		.3	.6	.7	.8	.9	1.	: 2	0.10	0.10	0.40	0.20	1.00
.1	.1	.4	.2		1.	1.	1.	1.	1.	1.	: 3	2.00	3.00	4.00	5.00	6.00
2.	3.	4.	5.		6.	7.	8.	9.	0.	2.	: 4
0.	0.	0.	0.		0.	0.	0.	0.	0.	0.	: 5	Р Е З У Л Ь Т А Т :
0.	0.	0.	0.		0.	0.	0.	0.	0.	0.	: 6	"минимакс" матрицы
0.	0.	0.	0.		0.	0.	0.	0.	0.	0.	: 7	a [2,3]= 0.50
0.	0.	0.	0.		0.	0.	0.	0.	0.	0.	: 8
0.	0.	0.	0.		0.	0.	0.	0.	0.	0.	: 9
1.	2.	3.	4.		5.	6.	7.	8.	9.	10.	: 10
===========================

Примечание. Экономия памяти обеспечивается описанием параметров-массивов как параметров-переменных (var).

Билет№46 Процедурный(ф-циАнальный)тип параметров процедур и ф-ций №46

В Турбо Паскале имеется процедурный тип (тип-процедура и тип-ф-ция). Для объявления процедурного типа используется заголовок процедуры или ф-ции без имени:

Type Proc1 = procedure (a, b : integer; c : char; x : real); Proc2 = procedure (var a, b); Proc3 = procedure; Func1 = function : real; Func2 = function (n : integer) : boolean;

Можно описывать переменные этих типов, например:

var p1, p2 : Proc1; f1, f2 : Func2;

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

Описания процедур или ф-ций, имена которых будут использоваться переменными процедурного типа, должны быть помещены между двумя директивами компилятора {$F+} и {$F-}, указывающими дальний тип вызова. Вместо этого можно установить опцию компилятора far.

Пример. Просуммировать значения ф-ции, вычисленные в точках, находящихся на равном расстоянии внутри заданного отрезка [0; x_кон], начиная с точки 0.

Аргументами ф-ции являются значение x = x0 = 0.0 (начальное значение) и рассчитываемые по формуле значения x = x + dx с учетом выполнении условия x  x_кон (правая граница отрезка в программе представлена переменной xEnd), dx - шаг изменения значение аргумента. Учитывая способ представления вещественных чисел, вместо условия x  x_кон надо проверять x < x_кон + dx/10. Расчет аргументов и значений ф-ции с их суммированием выполняется в процедуре, которая имеет параметр процедурного типа, задающий вид ф-ции. Приводятся фрагменты программы, реализующие указанные действия, вывод результатов осуществляется в выходной файл fout.

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

program SumFunction;

type Fun1 = function ( x : real) : real;

var xEnd, dx, S : real;

fout : Text;

{$F+}

function SinVal( x : real) : real; {аргумент(входной параметр):x }

begin SinVal := sin(x) end; {результат: значение ф-ции sin(x) }

function CompVal( x : real) : real; {аргумент(входной параметр): x }

begin CompVal := cos(x) / (1+sqr(x)) end; {результат : значение ф-ции}

{$F-}

procedure Sum( xEnd, dx : real; FunctionName : Fun1; var S : real);

{аргументы (входные параметры): xEnd, dx, FunctionName; результат (выходной параметр): S }

var i, j : integer; x, x0, f : real;

begin

writeln(fout,'Расчет сумм значений функции ');

i := 1; x0 := 0; f := FunctionName(x0); S := f;

{ Вычисления для 0.0 }

writeln(fout,'x=',x0:4:2,' f(x)=',f:7:4,' сумма =',S:7:4);

x := x0 + dx;

while ( x < xEnd + dx/10 ) do

begin

i := i + 1; f := FunctionName(x); S := S + f;

writeln(fout,'x=',x:4:2,' f(x)=',f:7:4,' сумма =',S:7:4);

x := x + dx;

end;

writeln(fout,'Для ',i,' аргументов сумма =',S:9:6);

writeln(fout,'-------------------------------');

end;

begin

…

Sum(xEnd, dx , SinVal, S);

Sum(xEnd, dx , CompVal, S);

…

end.

Билет№47 Бинарный алгоритм нахождения Нод. Структурная версия №47

Алгоритм Евклида, основывается на следующих св-вах НОД:

1. (a > b > 0)  gcd(a, b) = gcd(b, a mod b);

2. gcd(a, 0) = a.

Медленная, но верная версия алгоритма Евклида, использующая операцию вычитания, основывается на других свойствах НОД, а именно:

1. (a > b > 0)  gcd(a, b) = gcd(a  b, b);

2. gcd(a, b) = gcd(b, a);

3. gcd(a, a) = a.

Рассмотрим ещё одну версию алгоритма Евклида, использующую в качестве базовых операций деление на 2 и вычитание. Эта версия называется бинарным алгоритмом. Несмотря на то, что число шагов в этом алгоритме больше, чем в классическом алгоритме Евклида, использующем операцию деления, быстродействие данного алгоритма может оказаться выше, так как его базовая операция «div 2» выполняется компьютером быстрее. Бинарный алгоритм нахождения НОД основывается на следующих св-вах (здесь использовано обозначение Even(x) = not Odd(x)):

1. Even(a) & Even(b)  gcd(a, b) = 2 gcd(a div 2, b div);

2. Odd(a) & Even(b)  gcd(a, b) = gcd(a, b div 2);

3. gcd(a, b) = gcd(b, a);

4. (a > b)  gcd(a, b) = gcd(a  b, b);

5. Odd(a) & Odd(b)  Even(a  b) & (|a  b| < max(a, b)

Cвойства 3 и 4 уже использовались, свойство 5 очевидно, а свойства 1 и 2 можно обосновать, рассматривая разложение (1.1) чисел a и b на простые множители (интерес представляют только степени 2) и учитывая (1.2).

Общая идея бинарного алгоритма пользуясь св-ми 1–5, переходить от пары чисел a и b к новой паре a^* и b^*, таких, что max(a^*, b^*) < max(a, b) и, кроме того, gcd(a^*, b^*) = gcd(a, b), либо gcd(a^*, b^*)  связан известным образом с gcd(a, b). Разделим действия алгоритма на два этапа. На первом этапе определим по св-ву 1 число k (степень 2 в gcd(a, b)) и такие u и v, что gcd(a, b) = k gcd(u, v). Затем на втором этапе найдём такие u^* и v^*, что gcd(u^*, v^*) = gcd(u, v) и либо u^* = 0, либо v^* = 0. Тогда отличное от 0 число u или v и будет искомым НОД.

Первый этап реализуется следующим образом:

u := a; v := b; k := 1;

{ u>0 & v>0 & gcd(a, b) = k*gcd(u, v) }

while not Odd(u) and not Odd(v) do

begin u := u div 2; v := v div 2; k := k*2

end;

{ u>0 & v>0 & gcd(a, b) = k*gcd(u, v)&(Odd(u)orOdd(v)) }

Перед вторым этапом хотя бы одно из чисел u или v будет нечётным. Тогда для второго этапа запишем набросок цикла (k здесь уже не изменится):

{ u>0 & v>0 & gcd(a, b) = k*gcd(u, v)&(Odd(u)orOdd(v)) }

repeat

ТЕЛО ЦИКЛА

{ gcd(a, b) = k*gcd(u, v) }

until (u=0) xor (v=0);

{ gcd(a, b) = k*gcd(u, v) & (Odd(u) xor Odd(v)) }

if v=0 then gcd := u*k else gcd := v*k; {gcd = gcd(a, b)}

Тело этого цикла можно реализовать следующим образом. Сначала сделаем так, чтобы оба числа u и v стали нечётными (если это не так при входе в тело цикла):

{ (u>0 & v>0) & (Odd(u) or Odd(v)) }

while not Odd(u) do u := u div 2;

while not Odd(v) do v := v div 2;

{ Odd(u) & Odd(v)}

Затем, используя св-ва 35, добьёмся уменьшения max(u, v) так, чтобы одно из u или v стало чётным:

{ (u>0 & v>0) & Odd(u) & Odd(v)}

if u>v then u := uv else v := vu;{ Уменьшение max(u, v)}

{Odd(u) xor Odd(v) }

Заметим, что при такой реализации сравнения u и v в условном операторе if-then-else только значение v может стать равным 0. Поэтому можно упростить условие окончания цикла repeat-until, заменив его на условие v = 0. Кроме того, по завершении цикла теперь надо установить gcd(a, b) = u*k без выбора. В итоге бинарный алгоритм принимает следующий вид:

function GCD1(a, b: Nat0): Nat0;

{ Бинарный структурированный вариант алгоритма Евклида}

var u,v,k: Nat0;

begin

u := a; v := b; k := 1;

{ u>0 & v>0 & gcd(u, v) = gcd(a, b) }

while not Odd(u) and not Odd(v) do

begin u := u div 2; v := v div 2; k := k*2

end;

{ (u>0 & v>0) & gcd(a, b) = k*gcd(u, v) & (Odd(u) or Odd(v)) }

repeat { на 1-м шаге  Odd(u) or Odd(v), далее  Odd(u) xor Odd(v) }

while not Odd(u) do u := u div 2;

while not Odd(v) do v := v div 2;

{ Odd(u) & Odd(v)}

if u>v then u := uv else v := vu; { Уменьшение max(u,v)}

{Odd(u) xor Odd(v) }

until (v=0);

{ gcd(a, b) = k*gcd(u, v) & (Odd(u) xor Odd(v)) & v=0 }

GCD1 := u*k;

end {GCD1}

Билет№48 Бинарный алгоритм нахождения НОД. Неструктуированная версия №48

Рассмотрим более подробно действия второго этапа бинарного алгоритма.(бил№47) При входе в цикл repeat-until (т. е. на первом шаге) справедливо утверждение Odd(u) or Odd(v) и, возможно, ни один из двух циклов while-do не будет выполняться. На всех других шагах перед выполнением тела цикла repeat-until справедливо утверждение Odd(u) xor Odd(v), т. е. одно из чисел u или v чётно, и будет выполняться в точности один из двух циклов

while not Odd(u) do u := u div 2;

while not Odd(v) do v := v div 2,

но заранее неизвестно, какой именно. Попробуем исключить лишние проверки в циклах второго этапа и исключить один из циклов за счёт введения дополнительной переменной t, которая в нужный момент играет роль то u, то v. Для того чтобы каждый раз знать, чью роль играет переменная t, используем следующий приём («трюк»): поскольку все наши переменные неотрицательны, припишем с указанной целью значению t знак «+» или «».

Поскольку теперь остался только один цикл

while not Odd(t) do t := t div 2,

перед началом которого (при всех его выполнениях, кроме, возможно, первого) заранее известно, что значение t чётно, можно преобразовать его в цикл

repeat t := t div 2 until Odd(t).

Далее, для того чтобы правильно выполнять вычисления второго этапа при первом входе, перепишем этот цикл, используя оператор goto:

1: t := t div 2;

2: if not Odd(t) then goto 1;

{Odd(t)}

При самом первом выполнении этого цикла (т. е. при переходе от первого этапа ко второму) можно избежать лишних проверок, если «правильно» определить, какую из переменных u или v будет замещать переменная t, и, если заранее известно, что она имеет чётное значение, то перейти на метку 1, в противном случае – на метку 2. В связи с этим перепишем и внешний цикл repeat-until, используя оператор goto:

{repeat}

1: t := t div 2;

2: if not Odd(t) then goto 1;

Действия с t, u, v;

{until t = 0} if t <> 0 then goto 1

Фрагмент тела этого цикла «Действия с t, u, v» должен соответствовать оператору «if u > v then u := u  v else v := v  u» исходного (структурного) алгоритма. Этот фрагмент может быть реализован в виде

if t > 0 then u := t else v := t;

t := u  v; {Even(t)}

При этом на всех шагах цикла (кроме, быть может, первого) после выполнения условного оператора if-then-else большее из u и v будет заменено на abs(t). Действительно, если u > v, то после выполнения присваивания t := u  v получим t > 0, что останется справедливым после деления на 2, и, следовательно, при очередном выполнении if-then-else будет изменено значение переменной u. Аналогично при u < v будет изменено значение переменной v.

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

function GCD2(a, b: Nat0): Nat0;

{ Бинарный вариант алгоритма Евклида}

{ Версия с goto – неструктурированная }

var u, v, k: Nat0;

t : T_integer; {целый тип, согласованный с Nat0 }

label 1, 2;

begin u := a; v := b; k := 1;

{ u>0 & v>0 & gcd(u, v) = gcd(a, b) }

while not Odd(u) and not Odd(v) do

begin

u := u div 2; v := v div 2; k := k*2

end;

{ gcd(a, b) = k*gcd(u, v) & (Odd(u) or Odd(v)) }

if Odd(u) then begin t := v; goto 2 end

else t := u;

{(t>0  t = u) & (t<0  t = v)}

{repeat}

1: t := t div 2;

2: if not Odd(t) then goto 1;

if t>0 then u := t else v := t;

{большее из u и v заменено на abs(t)}

t: = u  v; {Even(t)}

{until t = 0} if t <> 0 then goto 1;

GCD2 := u*k;

end {GCD2}

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

Билет№49 Сравнение алгоритмов нахождения НОД №49

Для практического сравнительного анализа алгоритма Евклида, бинарного алгоритма и его неструктурированной версии была написана программа, измеряющая время работы этих алгоритмов на фиксированных тестовых данных. Программа вычисляет все числа Фибоначчи, представимые в стандартных типах Integer или LongInt, и для каждой пары соседних чисел Фибоначчи вычисляет их НОД по каждому из перечисленных алгоритмов. Время работы каждого алгоритма по всему набору тестовых данных измерялось с помощью стандартной функции GetTime. Оказалось, что время работы бинарного алгоритма в среднем на 15 % больше времени работы классического алгоритма Евклида, а для неструктурированной версии бинарного алгоритма  на 23 %. Этот результат объясняется тем, что операция div 2, используемая в бинарном алгоритме и его неструктурированной модификации, реализуется в Паскале не очень эффективно (без учёта специфики деления на 2). Ситуация изменится, если вместо операции div 2 использовать имеющуюся в Паскале операцию сдвига на 1 бит вправо shr 1, что для натуральных чисел эквивалентно по результату операции div 2.

Программа, реализующая описанные испытания алгоритмов.

program gcdb_t2;

{Измерение времени счёта трёх вариантов алгоритма gcd:}

{ 1) классический алгоритм Евклида с делением; }

{ 2) бинарный алгоритм (структурная версия); }

{ 3) бинарный алгоритм (неструктурная версия с goto ).}

{В этой программе деление на 2 реализовано через сдвиг shr}

Uses Dos; {для измерения времени счёта}

Const MaxNat = {MaxInt} MaxLongInt; {тип Integer или LongInt}

N_step= 7000 {для замедления};

type T_integer= {Integer} LongInt; {Этот тип нужен в функции gcd3 }

type Nat0 = 0..MaxNat;

Fun2 = function (a, b: Nat0): Nat0;

var f_out: Text;

function GCD(f: Fun2; a, b: Nat0 ): Nat0;

{Вызов одной из функций GCD#(a, b) }

begin GCD := f(a, b)

end {GCD};

function GCD0(a, b: Nat0): Nat0;

{ Стандартный вариант алгоритма Евклида с делением}

var u, v, Remainder: Nat0;

begin

u := a; v := b;

{Инв: u>=0 & v>=0 & gcd(u, v) = gcd(a, b) }

while v <> 0 do

begin { Инв & v<>0 }

Remainder := u mod v;

u := v; v := Remainder;

{ Инв & u<>0 }

end {while};

{ (Инв & v=0)  u=gcd(a, b) }

GCD0:=u

end {GCD0};

function GCD1(a, b: Nat0): Nat0;

{ Бинарный структурированный вариант алгоритма Евклида}

var u, v, k: Nat0;

begin

u := a; v := b; k := 1;

{ u>0 & v>0 & gcd(u, v) = gcd(a, b) }

while not Odd(u) and not Odd(v) do

begin u := u shr 1; v := v shr 1; k := k shl 1{*2}

end;

{ gcd(a, b) = k*gcd(u, v) & (Odd(u) or Odd(v)) }

repeat { на 1-м шаге  Odd(u) or Odd(v), далее  Odd(u) xor Odd(v) }

while not Odd(u) do u := u shr 1;

while not Odd(v) do v := v shr 1;

{ Odd(u) & Odd(v)}

if u > v then u := u  v else v := v  u; { Уменьшение max(u, v)}

{Odd(u) xor Odd(v) }

until (v = 0);

{ gcd(a, b) = k*gcd(u, v) & (Odd(u) xor Odd(v)) & v = 0 }

GCD1 := u*k;

end {GCD1};

function GCD3(a, b: Nat0): Nat0;

{ Версия с goto  неструктурированная }

var u, v, k: Nat0;

t : T_Integer;

label 1,2;

begin

u := a; v := b; k := 1; { u>0 & v>0 & gcd(u, v) = gcd(a, b)}

while not Odd(u) and not Odd(v) do

begin u := u shr 1; v := v shr 1; k := k shl 1 {*2}

end;

{ gcd(a, b) = k*gcd(u, v) & (Odd(u) or Odd(v)) }

if Odd(u) then begin t := v; goto 2 end

else t := u; {(t>0  t = u) & (t<0  t = v)}

{repeat}

1: if t>0 then t := t shr 1 else begin t := t; t := t shr 1; t := t end;

2: if not Odd(t) then goto 1;

if t>0 then u := t else v := t; {большее из u и v заменено на abs(t)}

t := u  v; {Even(t)}

{until t = 0} if t<>0 then goto 1;

GCD3 := u*k;

end {GCD3};

procedure MyGetTime ( var t: LongInt );

{выдает время в сотых долях секунды}

var h, m, s , hund: Word;

begin

GetTime( h, m , s, hund);

t := s + 60 * m; t := hund + 100 * t

end{ MyGetTime };

procedure MyUnPackTime ( t: LongInt; var m, s, hund : Word );

{переводит время t (в сотых долях секунды)

в минуты m, секунды s, сотые hund }

begin

hund := t mod 100;

t := t div 100; {в секундах}

s := t mod 60;

m := t div 60

end{ MyUnPackTime };

procedure FibTest ( f: Fun2);

var MaxNat, a, b, c : Nat0;

{i: Byte;}

d, k: Nat0;

dt, t1,t2 : LongInt;

min, sec, s100 : Word;

begin

{MaxNat и N_step  глобальные константы}

MyGetTime(t1); {время запуска}

for k:=1 to N_step do {цикл-замедлитель}

begin

a := 1; b := 0 {i := 1;}

while ( a <= (MaxNat  b) ) do

begin { a = F(i) & b = F(i  1) & a + b = F(i + 1) <= MaxNat }

c := a; a := a + b; b := c ;

{i := i + 1;}

d := GCD(f, a, b);

{ a = F(i) & b = F(i  1) }

end {while};

{a = F(i) & b = F(i 1) & a <= MaxNat & a + b = F(i + 1) > MaxNat}

end {for-замедлитель};

MyGetTime(t2); {время окончания}

WriteLn(f_out,'t1=', t1);

WriteLn(f_out,'t2=', t2);

dt := t2  t1; MyUnPackTime( dt, min, sec, s100);

if(s100<10)

then WriteLn(f_out, 'время = ', min,' мин ', sec,'.0', s100,' с')

else WriteLn(f_out, 'время = ', min,' мин ', sec,'.' , s100,' с');

end {FibTest};

begin

Assign(f_out, 't2Long99.res');

Rewrite(f_out);

WriteLn(f_out,'---------------- test 0 -------------------');

FibTest(GCD0);

WriteLn(f_out,'---------------- test 1 -------------------');

FibTest(GCD1);

WriteLn(f_out,'---------------- test 3 -------------------');

FibTest(GCD3);

Close(f_out);

end.

Результаты выполнения программы показывают, что бинарный алгоритм работает в среднем на 23 % быстрее классического алгоритма Евклида, а неструктурированная версия работает на 9 % медленнее, чем структурированный бинарный алгоритм.

Итак, можно сделать следующие выводы:

1. бинарный алгоритм действительно работает несколько быстрее, чем алгоритм Евклида;

2. неструктурированная версия не более эффективна, чем структурная, хотя при определённой реализации машинных операций возможны некоторые улучшения неструктурированной версии; впрочем, это требует учёта особенностей аппаратуры и не относится к области программирования на языке высокого уровня.

Билет№50 Соотношение между хоаровскими инвариантами цикла и индуктивными утверждениями Флойда №50

Индуктивное утверждение Флойда, согласованное с предусловием Q, приписано некоторой точке программы и является справедливым при каждом прохождении этой точки, если до выполнения программы относительно переменных было справедливо утверждение Q. Например, для цикла while-do и точки в конце тела цикла можно записать {Q} while B do begin S {Ф} end,

где Ф – индуктивное утверждение Флойда. Очевидно, хоаровский инвариант цикла является флойдовским индуктивным утверждением, а именно таким, что имеет место свойство тела цикла {inv & B} S {inv} и, кроме того, Q  inv и inv  Post. Оказывается, существуют индуктивные утверждения, которые не являются хоаровскими инвариантами.

В качестве примера рассмотрим ту же задачу, что и в 2.2, но напишем другую программу. Итак, требуется верифицировать программу:

var n, m, i: Integer; …{n>0}

m := n; i := 1;

while m > 1 do begin m := m div 2; i := i*2 end

{Post: (0<i  n < 2*i)}.

Содержательно понять смысл программы помогает рассмотрение двоичной записи значений переменных n и m. Пусть двоичная запись числа n содержит log₂ n + 1 двоичных разрядов. Иными словами, q = log₂ n  есть показатель старшей степени двойки в двоичной записи числа n. Тогда на каждом шаге отбрасываем один бит (операция m := m div 2) и определяем вес (степень двойки) младшего разряда нового значения m в записи исходного числа n (операция i := i*2). Когда дойдем до старшей единицы (m = 1), то получим требуемое i (см. утверждение Post), т. е. i =2^q и 2^q  n < 2^q + 1.

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

inv: (0<m*i  n < m*(2*i)) & (i = 2^j) & (j  0).

Здесь для записи утверждения введена «переменная-призрак» j, способствующая лучшему пониманию программы. Тогда имеем

{n > 0}

m := n; i := 1; {j := 0: Integer}

{inv}

while m > 1 do begin m := m div 2; i := i*2 {j := j + 1} end

{Post:(0 < i  n < 2*i) & (i = 2^j) & (j  0) & (m = 1)} Очевидно, первое и третье условия проверки аннотированного цикла выполнены: 1) Pred  inv; 3) (m = 1) & inv  Post.

Основной интерес представляет выполнение второго условия: обладает ли S св-вом {inv & B} S {inv}? Надо показать, что inv & B  wp (S  inv), при этом, по определению, имеет место св-во {wp (S  inv)} S {inv}.

Итак, пользуясь правилом вывода для операторов присваивания определим wp(S  inv) для тела цикла S  begin m := m div 2; i := i*2 {j := j + 1}end:

(0 < (m div 2)*(2*i)  n < (m div 2)*2*(2*i)) & (2*i = 2^j + 1) & (j + 1  0).

Теперь надо показать, что это утверждение следует из утверждения inv & B, т. е. из (0 < m*i  n < m*(2*i)) & (i = 2^j) & (j  0) & (m > 1). Так как (m div 2)*2  m, то (0 < m*i  n)  (0 < (m div 2)*(2*i)  n). Для правой части двойного неравенства для n аналогичным образом должны были бы иметь

(n < m*(2*i))  (n < (m div 2)*2*(2*i)).

Но это неверно! Ввиду важности вопроса сформулируем проблему, несколько изменив (упростив) задачу. Итак, сложилась следующая ситуация. Имеется программа Prog:

{Prog:} m := n; i := 1;

while m > 1 do

begin

m := m div 2; i := i*2

{точка A}

end {while}

с предполагаемым св-вом {n > 0} Prog {(n < 2*i) & (n > 0) & (i > 0)}.

Рассмотрим предполагаемое индуктивное утверждение Флойда Ф в точке A: (n < m*(2*i)) & (m  1) & (i > 0).

Очевидно, при i > 0 имеемwp(m := m div 2; i := i*2  (n < m*(2*i)) & (m  1)) 

 (n < (m div 2)*2*(2*i)) & (m > 1),

но полученное условие не следует из (m > 1) & Ф, т. е. неверно, что

(m > 1) & (n < m*(2*i))  (n < (m div 2)*2*(2*i)) & (m > 1)

Например, при n = 19, m = 5, i = 2 выполняется неравенство n < m*(2*i), т. е. 19 < 5*2*2 = 20. Однако неравенство n < (m div 2)*2*(2*i) при этом не выполняется.Действительно, (m div 2)*2*(2*i) = 2*2*2*2 = 16 < 19.

Таким образом, утверждение Ф не является хоаровским инвариантом цикла, так как тело цикла S не обладает свойством {B & Ф} S {Ф}.

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

log₂ n = log₂ m + log₂ i .

Сначала покажем, что оно является хоаровским инвариантом (и, следовательно, индуктивным утверждением), а затем  что H  Ф.

Используя «переменную-призрак» j и соотношение i = 2^j, утверждение H можно записать в виде log₂ n = log₂ m + j. Докажем, что H – инвариант Хоара нашего цикла. Действительно:

1) перед циклом log₂ n = log₂ n + 0;

2) при выходе из цикла m = 1 и log₂ n = 0 + j;

3) убедимся, что тело цикла обладает свойством

{(m > 1) & H} m := m div 2; i := i*2 {j := j + 1} {(m  1) & H};

для этого рассмотрим утверждение

wp(S  (m  1) & log₂ n = log₂ m + j) 

 ((m div 2)  1) & (log₂ n = log₂ (m div 2) + (j + 1)))

и учтём, что log₂ (m div 2) + 1 = log₂ m. Последнее равенство очевидным образом справедливо при четном m, а при нечетном m его справедливость следует из соотношений log₂ m = log₂ (m  1) ,  m div 2 = (m  1) div 2, где (m  1) – уже чётное.

Итак, H – хоаровский инвариант и, следовательно, индуктивное утверждение. Покажем, наконец, что H  (n < m*2*i). От противного: пусть n  m*2*i, тогда в силу монотонности функций log₂  и x имеем

log₂ n  log₂ (m*2*i) = 1 + log₂ m + j = 1 + j + log₂ m

и, таким образом, log₂ n  log₂ m + 1 + j , что противоречит исходному утверждению log₂ n = log₂ m + j.

Итак, утверждение (n < m*(2*i)) & (m  1) & (i > 0) является индуктивным утверждением Флойда, но не есть инвариант цикла в смысле Хоара.

Резюме: хоаровский инвариант цикла  это такое индуктивное утверждение, истинность которого устанавливается простейшей индукцией  индуктивный переход доказывается на одном шаге цикла, что в иной форме выражается свойством тела цикла {B & inv} S {inv}. В общей ситуации требуется применение метода математической индукции в его полном варианте, т. е. для доказательства справедливости индуктивного утверждения на текущем шаге цикла требуется использовать предположение о его справедливости на всех (!) предыдущих шагах. Иными словами, может потребоваться рассмотрение св-ва всей последовательности состояний переменных при выполнении цикла, а не просто св-ва изолированного (изъятого из этой последовательности) тела цикла, описывающего его поведение за один шаг.

Замечание. Полезно дать объяснение тому факту, что в рассмотренном примере утверждение H: log₂ n = log₂ m + j при n = 19, m = 5, i = 2 не справедливо (4  2 + 1).

Пример ситуации, когда для доказательства индуктивного утверждения требуется индукция за два шага:

var k, n, m: Integer; ...

{(k  0) & (m = n)}

while k <> 0 do begin k := k  1; n := n + (1)ⁿ end

{ n  m   1}

Неформальный анализ последовательности значений переменной n показывает, что

1) при четном m имеем n = m + 1, m, m + 1, m, m + 1, m, ...

2) при нечетном m имеем n = m  1, m, m  1, m, m  1, m, ... ,

т. е. последовательность значений n периодична с периодом 2, поэтому  n  m   1 – индуктивное утверждение. Формально этот факт устанавливается индукцией за пару шагов (база индукции – два первых шага). Однако утверждение   n  m   1 не является хоаровским инвариантом, поскольку тело цикла не обладает св-вом { n  m   1} n := n + (1)ⁿ {  n  m   1}. Действительно, неверно, что ( n  m   1)  ( (n + (1)ⁿ )  m   1). Например, при k = 1, n = 3, m = 4.

Рассмотрим более простой пример несовпадения хоаровского инварианта и индуктивного утверждения:

var y: Integer; x: Real;

{x = 0}

while y < 10 do

begin x := 2*x; y := y + 1 end

{x < 1}

Очевидно, что {x < 1} – индуктивное утверждение, согласованное с предусловием. Однако свойство {x < 1} x := 2*x; y := y + 1 {x < 1} не выполняется, т. е. {x < 1} – не есть хоаровский инвариант.

Билет№51 Алгоритмы сортировок,Простые и бинарные вставки №51

Сортировка массива по возрастанию(метод простых вставок)

Последовательно просматриваем a1 , ..., an-1 и каждый новый Эл-т ai вставляем на подходящее место в уже упорядоченную совокупность a0 , ..., ai-1 . Это место определяется последовательным сравнением ai с упорядоченными элементами a0 , ..., ai-1 .

Принимает:

* массив значений a с индексами эл-тов от 0 до N-1

* число эл-тов N

procedure Sort(var Arr : array of Real; N : Integer);

var

i, j, k, : Integer; Tmp : Real;

begin

N:=N-1; i:=1;

repeat

j:=0;

repeat

if Arr[i]<=Arr[j] then

begin

k:=i; Tmp:=Arr[i];

repeat

Arr[k]:=Arr[k-1]; k:=k-1;

until not(k>j);

Arr[j]:=Tmp; j:=i;

end ;

else

begin

j:=j+1

end;

until not(j<i);

i:=i+1

until not(i<=n);

end;

end.

Сортировка массива по возрастанию(мет. бинарных вставок)

Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том, что при поиске место, на которое надо вставить эл-т ai в уже упорядоченную совокупность a0 , ..., ai-1 , определяется алгоритмом деления пополам (отсюда и название алгоритма "бинарные вставки" здесь понимаем как "вставка делением пополам").

Принимает: *массив значений a с индексами ‘л-тов от 0 до N-1

*число эл-тов N

procedure Sort_binar(var Arr : array of Real; N : Integer);

var

b,c ,e, i, j, k, : Integer; Tmp : Real;

begin

i:=2;

repeat

b:=1; e:=i-1; c:=((b+e) div 2);

while b<>c do

begin

if Arr[c-1]>Arr[i-1] then

begin

e:=c

end

else

begin

b:=c

end;

c:=((b+e) div 2);

end;

if Arr[b-1]<Arr[i-1] then

begin

if Arr[i-1]>Arr[e-1] then

begin

b:=e+1

end

else

begin

b:=e

end;

end;

k:=i; Tmp:=Arr[i-1];

while k>b do

begin

Arr[k-1]:=Arr[k-1-1]; k:=k-1

end;

Arr[b-1]:=Tmp; i:=i+1;

until not(i<=n);

end;

end.

Билет№52 Алгоритмы сортировки. Простой выбор. Простые обмены(‘пузырёк’) №52

Задача сортировки состоит в упорядочении эл-тов массива по возрастанию или убыванию, основанном на перестановке необходимых эл-тов. Есть несколько подходов к организации сортировки (поиску элементов для перестановки), каждый из которых требует разного времени для достижения результата. Рассмотрим некоторые из методов на примере задачи сортировки по убыванию массива из N целых чисел. Для каждого метода реализуется отдельная процедура. Использующая сортировку программа приводится для первого метода. В ней вводятся необходимые для процедур общие типы и переменные. Вызвать требуемый метод можно путем замены имени вызываемой процедуры.

Сортировка выбором

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

-том (с номером 1). Потом находят максимум среди эл-тов со второго до последнего и меняют его со 2-м эл-том и т. д. В итоге, надо найти N – 1 максимум. Можно искать не максимум, а минимум и ставить его на последнее, предпоследнее и т. д. место. Также применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае количество шагов поиска составляет N div 2.

Вычислительная сложность сортировки выбором – величина порядка N², так как количество сравнений при поиске первого максимума равно N – 1, затем N – 2, N – 3, и т. д. до 1, а в итоге N(N – 1)/2.

program Sort;

type Array1 = array[1..100] of Integer;

var Massiv : Array1; N, i : Integer;

procedure Sort1_1( var A : Array1; N : Integer);

{ Выбором максимального элемента;

входной параметр: N; транзитный параметр: A }

var i, k, m, x : Integer;

begin

for k := 1 to N-1 do { k - номер элемента, с которого поиск max }

begin

m := k; { m - номер max }

for i := k+1 to N do if A[i] > A[m] then m := i;

{меняем местами элементы с номерами m и k }

x := A[m]; A[m] := A[k]; A[k] := x

end;

end;

begin

Write('Количество элементов массива: '); ReadLn(N);

for i := 1 to N do Read(Massiv[i]);

Sort1_1( Massiv, N);

for i := 1 to N do Write(Massiv[i],' ') {упорядоченный массив}

end.

Модификация процедуры сортировки выбором:

procedure Sort1_2( var A : Array1; N : Integer);

{ Выбором максимального и минимального элементов;

входной параметр: N; транзитный параметр: A }

var i, k, m, x, p : Integer;

begin

for k:=1 to N div 2 do { k - номер пары max и min }

begin

m:=k; { m - номер max }

p:=k; { p - номер min }

{ max и min ищутся среди элементов с k до N-k+1 }

for i := k+1 to N-k+1 do

if A[i] > A[m] then m:=i

else if A[i] < A[p] then p:=i;

{ меняем местами элементы с номерами m и k }

x := A[m]; A[m] := A[k]; A[k] := x;

if p = k then p := m;

{ если min стоял на месте k, то сейчас он на месте m }

{ меняем местами элементы с номерами p и N-k+1 }

x := A[p]; A[p] := A[N-k+1]; A[N-k+1] := x

end;

end;

Сортировка обменом (методом “пузырька”)

Метод заключается в том, что, начиная с последнего эл--нта, последовательно сравниваются пары соседних эл-тов массива. Если они не упорядочены, то обмениваем местами пару соседних эл-тов. После одного такого прохода на первом месте будет максимальный эл-т (“всплыл” первый “пузырек”). Затем надо рассматривать эл-ты от последнего до второго и т. д. Всего потребуется N – 1 проход. Вычислительная сложность сортировки обменом порядка N².

procedure Sort2_1( var A : Array1; N : Integer);

{ Обменная сортировка. Базовый вариант.

входной параметр: N транзитный параметр: A }

var i, k, x : Integer;

begin

for k := 2 to N do { надо выполнить N-k+1 сравнений }

for i := N downto k do

if A[i] > A[i-1] then {меняем местами соседние элементы}

begin x := A[i]; A[i] := A[i-1]; A[i-1] := x end;

end;

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

procedure Sort2_2( var A : Array1; N : Integer);

{ Обменная сортировка . Проверка перестановок.

входной параметр: N транзитный параметр: A }

var i, k, x : Integer; p:boolean;

begin

k := 2; { номер элемента, до которого первый проход }

p := true; { логическая переменная p истинна, если были перестановки, т. е. нужно продолжать сортировку }

while p do

begin p := false; { начало нового прохода, перестановок еще не было }

for i := N downto k do

if A[i] > A[i-1] then

begin { меняем элементы местами }

x := A[i]; A[i] := A[i-1]; A[i-1] := x;

p:=true; { и запоминаем факт перестановки }

end;

k := k+1; { уменьшаем количество пар для следующего прохода }

end;

end;

Дополнительно можно запоминать место последней перестановки. Если при очередном проходе последней парой эл-тов, которые поменялись местами, были A[j] и A[j-1], то эл-ты массива с первого до (j – 1)-го уже стоят на своих местах. В итоге можно уменьшить кол-во проверяемых пар до j-го эл-та включительно.

procedure Sort2_3( var A : Array1; N : Integer);

{ Обменная сортировка. Последняя перестановка.

входной параметр: N транзитный параметр: A }

var i, k, x, m : Integer;

begin

Write('Количество элементов массива '); ReadLn(N);

for i := 1 to N do Read(A[i]);

k := 2; {номер элемента, до которого первый проход}

while k > 0 do

begin

m := 0; { пока перестановок при проходе нет, номер равен 0 }

for i := N downto k do

if A[i] > A[i-1] then

begin { меняем элементы местами }

x := A[i]; A[i] := A[i-1]; A[i-1] := x;

m := i+1; { и запоминаем место перестановки }

end;

k := m { количество пар зависит от места последней перестановки }

end;

for i:=1 to N do Write(A[i],' ') {упорядоченный массив}

end;