Алгоритм большинства голосов Бойера-Мура, вторая итерация - PullRequest
Новая
       18

Алгоритм большинства голосов Бойера-Мура, вторая итерация

0 голосов
/ 04 августа 2020

В одном из моих учебников есть проблема:

Вам сообщают результаты президентских выборов. Каждый бюллетень представляется по одному, и на каждом бюллетене написано имя кандидата (предположим, что имена кандидатов представлены числами). Перед объявлением результата общее количество кандидатов и количество проголосовавших неизвестны. Все действительные бюллетени вводятся по одному, и этот процесс повторяется всего 2 раза. У нас есть только 2 простых варианта, которые мы можем использовать для всего процесса. Вы должны разработать алгоритм, который может решить, есть ли кандидат, набравший большинство голосов (то есть более 50%) голосовавших людей, или нет. Если такой кандидат существует, выведите имя кандидата, в противном случае выведите «бла-бла-бла»

Теперь, что первым пришло мне в голову, это использовать алгоритм большинства Бойера-Мура и продолжайте обновлять переменные большинство и счетчик , как только приходит следующий результат. Если я не дал этого ясно, результаты не сохраняются в массиве или где-либо еще. Вы получаете информацию об одном бюллетене, затем производите подсчет (и это продолжается до тех пор, пока не будут использованы все бюллетени, то есть у меня нет доступа к какой-либо предыдущей информации). Независимо от того, хранится эта информация в массиве или нет, я знаю, что могу запустить первую итерацию этого алгоритма, чтобы получить «возможный» результат большинства, так как алгоритм всегда выдает его. Моя проблема заключается во второй итерации, я вижу результаты еще раз, один за другим. Как я должен проверить, действительно ли мой исходный результат является большинством или нет? Есть ли другой способ обойти это с помощью всего 2 переменных?

1 Ответ

0 голосов
/ 04 августа 2020

Я предполагаю, что нам разрешено использовать циклы и переменную l oop для перебора списка.

Предположим, что информация о выборах хранится в votes. Он содержит номер кандидата, за который проголосовали люди. Мы будем считать каждого кандидата победителем и сохранять каждый номер кандидата как победителя на каждой итерации. Если мы сможем найти любого кандидата, число которого больше или равно 50% от количества голосов, мы можем сделать вывод, что кандидат является победителем. Таким образом, мы можем использовать только две переменные count и winner, чтобы получить имя победителя. 

def get_winner(votes):

    count = None
    winner = None

    for i in range(len(votes)):
        winner = votes[i]
        count = 0
        for j in range(i, len(votes)):
            if votes[i] == votes[j]:
                count += 1
        if count >= len(votes)*0.5:
            return winner
    return "blah blah blah"

if __name__ == "__main__":
    votes = [1, 3, 3, 3, 3, 3, 3, 2, 4, 1, 8]
    print(get_winner(votes))

Вывод: 

3
...