Вечерний матан
Бесполезный навык номер какой-то: умею сортировать 10 попарно неравных чисел не более чем за 22 парных сравнения. То есть, например, восстановить загаданный порядок 10 элементов, задав максимум 22 вопроса о том, какой из двух правее.
(Почти) кстати: количество возможных порядков N чисел равно N! (факториал N), это общеизвестно, а вот количество конфигураций, если возможны равенства - упорядоченные числа Белла; почти столько же, но меньше, получается конфигураций без равенств, но с допустимостью неполной информации, то есть когда все N чисел разбиваются любыми способами на группы, внутри каждой из которых установлен порядок (группы могут быть и единичными). А вот если одновременно допустимы и равные числа, и неполнота информации - то и такое уже есть в Симпсонах OEIS, фактически это количество разных заполнений бюллетеня преференциального голосования.
На этом месте могла быть таблица о том, сколько бит информации всё это занимает, но посчитать в уме двоичный логарифм каждый уважающий себя читатель должен уметь. Принимаю донаты на починку сарказмометра.
UPD: с сегодняшнего дня - еще и 20 чисел за 62 сравнения!
(Почти) кстати: количество возможных порядков N чисел равно N! (факториал N), это общеизвестно, а вот количество конфигураций, если возможны равенства - упорядоченные числа Белла; почти столько же, но меньше, получается конфигураций без равенств, но с допустимостью неполной информации, то есть когда все N чисел разбиваются любыми способами на группы, внутри каждой из которых установлен порядок (группы могут быть и единичными). А вот если одновременно допустимы и равные числа, и неполнота информации - то и такое уже есть в Симпсонах OEIS, фактически это количество разных заполнений бюллетеня преференциального голосования.
На этом месте могла быть таблица о том, сколько бит информации всё это занимает, но посчитать в уме двоичный логарифм каждый уважающий себя читатель должен уметь. Принимаю донаты на починку сарказмометра.
UPD: с сегодняшнего дня - еще и 20 чисел за 62 сравнения!