NetLab · Rules · Torrent Tracker · Have a problem? · Eng/Rus  Help      Search      Members      Gallery      Calendar
Welcome Guest ( Log In | Register | Validation ) Resend Validation Email
>  NetLab -> Forums -> Сайт -> Флейм -> Topic: На подумать

Pages: (3) 1 2 [3] ( Show unread post )

> На подумать
Print topic |
 FiL Member is Offline
 Posted: 16-06-2005, 00:29 (post 31, #430746)

Сварливый Мозг Клуба
Group: Roots
Group: Roots
Posts: 22885
QUOTE (muaddib @ 15-06-2005, 18:13)
тебе что надо сделать определить среднее между трех чисел при помощи двух сравнений. задачку с монетами или шариками и двумя взвешевании знаешь? здесь сейм принсипал ("а я еще и на машинке шить умею" © :shuffle:) и вообще в место того чтоб приставать предложили бы что дельное
задачку про нахождение среднего не знаю. найти среднее не могу. Туплю.
КАК? Не дайте умереть молодому :help:
PM Email Poster ICQ AOL MSN
Top Bottom
 obaldin Member is Offline
 Posted: 16-06-2005, 02:30 (post 32, #430779)

Медитатор

Group: Prestige
Posts: 4886
Warn:0%-----
QUOTE (Lexus @ 15-06-2005, 23:16)
Как можно высчитать середину 5 случайных чисел.  Найдите алгоритм, который максимум с 6 сравнениями находит "середину".

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

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


....проверил. У квиксорта. Но... у него в худшем случае - O(n2)... Продолжаем копать :)
PM
Top Bottom
 Lexus Member is Offline
 Posted: 16-06-2005, 08:10 (post 33, #430813)

Коллекционер
Group: Global Moders
Group: Global Moders
Posts: 10401
QUOTE (muaddib @ 15-06-2005, 23:21)
рега-рега-рега, минуточку-минуточу, что значит
QUOTE
середину 5 случайных чисел
? это median или mean? можно подробнее определение дать этому понятию.
median
PM Email Poster Users Website
Top Bottom
 Lexus Member is Offline
 Posted: 16-06-2005, 08:13 (post 34, #430816)

Коллекционер
Group: Global Moders
Group: Global Moders
Posts: 10401
QUOTE (obaldin @ 16-06-2005, 01:30)
QUOTE (Lexus @ 15-06-2005, 23:16)
Как можно высчитать середину 5 случайных чисел.  Найдите алгоритм, который максимум с 6 сравнениями находит "середину".

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

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

<!--DoHtmlBegin-->
....проверил. У квиксорта. Но... у него в худшем случае - O(n<sup>2</sup>)... Продолжаем копать :)
<!--DoHtmlEnd-->
вот я тож в хипе и квик сорте рою, так как тема как раз эта у нас сейчас.

Есть у кого линки на описание доказательст эти сортировок, т.к. доказательств того сколько времени каждый требует.
PM Email Poster Users Website
Top Bottom
 obaldin Member is Offline
 Posted: 16-06-2005, 09:33 (post 35, #430829)

Медитатор

Group: Prestige
Posts: 4886
Warn:0%-----
посмотри тут, кстати, упоминается, что для 5 элементов достаточно 6 сравнений для нахождения медианы.

Еще
немного

GIYF :)
PM
Top Bottom
Флейм
Topic Options Pages: (3) 1 2 [3]
>  NetLab -> Forums -> Сайт -> Флейм -> Topic: На подумать
Powered by Invision Power Board v1.3.1 Final.