<bgdev />free

Вход Регистрация

Задачка за хладилни техници и други да-ама-тьори
1

0 1 2 3 4 5 6 7
#50187 (ツ) |
Създадено на 18.11.2021, видяно: 678 пъти.
Дърти Хари
johnfound

А бе, какво стана със задачата. Решихте ли я аналитично? Че ми е интересно да си проверя интуицията.

Ми аз имам решение с брут форс ама е 13 гонки и е гарантиран репродуцируем резилтат. Сигурно не е най-оптималния.

В общи линии започва се точно като гъгълското решение за 3, но накрая се махат топ 3 заедно с последните двама от 4 и 5 група, те гарантирано не са в топ 5.

Остават 20.

Групираме ги в 4 групи, 4 гонки плюс една за подреждане плюс една за крайната елиминация

13.

Варианта на mergesort, които пусна Омега го прави за 10.

#50188 (ツ) johnfound
Последно редактирано на 18.11.2021 от johnfound, видяно: 676 пъти.

Добре бе, ето решение за 10 гонки, обяснено подробно:

Правим 5 гонки в 5 групи и така ги сортираме. След това вземаме първите от групите и правим от тях една група. Най-бързият е задължително в нея.

Правим гонка (6-та) и го разбираме кой е.

Вторият е или вторият от 6-тата гонка, или един от 4-мата втори в останалите 5 групи (без тази група от която идва 2) правим гонка от тези 5-ма и намираме вторият (7-ма).

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

И така нататък, общо 10 гонки.

За излъчване на N най-бързи (N>0), от общо X бегача, трябват X/N+N гонки. (но това не е точно rofl)

#50189 (ツ) Дърти Хари
Създадено на 18.11.2021, видяно: 669 пъти.
|
Дърти Хари
johnfound

А бе, какво стана със задачата. Решихте ли я аналитично? Че ми е интересно да си проверя интуицията.

Ми аз имам решение с брут форс ама е 13 гонки и е гарантиран репродуцируем резилтат. Сигурно не е най-оптималния.

В общи линии започва се точно като гъгълското решение за 3, но накрая се махат топ 3 заедно с последните двама от 4 и 5 група, те гарантирано не са в топ 5.

Остават 20.

Групираме ги в 4 групи, 4 гонки плюс една за подреждане плюс една за крайната елиминация

13.

Варианта на mergesort, които пусна Омега го прави за 10.

Кравар, глей си там калемчетата с ученическите проекти и не ми хвърляй киййворди.

Също така щом те е срам да си пуснеш простотиите под собствено име, поне измисли малко по-интересен чорапо акаунт. My link

Решението на омегата не е прецизно понеже избира следващия по случаен признак, и това е кой е свършил пръв от предната гонка.

#50192 (ツ) |
Последно редактирано на 18.11.2021 от |, видяно: 658 пъти.
Дърти Хари
|
Дърти Хари
johnfound

А бе, какво стана със задачата. Решихте ли я аналитично? Че ми е интересно да си проверя интуицията.

Ми аз имам решение с брут форс ама е 13 гонки и е гарантиран репродуцируем резилтат. Сигурно не е най-оптималния.

В общи линии започва се точно като гъгълското решение за 3, но накрая се махат топ 3 заедно с последните двама от 4 и 5 група, те гарантирано не са в топ 5.

Остават 20.

Групираме ги в 4 групи, 4 гонки плюс една за подреждане плюс една за крайната елиминация

13.

Варианта на mergesort, които пусна Омега го прави за 10.

Кравар, глей си там калемчетата с ученическите проекти и не ми хвърляй киййворди.

Също така щом те е срам да си пуснеш простотиите под собствено име, поне измисли малко по-интересен чорапо акаунт. My link

Решението на омегата не е прецизно понеже избира следващия по случаен признак, и това е кой е свършил пръв от предната гонка.

Абе, говедо, ти програмист ли си? Знаеш ли как работи merge sort? Решението на Омегата е прецизно и ти дава първите 5 винаги с 10 сравнения.

#50193 (ツ) |
Създадено на 18.11.2021, видяно: 652 пъти.
johnfound

Добре бе, ето решение за 10 гонки, обяснено подробно:

Правим 5 гонки в 5 групи и така ги сортираме. След това вземаме първите от групите и правим от тях една група. Най-бързият е задължително в нея.

