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

← →
pipll © (2004-10-05 00:12) [0]

Недавно услышал от программиста следующую задачу:

Имеется массив (одномерный, но число элементов m стремится к бесконечности). Нужно сделать циклическую перестановку на k элементов, причем не используя дополнительной памяти. Время перестановки не должно зависить от k и от m.

Слабо решить такую задачку?

← →
K.o.Z (2004-10-05 00:15) [1]

Я даже условия толком не понял, а ты про решение. :)
P.S. А самому? ;)

← →
pipll © (2004-10-05 00:19) [2]

2 K.o.Z: Имеется массив на n элементов. Допустим (a1, a2, a3, a4, a5, ..., an). Нужно сделать циклическую перестановку на k элементов (для простоты k=2 и перестановка назад). Т.е. должно получиться (a3, a4, a5, ..., an, a1, a2), причем не используя дополнительной памяти.

Сам я не представляю как это сделать :(

← →
Cobalt © (2004-10-05 00:20) [3]

Если требуется такая задача - то используйте связный список.

← →
jack128 © (2004-10-05 00:24) [4]

pipll © (05.10.04 0:12)
причем не используя дополнительной памяти.

невозможно. Ты даже по массиву пробежаться не можешь без даполнительной памяти (нужно же хранить счетчик цикла где то )

← →
}{enon © (2004-10-05 00:25) [5]

ИМХО можно через указатели, правда немного не соблюдаются условия :(

← →
KilkennyCat © (2004-10-05 00:25) [6]

машина Поста

← →
}{enon © (2004-10-05 00:29) [7]

Или еще вариант: вытащить из оперативки сколько-то бит (физически их выломать :), сдвинуть остальные, засунуть эти в освободившееся место.

← →
}{enon © (2004-10-05 00:30) [8]

Удалено модератором

← →
}{enon © (2004-10-05 00:31) [9]

Удалено модератором

← →
}{enon © (2004-10-05 00:32) [10]

Удалено модератором

← →
}{enon © (2004-10-05 00:32) [11]

Удалено модератором

← →
}{enon © (2004-10-05 00:33) [12]

Удалено модератором

← →
}{enon © (2004-10-05 00:33) [13]

Удалено модератором

← →
}{enon © (2004-10-05 00:36) [14]

Удалено модератором

← →
}{enon © (2004-10-05 00:37) [15]

Удалено модератором

← →
}{enon © (2004-10-05 00:42) [16]

Удалено модератором

← →
Sha © (2004-10-05 00:44) [17]

> pipll © (05.10.04 00:19) [2]

Во-первых, нужна переменная для организации цикла.

Если кроме переменных для организации цикла можно использовать переменную того же типа, что элемент массива, то это легко.

Если нельзя, то вспомни про xor.
Сначала научись переставлять с его помощью 2 любых элемента,
а дальше сообразишь сам.

← →
}{enon © (2004-10-05 01:02) [18]

2 Sha
Цикл видимо не подходит: время выполнения будет зависеть от m и k...

← →
jack128 © (2004-10-05 01:11) [19]

}{enon © (05.10.04 1:02) [18]
от k не будет.. А вот от m - да. Я вообще не очень преставляю, как можно провести операцию над m элементами, чтобы время выполнения этой операции не зависило от m

← →
}{enon © (2004-10-05 01:19) [20]

Примерно так:
type TValue = record v: integer; next: PValue; end; PValue = ^TValue;
Для того, чтобы переставить k элементов их m нужно поменять значение одной-двух переменных. Правда время поиска k-го элемента зависит от k, ну да черт с ним :)

← →
Alex Konshin © (2004-10-05 01:35) [21]

Циклический двухсвязный список.

← →
jack128 © (2004-10-05 02:01) [22]

}{enon © (05.10.04 1:19) [20]
Alex Konshin © (05.10.04 1:35) [21]
Господа, напоминаю, что речь идет не про список, а про массив!!!

← →
Fay © (2004-10-05 02:29) [23]

Нужно просто пересмотреть своё отношение к индексу массива 8)

← →
Ihor Osov'yak © (2004-10-05 02:34) [24]

хм..
В конце концов - массив - это некая абстракция, обеспечивающая доступ к элементу по индексу, детали реализации которой скрываются за особенностями аппаратной платформы, компилятора, синтаксиса..
Кто сказал, что элементы массива должны идти физически непрырывно и последовательно в памяти? Я имею ввиду общий случай.. И как пример - дос-платформа, модель памяти huge и массив размером больше, чем 64к.

Если принять все это во внимание, как вариант намбер ван - создаем модель, в которой массив отбражается на кольцефой буфер. Собственно, в такой модели ничего и решать не нужно - сдвигаем только указатедь на первый элемент на нужное число позиций. Время выполнения не будет зависить ни от n, ни от м...

