墨尔本大学COMP10001课业解析

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top

题意:
编程实现电子投票自动计数功能,对不同的投票方案有良好的支持性
解析:
背景:
大会选举,每位选民只能支持自己最喜欢的候选人,一人一票,获得最多选票的候选人赢得选举。

方案一:First Past the Post

实现first_past_the_post(votes)函数,参数votes是一个存储选票信息的列表,是一系列代表候选人名字的字符。
考虑用遍历列表的方法分别统计每个候选人的频率,比较大小后返回频率最高者的名字;存在最高得票的多个候选人票数一样的情况,返回 “tie”


方案二:Second Preference

实现second_preference(votes)函数,参数votes是一个存储
选票信息的二重列表。此方案用来解决方案一中,胜出者选票<=50%的情况。首先按第一志愿统计候选人频率,最高得票不过半,删掉第一志愿中得票最低的候选人(有多个按候选人首字母次序删除较前的候选人),并且统计剩余候选人得票数(第一志愿+第二志愿),返回最高者名字,若有多个返回 “tie”


方案三:Multiple Preferences

实现multiple_preferences(votes)函数,参数votes是一个存储选票信息的二重列表。方案二只进行一轮,方案三是多轮的改进版。样例中采取5志愿投票,类似方案二的方法进行。


涉及知识点:
python 列表,二重列表,循环
微信号:Ssss_970521

pdf全文
Project 1
21 August 2019

eVoting

• As A/Prof Teague mentioned in her guest lecture – a major challenge is how to run elections online

• Imagine you are a programmer for the Australian Electoral Commission, and you have been asked
to automate the counting of electronic votes. Can you write programs to automate vote counting for
different voting schemes?

Background

We consider an election where multiple candidates are running to be the representative of a given el
ectorate.Each voter lodges their vote for their preferred candidate(s).The candidate with the most vot
es wins the electorate.
• Example of a simple voting scheme Candidates: “chris”, “marion”, “nic”

Number of votes for each candidate:
“chris” : 121, “marion” : 399, “nic” : 180
Winning candidate: “marion”

Background

A major challenge in voting schemes is how to reflect the preferences of voters, so that the winning c
andidate has the support of the majority i.e. ideally > 50% of the votes.
We will consider three different voting schemes:

• First past the post (used in the UK, US, Survivor)
• Second preference
• Multiple preferences (used in Australia)

First Past the Post

• This is the simplest voting scheme.
• There is a given list of candidates.
• Each voter picks their preferred candidate.
• We count the number of votes for each candidate.
• The candidate with the most votes wins.
• Example of a simple voting scheme

Candidates: “chris”, “marion”, “nic”
Number of votes for each candidate:
“chris” : 121, “marion” : 399, “nic” : 180
Winning candidate: “marion”

First Past the Post

• Example of a simple voting scheme

Candidates: “chris”, “marion”, “nic”
Consider an electorate with 9 voters
List of votes:[“chris”, “marion”, “marion”, “nic”, “marion”, “nic”, “nic”, “chris”, “marion”]
Number of votes for each candidate:“chris” : 2, “marion” : 4, “nic” : 3
Winning candidate: “marion”

• Note: winner might not have an absolute majority.i.e., less than 50% of the electorate voted for the winner
• Note: an election can result in a tie, where two or more candidates have the highest number of votes

Candidates: “chris”, “marion”, “nic”
Consider an electorate with 9 voters
Votes:[“chris”, “nic”, “marion”, “nic”, “chris”, “nic”, “nic”, “chris”, “chris”]
Number of votes for each candidate:“chris” : 4, “marion” : 1, “nic” : 4
Winning candidate: “tie”

Question 1

You need to write a function that returns the outcome of an election for a given list of votes using the First Pa
st the Post voting scheme. Note: your function should use either a for loop or a while loop to count the votes.
first_past_the_post(votes)
votes: list of two or more strings, where each string corresponds to a vote for the candidate whose name is in
the string.Returns a string containing either the name of the candidate with the most votes using First Past th
e Post voting, or the string “tie” if there is a tie.
You can assume that there is no candidate with the name “tie”.

Example:

v1 = [“chris”, “marion”, “marion”, “nic”, “marion”, “nic”,“nic”, “chris”, “marion”]
first_past_the_post(v1)
returns “marion”

v2 = [“chris”, “nic”, “marion”, “nic”, “chris”, “nic”, “nic”,“chris”, “chris”]
first_past_the_post(v2)
returns “tie”

Second Preference

• A drawback of First Past the Post voting is that the winning candidate might not have the majority support
of the voters.
• For example, in the first set of votes the majority of voters did not vote for “marion”.
• Those voters for the losing candidates “nic” and “chris” might have preferred the other losing candidates ahea
d of the winner “marion”.
• For example, if the voters for “chris” preferred “nic” ahead of “marion”, and the voters for “nic” preferred “chris”
ahead of “marion”, then either “chris” or “nic” might be a better consensus winner with the majority of voters.
• An alternative voting scheme is to give each voter a second preference.
• Each voter gives their first preference candidate and their second preference candidate in their vote, i.e., they
pick two candidates in order of decreasing preference.
• We then count the votes for each candidate using the first preference votes (in the same way we would for Fir
st Past the Post), to see if there is a candidate with an absolute majority of the votes. If there is a candidate with >
50% of the first preference votes, then that candidate is the winner.
• If there is no candidate with an absolute majority based on the first preference votes, then we look at the second
preference votes. We find the candidate with the fewest number of first preference votes (the lowest vote candida
te). We then look at the second preferences of the votes for that candidate, and reallocate those votes to remaining candidates. The winner is the candidate with the most votes after the reallocation of the second preferences from
lowest vote candidate are added to the first preference votes for the other candidates.
• If there are two or more lowest vote candidates with an equal number of first preference votes, reallocate the can
didate whose name is lower than the other name if you compare the two names.
• Note: a candidate might receive no first preference votes but many second preference votes.

Candidates: “chris”, “marion”, “nic”
Consider an electorate with 9 voters
Votes:[[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”], [“nic”, “chris”],[“marion”, “nic”], [“nic”, ”chris”], [“nic”, “chris”], [“chris”, “nic”], [“marion”,“nic”]]
Number of votes for each candidate based on first preferences:“chris” : 2, “marion” : 4, “nic” : 3

No candidate with an absolute majority, “chris” has fewest first preferences.Reallocate second preferences from vot
es for “chris” to add to first preference votes for other candidates

“marion” : 4 + 0, “nic” : 3 + 2
Winning candidate: “nic”

Candidates: “chris”, “marion”, “nic”
Consider an electorate with 6 voters
Votes:[[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”], [“nic”, “chris”],[“chris”, “marion”], [“nic”, ”chris]]
Number of votes for each candidate based on first preferences:“chris” : 2, “marion” : 2, “nic” : 2

No candidate with an absolute majority, all candidates have same number of first preferences.Since “chris” < “marion”
< “nic”, reallocate second preferences from votes for “chris” to add to first preference votes for other candidates

“marion” : 2 + 1, “nic” : 2 + 1
Winning candidate: “tie”

Note:
– There is only one round of preference allocation in this scheme – from the candidate with the fewest number of votes.
– This method is still not guaranteed to result in a winner with an absolute majority of support.

You need to write a function that returns the outcome of an election for a given list of votes using the Second Preferenc
e voting scheme.second_preference(votes) votes: list of votes, where each vote is a list that contains two strings,
such that the first string is the name of the first preference candidate and the second string is the name of that second preference candidate for that vote.Returns a string containing either the name of the candidate with the most votes using Second Preference voting, or the string “tie” if there is a tie.You can assume that there is no candidate with the name “tie”
, and that all votes contain two preferences, and that the two preferences are different, i.e., [“chris”, “chris”] will not appea
r as a vote in this question.

Example:

v1 = [[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”],[“nic”, “chris”], [“marion”, “nic”], [“nic”, ”chris”], [“nic”,“chris”], [“chris”, “nic”], [“marion”, “nic”]]
second_preference(v1)
returns “nic”

v2 = [[“chris”, “nic”], [“marion”, “nic”], [“marion”, “chris”],[“nic”, “chris”], [“chris”, “marion”], [“nic”, ”chris]]
second_preference(v2)
returns “tie”

Example:

v3 = [[“chris”, “mini”], [“marion”, “nic”], [“marion”,“chris”], [“nic”, “chris”], [“marion”, “nic”], [“nic”,”chris”], [“nic”, “chris”], [“chris”, “mini”], [“marion”,“nic”]]
second_preference(v3)
returns “marion” 

Multiple Preferences
• Note that Second Preference voting does not always ensure that the winning candidate has the majority support of the voter
s (see the third example for Q2).
• Our third voting scheme called Multiple Preferences requires each voter to list all candidates in decreasing order of preference.
• In this case, we can apply multiple rounds of reallocation,where each time we reallocate the remaining preferences of the candidate with the lowest number of votes so far to the other candidates. We keep doing this until one candidate has an absolute majority, or there are only two candidates left.
• As before, if there are two or more lowest vote candidates with an equal number of allocated votes,then reallocate the candidate whose name is lower than the other name if you compare their names.
• Note that when reallocating a vote, the next preference may no longer be available if that candidate has already been reallocated, and so we go straight to the following preference (see below).

Candidates: “a”, “b”, “c”, “d”, “e”
Consider an electorate with 5 voters
Votes:[[“a”, “b”, “c”, “d”, “e”], [“b”, “e”, “d”, “c”, “a”], [“c”, “d”, “e”, “b”, “a”],[“d”, “b”, “a”, “c”, “e”], [“e”, “a”, “c”, “b”, “d”]]
Number of votes for each candidate based on first preferences:“a” : 1, “b” : 1, “c” : 1, “d” : 1, “e” : 1

No candidate has an absolute majority. Among the equal lowest candidates “a” has the name that is first in sorted order
Reallocate vote for “a” to the next preference candidate:
“b” [“b”, “e”, “d”, “c”, “a”], [“b”, “c”, “d”, “e”] – from “a”
“c” [“c”, “d”, “e”, “b”, “a”]
“d” [“d”, “b”, “a”, “c”, “e”]
“e” [“e”, “a”, “c”, “b”, “d”]