Правим гонка (6-та) и го разбираме кой е.

Вторият е или вторият от 6-тата гонка, или един от 4-мата втори в останалите 5 групи (без тази група от която идва 2) правим гонка от тези 5-ма и намираме вторият (7-ма).

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

И така нататък, общо 10 гонки.

За излъчване на N най-бързи (N>0), от общо X бегача, трябват X/N+N гонки. (но това не е точно rofl)

Обяснението на Омега е много по-разбираемо. След първите 5 гонки имаш 5 групи.

От там нататък съвсем унифицирано взимаш най-бързия останал от всяка от 5-те групи и ги сравняваш. Махаш най-бързия и на негово място слагаш останалият най-бърз от същатата група.

Елементарен merge sort. Въпросът е дали може с по-малко сравнения от това.

#50194 (ツ) Дон Реба
Създадено на 18.11.2021, видяно: 651 пъти.
johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

аз си го тествам със крайнаситуация - всиките 5 най-бързи са до един в първа гонка. тук мисе счупи теста, или не съм те разбрал правилно. третия трябва да е третия в групата на първите двама.

#50195 (ツ) johnfound
Създадено на 18.11.2021, видяно: 640 пъти.
Дон Реба
johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

аз си го тествам със крайнаситуация - всиките 5 най-бързи са до един в първа гонка. тук мисе счупи теста, или не съм те разбрал правилно. третия трябва да е третия в групата на първите двама.

Чакай да измисля по-лесно обяснение:

  1. Строяваме всички в каре 5х5

  2. Правим гонки във всяка колона и я подреждаме така че най-бързите да са най-отпред, а най-бавните най-отзат (5 гонки общо)

  3. Първият ред, съдържа най-бързия от всички в строя.

  4. Провеждаме гонка на хората в първият ред, намираме най-бързия и го махаме от строя.

  5. Неговата колона прави крачка напред, за да запълни дупката.

  6. Ако има празна колона, приключваме. Ако няма goto 3

#50197 (ツ) Дърти Хари
Създадено на 18.11.2021, видяно: 639 пъти.
johnfound
Дон Реба
johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

аз си го тествам със крайнаситуация - всиките 5 най-бързи са до един в първа гонка. тук мисе счупи теста, или не съм те разбрал правилно. третия трябва да е третия в групата на първите двама.

Чакай да измисля по-лесно обяснение:

  1. Строяваме всички в каре 5х5

  2. Правим гонки във всяка колона и я подреждаме така че най-бързите да са най-отпред, а най-бавните най-отзат (5 гонки общо)

  3. Първият ред, съдържа най-бързия от всички в строя.

  4. Провеждаме гонка на хората в първият ред, намираме най-бързия и го махаме от строя.

  5. Неговата колона прави крачка напред, за да запълни дупката.

  6. Ако има празна колона, приключваме. Ако няма goto 3

тоя дето прави крачка напред може да е всъщност деветия по бързина.

#50199 (ツ) johnfound
Създадено на 18.11.2021, видяно: 638 пъти.
Дърти Хари

тоя дето прави крачка напред може да е всъщност деветия по бързина.

Кой имаш предвид. Крачка напред прави цялата колона, а не един човек.

#50200 (ツ) |
Създадено на 18.11.2021, видяно: 635 пъти.
johnfound
Дон Реба
johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

аз си го тествам със крайнаситуация - всиките 5 най-бързи са до един в първа гонка. тук мисе счупи теста, или не съм те разбрал правилно. третия трябва да е третия в групата на първите двама.

Чакай да измисля по-лесно обяснение:

  1. Строяваме всички в каре 5х5

  2. Правим гонки във всяка колона и я подреждаме така че най-бързите да са най-отпред, а най-бавните най-отзат (5 гонки общо)

  3. Първият ред, съдържа най-бързия от всички в строя.

  4. Провеждаме гонка на хората в първият ред, намираме най-бързия и го махаме от строя.

  5. Неговата колона прави крачка напред, за да запълни дупката.

  6. Ако има празна колона, приключваме. Ако няма goto 3

Това е абсолютно същото като решението на Омега.

#50201 (ツ) Дърти Хари
Последно редактирано на 18.11.2021 от Дърти Хари, видяно: 633 пъти.
johnfound
Дърти Хари

