Закономерность в массиве Опции

[sheka]

Нужно в массиве 2n элементов поменять последовательность элементов на
а₁а_n+1a₂a_n+2...a_na_2n
Препод говорил, что с помощью одной переменной этого сделать нельзя. (доп массив из n элементов - не интересно).
Вот что получилось (один запоминается, а на его место ставится, но уже на свое место другой):

Curr := 2;
      buf := a[Curr];
      for i := 1 to 2*n-3 do
        begin
          if Curr mod 2 = 0 then
            Next := n+Curr div 2
          else
            Next := (Curr+1) div 2;
          a[Curr] := a[Next];
          Curr := Next;
        end;
      a[Curr] := buf;

но работает только для некоторых, и процент работающих с ростом n уменьшается.
Для неработающих: должен где-то быть вызов буфера, но этого я не делал, т.к. для этого, по моей фантазии надо как минимум еще один булевый 2n-2 массив, что еще хуже дополнительного массива.
Неужели он был прав?

Сообщение отредактировано: sheka - 1.11.2010 20:04

[TarasBer]

1. Берём x
2. Берём y = 2x mod (2n-1)
3. Меняем местами элементы x и y
4. Переходим к 1.

Проблема только в условиях начала и выхода из цикла.
Для 12 элементов картинка такая, видно, что надо провести один циклический обмен по специальной траектории.

Для другого n циклов может быть больше.
Суммарная длина циклов равна n-2 в любом случае.
Главное в общем виде понять, как выглядит каждая траектория (это уже я понял), и откуда начинается.
Заканчивать циклический обмен надо тогда, когда y становится равным x_start. Откуда начинать, вот в чём вопрос. Вот мы сделали один цикл, от единицы, при помощи счётчика мы даже можем установить, что мы прошли не все элементы. Каков номер следующего нетронутого элемента?

[Lapp]

Главное в общем виде понять, как выглядит каждая траектория (это уже я понял), и откуда начинается.
Заканчивать циклический обмен надо тогда, когда y становится равным x_start. Откуда начинать, вот в чём вопрос. Вот мы сделали один цикл, от единицы, при помощи счётчика мы даже можем установить, что мы прошли не все элементы. Каков номер следующего нетронутого элемента?

Именно. Подобный "пустяк" может оказаться принципиальным и пустить все "разумное, доброе, вечное" под откос )). TarasBer, мне будет очень интересно посмотреть на реализацию.. I believe in you!!