0

我的一本教科书中有一个问题如下。

你会得到总统选举的结果。每张选票都是一张一张的，每张选票上都写着候选人的名字（假设候选人的名字用数字表示）。在公布结果之前，候选人的总数和投票的人数是未知的。所有有效的选票都以一张作为输入，这个过程总共重复2次。我们只有 2 个简单的变量可以用于整个过程。您必须设计一种算法，该算法可以确定是否有候选人获得了投票者的多数票（即超过 50%）。如果存在这样的候选人，请打印候选人姓名，否则打印“blah blah blah”

现在我首先想到的是使用Boyer-Moore 多数算法并不断更新多数和计数器下一个结果出现时立即变量。如果我没有说清楚，结果不会存储在数组或其他任何地方。你得到一张选票的通知，然后你计算（这一直持续到所有选票都用完，这意味着我无法访问任何以前的信息）。无论此信息是否存储在数组中，我知道我仍然可以运行该算法的第一次迭代以获得“可能的”多数结果，因为该算法总是产生一个。我的问题在于第二次迭代。我一次又一次地看到结果。我应该如何验证我的原始结果是否确实是多数？有没有其他方法可以让我只用 2 个变量来解决它？

4

2 回答 2

0

您可以进行第一次迭代并在单个变量中跟踪投票。现在这个变量的值“可能”是多数。现在进行第二次迭代并计算第一次迭代指示的多数候选的第二个变量中出现的次数。这是为了验证第一次通过指示的候选人是否确实占多数。总的来说，您只需要 2 个变量和 2 次迭代。顺便说一句，这里是对 Boyer Moore 投票算法的一个很好的介绍 - https://satyadeepmaheshwari.medium.com/boyer-moore-voting-algorithm-in-plain-english-4a343fb4c6a1

于 2021-08-01T15:55:34.657 回答
0

我假设我们被允许使用循环和循环变量来迭代一个列表。

假设选举信息存储在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
于 2020-08-04T05:21:19.893 回答