Задача на общую программистскую логику

← →
DiamondShark © (2004-10-05 14:54) [40]

> KSergey © (05.10.04 14:20) [37]
> > [36] DiamondShark © (05.10.04 14:10)
> > Вместо перестановки использовать функцию преобразования
> > индекса.
>
> Но будет ли это хорошо, кроме формального удовлетворения
> условиям задачи? Вот что мне не понятно во всем этом...

А "хорошо" -- это как?

← →
Igorek © (2004-10-05 16:24) [41]

> Igorek © (05.10.04 14:33) [38]

Сформулирую попонятнее. Пусть у нас есть функция doXOR(dest, op2, l) - делающая операцию искл. ИЛИ над двумя массивами, которые начинаются по адресах dest, op2 (0 - начало исходного массива) длиной l и результат и пишет результат начиная с адреса dest. Ессно. аргументы должны удовлетворять условию непересечения и не выхода за пределы m.

Задача: за константное время (причем минимальное) осуществить кольцевой сдвиг используя для изменения исх. массива только doXOR().

← →
default © (2004-10-05 16:25) [42]

я думаю требовалось в задаче(по крайней мере такую раньше решал я...)без дополнительного массива обеспечить время работы алгоритма O(m)
то есть время работы алгоритма не зависит от величины свдига k

← →
Igorek © (2004-10-05 16:30) [43]

> default © (05.10.04 16:25) [42]

Согласно условию:
1) в формуле О(...) вообще не должны фигурировать ни m ни k
2) нельзя брать дополнительную память вообще (ни под массив, ни под переменные)

← →
default © (2004-10-05 16:34) [44]

Igorek © (05.10.04 16:30) [43]
пусть автор сабжа уточнит условие
я согласен что в нынешней постановке куча непоняток

← →
Igorek © (2004-10-05 16:39) [45]

> default © (05.10.04 16:34) [44]
> Igorek © (05.10.04 16:30) [43]
> пусть автор сабжа уточнит условие
> я согласен что в нынешней постановке куча непоняток

Согласен. Но попробуй решить [41]. Я тоже дома посмотрю.

← →
default © (2004-10-05 17:14) [46]

Igorek © (05.10.04 14:33) [38]
что-то я не понял
какой O(1)!?
этого быть просто не может при осуществлении физической перестановки, максимум без дополнительного массива можно достичь
временной сложности O(m) - это фактически значит что за одну перестановку каждый элемент массива обретает своё новое место
(это я делал)
в Вашем случае в подпрограмме doXor вы сами говорите о том чтоб длина массивов-параметров не превышала m
тут уже зависимость времени от m...

← →
default © (2004-10-05 18:36) [47]

[33]
забыли индекс элемента поставить
вместо Array[(m + k) mod m]
надо
Array[(m+k+i) mod m)]
или
Array[(k+i) mod m]
i-индекс элемента, индексация с 0

← →
Nikolay M. © (2004-10-05 18:45) [48]

> default © (05.10.04 18:36) [47]
> [33]
> забыли индекс элемента поставить

Угу, конечно :)

на основе [33]
то есть ф-ции отображения старых индексов на новые и обратной ей функции можно написать процедуру не зависящую от величины сдвига
procedure CyclicTransorm(var M: Array of TypeElement; Offset: Cardinal); var i, DestIndex, SourceIndex: Cardinal; El1, El2: TypeElement; begin DestIndex := 0; SourceIndex := Offset mod Length(M); El1 := M[SourceIndex]; for i := 0 to High(M) do begin El2 := M[DestIndex]; M[DestIndex] := El1; SourceIndex := DestIndex; if SourceIndex < Offset then DestIndex := SourceIndex - Offset + Length(M) else DestIndex := SourceIndex - Offset; El1 := El2; end; end;

если нужно, то поясню подробнее...

[49]
опс, обломчик
не учёл преобр-ия индексов 0-2 2-0 и тд то есть то что они могут зациклив-ся

> default © (05.10.04 17:14) [46]
> Igorek © (05.10.04 14:33) [38]
> что-то я не понял
> какой O(1)!?
> этого быть просто не может при осуществлении физической
> перестановки, максимум без дополнительного массива можно
> достичь
> временной сложности O(m) - это фактически значит что за
> одну перестановку каждый элемент массива обретает своё новое
> место
> (это я делал)
> в Вашем случае в подпрограмме doXor вы сами говорите о том
> чтоб длина массивов-параметров не превышала m
> тут уже зависимость времени от m...

Нас не интересует время работы doXor. Принимаем что оно константно.

Задача на общую программистскую логику Найти похожие ветки