buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #30 : Июль 12, 2013, 21:22:22 � |
|
Продолжение. 1. Начнём с простейшего - турнир 2-х. Требуется один результат по любому. 2. Турнир из 3-х. Будем считать, что у всех - разное кол-во очков, т.е. 0,1,2 (случай когда одинаковое рассм. отдельно): 3! = 6, log26 > 2, т.е. требуется 3 результата (т.е. все), как ни крути. Тоже никакой экономии. 2а. Если у всех одинаковое число очков, то требуется 1 рез-т, любой и по нему восстановятся остальные. Это частный случай, конечно, но можно догадаться, что максимум рез-тов требуется, когда у всех - разные очки - от 0 до К-1. 3. Турнир 4-х. Все рез-ты разные - 0,1,2,3. Всего таблица (треугольная) будет иметь (К-1)*К/2 = 6 клеток. 4!=24>4, т.е. требуется 5 бит/рез-тов из 6. Экономия - всего 1 бит. Итак, какой рез-т можно не спрашивать? Пусть участники - А,Б,В,Г Я бы запросил: А-Б, А-В, Б-В, Б-Г, В-Г, оставив за бортом рез-т А-Г. Если мы получили 00000, то порядок ГВБА и рез-т А-Г - 0 (А проиграл). Иначе можно убедится, что не все набрали разные очки. Если же рез-т 11111, то порядок АБВГ и А выиграл у Г. Аналогично можно высказаться о каждой комбинации 5 бит. Кстати, не все 32 комбинации релевантны при условии, что у всех разное кол-во очков. Перебирать все 32 комбинации, выделять из них 24 и определять рез-т А-Г я не буду - муторно Как видите, уже для 4-х участников выбрать 5 из 6 рез-тов - это работа более чем нудная. Например, запросить рез-ты А-Б,А-В,А-Г, Б-В,Б-Г и опустить - В-Г было бы неверным (если у всех разное кол-во очков), поскольку результат В-Г - существенен. Другими словами уже для 4-х участников редакции нужен комп и программа, чтоб отбросила 1 из 6 рез-тов. А я описал лишь случай, когда все набрали разное кол-во очков... Для 5: всего - 5*4/2=10, 5!=120>64, т.е. нужно 7 рез-тов из 10. Для 6: 6*5/2=15, 6!=720>512-> 9. Ну, для 16 - 16*15/2=120, 16!>244 -> 45. Но чтоб выбрать 45 из 120 я думаю требуется неслабая программа и нехилый комп...
|