Еще задача по программированию

← →
Romkin © (2006-12-01 12:41) [0]

Наш менеджер принес задачку, решить на Delphi.
Ну наконец-то я увидел нормальное задание для лабораторной по программированию!
Вот:
В целочисленном массиве A из M строк и N столбцов осуществить циклический сдвиг на величину N:
если N четно, то сдвиг "вверх"
если N нечетно, то сдвиг "вниз"

Решил, разумеется. Причем оптимальным способом. Потом придет за объяснениями - и не уйдет, пока не поймет, как это работает.
По моим прикидкам, там будет 4 вопроса "почему" :)

А кто-нибудь из форумчан может предложить максимально оптимальное решение? По асимптотике? Задачка-то интересная

Массив объявлен как
type TMatrix = array of array of integer;

← →
Курдль © (2006-12-01 12:44) [1]

> В целочисленном массиве A из M строк и N столбцов осуществить
> циклический сдвиг на величину N:

"Величина N" равна кол-ву столбцов?!!

← →
Romkin © (2006-12-01 12:50) [2]

> "Величина N" равна кол-ву столбцов?!!

Ну да, разумеется :)

← →
Alx2 © (2006-12-01 13:01) [3]

Циклический сдвиг на s элементов. Взял из старых записей-черновиков. Переделывать под описанный случай лень. Просто идея.
const n = 12; var data : array [0..n-1] of integer; k,s,p : integer; procedure swap(k,l : Integer); Var tmp : Integer; Begin tmp := data[k]; data[k] := data[l]; data[l] := tmp; End; begin for k := low(data) to High(data) do Data[k] := k; s := 8; k := 0; p := 0; s := s mod n; while s>0 do begin for p := 0 to s-1 do swap(k+p,n - s + p); inc(k,s); s := s mod (n - k); end; end.

← →
Alien1769 © (2006-12-01 13:05) [4]

Статейка "Поразрядная сортировка" очень даже рулит :)
Угадал?

← →
MBo © (2006-12-01 13:05) [5]

A B
C D
E F
должен превратиться в
C D
E F
A B
?

← →
Юрий Зотов © (2006-12-01 13:06) [6]

> Romkin © (01.12.06 12:41)

Сводится к циклическом сдвигу указателей в одномерном "наружном" массиве. Его, в свою очередь, можно реализовать "переносом хвоста в начало" (сдвиг вверх), либо наоборот (сдвиг вниз). Хотя вряд ли это будет оптимальнее, чем просто поменять значения указателей в цикле.

← →
Romkin © (2006-12-01 13:08) [7]

Alien1769 © (01.12.06 13:05) [4] При чем здесь сортировка?! :)
Alx2 © (01.12.06 13:01) [3] Некрасиво и неоптимально :) Количество перестановок примерно равно длине массива, умноженной на величину сдвига. Не катит :)
MBo © (01.12.06 13:05) [5] Это - сдвиг на две строки вниз. N - четно, надо на две вверх.
E F
A B
C D

← →
Alx2 © (2006-12-01 13:12) [8]

>Romkin © (01.12.06 13:08)

>Количество перестановок примерно равно длине массива,
>умноженной на величину сдвига.

Роман, обидные вещи говорите. Такую фигню я бы написал без "зауми" с mod

← →
Romkin © (2006-12-01 13:13) [9]

Юрий Зотов © (01.12.06 13:06) [6] Циклический сдвиг массива из M элементов на N позиций делается примерно за 2*M обменов элементов (считать лень, +-1). Это - оптимально.

← →
Alien1769 © (2006-12-01 13:16) [10]

> Alien1769 © (01.12.06 13:05) [4] При чем здесь сортировка?
> ! :)

Я имел ввиду твою статью, а там как раз описан случай приведенныей ЮЗ.

> Сводится к циклическом сдвигу указателей в одномерном "наружном"
> массиве. Его, в свою очередь, можно реализовать "переносом
> хвоста в начало" (сдвиг вверх), либо наоборот (сдвиг вниз).
> Хотя вряд ли это будет оптимальнее, чем просто поменять
> значения указателей в цикле.

