Задача 1. Пусть дан упорядоченный по не убыванию элементов массив b [1: n] (n>=1). Требуется определить максимальную длину p площадки массива. Задача взята из [2].

Площадка массива - это последовательность равных значений. Длина площадки - это количество элементов в последовательности.

Входные данные: nN, b [1: n] Z.

Выходные данные: p - максимальная площадка массива b [1: n].

Метод решения. Сформулируем предусловие

Q: ( i: 1 i < n: b [i] b [i+1]) and (n>=1).

Массив из одного элемента считается упорядоченным. Определим постусловие R: значение p будем считать длиной максимальной площадки, если существует в массиве последовательность из p равных значений и нет последовательности из p+1 равных значений. Заметим, что если сегмент b [j: j+p-1] является площадкой длины p, то, следовательно, b [j] = b [j+p-1]. Запишем это определение на языке предикатов:

R: ( j: 1 j n- (p-1): b [j] = b [j+p-1]) and

( j: 1 j n-p: b [j] b [j+p])

Используя R, определим инвариант P.

Для этого заменим в R константу n переменной i и добавим границы изменения переменной i, тогда получим инвариант P:

(1 i n) and

( j: 1 j i- (p-1): b [j] = b [j+p-1]) and

( j: 1 j i-p: b [j] b [j+p]),

где p - длина максимальной площадки в массиве b [1: i].

Очевидно, что длина площадки в массиве b [1: 1] равна 1. Значит, для инициализации цикла необходимо выполнить оператор:

i: =1; p: =1;

Ограничивающая функция имеет вид t: n-i.

Охрана цикла

B: i < n.

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

i: = i+1; и i: = i+1; p: = p+1;

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

(1 i+1 n) and

( j: 1 j i+1- (p-1): b [j] = b [j+p-1]) and

( j: 1 j i+1-p: b [j] b [j+p])

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

Если p ? длина максимальной площадки в массиве b [1: i], то p ? длина максимальной площадки и в массиве b [1: i+1], но при условии

b [i+1-p] b [i+1].

Для второго оператора условие имеет вид:

b [i+1-p] = b [i+1].

Теперь можно сформулировать алгоритм:

i: =1; p: =1;

while i < n do

begin

if b [i+1-p] b [i+1] then i: = i+1;

if b [i+1-p] = b [i+1] then

begin i: = i+1; p: = p+1 end

end;

Опишем алгоритм в виде процедуры Plosh в следующей интерпретации: заменим два условных оператора в короткой форме одним условным оператором в короткой форме (выносим оператор i: = i+1; из условных операторов).

const n_max=20;

type T_El=integer;

vect=array [1. n_max] of T_El;

procedure Plosh (n: integer; const b: vect; var p: integer);

var i: integer;

begin

i: =1; p: =1;

while i < n do

begin

if b [i+1-p] = b [i+1] then p: = p+1;

i: = i+1

end

end;

Замечание. Тело цикла в последней интерпретации эффективней предыдущего варианта (короче и меньше операций сравнения). Но предыдущий вариант вытекает непосредственно из представленной теории и поэтому понятен.

Задача 2. Пусть дан массив b [1: n] (n>=1). Требуется выделить каждую площадку массива, определить количество площадок и максимальную длину p площадки массива.

Входные данные: n N, b [1: n] Z.

Выходные данные: площадки массива b [1: n],

k - количество площадок,

p - максимальная длина площадки.

Метод решения

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

( j: i j n-j: b [j] = b [i]),

где i - индекс очередного элемента массива.

Ограничивающая функция t: n-j.

Значит, для решения задачи имеем вложенные циклы. Сформулируем алгоритм определения только p (предыдущая задача) с помощью вложенных циклов:

i: =1; p: =0;

while i<=n do

begin

j: =i;

while (j<=n) and (b [i] =b [j]) do

j: =j+1;

p: =max (p,j-i);

i: =j

end;

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

Алгоритм решения задачи представим в виде процедуры Anal_Plosh:

procedure Anal_Plosh (n: integer; const b: vect;

var k,p: integer);

var i,j,t: integer;

begin

i: =1; p: =0; k: =0;

while i<=n do

begin

j: =i;

while (j<=n) and (b [i] =b [j]) do

begin write (b [j],' '); j: =j+1 end;

if j-i>0 then { определена площадка }

begin

if j-i>p then p: =j-i; { определение max (p,j-i); }

k: =k+1;

writeln { для вывода новой площадки }

end;

i: =j

end

end;

Задача 3. Выделить из массива последовательности, удовлетворяющие некоторому условию.

Входные данные: n N, b [1: n] Z.

логическое выражение, определяющее условие.

Выходные данные: последовательности (площадки) массива b [1: n],

k - количество последовательностей,

p - максимальная длина последовательности.

Метод решения

Для определенности будем считать, что необходимо выделить из массива неубывающие последовательности:

b [j-1] b [j] при j=i+1, i+2,…, n,

где i - индекс очередного элемента массива.

Если вести счет количества элементов последовательности с одновременной обработкой элемента (с выдачей), как это реализовано в предыдущей задаче:

j: =i+1;

while (j<=n) and (b [j-1] <= b [j]) do

begin write (b [j-1],' '); j: =j+1 end;

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

По окончании внутреннего циклического процесса нужно проверить, выделена ли последовательность (j-i>0). Если последовательность выделена, то выполняются следующие действия: определяются k, p и выдаются элементы последовательности.

Описание алгоритма

i: =1; p: =0; k: =0;

while i<=n do

begin

j: =i+1;

while (j<=n) and (b [j-1] <=b [j]) do

j: =j+1;

if j-i>0 then

begin k: =k+1; if j-i>p then p: =j-i;

for t: =1 to j-i do write (b [i+t-1],' ');

writeln

end;

i: =j

end;

Замечание. В этом алгоритме элементы последовательности просматриваются дважды. Первый раз ведется счет элементов последовательности (j-i) с определением индексов начала и конца последовательности (i,j). Второй раз элементы последовательности выдаются на экран.

Алгоритм решения задачи представим в виде процедуры Sequence, входными данными которой являются массив b [1: n] и булевская функция B, которая анализирует условие выбора элементов последовательности. В данной задаче в качестве фактической функции будем использовать функцию Prov, которая проверяет, находятся ли значения x и y в отношении: x y.

const n_max=30;

type vect=array [1. n_max] of integer;

func=function (x,y: integer): Boolean;

function Prov (x,y: integer): Boolean;

begin

Prov: =x <= y

end;

procedure Sequence (n: integer; const a: vect;

B: func; var k,p: integer);

var i,j,t: integer;

begin

i: =1; p: =0; k: =0;

while i<=n do

begin

j: =i+1;

while (j<=n) and (B (b [j-1],b [j])) do

j: =j+1;

if j-i>0 then

begin k: =k+1; if j-i>p then p: =j-i;

for t: =1 to j-i do write (b [i+t-1],' ');

writeln

end;

i: =j

end

end;

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

Задача 4. Определить количество площадок массива b [1: n].

Входные данные: n N, b [1: n] Z.

Выходные данные: количество площадок.

Предусловие и постусловие те же, что и в задаче 1.

Определим инвариант и ограничивающую функцию.

P: 1 i n and q = количество площадок в b [1: i-1].

t: n-i.

Алгоритм представим в виде функции Count_S:

function Count_S (n: integer; const b: vect): integer;

var i,q: integer;

begin

i: =1; q: =1;

while i<n do

begin

if b [i] <>b [i+1] then q: =q+1;

i: =i+1

end;

Count_S: =q

end;

2.2 Поиск элемента в матрице