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

[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 - 2.11.2010 0:04

[Гость]

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

[Гость]

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

[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: если будешь (собершенно случайно)) читать этот тред, попробуй связать его с Поменять местом с помощью цикла. . Может, тебе удастся, наконец, понять, что я от тебя хотел там..

[Гость]

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

[Lapp]

если задать n наперёд, то написать алгоритм, дающий сложность O(n) для данного конкретного n, ничего не стоит.

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

Чего скажешь, TarasBer?

[offtop]эй, Тарас, ты пароль забыл что ли? выслать новый?..[/offtop]

[Гость]

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

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

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

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

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

[Lapp]

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

А зачем тогда писать слова про "заданное наперед n"? Чем оно тогда отличается от вульгарного "просто" n?

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

Эти слова будут иметь вес только после либо: а) определения общего алгоритма, либо б) рассуждений, позволяющих это утверждать без общего алгоритма.. блин, писал эту фразу минуты полторы! и все равно какую-то чушь написал.. Короче - давай уже, показывай свой гениальный алгоритм, Ферма ты наш дорогой и любимый.. ))

Если не хочешь "перелогиниваться" - хоть напиши ник.. В форме есть специальное место для этого, ревизор ты наш инкогнито )).

[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!!

[TarasBer]

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

[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 - 2.11.2010 0:03

[TarasBer]

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

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

> if a[Curr] mod 2 = 0

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

Сообщение отредактировано: TarasBer - 1.11.2010 0:01

[Unconnected]

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

[Lapp]

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

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

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

Шека же сказал на этот счет:

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

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

(где я так и не понял, когда она не должна пройти тестов))?

млиннучетывнатуре подставь числа типа 12345 23456 получи RCE и сиди кайфуй ))

[sheka]

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

> if a[Curr] mod 2 = 0

И как ты собираешься его содержимое "брать по модулю 2"?

очепятка И работало оно только потому, что значения элементов массива были пронумерованы как индексы.

Добавлено через 14 мин.

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

Volvo где-то отвечал на этот вопрос: "как хочешь так и пиши".
В следующий раз попробую, так как ты сказал, может понравится.

Сообщение отредактировано: sheka - 2.11.2010 0:09