← →
Romkin © (2006-12-01 13:17) [11]

Alx2 © (01.12.06 13:12) [8] О, сорри. Не увидел :) Увидел два цикла. Сколько обменов у тебя?

← →
Romkin © (2006-12-01 13:47) [12]

Alien1769 © (01.12.06 13:16) [10] Здесь удобнее внутри массива все делать, как сказал Зотов, указателями, практически-то это можно трактовать как одномерный массив указателей на массивы :)
Но вот как сдвинуть внутри массива с наименьшими затратами - вот это интересно. Сейчас пытаюсь разобраться с [3] :)
У меня - другой алгоритм.

← →
Alx2 © (2006-12-01 13:56) [13]

К алгоритму в Alx2 © (01.12.06 13:01) [3]

пусть n - число элементов.
пусть s - сдвиг.

Если n>s то незачем нарезать полные обороты по массиву.
Поэтому есть строчка s := s mod n;

Далее. пусть k = номер элемента, с которого начинается массив.
Перетащив s элементов из хвоста в начало мы добиваемся того, что начало массива в полном порядке. А хвост совпадает с началом.
Это делает строчка
for p := 0 to s-1 do swap(k+p,n - s + p);

Осталось осуществить сдвиг для необработанной части массива. То есть переходим к той же самой задаче, но в которой длина массива уже меньше.

Говорим, что наш новый массив теперь начинается с позиции k=k+s
вычислям новый сдвиг с учетом новой длины: s := s mod (n - k);
И все повторяем снова - элементы хвоста ставятся на свои места, а начало уходит в хвост.
Так повторяем до тех пор, пока новый сдвиг s не станет нулем.

Примерная и (кажется) завышенная оценка количества обменов в худшем случае: n + log(n) - из интуитивных соображений. Пока не могу дать более строго

← →
MBo © (2006-12-01 14:00) [14]

M + o(M) полуобменов

function GCD(A, B: Integer): Integer; var Temp: Integer; begin while (B > 0) do begin Temp := A mod B; A := B; B := Temp; end; Result := A; end; procedure ShiftArrDown(pc: PPointerArray; M, N: Integer); var p: Pointer; iCurr, iTo, iFrom, GC, NGC, k: Integer; begin GC := GCD(M, N); NGC := M div GC; for iCurr := M - 1 downto M - GC do begin p := pc[iCurr]; iTo := iCurr; for k := 1 to NGC - 1 do begin iFrom := iTo - N; if iFrom < 0 then iFrom := iFrom + M; pc[iTo] := pc[iFrom]; iTo := iFrom; end; pc[iTo] := p; end; end; вызов if Odd(N) then Shft := N mod M else Shft := (N * M - N) mod M; ShiftArrDown(@A[0], M, Shft);

← →
Romkin © (2006-12-01 14:13) [15]

