Алгоритм: поиск самого большого элемента списка

Question

Подвох: разрешены только сравнения между элементами списка. Например, предположим, у нас есть 1 000 000 шахматистов, и нам поручено найти лучшего шахматиста в группе. Мы можем сыграть одного шахматиста против любого другого шахматиста. Теперь мы хотим минимизировать максимальное количество игр, в которые играет каждый игрок .

Если игрок A бьет игрока B и B бьет C , мы можем предположить, что A лучше чем C . Что такое наименьшее значение n , при котором ни один игрок не играет больше, чем n игр?

@ Карл: Это не домашняя работа; это на самом деле подзадача более серьезной проблемы от SPOJ.

Answer 1

Готов поспорить, что ответом является двоичный журнал количества людей.

Вы устанавливаете бинарное дерево в качестве турнирной лестницы. Это означает, что большинство игр, в которые кто-либо играет, это высота дерева. Высота бинарного дерева будет log n

Answer 2

Вместо построения абстрактной структуры данных, такой как бинарное дерево, и разрешения турнира, вы можете переосмыслить свою цель в другом свете:

Устранить все элементы в списке, которые не наибольшее

Вы обнаружите, что выполнение этого может быть гораздо более алгоритмически целесообразнее, чем построить дерево и посеять «турнир».

Я могу продемонстрироватьчто устранение всех элементов в списке, которые не являются самыми большими, может быть сделано с наихудшим сценарием log n вызовов / сравнений на элемент.

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

1. Соедините последовательные элементы и удалите из списка младшие из двух.Игнорируйте непарный элемент, если он есть.

   Это можно сделать, выполнив итерацию от 0 <= <code>i 2i и 2i+1.

   , т.е. для n = 7, int (n / 2) = 3, i = 0,1,2;сравните индексы 0 и 1, 2 и 3, 4 и 5.

2. Всего должно быть исключено int (n / 2) индексов.Вычтите это количество из n.Затем повторяйте 1, пока не останется только один индекс.Это будет ваш самый большой.

Вот реализация в Ruby:

def find_largest(list)

  n = list.size
  working_list = list.clone()

  while n > 1

    temp_list = Array.new()

    for i in (0...n/2)          # remember to cast n/2 to integer if not automatic
      if working_list[2*i] > working_list[2*i+1]
        new_list.push(working_list[2*i])
      else
        new_list.push(working_list[2*i+1])
      end
    end

    working_list = temp_list

    n -= n/2                    # remember to cast n/2 to integer if not automatic

  end

  return working_list[0]

end

Answer 3

Как найти самый большой элемент списка

Если список упорядочен, то самый большой элемент - это первый (или последний) элемент списка.

Если список не упорядочен, то:

Element biggest = list.get(0);
for (Element e : list) {
    if (e.compareWith(biggest) > 0) {
        biggest = e;
    }
}

---

Например, предположим, у нас есть 1 000 000 шахматистов, и нам поручено найти лучшего шахматиста в группе. Теперь мы хотим минимизировать максимальное количество игр, в которые играет любой игрок.

С новым ограничением последнего предложения ...

Ответ № 1: ноль игр. Сравните рейтинг шахматиста, и тот, у кого лучший рейтинг, является объективно лучшим игроком ... согласно рейтингу.

Ответ # 2: не более ceiling(log2(nos_players)) игр, сыгранных на игрока. Турнир на выбывание / выбывание исключает половину игроков в каждом раунде, поэтому количество раундов и, следовательно, максимальное количество игр, сыгранных любым игроком, составляет ceiling(log2(nos_players)).

Соответствующий алгоритм тривиально:

List players = ...
while (players.size() > 1) {
    List winners = new ArrayList();
    Iterator it = players.iterator();
    while (it.hasNext()) {
        Player p1 = it.next();
        if (it.hasNext()) {
            Player p2 = it.next();
            int result = p1.compareTo(p2);
            if (result < 0) {
                winners.add(p2);
            } else if (result > 0) {
                winners.add(p1);
            } else {
                throw new Exception("draws are impossible in chess");
            }
        } else {
            winners.add(p1); // bye
        }
    }
    players = winners;
}

(Кроме того: если у вас также есть заранее определенный рейтинг для игроков, а число игроков N не менее чем на 2 меньше ceiling(log2(N)), вы можете договориться о том, чтобы лучшие 2 игрока получили прощание в одном раунде. Если 2 лучших игрока встретятся в финале, тогда каждый сыграет меньше, чем ceiling(log2(N)) игр ... что является улучшением решения, в котором байты распределяются случайным образом.)

На самом деле, ответ № 2 не работает для игры в шахматы, поскольку он не учитывает тот факт, что значительный процент реальных шахматных партий составляют ничьи; ни один из игроков не выигрывает. Действительно, тот факт, что игрок A побил игрока B в одной игре , не означает , что означает, что A - лучший игрок, чем B. Чтобы определить, кто является лучшим из любых двух игроков, они должны сыграть несколько партий и подсчитать победы и поражения. Короче говоря, представление о том, что для шахматистов существует отношение «лучше чем», ПОЛНОСТЬЮ нереалистично.

---

Несмотря на вышеприведенные пункты, нокаут НЕ является практическим способом организации шахматного турнира. Все будут находиться на стойке организатора турнира и жаловаться на то, что им приходится играть в игры с игроками намного лучше (или хуже), чем они сами.

Реальный шахматный (или аналогичный) турнир работает так, что вы выбираете количество раундов, которое хотите сыграть первым. Затем в "круговом" турнире вы выбираете N лучших игроков по рейтингу. и договориться, чтобы каждый игрок играл друг за друга. Игрок с лучшим результатом выигрыша / ничьей является победителем, и в случае ничьей вы используете (скажем) «сумму очков противников» в качестве прерывателя ничьей. Есть и другие стили турниров, которые обслуживают больше игроков / меньше раундов.

Answer 4

Насколько я знаю, нет алгоритма для решения вашей проблемы без какой-либо дополнительной внешней информации для ранжирования игроков (например, посева). Если вы могли бы правильно посеять игроков, вы можете найти лучшего игрока за меньшее количество раундов, чем худший случай, предложенный Дж. Вонгом.

Пример результатов 2 раундов 10 игроков: A - лучший, ceil (log 10) = 4

A> B; C> D; E> F; G> H; I> J

А> С; B> E; F> G; D> I