程序员的数学基础课
黄申
LinkedIn 资深数据科学家
82496 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 58 讲
导读 (1讲)
基础思想篇 (18讲)
程序员的数学基础课
15
15
1.0x
00:00/00:00
登录|注册

08 | 组合:如何让计算机安排世界杯的赛程?

你好,我是黄申。
2018 年足球世界杯结束有半年了,当时激烈的赛况你现在还记忆犹新吧?你知道这场足球盛宴的比赛日程是怎么安排的吗?如果现在你是组委会,你会怎么安排比赛日程呢?我们可以用上一节的排列思想,让全部的 32 支入围球队都和其他球队进行一次主客场的比赛。
自己不可能和自己比赛,因此在这种不可重复的排列中,主场球队有 32 种选择,而客场球队有 31 种选择。那么一共要进行多少场比赛呢?很简单,就是 32x31=992 场!这也太夸张了吧?一天看 2 场,也要 1 年多才能看完!即使球迷开心了,可是每队球员要踢主客场共 62 场,早已累趴下了。
好吧,既然这样,我们是否可以取消主客场制,让任意两个球队之间只要踢 1 场就好啦?取消主客场,这就意味着原来两队之间的比赛由 2 场降为 1 场,那么所有比赛场次就是 992/2=496 场。还是很多,对吧?
是的,这就是为什么要将所有 32 支队伍分成 8 个小组先进行小组赛的原因。一旦分成小组,每个小组的赛事就是 (4x3)/2=6 场。所有小组赛就是 6x8=48 场。
再加上在 16 强阶段开始采取淘汰制,两两淘汰,所以需要 8+4+2+2=16 场淘汰赛(最后一次加 2 是因为还有 3、4 名的决赛),那么整个世界杯决赛阶段就是 48+16=64 场比赛。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《程序员的数学基础课》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(61)

  • 最新
  • 精选
  • 罗耀龙@坐忘
    茶艺师学编程 可以这么记: 排列—大家走到一块,还要比个高低 组合—大家聚到一起,就是有缘 生活中的一个例子,比如婚姻,就应该是组合,“我和你一起,怎么都好”,而不是“排列”,“你,都得听我的!”

    作者回复: 关于婚姻的点,要点赞👍

    2
    29
  • 风轨
    从100人中选10人得3等奖,C(100, 10) = 17310309456440 再从剩下90人中选3人的3等奖,C(90, 3) = 117480 再从剩下87人中选1人得1等奖, C(87, 1) = 87 总共有大约有1.8×10^20种可能性, 假设我们的计算机每1ns就能输出1个结果,全部输出来大约要5610年! 假设每个结果占13个字节,把结果保存下来大约要占1995EB,远远大于世界上存储总容量! 当数据量比较小时,还是可以算的: public class Combination { /** * 求组合数 * * @param n * @param r * @return */ static int c(int n, int r) { if (r > n) { return 0; } int R = n - r; int ret = 1; while (n > R) { ret *= n--; } while (r > 1) { ret /= r--; } return ret; } /** * 求组合情况 * @param es * @param r * @param I 数组es开始取数位置 * @return */ static int[][] C(int[] es, int r, int I) { int[][] rst = new int[c(es.length - I, r)][]; if (r == 1) { for (int rsti = 0; rsti < rst.length; rsti++, I++) { rst[rsti] = new int[] { es[I] }; } } else { for (int rsti = 0; I < es.length; I++) { int[][] srst = C(es, r - 1, I + 1); for (int[] sc : srst) { int[] t = rst[rsti] = new int[sc.length + 1]; t[0] = es[I]; System.arraycopy(sc, 0, t, 1, sc.length); rsti++; } } } return rst; } public static void main(String[] args) { int[][] c = C(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, 3, 0); for (int[] cc : c) { System.out.println(Arrays.toString(cc)); } /** * 输出结果 * [1, 2, 3] * [1, 2, 4] * [1, 2, 5] * [1, 2, 6] * ··· 省略111行 ··· * [6, 9, 10] * [7, 8, 9] * [7, 8, 10] * [7, 9, 10] * [8, 9, 10] * */ } }

    作者回复: 确实数字取得太大了

    4
    21
  • 夏微凉
    黄老师,我这几天一直在纠结思考题,总共10人,一等名1名,二等奖2名,三等3名,还是没有完全理解思路,希望老师方便的时候解答下

    作者回复: 这道题是用到了组合及排列,先看100个人里取1人的数量是C100,1 (格式问题,C100,1表示从100人里取1人的组合数量),剩下99人里取2人为C99,2,再剩下97人里取3人为C97,3,然后再利用排列,总共可能为C100,1 x C99,2 x C97,3

    5
    6
  • Ball
    用组合思想来处理多元词组的问题确实妙

    作者回复: 数学思维很重要,多多学习和运用,你会发现更多妙用

    3
  • 天涯不是咫尺
    老师,为什么主场球队有32种选择,客场球队只有31种选择?

    作者回复: 因为自己不会和自己踢,所以选定主场球队之后,客场就只有31种选择。同样,如果先选择客场,那么也有32种选择,但是主场就只有31种了

    3
  • 文刂 氵共 超
    使用C++实现组合问题-从n个数中取出m个不同的元素,不考虑顺序 #include <iostream> #include <vector> using namespace std; template <class T> void PrintVector(vector<T> & DataVec) { for (size_t i = 0; i < DataVec.size(); ++i) { cout << DataVec[i] << " "; } cout << endl; } template <class T> void Combination(vector<T> &DataVec, int m, vector<T> &resultVec) { if (m <= 0 && m > DataVec.size()) { return; } if (resultVec.size() == m) { PrintVector(resultVec); return; } for (size_t i = 0; i < DataVec.size(); ++i) { vector<T> tempResultVec = resultVec; tempResultVec.push_back(DataVec[i]); vector<T> tempDataVec(DataVec.begin()+i+1, DataVec.end()); Combination(tempDataVec, m, tempResultVec); } } int _tmain(int argc, _TCHAR* argv[]) { vector<int> resultV; int dataList[] = {2,6,8,23,78,45,32,64}; vector<int> dataV(dataList, dataList+8); Combination(dataV, 5, resultV); PrintVector(resultV); return 0; }

    作者回复: 使用栈来实现递归过程的想法很棒

    2
  • Geek_c23a4c
    连锁店的销售业绩报表的例子不是太理解。意思是分店名称、所在城市、销售品类三个维度做组合来对不同的维度的组合进行统计吗?这个和上面多元文法的应用比起来没啥意思,感觉脱节了

    作者回复: 对,这里举出组合可能的不同应用场景,多元文法和销售维度没有联系

    1
  • DFighting
    组合是不考虑顺序的排列,但是应用的时候需要存储数据,存储的势必只是某种组合的某种排列方式,这时候就需要一个标准化的流程来保证同一种组合的不同排列都可以转换成标准的排列已完成程序的存储,检索和比对

    作者回复: 很好的总结

  • 吾颜六涩
    看到了组合的实用性

    作者回复: 很高兴对你有价值

  • test
    多元文法的解法存在一个问题,用户的输入会有单词间前后顺序不同造成的语意上下文不同。

    作者回复: 是的

收起评论
显示
设置
留言
61
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部