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

[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

[Lapp]

Неужели он был прав?

Грубо говоря, правило такое: либо ты тратишь память, либо время. Ничего невозможного нет, если только не рассчитывать на то, чтобы сделать за один проход (то есть за O(n), как уже заметил TarasBer). Короче, вот тебе вполне рабочая реализация:

  for i:=1 to n do begin
    b:=a[n+i];
    for j:=n+i downto 2*i do a[j]:=a[j-1];
    a[2*i]:=b;
  end;

Как опять же верно заметил Тарас, можно было бы обойтись и без буфера (ессно, снова за счет некоторого замедления), примерно так:

  for i:=1 to n do for j:=n+i-1 downto 2*i do begin
    {$R-}
    Inc(a[j],a[j+1]);
    a[j+1]:=a[j]-a[j+1];
    Dec(a[j],a[j+1])
    {$R+}
  end;

2 Unconnected: если будешь (собершенно случайно)) читать этот тред, попробуй связать его с Поменять местом с помощью цикла. . Может, тебе удастся, наконец, понять, что я от тебя хотел там..