Примеры построения программ

Выделение последовательности из массива

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

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

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

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

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

Q: (i: 1 i =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.

begin.

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

i: =i+1.

end;

Count_S: =q.

end;