Автомобильная головоломка

Ответ 1

После вдохновения Диалектика. Разделитесь на 7 случайных групп и расы каждого из них, затем расы медианных этих групп. Этот автомобиль становится стержнем, и мы уже знаем его отношение к 30 другим автомобилям, прямо или косвенно (это свойство медианы медиан). Поэтому, чтобы разместить это с. в других 18 нам нужно запустить 3 гонки, включая шарнир. После поворота нам нужно регенерировать максимум 33 машины. Продолжать. Я закончил с 29 гонками. Даже если вы предполагаете, что нужна полная сортировка, а это не так, существует нижняя граница в 17 гонках (истинная нижняя граница будет еще ниже), что намного меньше 29. Поэтому я подозреваю, что это неправильный ответ, но так как этого недостатка не было, вот субоптимальный. Если вы посмотрите на исследование сортировочных сетей (эта проблема с гонками ограничена двумя автомобилями за раз), поиск оптимальных сетей затруднен, и оптимальные сети известны только для очень маленьких размеров, определенно не до 49. Я не знаю любые исследования сетей с 7-сторонними компараторами.

Может быть, пример может помочь. Пусть говорят, что числа машин от самого медленного до самого быстрого и упорядочивают их в матрице 7x7 (произвольно, так как мы не знаем скоростей, пока не будем участвовать в них).

     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]   34   25   45   43   26   21   13
[2,]   11   24    2   40   14   30   32
[3,]   27   19   29   42    4   17   46
[4,]   15   10   39   33    1    9    5
[5,]   28   18   41    8   23   20    6
[6,]   16    3   38    7   12   22   36
[7,]   31   44   48   35   49   37   47

Затем прогоните каждую из столбцов и отсортируйте их по исходу гонки:

     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]   11    3    2    7    1    9    5
[2,]   15   10   29    8    4   17    6
[3,]   16   18   38   33   12   20   13
[4,]   27   19   39   35   14   21   32
[5,]   28   24   41   40   23   22   36
[6,]   31   25   45   42   26   30   46
[7,]   34   44   48   43   49   37   47

Теперь давайте расу №4 (медианы) и перестройте столбцы в соответствии с результатом

     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    3    9   11    5    7    2
[2,]    4   10   17   15    6    8   29
[3,]   12   18   20   16   13   33   38
[4,]   14   19   21   27   32   35   39
[5,]   23   24   22   28   36   40   41
[6,]   26   25   30   31   46   42   45
[7,]   49   44   37   34   47   43   48

Теперь заметим, что медиана медиан (элемент [4,4]) быстрее, чем любой автомобиль выше и слева и медленнее, чем любой автомобиль внизу и справа (это свойство медианы медиан). Для других автомобилей (нижний левый и правый верхний) мы не знаем, поэтому нам нужно участвовать в гонках против [4,4], 6 за раз (3 гонки). Теперь мы наблюдаем, что 26 автомобилей медленнее, чем [4,4], и поэтому медиана должна быть одной из них. Не нужно больше гоняться за другими. Теперь повторите процесс с этими 26 автомобилями.

Ответ 2

У меня есть решение, требующее только 17 рас.

Во-первых, позвольте мне объяснить простое решение, требующее 32 гонки. Разделите автомобили на 7 групп по 7 и расы каждой группы (7 гонок). Повторите 25 раз: выберите самый быстрый оставшийся автомобиль из каждой группы и введите его в гонку и отложите победителя (25 гонок). Первая из 25 гонок определяет самый быстрый общий автомобиль (№1), вторая гонка определяет # 2 и т.д.

Теперь решение с только 17 гонками:

