Помощь - Поиск - Пользователи - Календарь
Полная версия: Закономерность в массиве
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
sheka
Нужно в массиве 2n элементов поменять последовательность элементов на
а1аn+1a2an+2...ana2n
Препод говорил, что с помощью одной переменной этого сделать нельзя. (доп массив из 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 массив, что еще хуже дополнительного массива.
Неужели он был прав?
Гость
Парными перестановками можно переставить массив не то, что без дополнительного массива, а даже без дополнительной переменной.
Гость
Или требуется именно за O(n) сделать?
Хм, интересно.
Lapp
Цитата(sheka @ 29.10.2010 21:59) *
Неужели он был прав?
Грубо говоря, правило такое: либо ты тратишь память, либо время. Ничего невозможного нет, если только не рассчитывать на то, чтобы сделать за один проход (то есть за 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: если будешь (собершенно случайно)) читать этот тред, попробуй связать его с Поменять местом с помощью цикла. . Может, тебе удастся, наконец, понять, что я от тебя хотел там.. blum.gif
Гость
TarasBer прикинул на бумаге, и TarasBer решил, что вся эта перестановка некоторым образом раскладывается на несколко циклических перестановок (как и вообще любая перестановка). TarasBer считает, что надо найти некую общую закономерность, чтобы решить задачу за O(n). TarasBer считает очевидным, что если задать n наперёд, то написать алгоритм, дающий сложность O(n) для данного конкретного n, ничего не стоит.
Lapp
Цитата(Гость @ 30.10.2010 13:43) *
если задать n наперёд, то написать алгоритм, дающий сложность O(n) для данного конкретного n, ничего не стоит.
TarasBer, а Tarasber.. погоди.. ты хочешь сказать, что для всех натуральных n нужно писать свой специальный алгоритм?.. blink.gif
Боюсь, что если TarasBer даже это и сделает (причем, не за бесконечное время), то ему, TarasBer'у, будет непросто - ой непросто, TarasBer! - доказать, что соблюдена асимптотика O(n)..

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

[offtop]эй, Тарас, ты пароль забыл что ли? выслать новый?..[/offtop]
Гость
Лень перелогиниваться. До картинок дело не дошло пока.

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

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

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

Суммарная длина циклов равна n.
Lapp
Цитата(Гость @ 30.10.2010 15:57) *
Можно, но не нужно. Надо найти закономерность, чтобы общий алгоритм выделить.
А зачем тогда писать слова про "заданное наперед n"? Чем оно тогда отличается от вульгарного "просто" n? smile.gif

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

Если не хочешь "перелогиниваться" - хоть напиши ник.. В форме есть специальное место для этого, ревизор ты наш инкогнито )).
TarasBer
1. Берём x
2. Берём y = 2x mod (2n-1)
3. Меняем местами элементы x и y
4. Переходим к 1.

Проблема только в условиях начала и выхода из цикла.
Для 12 элементов картинка такая, видно, что надо провести один циклический обмен по специальной траектории.
Нажмите для просмотра прикрепленного файла
Для другого n циклов может быть больше.
Суммарная длина циклов равна n-2 в любом случае.
Главное в общем виде понять, как выглядит каждая траектория (это уже я понял), и откуда начинается.
Заканчивать циклический обмен надо тогда, когда y становится равным x_start. Откуда начинать, вот в чём вопрос. Вот мы сделали один цикл, от единицы, при помощи счётчика мы даже можем установить, что мы прошли не все элементы. Каков номер следующего нетронутого элемента?
Lapp
Цитата(TarasBer @ 30.10.2010 16:30) *
Главное в общем виде понять, как выглядит каждая траектория (это уже я понял), и откуда начинается.
Заканчивать циклический обмен надо тогда, когда y становится равным x_start. Откуда начинать, вот в чём вопрос. Вот мы сделали один цикл, от единицы, при помощи счётчика мы даже можем установить, что мы прошли не все элементы. Каков номер следующего нетронутого элемента?
Именно. Подобный "пустяк" может оказаться принципиальным и пустить все "разумное, доброе, вечное" под откос )). TarasBer, мне будет очень интересно посмотреть на реализацию.. I believe in you!! respect.gif
TarasBer
Короче, алгебраисты нужны
При каких эн верно
min{k|2^k===1(mod 2n-1)}=2n-2
А при каких нет.
Что-то из теории вычетов. У меня она плохо шла, я больше красивые картинки с треугольниками любил.
sheka
Цитата
сделать за один проход
Я это подразумевал smile.gif
Цитата
можно было бы обойтись и без буфера
Товарищ преподаватель чуть-чуть бушует, если пользоваться такой арифметикой для массивов.
Цитата
Именно. Подобный "пустяк"
Именно. smile.gif
И насчет "пустяк": вот
код (Показать/Скрыть)
, на основе которого я сделал свое заключение о "пустяк" в 1м посте.

