Drobiazgi

Odwracamy, obracamy...

Dana jest $|n$ -elementowa tablica $a[1::n];$ którą chcemy odwrócić, czyli spowodować, że jej elementy będą zapisane w kolejności $|a[n];a[n −1]; :::;a[1]:$

Najłatwiej to zrobić w miejscu (czyli używając jedynie stałej liczby komórek pamięci dla zmiennych pomocniczych), korzystając z instrukcji $|swap(a[i], a[ j])$ zamieniającej miejscami wartości dwóch elementów:

$for i = 1 to⌊n/2⌋ do swap(a[i],a[n + 1− i]);$

Nietrudno się przekonać, że powyższy kod wywołuje instrukcję zamiany jedynie $|⌊n⌋ 2$ razy, co w przypadku odwrócenia tablicy jest wynikiem optymalnym.

A teraz trudniejsze zadanie: chcemy tę samą tablicę obrócić o $|k$ komórek w lewo, czyli ustawić jej elementy w kolejności $|a[k+ 1],a[k +2],...,a[n],a[1],...,a[k].$ I tym razem spróbujmy to zrobić, używając jedynie instrukcji zamiany.

Można w tym celu trzykrotnie wywołać omówioną przed chwilą procedurę odwracania tablicy:

rev(a[1..k]);rev(a[k+ 1..n]);rev(a[1..n]);

Ten kod wykona $k n−k n |⌊2⌋+ ⌊ 2 ⌋+ ⌊2⌋$ instrukcji zamiany, co w zależności od parzystości liczb $|n$ i $k$ da nam $n$ lub $n − 1$ instrukcji. Pytanie: czy da się mniej?

Poniższy kod obraca tablicę, dzieląc ją na $|nwd(n, k)$ cykli o długości $| n/nwd(n, k)$ i wykonując obrót każdego z nich niezależnie, do czego potrzebuje $|n/nwd(n, k)− 1$ instrukcji zamiany:

$for i = 1 to nwd(n, k) do for j = 1 to n/ nwd(n, k)− 1 do swap(a[i +n ( j −1) ⋅k],a[i +n j⋅k]);$

Operacja $i +n j$ oznacza tu $|(i + j− 1) mod n +1.$ Zatem w tym rozwiązaniu użyjemy w sumie $n − nwd(n, k)$ instrukcji zamiany. A czy ten wynik da się poprawić?