Форум: "Прочее";
Текущий архив: 2006.09.17;
Скачать: [xml.tar.bz2];
ВнизЗадачка Найти похожие ветки
← →
default © (2006-08-21 09:32) [0]"Дан массив, содержащий некоторую перестановку чисел 0.. N-1
Отсортировать его за О(N) операций и с O(1) доп. памяти."
когда-то была предложена MBo
решение у меня её есть(для проверки вашего)
так решать её нельзя: for i := 0 to High(A) do A[i] := i;
ибо подразумевается, что сортироваться могут записи, ключ сортировки которых как раз такое число
задача в принципе имеет практическую ценность
например, сортировка записей о всех жителях дома с полем номера квартиры(жители одной квартиры представляют одну запись)
← →
Vendict © (2006-08-21 19:22) [1]default © (21.08.06 9:32)
можно с O(N) дополнительной памяти за O(N) время - цифровая сортировка.
Есть же теорема в книжке "Алгоритмы. Построение и анализ" что осортировать быстрее чем за O(nlogn) невозможно.
Цифровая сортировка отдельно, но там используется O(max)
(где max - наибольшее число) памяти.
Интересно, решаема ли твоя задача...
← →
default © (2006-08-21 19:48) [2]Vendict © (21.08.06 19:22) [1]
я её решил минут за 40(возможно потому, что раньше решал задачи со сходной идеей), так что решаема
← →
MBo © (2006-08-21 19:58) [3]>то осортировать быстрее чем за O(nlogn) невозможно
Это для универсальных сортировок, основанных на сравнениях.
В данном же случае есть особые условия, которые позволяют уложиться в указанные ограничения.
← →
Vendict © (2006-08-21 21:38) [4]default © (21.08.06 19:48) [2]
значит ты будешь ждать пока кто-нибудь ещё решит ? интересно знать окончание ветки. мне самому думать влом.
MBo © (21.08.06 19:58) [3]
универсальных сортировок, основанных на сравнениях.
да да. совсем забыл. а разве можно без сравнения ?
← →
DillerXX © (2006-08-21 21:41) [5]
> да да. совсем забыл. а разве можно без сравнения ?
Читаем с-ва перестановки. И тем более цифровой метод (или как называется?) тоже без сравнения. Точнее только сравнение с 0 кажой ячейки в конце происходит.
← →
Ketmar © (2006-08-21 22:00) [6]> [5] DillerXX © (21.08.06 21:41)
кажется, RadixSort называется. когда-то отлично использовался мной в 3d-интрушках на асме под DOS. %-)
← →
default © (2006-08-21 22:07) [7]Vendict © (21.08.06 21:38) [4]
ну да
есть на этом форуме люди которым такие задачи интересны
например, SergP, порой такие финты выдаёт:)
← →
guav © (2006-08-21 22:25) [8]> так решать её нельзя: for i := 0 to High(A) do A[i] := i;
А так можно ?for i := 0 to High(A) do Result[A[i]] := A[i];
← →
SergP © (2006-08-21 23:11) [9]> [8] guav © (21.08.06 22:25)
> > так решать её нельзя: for i := 0 to High(A) do A[i] :=
> i;
>
> А так можно ?
> for i := 0 to High(A) do Result[A[i]] := A[i];
не выполняется условие (выделенное жирным)
> Отсортировать его за О(N) операций и с O(1) доп. памяти.
ИМХО так должно быть:
for i:=0 to N-1 do
begin
k:=a[a[i]];
a[a[i]]:=a[i];
a[i]:=k;
end;
← →
default © (2006-08-21 23:13) [10]guav © (21.08.06 22:25) [8]
"и с O(1) доп. памяти."
← →
default © (2006-08-21 23:17) [11]SergP © (21.08.06 23:11) [9]
неа, подумай, ты не такие задачи решал:) эта фигня почти-что
← →
guav © (2006-08-21 23:49) [12]
i := 0;
for i := 0 to High(A) do
begin
j := A[i];
while j <> i do
begin
k := A[j];
A[j] := j;
j := k;
end;
end;
← →
default © (2006-08-22 00:00) [13]guav © (21.08.06 23:49) [12]
ход мысли верен
есть ошибка(думаю по невнимательности)
← →
guav © (2006-08-22 00:11) [14]Думаю ошибка в условии внутреннего цикла
i := 0;
for i := 0 to High(A) do
begin
j := A[i];
while A[i] <> i do
begin
k := A[j];
A[j] := j;
j := k;
end;
end;
← →
SergP © (2006-08-22 09:34) [15]> [11] default © (21.08.06 23:17)
> SergP © (21.08.06 23:11) [9]
> неа, подумай, ты не такие задачи решал:) эта фигня почти-
> что
После того как запостил и сам увидел что фигня... Но здесь сообщения редактировать нельзя.. :-)
← →
default © (2006-08-22 10:05) [16]guav © (22.08.06 00:11) [14]
верно, почти один в один
procedure HyperSort(var A: Array of Cardinal);
var
i, j, t: Cardinal;
begin
for i := 0 to High(A) do begin
j := A[i];
while i <> A[i] do begin
t := A[j];
A[j] := j;
j := t;
end;
end;
end;
SergP © (22.08.06 09:34) [15]
я имел ввиду фигня про сложность задачи:)
← →
palva © (2006-08-22 10:23) [17]Попробую то же самое на великом и могучем русском языке.
Просматриваем массив с начала. Если все время a[i] = i, то все элементы на своем месте и ничего делать не надо. Но вот встретился первый элемент для которого a[i] <> i, скажем, a[k]. Вынимаем его из массива, в массиве остается дыра. Вынутый элемент должен находиться на a[k] месте. Но это место занято каким-то другим элементом a[a[k]], который явно находится не на своем месте, поскольку в противном случае он был бы равен a[k], а мы знаем что в массиве нет одинаковых элементов. Так что элемент a[a[k]] вынем, а на его место вставим элемент a[k]. В результате количество элементов на своем месте увеличится на один, а вынутый элемент изменит свое значение. Далее найдем место для нового вынутого элемента и т. д. До бесконечности это продолжаться не может, поскольку число элементов не на своем месте все время уменьшается, и в конце-концов мы обнаружим, что очередной вынутый элемент претендует на место, занятое дырой с индексом k. Закроем эту дыру и продолжим последовательный просмотр массива в поисках элементов не на своем месте.
← →
SergP. (2006-08-22 10:52) [18]
> procedure HyperSort(var A: Array of Cardinal);
> var
> i, j, t: Cardinal;
> begin
> for i := 0 to High(A) do begin
> j := A[i];
> while i <> A[i] do begin
> t := A[j];
> A[j] := j;
> j := t;
> end;
> end;
> end;
Біла у меня такая мысль, но почему-то первоначально показалось, что
условите Отсортировать его за О(N) не выполняется из-за вложенных циклов. Хотя на самом деле в принципе оно все-таки выполняется
← →
default © (2006-08-22 13:38) [19]offtopic
palva © (22.08.06 10:23) [17]
Вы вроде бы знакомы с C#?
будет время загляните сюда http://delphimaster.net/view/13-1156238574/
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2006.09.17;
Скачать: [xml.tar.bz2];
Память: 0.53 MB
Время: 0.05 c