Нужно в массиве 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 массив, что еще хуже дополнительного массива. Неужели он был прав?
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 элементов картинка такая, видно, что надо провести один циклический обмен по специальной траектории.
Удачный пример я тоже такие картинки рисовал и думал даже их в графике для наглядности сделать, но как-то и с помощью статистики все понял(а руки так и чесались нарисовать).
ЗЫ: Предмет называется "Структуры Данных и Алгоритмы", и на нем нас учат делать все как можно быстрее, почему-то не сильно обращая внимание на память(но только в аспекте сравнения со скоростью).