程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

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

黄申 2018-12-31
你好,我是黄申。
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/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(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]
             *
             */
        }
    }

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

    2018-12-31
    1
    9
  • 行者
    案例python实现:

    comb = ['t1', 't2', 't3', 't4', 't5']
    import copy

    def combination(n, comb, result):

        if n == 0:
            print(result)
            return
        for i in comb:
            newResult = copy.copy(result)
            newComb = copy.copy(comb)
            newResult.append(i)
            newComb = list(set(newComb).difference(set(comb[:comb.index(i) + 1])))
            combination(n - 1, newComb, newResult)

    combination(4, comb, [])
    2019-01-02
    5
  • Wing·三金
    思路一:
    先运行combine(100, 1),将所有结果保存。然后用一层迭代对每个结果运行combine(99, 3),将所有结果append进去。
    然后再来一层迭代对上一结果运行combine(96, 10),同样依次append进去。
    此处的关键点在于每个迭代下得将上一结果中的数拿掉,以及得保存临时结果。

    此思路也等价于直接上三个嵌套循环+运行递归程序。

    思路二:
    先运行combine(100, 14),对每个结果运行combine(14, 10),再对每个更新的结果运行combine(4, 3)。其实就是思路一逆过来。

    理论上二者的复杂度是一样的,用scipy验证了下确实如此。
    2018-12-31
    5
  • Ricky
    #include <iostream>
    #include <vector>

    using namespace std;
    void winPrize(int f, int s, int t,
            vector<int> &first, vector<int> &second, vector<int> &third, vector<int> &base) {

        if (first.size() == f && second.size() == s && third.size() == t) {
            cout << "\nAwards Notification" << endl;
            cout << "Prize 1: " << first.back() << endl;
            cout << "Prize 2: ";
            for (int x: second) {
                cout << x << " ";
            }
            cout << endl;
            cout << "Prize 3: ";
            for (int y: third) {
                cout << y << " ";
            }
            cout << endl;
            return;
        }
        for (int x: base) {
            // 每次仅添加一个成员进奖项圈, 优先级按照一等奖 > 二等奖 > 三等奖
            auto f1 = first, s1 = second, t1 = third, left = base;
            if (first.size() < f) {
                f1.push_back(x);
            } else if (second.size() < s) {
                s1.push_back(x);
            } else if (third.size() < t) {
                t1.push_back(x);
            }
            // 删除成员
            auto iter = left.begin();
            while (iter != left.end()) {
                if (*iter == x) {
                    iter = left.erase(iter);
                } else iter++;
            }
            winPrize(f, s, t, f1, s1, t1, left);
        }
    }

    void winPrize(int tl, int f, int s, int t) {
        vector<int> first, second, third, base;
        for (int i = 0; i < tl; ++i) {
            base.push_back(i);
        }

        winPrize(f, s, t, first, second, third, base);
    }
    int main() {
        cout << "Prize Result" << endl;
        winPrize(10, 1, 2, 3);
        return 0;
    }
    ******************结果********************
    Awards Notification
    Prize 1: 2
    Prize 2: 0 6
    Prize 3: 8 3 1

    Awards Notification
    Prize 1: 2
    Prize 2: 0 6
    Prize 3: 8 3 4

    Awards Notification
    Prize 1: 2
    Prize 2: 0 6
    Prize 3: 8 3 5

    Awards Notification
    Prize 1: 2
    Prize 2: 0 6
    Prize 3: 8 3 7
    2019-01-10
    4
  • qinggeouye
    python (比较粗暴的解法...)
    import copy

    def lucky_draw_combination(n, m, result=None, all_results=None):
        """
        使用函数的递归(嵌套)调用,找出所有可能的中奖者的组合
        :param all_results: 中奖者的所有组合
        :param n: 参与抽奖的人
        :param result: 抽奖结果
        :param m: 中奖的人数
        :return: None
        """
        if result is None:
            result = []
        if all_results is None:
            all_results = []
        if len(result) == m:
            # print(result)
            return all_results.append(result)
        for i in range(len(n)):
            # 从剩下的人中,抽出一个人加入结果
            new_result = copy.copy(result)
            new_result.append(n[i])
            # 每人最多只能被抽中一次,当前被抽中的人之后的人,进入下一次抽奖
            rest_n = n[i + 1: len(n)]
            # 递归调用 在剩下的人中继续抽奖
            lucky_draw_combination(rest_n, m, new_result, all_results)
        return all_results


    if __name__ == "__main__":
        total = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 被抽奖人列表
        m_ = [3, 2, 1] # 三等奖、二等奖、一等奖的个数
        lucky1 = lucky_draw_combination(total, m_[0])
        for k1 in lucky1:
            total2 = copy.copy(total)
            for j1 in k1:
                total2.remove(j1)
            lucky2 = lucky_draw_combination(total2, m_[1])
            for k2 in lucky2:
                total3 = copy.copy(total2)
                for j2 in k2:
                    total3.remove(j2)
                lucky3 = lucky_draw_combination(total3, m_[2])
                for k3 in lucky3:
                    print(k1, k2, k3)
    2019-02-10
    3
  • Paul Shan
    总结
    排列的递归公式是P(n,m) = nP(n-1,m-1)
    可以按照这条公式组织递归,也就是一次n的循环(放入第i号元素)调用P(n-1,m-1)

    组合的递归公式是C(n,m) = C(n-1,m-1) +C(n-1,m)
    可以按照这条公式(放入或者不放入第0号元素)递归调用
    2019-08-21
    1
  • flow
    // JavaScript实现
    var arr = [1, 2, 3, 4, 5, 6];

    function genGroup(arr, result, count) {
      if (result.length === count) {
        console.log(result);
        return;
      }

      for (let i = 0; i < arr.length; i++) {
        let new_arr = [...arr];
        let new_result = [...result];
        new_result.push(arr[i]);
        new_arr.splice(0, i + 1);
        genGroup(new_arr, new_result, count);
      }
    }

    genGroup(arr, [], 3);
    // 思考题也是同理, 100人取14个, 第1个为一等奖, 2-4为二等奖, 5-14为三等奖
    2019-04-16
    1
  • 夏微凉
    黄老师,我这几天一直在纠结思考题,总共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

    2019-01-14
    1
  • 文刂 氵共 超
    使用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;
    }

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

    2019-01-04
    1
  • Youngggg
    由于数量过大 设置10个人中 1等奖1名 2等奖2名 3等奖3名
    import copy
    word = []
    for i in range(1,11):
        word.append(i)
    def sort(one_num, two_num, three_num, one_result=[], two_result=[], three_result=[]):
        if len(one_result) == one_num and len(two_result) == two_num and len(three_result) == three_num:
            print("一等奖", one_result)
            print("二等奖", two_result)
            print("三等奖", three_result)
            return
        else:
            i = 0
            while i < len(word):
                if word[i] not in one_result and len(one_result) < one_num:
                    if len(one_result)>0:
                        if one_result[-1] > word[i]:
                            i = i+1
                            continue
                    new_one_result = copy.copy(one_result)
                    new_one_result.append(word[i])
                    i = i+1
                    sort(one_num, two_num, three_num, new_one_result, [], [])
                elif word[i] not in one_result and word[i] not in two_result and len(two_result) < two_num:
                    if len(two_result)>0:
                        if two_result[-1] > word[i]:
                            i = i + 1
                            continue
                    new_two_result = copy.copy(two_result)
                    new_two_result.append(word[i])
                    i = i+1
                    sort(one_num, two_num, three_num, one_result, new_two_result, [])
                elif word[i] not in one_result and word[i] not in two_result and word[i] not in three_result and len(three_result) < three_num:
                    if len(three_result)>0:
                        if three_result[-1] > word[i]:
                            i = i+1
                            continue
                    new_three_result = copy.copy(three_result)
                    new_three_result.append(word[i])
                    i = i+1
                    sort(one_num, two_num, three_num, one_result, two_result, new_three_result)
                else:
                    i = i+1
                    continue
    sort(1, 2, 3, [], [], [])
    运行结果:
    一等奖 [1]
    二等奖 [2, 3]
    三等奖 [4, 5, 6]
    .....
    2019-01-02
    1
  • teddytyy
    100!/(90!*10!) * 90!/(87!*3!) * 87
    2019-12-05
  • aoe
    原来组合这么强大!
    2019-11-30
  • 顾骨
    // decrease decreate []int{3,2,1} to []int{0,0,0} gradually
    func decrease(c []int) {
    for i := range c {
    if 0 != c[i] {
    c[i]--
    break
    }
    }
    }

    // delElement delete target element from c
    func delElement(c []string, target string) []string {
    var newc []string
    for i := range c {
    if target == c[i] {
    newc = append(newc, c[0:i]...)
    newc = append(newc, c[i+1:]...)
    return newc
    }
    }
    return nil
    }

    // in a total of 10 person, the number of third prize is 3,
    // the number of second prize is 2,the number of first prize is 1,
    // combinations=120*21*5=12600
    //
    // prize format: int[3,2,1], it means the number of third prize is 3,the number of second prize is 2,the number of first prize is 1
    func lottery(origin, rest, result []string, prize []int) {
    // it means that the third prize is over, go to the second prize and so on
    if 0 == prize[0] {
    origin = rest
    prize = prize[1:]
    }

    // it means lottery game is over, print result
    if 0 == len(prize) {
    fmt.Println(result)
    return
    }

    for i := range origin {
    var newResult []string
    newResult = append(newResult, result...) // copy result
    newResult = append(newResult, origin[i])

    var newRest []string
    newRest = delElement(rest, origin[i])

    var newPrize []int
    newPrize = append(newPrize, prize...)
    decrease(newPrize)

    lottery(origin[i+1:], newRest, newResult, newPrize)
    }
    }

    func main() {
    in := []string{"m0", "m1", "m2", "m3", "m4"}
    lottery(in, in, []string{}, []int{2, 1, 1}) //output: 60
    fmt.Println("-------------------------")
    in = []string{"m0", "m1", "m2", "m3", "m4", "m5", "m6", "m6", "m8", "m9"}
    lottery(in, in, []string{}, []int{3, 2, 1}) //output: 12600
    }
    2019-11-15
  • 建强
    简单地用Python写了一程序,由于组合的数量太多,程序中加了适当的限制
    import copy
    '''
    参数说明:
    all_person: 全体人员列表
    sel_person: 可选人员列表
    award_rank: 当前正在抽奖的等级
    award_result: 各奖项的人员列表
    award_psn_num:各奖项的人数列表
    '''
    def assemble(all_person,sel_person,award_rank,award_result,award_psn_num):
        global schema_num
        global schema_limit

        #超出组合限制,则不再作组合运算
        if schema_limit > 0 and schema_num > schema_limit:
            return

        #输出结果
        if sum(award_psn_num) == 0:
            schema_num += 1
            print('-'*10,'方案'+ str(schema_num), '-'*10)
            for i in range(len(award_result)):
                print('{}等奖:{}'.format(i+1,','.join(award_result[i])))
            print('-'*30)
            print()
            return

        #挑选当前奖项的人员
        i = award_rank - 1

        if i>= 0 and award_psn_num[i] > 0:
            new_award_psn_num = award_psn_num.copy()
            new_award_psn_num[i] -= 1
            for j in range(len(sel_person)):
                new_award_result = copy.deepcopy(award_result)
                new_award_result[i].append(sel_person[j])
                new_sel_person = sel_person[j+1:].copy()
                assemble(all_person, new_sel_person, award_rank, new_award_result, new_award_psn_num)
        else:
            #初始化下一奖项的可选人员
            if i > 0 and len(award_result[i-1]) == 0:
                new_sel_person = all_person.copy()

                award_psn = []
                for result in award_result:
                    award_psn += result

                for psn in award_psn:
                    new_sel_person.remove(psn)
            
                #抽取下一奖项人员
                assemble(all_person, new_sel_person, award_rank-1, award_result, award_psn_num)
               
    def main():
        person_num = 100 #总人数
        award3_num = 10 #三等奖人数
        award2_num = 3 #二等奖人数
        award1_num = 1 #一等奖人数
        person_list = ['P' + str(i) for i in range(person_num)]
        assemble(person_list, person_list.copy(), 3, [[], [], []], [award1_num, award2_num, award3_num])

    if __name__ == '__main__':
        schema_num = 0
        schema_limit = 10 #限制组合的次数
        main()
    2019-10-27
  • monalisali
    老师那个 “red bluetooth mouse” 真是大开眼界了! 其实把数学思维对应到程序解决方案这个过程才是最难的,就像程序员要把现实世界的问题抽象成代码一样。

    作者回复: 很高兴对你有所帮助!

    2019-10-23
  • 丁丁历险记
    讲个段子
    淘汰赛 14只球队输一场,第四名输两场。
    刚好16场。
    2019-10-09
  • Paul Shan
    思考题
    C(100,14) C(14,10)C(4,3)种可能性
    2019-08-20
  • C语言 递归实现组合

    #include <stdio.h>

    //记录项的定义
    typedef struct record_type {
    int data;
    } RecordType;

    #define MAX_NBR 100


    static void visit(RecordType r[], int s[], int n)
    {
    int i;

    for (i = 0; i < n - 1; i++)
    printf("%d, ", r[s[i]].data);
    printf("%d\n", r[s[i]].data);
    }


    // s 和 rest 数组,存的是索引
    void recursion(RecordType r[], int s[], int n, int rest[], int m, int num)
    {
    if (n < num)
    {
    int i, j;
    int rest2[MAX_NBR];

    for (i = 0; i < m; i++)
    {
    s[n] = rest[i];
    for (j = 0; j < m-i-1; j++)
    rest2[j] = rest[i+1+j];

    recursion(r, s, n + 1, rest2, m-i-1, num);
    }
    }
    else
    {
    visit(r, s, n);
    }
    }

    void combination(RecordType r[], int len, int num)
    {
    int n, m;
    int s[MAX_NBR], rest[MAX_NBR];

    n = 0;
    m = len;
    for (int i = 0; i < len; i++)
    rest[i] = i;

    recursion(r, s, n, rest, m, num);
    }


    int main(void)
    {
    int data[5] = { 1, 2, 3, 4, 5 };
    RecordType r[5];

    for (int i = 0; i < 5; i++)
    r[i].data = data[i];

    combination(r, 5, 3);
    }
    2019-06-20
  • jiangjing
    直接等于 C(100,10+3+1)?
    2019-04-25
  • Joe
    C++实现
    #include <cmath>
      #include <iostream>
      #include <vector>
      
      using namespace std;

      class Combination {
        private:
        const int firstPrize;
        const int secondPrize;
        const int thirdPrize;
      
        public:
        Combination(int x, int y, int z)
            : firstPrize(x), secondPrize(y), thirdPrize(z) {
        }
        /**
        * @description:
        * 从10个人中选出三等奖3人,二等奖2人,一等奖1人,不能重复获奖。
        * @param {type} rewardNum- 指定赏金数, result- 奖赏方式结果。
        * @return: null
        */
      void rewardMethods(vector<int> result, vector<int> candidate) {
          unsigned int len = thirdPrize + secondPrize + firstPrize;
          if (result.size() == len) {
            // 输出结果
            resultOutput(result);
            return;
          } else {
            for (unsigned int i = 0; i < candidate.size(); i++) {
              vector<int> resultNew = result;
              resultNew.push_back(candidate[i]);
      
              vector<int> candidateNew;
              copyElem(candidate, candidateNew, i + 1);
              rewardMethods(resultNew, candidateNew);
            }
          }
        }
        // 数据复制函数
        void copyElem(vector<int>& input, vector<int>& output, int i) {
          vector<int>::iterator it = input.begin() + i;
          for (; it < input.end(); it++) {
            output.push_back(*it);
          }
        }
      // 数据复制函数
        void copyElem(vector<int>& input, vector<int>& output, int i) {
          vector<int>::iterator it = input.begin() + i;
          for (; it < input.end(); it++) {
            output.push_back(*it);
          }
        }
        // 输出结果
        void resultOutput(vector<int> res) {
          for (unsigned int i = 0; i < res.size(); i++) {
            if (i == thirdPrize) cout << '*';
            if (i == thirdPrize + secondPrize) cout << '*';
            cout << res[i] << ' ';
          }
          cout << endl;
        }
      };
      
      // test
      int main(void) {
        Combination test(1, 2, 3);
        vector<int> res;
        vector<int> candidate;
        // 输入
        for (unsigned int i = 0; i < 10; i++) {
          candidate.push_back(i + 1);
        }
        test.rewardMethods(res, candidate);
      }
    2019-01-10
收起评论
29
返回
顶部