Скачать: CL | DM;

Очень сложная задача на сортировку   Найти похожие ветки 

← →
Igorek ©   (2003-12-19 15:48) [0]

Дан массив из N элементов. Есть Boolean функция Max - сравнения двух элементов.

Написать процедуру, которая выдает массив индексов элементов по возрастанию, при этом минимально возможное колличество раз вызывая ф-цию Max.

---

← →
Семен Сорокин ©   (2003-12-19 15:52) [1]

Загнать массив в TList, обработать Sort...
Функция Max - ни разу не выховется :))

---

← →
MBo ©   (2003-12-19 15:55) [2]

Уточни - Max здесь означает
function AGreaterThanB(A,B:Integer):Boolean;
так?

И еще один момент - элементы массива - целые или любые, на которых определено отношение порядка (><=)?

---

← →
Igorek ©   (2003-12-19 16:26) [3]

> MBo © (19.12.03 15:55) [2]
> Уточни - Max здесь означает
> function AGreaterThanB(A,B:Integer):Boolean;
> так?

Да. Равно True, когда А >B, иначе False.

> И еще один момент - элементы массива - целые или любые,
> на которых определено отношение порядка (><=)?

Любые. Впрочем это нам неизвесно. Дана только функция сравнения и то, что для них справедливо отношение транзитивности.

---

← →
Romkin ©   (2003-12-19 16:32) [4]

ответ: N*Log(N) раз (логарифм по основанию 2)

---

← →
Digitman ©   (2003-12-19 16:34) [5]

QuickSort - достаточно оптимальный алгоритм, если распределение заранее неизвестно и не имеет заранее огрворенных закономерностей

---

← →
Romkin ©   (2003-12-19 16:36) [6]

ЭЭ! Он может и на N^2 выскочить

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.019 c