Loading...
arnold avatar arnold 50 Точки

Интересна задача

Съвет за подход и измисляне на логиката в тази задача, ако някой има опит в подобен тип задача и съставянето им като конзолно приложение

 

 

Задача. 16 плувци се състезват в басейн с 4 коридора. Имаме награди за 1-во до 5-то място. Можем ли да ги определем със 7 старта? Как?

N-то място означава победата (директна или индиректна) над всеки следващ - засичането няма значение

Тагове:
1
Структури от данни и алгоритми 09/06/2023 21:46:58
MartinBG avatar MartinBG 4803 Точки

Сигурно ли е, че тази задача има 100% работещо решение само със 7 старта?

Най-вероятно - да, защото иначе кой ще си играе да я измисля! devil

 

За улеснение, ще маркираме 16-те плувци с номера от 1-16, като тези номера ще отговарят и на способностите им (№1 е най-бърз, №16 - най-бавен).

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

Ето няколко сценария набързо, за които крайната класация винаги трябва да е 1, 2, 3, 4, 5 без значение за останалите места:

  • (1, 2, 3, 4) и (5, 6, 7, 8) се падат в първите 2 старта
  • (1, 2, 3, 16) и (4, 5, 6, 7) се падат в първите 2 старта
  • (1, 2, 15, 16), (3, 4, 13, 14), (5, 6, 7, 8) се падат в първите 3 старта
  • (1, 2, 15, 16), (3, 12, 13, 14), (4, 9, 10, 11), (5, 6, 7, 8) се падат в първите 4 старта
  • (1, 5, 6, 7), (2, 3, 4, 8) се падат в първите 2 старта

И така нататък.

Доста комбинации, които едва ли ще могат да се обхванат в универсален алгоритъм, който да работи със 7 старта общо, т.е. като махнем първите 4 ни остават само 3. Явно този подход няма да сработи.

 

Да помислим в друга посока. Вместо да разделяме плувците на 4 първоначални групи, нека просто да изберем 4 произволни плувци за първата група. След всяко състезание вземаме най-добрия измежду тях и го пускаме срещу 3-ма от оставащите плувци, като по този начин след последното 5-то състезание ще имаме най-бързия плувец измежду всички, но също ще имаме и някаква реална основа за сравняване на бързината на всички плувци, тъй като във всяко следващо състезание имаме по един плувец от предходното. И така, след 5 състезания сме открили кой е шампион и с оставащите 2 трябва да определим класацията от 2 до 5-то място. Ето няколко сценария:

  • (1, 2, 3, 4), (1, 5, 6, 7), (1, 8, 9, 10), (1, 11, 12, 13), (1, 14, 15, 16) - най-лошият вариант, защото не сме получили никаква допълнителна информация за способностите на плувците между отделните групи
  • (13, 14, 15, 16), (13, 10, 11, 12), (10, 7, 8, 9), (9, 4, 5, 6), (4, 1, 2, 3) - най-добрият вариант, защото последната група ни дава класацията от 1во до 4-то място, а 5-то място идва от класиралият се на второ място в предпоследната група

Явно сме на прав път, защото имаме решение с 5 старта за идеалния случай, но за първия пример нямаме шанс да намерим решение с оставащите ни 2 старта.

 

Да поитерираме още малко върху последната идея. От примерите се вижда, че ако пренасяме победителя между състезанията, всъщност може да загубим ценна информация за силата на плувците в отделните групи. Да видим един пример какво ще стане, ако вместо победителят, пренасяме класиралия се на 2-ра позиция плувец:

  • (1, 2, 3, 4), (2, 5, 6, 7), (5, 8, 9, 10), (8, 11, 12, 13), (11, 14, 15, 16) - не се сещам за вариант да се направи класацията само с още 2 състезания.

Най-вероятно по подобен начин ще се развият нещата и ако пренасяме класиралият се на 3-та или на 4-та позиция между отделните състезания.

 

Какво ще стане, ако вместо един, пренасяме по двама състезатели? Получават се точно 7 състезания: 4 плувци в първото, оставащите 12 състезатели се разделят на 6 групи от по 2 плувци, които се състезават с двама от предходния старт.

Тази идея изглежда обещаваща, защото пренася най-много информация между отделните състезания, без да преминаваме лимита от 7 старта. Остава да изберем дали да пренасяме плувците, класирали се на 1 и 2, 1 и 3, 1 и 4, 2 и 3 или 3 и 4 място в старта и да разиграем няколко сценария с тези варианти докато отсеем най-удачния... ако има такъв, измежду тях, разбира се! Оставям тази занимавка за някой друг, че този пост и без друго вече е доста дълъг. smiley

 

2
12/06/2023 01:35:32
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.