Ничего не понимаю :)))
У меня ровно M или M+1 обменов:
procedure ReverseArr(var Arr: TMatrix; FromInd, ToInd: integer); var i: integer; T: pointer; begin assert((FromInd >= 0) and (FromInd <= High(Arr)), "Начальный индекс должен лежать в границах массива"); assert((ToInd >= 0) and (ToInd <= High(Arr)), "Конечный индекс должен лежать в границах массива"); if ToInd = FromInd then //Допустимо, но нечего делать exit; for i := 0 to (ToInd - FromInd) div 2 do begin //Внимание! Меняем указатели на массивы!!! T := pointer(Arr[FromInd + i]); pointer(Arr[FromInd + i]) := pointer(Arr[ToInd - i]); pointer(Arr[ToInd - i]) := T; end; end; procedure RotateLines(var Arr: TMatrix; NumLines: integer); begin assert((NumLines > 0) and (NumLines < Length(Arr)), "Смещение должно лежать в границах массива и быть существенным"); ReverseArr(Arr, 0, NumLines - 1); ReverseArr(Arr, NumLines, High(Arr)); ReverseArr(Arr, 0, High(Arr)); end;
Кажется, я делаю лишние :(
Но не могу понять, вроде процедура реверса у меня правильная!

Но почему у Alx2 обменов гораздо меньше?!

← →
Romkin © (2006-12-01 14:24) [16]

Ну точно! procedure ReverseArr(var Arr: TMatrix; FromInd, ToInd: integer); var i: integer; T: pointer; begin assert((FromInd >= 0) and (FromInd <= High(Arr)), "Начальный индекс должен лежать в границах массива"); assert((ToInd >= 0) and (ToInd <= High(Arr)), "Конечный индекс должен лежать в границах массива"); if ToInd = FromInd then //Допустимо, но нечего делать exit; for i := 1 to (ToInd - FromInd + 1) div 2 do begin //Внимание! Меняем указатели на массивы!!! T := pointer(Arr[FromInd + i - 1]); pointer(Arr[FromInd + i - 1]) := pointer(Arr[ToInd - i + 1]); pointer(Arr[ToInd - i + 1]) := T; end; end;
Ровно M обменов...

← →
Alx2 © (2006-12-01 14:25) [17]

>Romkin © (01.12.06 14:13) [15]

У Бориса (MBo) их еще меньше, хотя идея та же. Мой код еще можно причесывать дальше.

← →
Romkin © (2006-12-01 14:32) [18]

Не понимаю все же. Ведь при циклическом сдвиге сдвигаются все элементы. Как может быть число перестановок меньше числа элементов?

← →
Игорь Шевченко © (2006-12-01 14:35) [19]

MBo © (01.12.06 14:00) [14]

Борис, выключи обфускатор :)

← →
MBo © (2006-12-01 14:41) [20]

>Как может быть число перестановок меньше числа элементов?
может, тебя смутило, что у Alx2 N означает длину массива, а не M, как у тебя?

← →
Alx2 © (2006-12-01 14:43) [21]

>Romkin © (01.12.06 14:32) [18]

>Как может быть число перестановок меньше числа элементов?
Например, обменять местами половинки массивов можно за n/2 обменов.
А это как раз сдвиг на n/2.

Кстати, отсюда еще одна идея по новому алгориму рождается - в бинарный вид и от него "пляшем" :) Но уже не уверен, что получится лучше.

← →
Юрий Зотов © (2006-12-01 14:45) [22]

Можно решить задачу в три строчки: SetLength и 2 раза Move. Такое решение считается оптимальным, или нет?

← →
clickmaker © (2006-12-01 14:47) [23]

> [22] Юрий Зотов © (01.12.06 14:45)

это не спортивно )

Alx2 © (01.12.06 14:43) [21] Млин. Перепутал обмены с обращениями... Я и в самом начале спутал это, когда говорил о 2N :(

> Romkin © (01.12.06 14:50) [27]

Зачем двумерный? Внутренние массивы вообще на трогаем, а в наружном, одномерном переставляем указатели на внутренние.

Точнее, не в нем самом, а делаем его новый экземпляр. Ставим ему ту же длину, потом копируем в него из исходного массива один кусок указателей, потом другой.

> [29] Romkin © (01.12.06 15:02)
> Угу. И начинаются игры с финализацией

Да чего там финализировать? FillChar нулями и усе.

> [28] Юрий Зотов © (01.12.06 14:54)
> Точнее, не в нем самом, а делаем его новый экземпляр.

Думаю и в нем самом можно.
type TVector = array of Pointer; var Matrix: TMatrix; Vector: TVector absolute Matrix;
а дальше SetLength, 2 Move и отладчик с CPU Window :)))

> Romkin © (01.12.06 15:02) [29]

А это уже второй вопрос, профессор.
:о)

ТЗ выполнено, а дополнительные пожелания заказчика готов удовлетворить в дополнительные сроки и за дополнительную плату.
:о)

> [30] evvcom © (01.12.06 15:08)
> Да чего там финализировать? FillChar нулями и усе.

Кстати, если этот массив будет TVector, то и FillChar не нужен.

И вот, дошли руки:
Оценка для [3]
Максимальное число обменов = n
Минимальное = n/2
И сложность такая же, как в алгоритме MBo © (01.12.06 14:00)

Еще задача по программированию Найти похожие ветки