Наша стратегия состоит в том, чтобы сначала определить 24 самых быстрых автомобиля (позвольте этим машинам "быстро" ). Затем мы найдем самый быстрый из остальных (# 25).

Случайно размещайте автомобили на сетке 7x7 и расы каждого ряда (7 гонок). Затем запустите финиширование 3-го места из каждой гонки (8-я гонка) и сортируйте ряды по скорости финишера 3-го места.

Итак, после 8 гонок мы имеем это:

Каждая ячейка сетки представляет собой автомобиль. Стрелка указывает на более быстрый автомобиль. Обратите внимание, что стрелка транзитивна.

Уже мы можем идентифицировать 8 "быстрых" автомобилей:

Как мы знаем, что они быстрые? Взгляните на синюю "х". Только 23 машины, возможно, быстрее, чем это (не в правом нижнем положении 5x5). Таким образом, это, безусловно, "быстро". Вы можете проверить это для других x.

Мы определили 8 из 24 "быстрых" автомобилей. Удалите эти 8 из будущего рассмотрения. Сейчас мы ищем самые быстрые 16 оставшихся автомобилей. Наши семь групп имеют размеры 4,4,5,7,7,7 и 7. (Для диаграмм, всякий раз, когда мы снимаем автомобиль, пусть скользит оставшиеся автомобили в строке слева.)

Пусть гонка второй самый быстрый оставшийся автомобиль каждой группы, и сортировать строки соответственно (9-я гонка). Как и прежде, мы можем идентифицировать 4 автомобиля, которые, безусловно, относятся к числу 16 самых быстрых (то есть "быстрых" ):

Я окрашиваюсь в ячейки, где могут быть удаленные автомобили, но это пока не действует.
Мы определили 12 "быстрых" автомобилей. Удалите "быстрые" автомобили, и мы ищем самые быстрые 12 оставшихся автомобилей. Наши группы имеют размеры от 2 до 7. Пусть гонка второй самый быстрый оставшийся автомобиль каждой группы, и сортировать строки соответственно (10-я гонка). Мы идентифицируем 2 машины, которые входят в число 12 самых быстрых (то есть "быстрых" ):

(10 "быстрых" автомобилей остаются.)

Мы можем повторить предыдущий шаг еще раз (11-я и 12-я гонки). Каждый раз мы удаляем еще 2 машины. Однако обратите внимание, что в строке/группе может быть 0 или 1 автомобиль. Если в нем есть 1 автомобиль, мы раскачаем этот автомобиль вместо "второго самого быстрого". Если эта машина победит, мы знаем, что она "скорейшая", а также следующая самая быстрая машина второго места. В любом случае мы идентифицируем 2 "скоростных" автомобиля. (6 "быстрых" машин остаются.)

После 12 гонок мы определили и удалили 18 "быстрых" автомобилей. Нам нужно идентифицировать оставшиеся 6 "быстрых" автомобилей.

Теперь позвольте просто разыграть самый быстрый оставшийся автомобиль в каждой группе (13-я гонка) и отсортировать строки соответственно. Победитель "скорейший". 5 слева.

После этой последней гонки есть только 2 машины, которые могли бы стать самым быстрым оставшимся автомобилем. Синий os:

Кроме того, вторым самым быстрым оставшимся автомобилем является синий "o" или зеленый "o". Пусть гонка этих 5 автомобилей (14-я гонка), а два лучших финалиста - "скорейшие". 3 слева.

Повторите два последних шага/гонки, чтобы определить последние 3 скоростных автомобиля (15-я и 16-я гонки).

Итак, мы определили 24 "скоростных" автомобиля. Самый быстрый оставшийся автомобиль должен быть 25-м самым быстрым. Мы можем найти этот автомобиль, просто участвуя в гонках самого быстрого автомобиля в каждом ряду/группе (17-я гонка).

Ответ 3

Попробуйте один из этих алгоритмов

http://en.wikipedia.org/wiki/Quick_select

Ответ 4

http://www.sureinterview.com/shwqst/1062001

Первый раунд

• (7 гонок) Разделите автомобили на 7 групп и получите заказ в каждой группе.
• (1 раса) Возьмите 7 медиан и получите заказ. Найдите медиану медианов (обозначим как o). В следующем примере это 34.
• (3 гонки) Найдите ранг медианы медиан. Возьмите 6 элементов из левого нижнего угла (25 ~ 33) и верхнего правого угла (13 ~ 21) и идите против o (34). После 3 раундов мы знаем ранг этой медианы медианов внутри всего набора. Наилучшим случаем является то, что o - глобальная медиана (25-е место). Хуже всего то, что o - это 16-й или 34-й самый быстрый.

В этом примере показан один возможный наихудший случай.

1   2   3   4   13  14  15  <- group 1
5   6   7   8   16  17  18 
9   10  11  12  19  20  21     ...
22  23  24  34  35  36  37
25  26  27  38  39  40  41  <- group 5
28  29  30  42  43  44  45  <- group 6
31  32  33  46  47  48  49  <- group 7

Круглый стол

Мы хотим найти ранг других медианов в бинарном поиске.

• (3 гонки) Выберите медиану меньше 34, что равно 12. Проведите ее против автомобилей с нижним левым и верхним правом углами. После 3 гонок мы знаем, что его ранг равен 12.

Теперь разрыв между этими двумя медианами не превышает 21, как показано в этом примере.

Третий раунд

Переставьте 21 автомобиль ( > 12 и < 34) следующим образом.

13  14  15  <- group 1
16  17  18 
19  20  21     ...
22  23  24
25  26  27  <- group 5
28  29  30  <- group 6
31  32  33  <- group 7

Каждая строка все еще сортируется.

• (1 раса). Теперь снова найдите медианную медианную, которая равна 23.
• (1 гонка) Найдите рейтинг. После этого шага мы знаем, что автомобиль на предыдущем этапе занимает 23 место.
• (1 раса) Подобно бинарному поиску, проверьте ранг другой медианы, 29.
• (1 гонка) Сортировать все автомобили между 23 ~ 29 (эксклюзивные). Найден 25-й самый быстрый автомобиль.

Поэтому для получения 25-го самого быстрого автомобиля требуется не более 18 гонок.

Ответ 5

Не можете ли вы итеративно разделить пул, определив точное положение автомобиля?

Выберите автомобиль в случайном порядке, чтобы Пробегайте через каждый из 48 автомобилей, разыгрывая их группами по 6 против поворотного автомобиля Теперь вы знаете точную позицию поворотного автомобиля.

Теперь запустите тот же процесс на той части набора, который, как вы знаете, включите в нее позицию 25. Если в оставшемся разделе содержится менее семи элементов, это легко определить.

В худшем случае это поистине ужасно, но может быть смягчено путем выбора последовательных опорных точек каким-то полуинтеллектуальным способом.

Ответ 6

Вы всегда можете решить это в 8 гонках... Давайте возьмем Pivot Car сказать Car1 и раскачать его со всеми другими автомобилями в 8 гонках и взять относительную скорость других автомобилей по Car1. скажем, результат приведен ниже: Прочтите автомобиль # (Относительная скорость до Car1)

Гонка 1: Car1- (0), Car2 - (+ 10), Car3 (+5), Car4 (+7), Car5 (-3), Car6 (-4), Car7 (+1)

Гонка 2: Car1- (0), Car8 - (+ 10), Car9 (+5), Car10 (+7), Car11 (-3), Car12 (-4), Car13 (+1)

Гонка 3: Car1- (0), Car14 - (+ 11), Car15 (+4), Car16 (+6), Car17 (-4), Car18 (-10), Car19 (+2)

Гонка 4: Car1- (0), Car20 (+9), Car21 (+3), Car22 (+5), Car23 (-5), Car24 (-11), Car25 (+3)

Гонка 5: Car1- (0), Car26 - (+ 8), Car27 (+2), Car28 (+6), Car29 (-6), Car30 (-12), Car31 (+4)

Гонка 6: Car1- (0), Car32 - (+ 7), Car33 (+1), Car34 (+3), Car35 (-7), Car36 (-13), Car37 (+5)

Гонка 7: Car1- (0), Car38 - (+ 6), Car39 (-1), Car40 (+2), Car41 (-8), Car42 (-14), Car43 (+6)

Гонка 8: Car1- (0), Car44 - (+ 5), Car45 (-2), Car46 (+1), Car47 (-9), Car48 (-15), Car49 (+7)

Так как Car1 является поворотным автомобилем, и скорость каждого автомобиля согласована во всех гонках, мы можем сгруппировать все результаты.

Если вы отсортируете относительную скорость (wrt car1), вы можете узнать 25-й самый быстрый автомобиль.