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

[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

[sheka]

сделать за один проход

Я это подразумевал

можно было бы обойтись и без буфера

Товарищ преподаватель чуть-чуть бушует, если пользоваться такой арифметикой для массивов.

Именно. Подобный "пустяк"

Именно.
И насчет "пустяк": вот

код (Показать/Скрыть)

uses
  Crt, Graph;

const
  NMax = 100; 

var
  a: array [1..2*NMax] of integer;
  i: integer;
  buf: integer;
  Curr, Next, n: integer;
  Res: boolean;
  f: text;
  Ok, Bed: integer;

begin
  clrscr;
  assign(f,'out.txt');
  rewrite(f);
  for n := 1 to NMax do //проверка работоспособности алгоритма для разных n
    begin
      for i := 1 to 2*n do //заполнение массива - для красоты и наглядности
        a[i] := i;

      write(f,'Before:'); //вывод массива до изменений
      for i := 1 to 2*n do
        write(f,a[i]:3);
      writeln(f);

      Curr := 2; //собственно решение
      buf := a[Curr];
      for i := 1 to 2*n-3 do //цикл длины 2*n-3
        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;

      write(f,'After :'); //вывод массива после изменений
      for i := 1 to 2*n do
        write(f,a[i]:3);
      writeln(f);

      Res := true; //подсчет количества n для которых правильный алгоритм работает правильно
      for i := 1 to n do
        if a[2*i] <> a[2*i-1] + n then 
          begin
            Res := false;
            break;
          end;
      if Res then inc(Ok)
      else inc(Bed);
      writeln(f,'N = ',n,'; Result = ', res);
      writeln(f);
    end;
    writeln(f,'Ok = ',Ok,'; Bed = ', Bed);
    close(f);
  //readln;
end.

, на основе которого я сделал свое заключение о "пустяк" в 1м посте.

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

Удачный пример я тоже такие картинки рисовал и думал даже их в графике для наглядности сделать, но как-то и с помощью статистики все понял(а руки так и чесались нарисовать).

ЗЫ: Предмет называется "Структуры Данных и Алгоритмы", и на нем нас учат делать все как можно быстрее, почему-то не сильно обращая внимание на память(но только в аспекте сравнения со скоростью).

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