|
|
 |
Условие
(Из книги Д. Гриса) Дан массив целых чисел x[1]..x[m+n], рассматриваемый как соединение двух его отрезков: начала x[1]..x[m] длины m и конца x[m+1]..x[m+n] длины n. Не используя дополнительных массивов, переставить начало и конец. (Число действий порядка m + n.)Решение
Вариант 1. Перевернём (расположим в обратном порядке) отдельно начало и конец массива, а затем перевернём весь массив как единое целое.Вариант 2. (А.Г.Кушниренко) Рассматривая массив записанным по кругу, видим, что требуемое действие — поворот круга. Как известно, поворот есть композиция двух осевых симметрий.
Вариант 3. Рассмотрим более общую задачу — обмен двух участков массива x[p+1]..x[q] и x[q+1]..x[r]. Предположим, что длина левого участка (назовём его A) не больше длины правого (назовём его B). Выделим в B начало той же длины, что и A, назовём его B1, а остаток B2. (Так что B = B1 + B2, если обозначать плюсом приписывание массивов друг к другу.) Нам надо из A + B1 + B2 получить B1 + B2 + A. Меняя местами участки A и B1 — они имеют одинаковую длину, и сделать это легко, — получаем B1 + A + B2, и осталось поменять местами A и B2. Тем самым мы свели дело к перестановке двух отрезков меньшей длины. Итак, получаем такую схему программы:
p := 0; q := m; r := m + n;
{инвариант: осталось переставить x[p+1..q], x[q+1..r]}
while (p <> q) and (q <> r) do begin
| {оба участка непусты}
| if (q - p) <= (r - q) then begin
| | ..переставить x[p+1]..x[q] и x[q+1]..x[q+(q-p)]
| | pnew := q; qnew := q + (q - p);
| | p := pnew; q := qnew;
| end else begin
| | ..переставить x[q-(r-q)+1]..x[q] и x[q+1]..x[r]
| | qnew := q - (r - q); rnew := q;
| | q := qnew; r := rnew;
| end;
end;
Оценка времени работы: на очередном шаге оставшийся для
обработки участок становится короче на длину A; число
действий при этом также пропорционально длине A.