Цитата
Для 12 элементов картинка такая, видно, что надо провести один циклический обмен по специальной траектории.
Удачный пример good.gif я тоже такие картинки рисовал и думал даже их в графике для наглядности сделать, но как-то и с помощью статистики все понял(а руки так и чесались нарисоватьsmile.gif).

ЗЫ: Предмет называется "Структуры Данных и Алгоритмы", и на нем нас учат делать все как можно быстрее, почему-то не сильно обращая внимание на память(но только в аспекте сравнения со скоростью).
TarasBer
Ща попытаюсь разобраться, что тут написано.
У тебя код очень на лестницу смахивает, тяжело читать. Слово begin не надо отступать на два пробела из-под end. Его можно вообще с if на одной строке писать - ключевые слова все жирные, одинаково хороши видно.

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

> if a[Curr] mod 2 = 0

не понял, это же для произвольного массива надо! Как это ты обращаешься к содержимому и что-то делаешь исходя из его чётности?
Unconnected
Поясните плз, смысл в том, чтобы an элементы менять местами с an+1 ? Тогда, почему бы не сделать что-то типа процедуры swap по ссылке, данной Lapp'ом (где я так и не понял, когда она не должна пройти тестов))?
Lapp
Шек, я совершенно согласен с ТарасБером: желание вникать в твой код улетучивается сразу после того, как взгляд напарывается на сравнение элементов массива. Почему это вообще может быть of value? Какая разница, что там внутри? Лично я полагал, что массив может быть и вовсе не цифровым, а, скажем, из string или запись на много килобайт (что оправдывает нежелание вводить доп. переменную этого типа). И как ты собираешься его содержимое "брать по модулю 2"?.. blink.gif

И еще - пожалуйста, в будущем постарайся не "подразумевать", а явно сообщать..
Цитата(Unconnected @ 31.10.2010 21:39) *

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

Шека же сказал на этот счет:
Цитата
Цитата
можно было бы обойтись и без буфера

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


Цитата
(где я так и не понял, когда она не должна пройти тестов))?
млиннучетывнатуре подставь числа типа 12345 23456 получи RCE и сиди кайфуй ))
sheka
Пожалуй, прокомментирую код - думаю, отвечу на все вопросы.
Цитата
> if a[Curr] mod 2 = 0

Цитата
И как ты собираешься его содержимое "брать по модулю 2"?
очепятка smile.gif И работало оно только потому, что значения элементов массива были пронумерованы как индексы.

Добавлено через 14 мин.
Цитата
У тебя код очень на лестницу смахивает, тяжело читать. Слово begin не надо отступать на два пробела из-под end. Его можно вообще с if на одной строке писать - ключевые слова все жирные, одинаково хороши видно.
Volvo где-то отвечал на этот вопрос: "как хочешь так и пиши".
В следующий раз попробую, так как ты сказал, может понравится.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.