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

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

Pred: (m < k < n) & (a[m..n) = A[m..n)),

Post: (s = m + n  k) & (a[m..s) =

= A[k..n)) & (a[s..n) = A[m..k))

и изобразим их в виде картинок:

	m	k	n
Pred: a:	Сегмент 1	Сегмент 2	& (m < k < n)

	m	s	n
Post: a:	Сегмент 2	Сегмент 1	& (s = m + n  k)

Иногда такую перестановку сегментов называют циклическим сдвигом на k  m позиций влево (обычно при m = 1).

Рассмотрим решение этой задачи, опирающееся на использование процедуры SwapEq перестановки сегментов равной длины из 4.6.1.

Представим последовательность  = a_m a_m+1 ... a_n1  в виде конкатенации двух подпоследовательностей  = a_m a_m+1 ... a_k1 и  = a_k a_k+1 ... a_n1, т. е.  =   . Сначала рассмотрим ситуацию, когда Length(  ) < Length(  ), т. е. k  m < n  k. Выделим в конце последовательности  часть, равную по длине последовательности :  = ₁ ₂ , где ₁ = a_k a_k+1 ... a_s1 и ₂ = a_s a_s+1 ... a_n1, а Length(  ) = k  m = Length( ₂ ) = n  s, т. е. s = m + n  k. Тогда исходное состояние массива описывается картинкой

	m	k	s	n
a:		1	2

Используя процедуру SwapEq, переставим сегменты равной длины, содержащие  и ₂, и получим состояние, описываемое картинкой

	m	k	s	n
a:	2	1	

Далее можно завершить решение задачи, переставив сегменты, содержащие ₂ и ₁, т. е. решив аналогичную задачу перестановки сегментов применительно к отрезку массива a[m..s), меньшему, чем исходный отрезок a[m..n).

Рассмотрим теперь ситуацию, когда Length(  ) > Length(  ), т. е. k  m > n  k. Состояние до вызова процедуры SwapEq описывает картинка

	m	s	k	n
a:	1	2	

а состояние после вызова  картинка

	m	s	k	n
a:		2	1

Затем, как и в первом случае, нужно переставить сегменты, содержащие ₂ и ₁. В обеих рассмотренных ситуациях процесс следует продолжать, пока не будут получены сегменты равной длины, после чего решение задачи завершается заключительным применением процедуры SwapEq.

Учтем следующее:Во-первых, заметим, что в обеих рассмотренных ситуациях после применения процедуры SwapEq граница сегментов k не изменилась, но от исходного отрезка a[m..n) перешли в первой ситуации к отрезку a[m..s), содержащему очередную пару переставляемых сегментов, а во второй ситуации  к отрезку a[s..n). Во-вторых, удобно левую m и правую n границы обрабатываемого отрезка отсчитывать от границы k переставляемых сегментов, зная их длины p и q, т. е. m = k  p и n = k + q. Пересчет длин p и q осуществляется просто: в первой ситуации следует выполнить q := q  p, а во второй  p := p  q. Используя переменные p и q, запишем инвариант цикла:

	m	k  p	k	k + q	n
a:	Обрабо тано	Переставить с a[k..k + q]	Переставить с a[k  p..k]	Обработано	& (0 < p  k  m)
				& (0 < q  n  k)

В итоге программу перестановки сегментов разной длины записываем следующим образом:

p := k  m; q := n  k;

{bound: max(p,q)}

while  p  q  do

if  p > q  then begin  SwapEq(a, k  p, k, q);

p := p  q

end

else  {p < q}

begin   SwapEq(a, k  p, k + q  p, p);

q := q  p

end;

{end-while}

SwapEq(a, k  p, k, p)

Заметим, что если из этой программы удалить все вызовы процедуры SwapEq, то получим алгоритм Евклида для вычисления НОД(p, q).

Билет№34 Задача перестановки сегментов массива разной длины.Решение испол. Вспом проц обращения сегмента №34

Пусть дана последовательность _mn = a_m a_m+1 ... a_n1. Определим функцию обращения последовательности Rev( _mn ) = a_n1 a_n2 ... a_m+1 a_m. Запишем заголовок процедуры обращения сегмента массива:

procedure  Reverse( var  a: Vector; m, n: Index);

{Pred: (Low(a)  m) & (m < n  High(a) + 1) & a[m..n) =  A[m..n) }

{Post: (Low(a)  m)&(m < n  High(a) + 1) & a[m..n) = Rev(A[m..n))}

Утверждение a[m..n) = Rev(A[m..n)) можно детализировать: ( i: m  i < n: a[i] = A[(m + n  1)  i]).

Индекс эл-та A[(m + n  1)  i]) определен здесь из следующих соображений. Рассмотрим картинку

	m	n
a:
	 
	i j

Ясно, что первыми должны поменяться местами эл--ты с номерами i = m и j = n  1. То же относится к следующей паре эл-тов с номерами i = m + 1 и j = n  2, затем к паре i = m + 2 и j = n  3 и т. д. При этом, очевидно, будет сохраняться соотношение i + j = const = m + n  1, или j = const  i.

Инвариантом цикла обменов может быть утверждение

	m	i	j		n
a :	Обменены			Обменены	&(m  i < k) & (i  + j = m + n  1) &
			& (k = (m + n) div 2)

Если m + n чётное, то k  начало правой половины массива, а если m + n нечётное, то k  в точности средний элемент сегмента a[m..n).

Теперь в качестве тела процедуры Reverse можно написать

var  k, i, j: Index;

begin

k := (m + n) div 2;

j := n;

for  i := m  to k  1 do  begin j := j  1;  a[i]  a[j] end;

end  {Reverse}

Индуктивным утверждением цикла, соответствующим приведенной картинке, является

P([m..i])  (a[m..i] = Rev(A[j..n)) & (a[j..n) = Rev(A[m..i])) (a(i..j) = A(i..j))& (m  i < k) & (i + j = m + n  1) & (k = (m + n) div 2).