Задача перестановки сегментов разной длины (третье решение)

Другое решение этой задачи можно получить, применив следующий эвристический прием. Пусть на лист бумаги справа от картинки, изображающей исходное состояние массива a[m..n), поставлено зеркало, так, что в нем можно увидеть отражение картинки:

m	k	n	n	k	m
				Отражение 	Отражение 
	Зеркало

Можно заметить, что зеркально отраженное состояние массива похоже на требуемое, отличаясь лишь обратным (зеркальным) порядком следования эл-тов в отражениях сегментов  и . Сопоставим операции зеркального отражения операцию обращения сегмента массива. Поскольку для  =    Rev(  ) = Rev(  )  Rev(  ), то конечное состояние массива, содержащего последовательность    , можно получить следующим образом:    = Rev(Rev(  )  Rev(  )).

Эти соображения приводят к программе, использующей процедуру Reverse из 4.6.2:

begin

Reverse(a, m, k);

Reverse(a, k, n);

Reverse(a, m, n)

End

Билет№35 Задача о равнинах (с испол массива) №35

В 3.5 (Билет№25)была рассмотрена задача о равнинах. Требовалось вычислить функцию f() = «длина самой длинной равнины в ».

Индуктивным расширением в этой задаче являлась функция F() = {f (), Lconc(), Last()},

где Lconc()  длина конкурирующей «хвостовой» равнины, а Last()  последний элемент. Использовались следующие индуктивные соотношения:

f(*x) = max(f(), Lconc(*x)),  Lconc() + 1, если x = Last(),

Lconc(*x) =  

 1, если x  Last(),

Last(*x) = x.

Если последовательность  реализуется массивом a[1..n], то ₁ и Last(_i) = a[i], а также f(₁) = 1 и Lconc(₁) = 1. Программу из примера 3 в 3.5, вычисляющую функцию f(), в этом случае перепишем в виде

y := 1; Lconc := 1;

for i := 2  to  n  do

{ a[i]  новый элемент x, Last() = a[i  1] }

if  a[i] = a[i  1]  then

begin

Lconc := Lconc + 1;

if  y < Lconc  then  y := Lconc {y := y + 1}

end

else  Lconc := 1

Рассмотрим модификацию задачи о равнинах. Пусть исходная последовательность (представляемая массивом) упорядочена: ( i:  1  i < n:   a[i]  a[i + 1]).

Решение задачи в такой постановке получим из ранее приведенного решения первоначальной задачи. Заметим, что важным следствием дополнительного св-ва упорядоченности входной последовательности является следующее: в определении равнины a[j..k] (при 1  j  k  n)

((j = 1) or (a[j  1]  a[j])) & ((k = n) or (a[k]  a[k + 1])) &

& (i: j  i  k:  a[i] = a[i + 1])

последний конъюнктивный член можно заменить на a[j] = a[k]. Учтём этот факт при анализе предыдущей программы. Действительно, индуктивным утверждением цикла в ней является

P([2..i)): (y = рекорд()) & (Lconc  y) & (a[i  Lconc] = a[i 1]),которое после выполнения тела цикла преобразуется в утверждение

P([2..i]): (y = рекорд()) & (Lconc  y) & (a[i  Lconc + 1] = a[i]).Про рекордную равнину известно, что( k:  y  k  i:  a[k  y + 1] = a[k]).

Когда изменяется значение переменной y? Поскольку Lconc увеличивается на каждом шаге не более чем на 1, то увеличение y (на 1) происходит тогда (см. комментарий {y := y + 1} в программе), когда y = Lconc, и при этом добавление a[i] удлиняет «хвостовую» равнину (Lconc := Lconc + 1). В этом случае равенство

a[i  Lconc] = a[i  1]

равносильно равенству a[i  y] = a[i  1].

С другой стороны, пока Lconc не сравняется с y,

(a[i  Lconc] = a[i  1]) & (a[i  y]  a[i  1]).

Заметим теперь, что переменную Lconc вообще можно исключить из алгоритма! Действительно, на очередном шаге цикла возможны три ситуации:

а) конкурент не увеличился: с y ничего не делать;

б) конкурент увеличился, но Lconc  y: с y ничего не делать;

в) конкурент увеличился и Lconc > y: нужно увеличить y на 1.

Ситуацию «в» можно выделить, проверяя равенство a[i  y] = a[i]. Если равенство справедливо, то установить новый рекорд равным y + 1, иначе старый рекорд y сохраняется.

Эти соображения приводят к следующему варианту программы:

y := 1;

{P([2..i)): y  рекорд на отрезке a[1..i)}

for  i := 2  to  n  do   if  a[i  y] = a[i]  then  y := y + 1

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

Билет№36 Задач поиска Эл-та массива.Линейный поиск №36