Решение последовательными обменами

Можно ли помещать сдвигаемый эл-т массива сразу на нужную позицию? Рассмотрим несколько простых примеров. Пусть n = 8, а k = 3. Исходное и конечное состояния массива изображены на рис. 4.2.

Начнём с элемента a[1]. Он должен попасть в позицию 5, но она пока что занята. Отложим элемент a[1]. На его место должен попасть элемент с индексом 1 + 3 = 4 (в более общем случае – элемент с индексом 1 + k). Переместим a[4] в позицию с номером 1. Далее на место с номером 4 должен попасть элемент a[4 + 3], т. е. a[7]. Переместим a[7] в позицию с номером 4. Затем определим элемент, который должен занять прежнее место элемента a[7]. Для этого вычислим его номер: 7 + 3 = 10. Элемента с таким номером в массиве нет. Очевидно, что нужный нам номер можно получить, «замкнув массив в кольцо», как показано на рисунке слева, и переместиться по кольцу на три позиции по часовой стрелке от элемента с номером 7. Нужным элементом будет элемент с номером 3. Его индекс можно получить, вычитая 7 из 10. В общем случае на место эл-та a[i] должен записываться эл-т a[i + k], если i + k  n. Если же i + k  n, то номер записываемого эл-та следует вычислить как (i + k)  n + 1. Далее, действуя таким образом, получим ещё три перемещения 6  3, 2  6, 5  2 (здесь указаны номера позиций). Следующим должно бы стать перемещение 1  5, но эл-т a[1] уже участвовал в этом процессе, а именно, вспомним, что он был «отложен», а его место занял исходный эл-т a[4]. Таким образом, процесс перемещений завершается записью отложенного эл-та в позицию с номером 5. В итоге все 7 эл-тов заняли новые места, что схематично отражено на рис. 4.3.

Однако не во всех случаях результат получается так просто. Рассмотрим пример с n = 9 и k = 2. Действуя, как и ранее, получим последовательность перемещений 1  x, 3  1, 5  3, 7  5, x  7. Здесь x обозначает хранилище для первого (отложенного) эл-та. Процесс перемещений (рис. 4.4) завершается при попадании в массиве на исходное место отложенного эл-та (в данном случае a[1]).

Очевидно, что переместилась только часть эл-тов массива, а именно эл-ты 1, 3, 5, 7. Перемещения этих эл-тов образуют замкнутую «траекторию» (цикл). Эл-ты 2, 4, 6, 8 остались вне наших действий. В данном примере можно продолжить перемещения, начав их теперь уже с эл-та 2. Эти перемещения также образуют цикл, как показано на рис. 4.5 (этот второй цикл изображен сверху над изображением массива).

В данном примере потребовались перемещения всего по двум замкнутым траекториям (циклам). В других случаях, например при n = 10 и k = 3, перемещения образуют три цикла. Оказывается, что количество циклов равно НОД(n  1, k). Для того чтобы убедиться в этом, удобнее нумеровать эл-ты массива от 0 до n  1. При этом переход через границу массива («закольцовывание») осуществляется операцией mod n над текущим индексом. Для начального эл-та i₀ (0  i₀ < n) цикл замыкается, если (i₀ + p k) mod n = i₀, при этом p должно быть минимальным из удовлетворяющих этому уравнению. Отсюда следует, что должно выполняться (p k) mod n = 0 или p k = q n, где q = (p k) div n. Поскольку, кроме того, (p k) mod k = 0 и p  минимальное из возможных, то p k = НОК(k, n). Таким образом, длина цикла (замкнутой траектории) p = НОК(k, n)  k, а в силу соотношения k n = НОК(k, n)  НОД(k, n) длина цикла p = n  НОД(k, n) и, следовательно, число таких траекторий НОД(k, n) = n  p.

Итак, данный алгоритм обрабатывает Nc = НОД(k, n) замкнутых траекторий. Перемещение эл-тов i-й траектории начинается с эл-та с номером i. Пусть номер текущего эл-та обозначен как Cur, а номер следующего  как Next. Тогда каждый шаг цикла перемещений по замкнутой траектории заключается в перенесении э-та Next на уже «подготовленное» место Cur и изменении значений Cur и Next. Эти соображения приводят к следующему алгоритму (здесь элементы массива нумеруются от 1 до n).

Nc := gcd(n, k);

for i := 1 to Nc do

begin {i – начальный эл-т i-й траектории}

x := a[i]; {отложенный первый эл-т}

Cur := i;

Next := Cur + k; if Next > n then Next := Next  n;

{Cur  куда перемещать}

while Next  i  do

begin

a[Cur] := a[Next];

Cur := Next;

Next := Next + k; if Next > n then Next := Next  n;

end {while};

{Next = i}

a[Cur] := x

end {for}

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

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

Пусть задан отрезок массива а[m..n) и (nm) чётно. Сплошные части отрезка назовём сегментами. Выделим в а[m..n) два сегмента равной длины: а[m..k) и а[k..n), где k = (m + n)/2. Размер каждого сегмента есть s = (n  m)/2 и k = m + s. Этому соответствует картинка

	m	k	n
a:	Сегмент 1	Сегмент 2

Задача состоит в перестановке сегментов 1 и 2. Запишем предутверждение и постутверждение этой задачи:

Pred: (m + n = 2 k) & (m < k < n) & (а[m..n) = A[m..n)),

Post: (m + n = 2 k) & (m < k < n) & (а[m..k) = 

=A[k..n)) & (а[k..n) = A[m..k)).

Очевидно, что задачу можно решить, используя цикл, на каждом шаге которого два эл-та (по одному из каждого сегмента) меняются местами. Инвариантом цикла может быть утверждение:

	m	i	k	j	n
a:	Обменены	Исходные	Обменены	Исходные	& (m  i  k) & (j = s + i)

Тогда, используя цикл for-to-do, получим программу:

k := (m + n) div 2; for i := m to k  1 do a[i]  a[s + i].

Чтобы избежать на каждом шаге сложения при вычислении индекса s + i, можно наращивать на 1 переменную j = s + i  синхронно с изменением i:

k :=(m + n) div 2; j := m + s  1;

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

Если требуется переставить два неприлегающих сегмента a[m..m + s) и a[k..k + s), то эта задача может быть решена аналогичным образом:

procedure SwapEq ( var a: Vector; m, k: index; s: index0);

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

{ Post: (m+s  k) & (a[m..m+s) = A[k..k+s)) & (a[k..k+s) = A[m..m+s))& (a[m+s..k) = A[m+s..k))}

var  i, j: index;

begin

j := k  1; { в цикле будет j = k – m + i }

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

end  {SwapEq}

Здесь следующая картинка

	m	i	m + s	k	j		k + s
a:	Обменены	Исходные	Не менять	Обменены	Исходные		& (m  i <  m + s) &
				&(m + s  k)		& (j = k – m + i)

является основной частью индуктивного утверждения P([m..i)) для цикла for.