ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76242
Темы:    [ Одномерные массивы ]
[ Движения ]
Сложность: 2+
Классы:
В корзину
Прислать комментарий

Условие

(Из книги Д. Гриса) Дан массив целых чисел 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.

Источники и прецеденты использования

книга
Автор А.Шень
Название Программирование: теоремы и задачи
Издательство МЦНМО
Издание второе
Год издания 2004
глава
Номер 1
Название Переменные, выражения, присваивания
параграф
Номер 2
Название Массивы
задача
Номер 1.2.11

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .