【CS50x】Runoff 题解(上)

简介: 【CS50x】Runoff 题解(上)

前言



CS50x 是哈佛大学推出的一门知名公开课,本课程是一门计算机科学的导论课程,适合于对计算机科学感兴趣的任何人学习,不需要任何基础。通过学习本课程有助于对计算机科学的体系建立一个基本的概念,其学习内容如下:


image.png

Runoff



昨天我们更新了【CS50x】Plurality 题解,Plurality 是我们平时最常使用的投票排名系统,也被称为“得票最多者当选”或者”赢家通吃“的方法,就是每个选民只能投票给一个候选人,在选举结束时,获得最多选票的候选人会成为选举的胜利者。

但这种方法局限性非常大,就比如下面这种三个候选人的情况怎么选:


image.png


Alice 和 Bob 各有两张选票,我们难道要宣布两个赢家吗?所以就牵扯到今天我们要使用的 Runoff 投票系统,在该系统中,选民可以投票给多个候选人,可以根据喜欢偏好来对候选人进行排名,而不是仅仅投票给他们最喜欢的候选人,由此产生的选票如下所示:


image.png


这样做会使以前平分秋色的选举可能产生一个赢家,Alice 和 Bob 刚开始票数相同,Charlie 出局,发现选择 Charlie 的投票者更喜欢 Alice,所以可以宣布获胜者为 Alice。


但是还有一种情况:


image.png


这种情况下,Charlie 4票,Bob 3票,Alice 2票,但是上面五个人都是喜欢 Alice,Bob 大于 Charlie,所以我们必须加上一条规则:只有候选人获得超过50%的选票才可以获得胜利,如果没有人超过50%,就发生“即时决选”,将得票最少的候选人淘汰出局,原先原先选择该候选人作为第一选择的任何人现在都将考虑他们的第二选择。


如果没有一个候选人获得多数选票,那么最后一个候选人就会被淘汰,任何投票给他们的人都会转而投票给他们的下一个候选人(如果还没有被淘汰)。一旦一个候选人获得多数票,那个候选人就被宣布为胜利者。


但是如果剩下的候选人拥有一样的票数,那么意味着我们需要淘汰所有人,所以我们必须考虑这个边界情况。


总结



  • 读取候选人信息
  • 得到未淘汰的候选人的票数,总结为偏好数组
  • 判断是否有胜者产生
  • 找到最小值
  • 判断是否为平局
  • 淘汰票数最少的候选人
目录
相关文章
|
算法
【CS50x】 Tideman 题解(上)
【CS50x】 Tideman 题解(上)
1008 0
【CS50x】 Tideman 题解(上)
|
监控 Shell Linux
【Shell 命令集合 系统管理 】⭐⭐⭐Linux 向进程发送信号 kill命令 使用指南
【Shell 命令集合 系统管理 】⭐⭐⭐Linux 向进程发送信号 kill命令 使用指南
294 0
|
8月前
|
消息中间件 运维 Cloud Native
UU 跑腿云原生化,突围同城配送赛道
UU跑腿自2015年上线以来,已覆盖全国200余座城市,拥有超过850万“跑男”,成为同城即时生活服务行业的头部企业。面对激烈竞争,UU跑腿通过创新获客方式和数字化业务平台建设,实现了波浪式用户增长。为应对快速增长的业务需求,UU跑腿积极推进云原生化,优化IT基础设施,实现了80%的微服务无缝迁移、1分钟内弹性伸缩、80%的运维成本降低及80%的变更稳定性提升,显著提高了系统的稳定性和效率,成为行业内的黑马。
364 16
|
11月前
|
监控 数据可视化 项目管理
关键链项目管理是什么?它如何优化传统项目管理?
关键链项目管理(CCPM)由艾利·高德拉特提出,通过优化资源分配和减少多任务并行的浪费,显著提高项目执行效率与成功率。本文介绍CCPM的核心理念、与传统项目管理的区别及优势,并推荐几款支持CCPM的项目管理软件,如ProChain、板栗看板等,帮助企业更好地实施这一高效管理方法。
539 0
|
Java API 数据库
thymeleaf 中 通用的分页方法
thymeleaf 中 通用的分页方法
190 0
|
监控 程序员 开发工具
如何规范Git提交-参考阿里云开发者社区
这篇文章分享了如何规范Git提交,介绍了commit message的格式规范,并通过webhook监控机制来确保代码提交的规范性,从而提高研发效率和代码维护质量。
|
SQL 关系型数据库 MySQL
923.【mysql】 only full group by 模式
923.【mysql】 only full group by 模式
514 1
|
Web App开发 存储 移动开发
Uncaught (in promise) DOMException: The play() request was interrupted by a new load request.异常处理
Uncaught (in promise) DOMException: The play() request was interrupted by a new load request.异常处理
1457 0
|
编译器 C语言 C++
CMake基础(9)使用Clang编译
CMake基础(9)使用Clang编译
1175 0
【CS50x】 Tideman 题解(下)
【CS50x】 Tideman 题解(下)
1131 0
【CS50x】 Tideman 题解(下)