Версия для печати темы

Автор: sheka 30.10.2010 0:59

Нужно в массиве 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;

Автор: Гость 30.10.2010 1:57

Парными перестановками можно переставить массив не то, что без дополнительного массива, а даже без дополнительной переменной.

Автор: Гость 30.10.2010 1:58

Или требуется именно за O(n) сделать?
Хм, интересно.

Автор: Lapp 30.10.2010 9:58

Цитата(sheka @ 29.10.2010 21:59)

  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;

Автор: Гость 30.10.2010 16:43

TarasBer прикинул на бумаге, и TarasBer решил, что вся эта перестановка некоторым образом раскладывается на несколко циклических перестановок (как и вообще любая перестановка). TarasBer считает, что надо найти некую общую закономерность, чтобы решить задачу за O(n). TarasBer считает очевидным, что если задать n наперёд, то написать алгоритм, дающий сложность O(n) для данного конкретного n, ничего не стоит.

Автор: Lapp 30.10.2010 17:58

Цитата(Гость @ 30.10.2010 13:43)

Автор: Гость 30.10.2010 18:57

Лень перелогиниваться. До картинок дело не дошло пока.

> ты хочешь сказать, что для всех натуральных n нужно писать свой специальный алгоритм?..

Можно, но не нужно. Надо найти закономерность, чтобы общий алгоритм выделить.

> то ему, TarasBer'у, будет непросто - ой непросто, TarasBer! - доказать, что соблюдена асимптотика O(n)..

Суммарная длина циклов равна n.

Автор: Lapp 30.10.2010 19:17

Цитата(Гость @ 30.10.2010 15:57)

Автор: TarasBer 30.10.2010 19:30

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

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

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

Автор: Lapp 31.10.2010 8:54

Цитата(TarasBer @ 30.10.2010 16:30)

Автор: TarasBer 31.10.2010 14:58

Короче, алгебраисты нужны
При каких эн верно
min{k|2^k===1(mod 2n-1)}=2n-2
А при каких нет.
Что-то из теории вычетов. У меня она плохо шла, я больше красивые картинки с треугольниками любил.

Автор: sheka 31.10.2010 22:55

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.

Автор: TarasBer 31.10.2010 23:53

Ща попытаюсь разобраться, что тут написано.
У тебя код очень на лестницу смахивает, тяжело читать. Слово begin не надо отступать на два пробела из-под end. Его можно вообще с if на одной строке писать - ключевые слова все жирные, одинаково хороши видно.

Просмотрел код. Он работает? Не думаю, ты же просто делаешь один цикл длины n. То есть цикл, возможно, получается с перехлёстом и вообще не так.

> if a[Curr] mod 2 = 0

не понял, это же для произвольного массива надо! Как это ты обращаешься к содержимому и что-то делаешь исходя из его чётности?

Автор: Unconnected 1.11.2010 1:39

Поясните плз, смысл в том, чтобы a_n элементы менять местами с a_n+1 ? Тогда, почему бы не сделать что-то типа процедуры swap по ссылке, данной Lapp'ом (где я так и не понял, когда она не должна пройти тестов))?

Автор: Lapp 1.11.2010 10:44

Шек, я совершенно согласен с ТарасБером: желание вникать в твой код улетучивается сразу после того, как взгляд напарывается на сравнение элементов массива. Почему это вообще может быть of value? Какая разница, что там внутри? Лично я полагал, что массив может быть и вовсе не цифровым, а, скажем, из string или запись на много килобайт (что оправдывает нежелание вводить доп. переменную этого типа). И как ты собираешься его содержимое "брать по модулю 2"?..

И еще - пожалуйста, в будущем постарайся не "подразумевать", а явно сообщать..

Цитата(Unconnected @ 31.10.2010 21:39)

Автор: sheka 1.11.2010 23:56

Пожалуй, прокомментирую код - думаю, отвечу на все вопросы.