тоя дето прави крачка напред може да е всъщност деветия по бързина.

Кой имаш предвид. Крачка напред прави цялата колона, а не един човек.

Втория от най-бързата група може да е най-бавния от останалите от първите две колони. Внася се случаен елемент в алгоритъма. Не е лош, но не ми харесва. И да това е мердж шита на краваря дето се крие зад омегата.

#50203 (ツ) johnfound
Създадено на 18.11.2021, видяно: 632 пъти.
|

Това е абсолютно същото като решението на Омега.

Да напомням ли, че постнах отговора на първата страница на темата, при това със кратко, но по същество вярно описание на алгоритъма – интуицията си е интуиция, не можеш я пропи.

#50204 (ツ) |
Създадено на 18.11.2021, видяно: 631 пъти.
Дърти Хари
johnfound
Дърти Хари

тоя дето прави крачка напред може да е всъщност деветия по бързина.

Кой имаш предвид. Крачка напред прави цялата колона, а не един човек.

Втория от най-бързата група може да е най-бавния от останалите от първите две колони.

И какво като е? Ти си намерил най-бързия от тази група. Втория ще остане в петорката до края на 5-те сравнения.

#50205 (ツ) |
Създадено на 18.11.2021, видяно: 630 пъти.
johnfound
|

Това е абсолютно същото като решението на Омега.

Да напомням ли, че постнах отговора на първата страница на темата, при това със кратко, но по същество вярно описание на алгоритъма – интуицията си е интуиция, не можеш я пропи.

Постнал си 10, не решение. Все още не знаем дали 10 е вярното число.

#50206 (ツ) johnfound
Създадено на 18.11.2021, видяно: 626 пъти.
|

Постнал си 10, не решение. Все още не знаем дали 10 е вярното число.

Постнал съм и решение. И то отговаря на подробното описание, което направих преди малко. Ама ти нали не можеш да четеш с разбиране...

#50207 (ツ) |
Създадено на 18.11.2021, видяно: 624 пъти.
johnfound
|

Постнал си 10, не решение. Все още не знаем дали 10 е вярното число.

Постнал съм и решение. И то отговаря на подробното описание, което направих преди малко. Ама ти нали не можеш да четеш с разбиране...

Не. Решението ти е надбягване на всички редове и надбягване на всички колони. Това не е същото.

#50208 (ツ) |
Създадено на 18.11.2021, видяно: 622 пъти.
Дърти Хари

Внася се случаен елемент в алгоритъма. Не е лош, но не ми харесва. И да това е мердж шита на краваря дето се крие зад омегата.

Никакъв случаен елемент не се внася.

#50209 (ツ) miron
Последно редактирано на 18.11.2021 от miron, видяно: 611 пъти.

Правим пет гонки и след това правим гонка на петимата класирали се на второ място. Подреждаме ги в таблица където всеки ред е резултатите от първата гонка, а класирането са по класирането на гонката на вторите.

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

Аналогично за останалите варианти може да се намери подходяща гонка за да ги доподреди.

Айде кажете къде бъркам :)

#50222 (ツ) janbird
Създадено на 18.11.2021, видяно: 597 пъти.

7 гонки. Първите 5 са ясни. Втората е с първенците и тогаз ни интересуват: 1А 1Б 1С 2А 2Б 3А

където (1-3)А са от групата на победителя, (1-2)Б са на втория, 1С е третия. Правим гонка с тез без победителя и сме ги намерили.

#50225 (ツ) miron
Създадено на 18.11.2021, видяно: 588 пъти.
janbird

7 гонки. Първите 5 са ясни. Втората е с първенците и тогаз ни интересуват: 1А 1Б 1С 2А 2Б 3А

където (1-3)А са от групата на победителя, (1-2)Б са на втория, 1С е третия. Правим гонка с тез без победителя и сме ги намерили.

Не разбрах какво ще направиш, ако всички най-бързи коне са събрани в една от първите пет гонки (1-5А например)

0 1 2 3 4 5 6 7

Задачка за хладилни техници и други да-ама-тьори
1

AsmBB v3.0 (check-in: a316dab8b98d07d9); SQLite v3.42.0 (check-in: 831d0fb2836b71c9);
©2016..2023 John Found; Licensed under EUPL. Powered by Assembly language Created with Fresh IDE