站队问题、分糖果问题

╰半橙微兮° 2022-06-09 10:00 248阅读 0赞

*   *   *  站队问题
         *  分糖果

--------------------

### 站队问题 ###

n个人站队，他们的编号依次从1到n，要求编号为a的人必须在编号为b的人的左边，但不要求一定相邻，请问共有多少种排法？第二问如果要求a必须在b的左边，并且一定要相邻，请问一共有多少种排法？

给定人数n及两个人的编号a和b，请返回一个两个元素的数组，其中两个元素依次为两个问题的答案。保证人数小于等于10。

测试样例：  
7,1,2  
返回：\[2520,720\]

**我的提交**

# -*- coding:utf-8 -*-
    
    class StandInLine:
        def getWays(self, n, a, b):
            # write code here
            result = [0, 0]
            result[0] = self.C(n) / 2
            result[1] = self.C(n - 1)
            return result
    
        def C(self, n):
            sum = 1
            for i in range(1, n + 1):
                sum = sum * i
            return sum

参考答案

class StandInLine {
    public:
        vector getWays(int n, int a, int b) {
            vector ret;
            int tmp = 1;
            for(int i = 2;i <= n;++ i) tmp *= i;
            ret.push_back(tmp / 2);
            tmp = 1;
            for(int i = 2;i < n;++ i) tmp *= i;
            ret.push_back(tmp);
            return ret;
        }
    };

--------------------

### 分糖果 ###

n颗相同的糖果，分给m个人，每人至少一颗，问有多少种分法。

给定n和m，请返回方案数，保证n小于等于12，且m小于等于n。

测试样例：  
10,3  
返回：36

# -*- coding:utf-8 -*-
    
    class Distribution:
        def getWays(self, n, m):
            # write code here
            n=n-1
            m=m-1
            ans=fac(n)/fac(m)/fac(n-m)
            return ans
    
    def fac(n):
        assert n>=0;
        if n<2:
            return 1
        else:
            return n*fac(n-1)

**参考答案**

class Distribution {
    public:
        int getWays(int n, int m) {
            int A = 1,B = 1,C = 1;
            for(int i = 2;i <= m - 1;++ i) A *= i;
            for(int i = 2;i <= n - 1;++ i) B *= i;
            for(int i = 2;i <= n - m;++ i) C *= i;
            return B / A / C;
        }
    };