← →
Ihor Osov'yak © (2004-10-05 02:36) [25]

2 [23] Fay © (05.10.04 02:29)

Когда я писал свой опус, я Вашего сообщения еще не видел.

← →
Fay © (2004-10-05 03:18) [26]

Ну что Вы, очень интересно было прочесть!
Приятно посмотреть, как когда человек так чётко и понятно выражает мысль - вещь эфемерную и стремительную.

← →
Cobalt © (2004-10-05 08:48) [27]

Действительно, независимо от k - вряд ли получится.

← →
Zlod3y © (2004-10-05 08:55) [28]

jack128 © (05.10.04 02:01) [22]

}{enon © (05.10.04 1:19) [20]
Alex Konshin © (05.10.04 1:35) [21]
Господа, напоминаю, что речь идет не про список, а про массив!!!

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

Ihor Osov"yak © (05.10.04 02:34) [24]
Полностью согласен

← →
Zlod3y © (2004-10-05 08:59) [29]

надо просто у каждого элемента поменять индекс? я прав?

← →
Fay © (2004-10-05 09:11) [30]

2 Zlod3y © (05.10.04 08:59) [29]

Индекс существует только в голове программиста. Там и меняй - оставь массив в покое.

← →
Igorek © (2004-10-05 13:35) [31]

> KilkennyCat © (05.10.04 00:25) [6]
> машина Поста

Можно поподробнее, что имелось ввиду?

> Ihor Osov"yak © (05.10.04 02:34) [24]
> хм..
> В конце концов - массив - это некая абстракция, обеспечивающая
> доступ к элементу по индексу,

Ты говоришь про список с индексированым доступом. А в таких задачах массив - это конкретная вещь. Блок памяти с элементами одинакового размера. Доступ по индексу осуществляется вычислением смещения от начала. Т.е. алгоритмические задачи решаются независимо от апаратной/операц. платформы с применением алгоритмического языка.
Соотв. народ немного путается. Можно реализовать на основе массива произвольные структуры данных - стеки, очереди, кольцевые буферы, связные списки, етс. но не наоборот.

← →
KSergey © (2004-10-05 13:55) [32]

> [24] Ihor Osov"yak © (05.10.04 02:34)

Тут, видимо, надо определиться с термином "массив". Все же на мой взгляд - это

> [31] Igorek © (05.10.04 13:35)
> Доступ по индексу осуществляется вычислением смещения от начала.

Хотя я и безусловно согласен, что это лишь реализация, от которой легко абстрагироваться "вообще", однако если речь вести о некоем реально существующем компиляторе, то получается, что

1) либо надо менять его логику по доступу к элементу массива (т.е. по сути менять компилятор с учетом указанных требований: внешне здаваемое смещение первого элемета и реализация "цикличности")

2) либо менять циклы обхода массива (или, того хуже, методов доступа в конкретному элементу; фактически то же, что и 1, только реализация не внутри компилятора)

В принципе, вероятно вариант 2 и имелся в виду в плане "изменения взгляда" на проблему, однако можно ли это считать ответом на поставленный вопрос в том смысле, что мы рассматриваем не только саму по себе задачу "перестановки", а еще и полезное использование такого "иного взгляда" на мир (массив)?

← →
Nikolay M. © (2004-10-05 13:59) [33]

Обращение к элементу массива путем Array[(m + k) mod m] спасет гиганта мысли?

← →
TUser © (2004-10-05 14:01) [34]

Перестановку - перевораяиванием. Время = два эм, а чтобы от m не зависело, это я вообще не понимаю.

----->---------------------------------->

<-----<----------------------------------

---------------------------------->----->

← →
Vitaly © (2004-10-05 14:06) [35]

> Обращение к элементу массива путем Array[(m + k) mod m]
> спасет гиганта мысли?

Это ОЧЕНЬ ДОЛГО (:о)), хотя от м точно не зависит.
Как и от ж.

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

Вместо перестановки использовать функцию преобразования индекса.

> [36] DiamondShark © (05.10.04 14:10)
> Вместо перестановки использовать функцию преобразования
> индекса.

Но будет ли это хорошо, кроме формального удовлетворения условиям задачи? Вот что мне не понятно во всем этом...

Фактически надо обменять два блока памяти. Это можно сделать при помощи xor. xor доступна на двумя элементами. И если рассматривать условие формально, то можно просто изменить размер элемента до необходимого. Тогда xor над целыми блоками будет считаться одной операцией. И мы получим скорость O(1).

pipll © (05.10.04 00:19) [2]
я делал раньше без дополнительного массива
надо на бумажке поколдовать...
ничего особенного задачка

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

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

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

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

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

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

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

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

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

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

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

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

на основе [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. Принимаем что оно константно.

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