Варианта на mergesort, които пусна Омега го прави за 10.
Задачка за хладилни техници и други да-ама-тьори
Добре бе, ето решение за 10 гонки, обяснено подробно:
Правим 5 гонки в 5 групи и така ги сортираме. След това вземаме първите от групите и правим от тях една група. Най-бързият е задължително в нея.
Правим гонка (6-та) и го разбираме кой е.
Вторият е или вторият от 6-тата гонка, или един от 4-мата втори в останалите 5 групи (без тази група от която идва 2) правим гонка от тези 5-ма и намираме вторият (7-ма).
Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).
И така нататък, общо 10 гонки.
За излъчване на N най-бързи (N>0), от общо X бегача, трябват X/N+N гонки. (но това не е точно 
)
Кравар, глей си там калемчетата с ученическите проекти и не ми хвърляй киййворди.
Също така щом те е срам да си пуснеш простотиите под собствено име, поне измисли малко по-интересен чорапо акаунт. My link
Решението на омегата не е прецизно понеже избира следващия по случаен признак, и това е кой е свършил пръв от предната гонка.
Абе, говедо, ти програмист ли си? Знаеш ли как работи merge sort? Решението на Омегата е прецизно и ти дава първите 5 винаги с 10 сравнения.
Обяснението на Омега е много по-разбираемо. След първите 5 гонки имаш 5 групи.
От там нататък съвсем унифицирано взимаш най-бързия останал от всяка от 5-те групи и ги сравняваш. Махаш най-бързия и на негово място слагаш останалият най-бърз от същатата група.
Елементарен merge sort. Въпросът е дали може с по-малко сравнения от това.
аз си го тествам със крайнаситуация - всиките 5 най-бързи са до един в първа гонка. тук мисе счупи теста, или не съм те разбрал правилно. третия трябва да е третия в групата на първите двама.
Чакай да измисля по-лесно обяснение:
Строяваме всички в каре 5х5
Правим гонки във всяка колона и я подреждаме така че най-бързите да са най-отпред, а най-бавните най-отзат (5 гонки общо)
Първият ред, съдържа най-бързия от всички в строя.
Провеждаме гонка на хората в първият ред, намираме най-бързия и го махаме от строя.
Неговата колона прави крачка напред, за да запълни дупката.
Ако има празна колона, приключваме. Ако няма goto 3
тоя дето прави крачка напред може да е всъщност деветия по бързина.
Кой имаш предвид. Крачка напред прави цялата колона, а не един човек.
Това е абсолютно същото като решението на Омега.
Втория от най-бързата група може да е най-бавния от останалите от първите две колони. Внася се случаен елемент в алгоритъма. Не е лош, но не ми харесва. И да това е мердж шита на краваря дето се крие зад омегата.
Да напомням ли, че постнах отговора на първата страница на темата, при това със кратко, но по същество вярно описание на алгоритъма – интуицията си е интуиция, не можеш я пропи.
И какво като е? Ти си намерил най-бързия от тази група. Втория ще остане в петорката до края на 5-те сравнения.
Постнал си 10, не решение. Все още не знаем дали 10 е вярното число.
Постнал съм и решение. И то отговаря на подробното описание, което направих преди малко. Ама ти нали не можеш да четеш с разбиране...
Не. Решението ти е надбягване на всички редове и надбягване на всички колони. Това не е същото.
Правим пет гонки и след това правим гонка на петимата класирали се на второ място. Подреждаме ги в таблица където всеки ред е резултатите от първата гонка, а класирането са по класирането на гонката на вторите.
1 6 11 16 21
2 7 12 17 22
3 8 13 18 23
4 9 14 19 24
5 10 15 20 25
1 ясно че е сред 5 най-бързи, а като махнем всички за които има 5 по-бързи остава това:
1 6 11 16 21
2 7 12
3
4
5
Правим гонка между 3,4,5,7 и 11 (7 гонка) Ако 7 и 11 са първи и втори - най бързи са 1, 2, 6, 7 и 11. Поправка: Трябва да се направи гонка между 11 и 12 или между 2, 11, 7, 16 и 21 - значи пак 8 гонки
Ако първите трима са 3, 4 и 5 тогава трябва да се направи гонка с тях и 2 и 6. И да се вземат първите 4
Аналогично за останалите варианти може да се намери подходяща гонка за да ги доподреди.
Айде кажете къде бъркам :)
7 гонки. Първите 5 са ясни. Втората е с първенците и тогаз ни интересуват: 1А 1Б 1С 2А 2Б 3А
където (1-3)А са от групата на победителя, (1-2)Б са на втория, 1С е третия. Правим гонка с тез без победителя и сме ги намерили.