No candidate has an absolute majority. Among the equal lowest candidates
(“c”, “d”, “e”), “c” has the name that is first in sorted order.
Reallocate vote for “c” to the next preference candidate:
“b” [“b”, “e”, “d”, “c”, “a”], [“b”, “c”, “d”, “e”]
“d” [“d”, “b”, “a”, “c”, “e”], [“d”, “e”, “b”, “a”] – from “c”
“e” [“e”, “a”, “c”, “b”, “d”]
No candidate has an absolute majority. “e” is the candidate with the fewest
votes.
Reallocate vote for “e” to the next preference candidate (note: both “a” and
“c” have already been eliminated, so the next preference from “e” is “b”:
“b” [“b”, “e”, “d”, “c”, “a”], [“b”, “c”, “d”, “e”], [“b”, “d”]
“d” [“d”, “b”, “a”, “c”, “e”], [“d”, “e”, “b”, “a”]
Candidate “b” has an absolute majority and wins the election!

Here is another example
Votes:
[[“b”, “c”, “a”], [“c”, “b”, “a”]]
Number of votes for each candidate based on first preferences:
“a” : 0, “b” : 1, “c” : 1
No candidate has an absolute majority. Among the equal lowest candidates
“a” has the name that is first in sorted order
As there are no votes for a, we have no preferences to allocate,
and a is eliminated.
That leaves two candidates b and c, and we terminate with a tie.
*
Question 3*

You need to write a function that returns the outcome of an election for a given list of votes using the Multiple Preferences voting scheme.

multiple_preferences(votes)

votes: list of votes, where each vote is a list of strings corresponding to the candidates in decreasing order of preference.
Returns a string containing either the name of the candidate with the most votes using Multiple Preferences voting, or the string “tie” if there is a tie.
You can assume that there is no candidate with the name “tie”, that each vote contains all candidates, and that each candi
date appears only once in each vote.

Example:

v1 = [[“a”, “b”, “c”, “d”, “e”], [“b”, “e”, “d”, “c”, “a”],[“c”, “d”, “e”, “b”, “a”], [“d”, “b”, “a”, “c”, “e”],[“e”, “a”, “c”, “b”, “d”]]
multiple_preferences(v1)
returns “b” 

Example:

v2 = [[“a”, “b”, “c”, “d”, “e”], [“b”, “e”, “d”, “c”, “a”],[“c”, “d”, “e”, “b”, “a”], [“d”, “b”, “a”, “c”, “e”],[“d”, “a”, “b”, “c”, “e”], [“e”, “a”, “c”, “b”, “d”]]
multiple_preferences(v2)
returns “tie” 

Valid Votes
Before votes are counted in a real election, we need to make sure that a vote is valid, i.e., it does not contain any mistakes.
We will focus on checking whether a given vote is valid for Multiple Preferences voting.
Consider an electorate with 5 candidates [“a”, “b”, “c”, “d”, “e”]
[“b”, “e”, “d”, “c”, “a”] is a valid vote
[“d”, “b”, “a”, “c”] is not a valid vote in this electorate
[“d”, “g”, “b”, “a”, “c”] is not a valid vote in this electorate

You need to write a function that returns True if the given vote is valid for the given list of candidates using the Multiple Preferences voting scheme.
is_valid_vote(vote, candidates)
vote: a vote to be validated (could have incorrect syntax for a Multiple Preferences vote) candidates: a list of unique strings corresponding to the candidates.Returns a Boolean value True if the given vote is valid for the given list of candidates, or F
alse otherwise.
You can assume that the given list of candidates is correctly formatted
and does not contain any errors. You should use the specification of
votes for Multiple Preferences voting as described in Question 3.

Example:

c = [“tom1”, “li”, “tom2”]
is_valid_vote([“tom2, “tom1”, “li”], c)
returns True
is_valid_vote([“tom2”, “tom2”, “li”], c)
returns False
is_valid_vote(“tom2”, c)
returns False

Academic Honesty

• All assessment items (worksheets, projects, test and exam)
must be your own, individual, original work.
• Any code that is submitted for assessment will be
automatically compared against other students’ code and
other code sources using sophisticated similarity checking
software
• Cases of potential copying or submitting code that is not your
own may lead to a formal academic misconduct hearing.
• Potential penalties can include getting zero for the project,
failing the subject, or even expulsion from the university in
severe cases.
• For further information, please see the university’s Academic
Honesty and Plagiarism website, or ask your lecturer.
Academic Honesty
The fastest way to fail the subject is to
hand in code that is not your own!!!
Academic Honesty
For example:
• you must not copy the code of other students
• you must not make your code available to others to see
• do not give other students your login id and password
• do not share USB memory drives
• do not post your code on public forums, or any other activity
that would make your code available to others
• do not ask other students to see their code
• do not submit code that has been written by someone else
If other students ask to see your code, please say “no”, as
copying (collusion or plagiarism) is considered academic
misconduct, and all students involved may face penalties (both
the student who copied, and the student who made their code
available).
Conclusion
• The project questions will be submitted via Grok.
• The project will be made available in Grok shortly after
today’s lecture (in a day or so).
• You can submit as many times as you like to Grok. We will
mark the last version you submit before the deadline. Submit
early and often! Even when your code is incomplete.
• We mark your last submission made before the deadline.
• The specification of the project questions and the deadline
will be announced very soon in Grok.
• This project is worth 15% of the final subject.
• We will be marking the correctness, quality, readability and
commenting of your code.
• The deadline (to be confirmed in Grok) will be 23:59 Thursday
12 September 2019.



51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468