NEFU离散数学实验1-排列组合

Myth丶恋晨 2024-04-17 13:33 58阅读 0赞

相关概念

> 在离散数学中，组合数是一种用于计算从n个不同元素中选取m个元素的方式。以下是一些与组合数相关的概念：
> 
> 1.  排列：从n个不同元素中选取m个元素进行排列，排列数用P(n, m)表示，计算公式为P(n, m) = n! / (n - m)!
> 2.  组合：从n个不同元素中选取m个元素进行组合，组合数用C(n, m)表示，计算公式为C(n, m) = n! / (m! \* (n - m)!)
> 3.  二项式系数：组合数也称为二项式系数，表示为C(n, m)。二项式系数可以用来展开二项式表达式的系数，如(a + b)^n的展开式中，每一项的系数就是C(n, m)。
> 4.  杨辉三角形：杨辉三角形是一种图形化展示组合数的方式。在杨辉三角形中，每个数是它上方两个数之和，每一行的两端数都为1，其余数为上方两个数之和。杨辉三角形中的每个数就是组合数C(n, m)。
> 5.  组合恒等式：组合恒等式是指一系列关于组合数的等式，如C(n, m) = C(n, n - m)，C(n, m) = C(n - 1, m - 1) + C(n - 1, m)等等。这些等式可以用于简化组合数的计算。

#### 1. (程序题) ####

> 非降路径
> 
> 在平面直角坐标系内，有(a,b)和(c,d)两点，且a,b,c,d都大于0，而且(c,d)点位于(a,b)点的右上方！
> 
> 从(a,b)出发走到(c,d)点，只能向上走和向右走，请问共有多少种走法（非降路径数）？
> 
> 输入：
> 
> 输入a,b,c,d(0<=a,b,c,d<=12)
> 
> 输出：
> 
> 输出非降路径数！
> 
> 例子输入:
> 
> 0 0 2 2
> 
> 例子输出：
> 
> 6

#include <iostream>
    
    using namespace std;
    
    
    
    int Count(int n,int m)
    
    {
    
        if(n==m||m==0)
    
            return 1;
    
        else
    
            return Count(n-1,m)+Count(n-1,m-1);
    
    }
    
    
    
    int main()
    
    {
    
        int a,b,c,d,sum;
    
        while(cin>>a>>b>>c>>d){
    
        sum=Count(c-a+d-b,c-a);
    
        cout<<sum<<endl;
    
        }
    
        return 0;
    
    }

> 直接用书上P199公式吧
> 
> ![ans=C\_\{c-a+d-b\}^\{c-a\}][ans_C_c-a_d-b_c-a]
> 
> 本质是求组合数，数据非常友好，但是你直接阶乘会溢出的，所以我们求组合数要用递推式

#### 2. (程序题)特殊的非降路径 ####

> 设a,b,c,d,m,n是非负整数，其中 a<=c<=m,b<=d<=n;请你计算从(a,b)点经过(c,d)点到(m,n)点的非降路径数？
> 
> 输入：
> 
> 在一行内输入a,b,c,d,m,b,所有的数值范围为【0-14】，本题为单组数据。
> 
> 输出：
> 
> 在一行内输出非降路径数。
> 
> 例子输入：
> 
> 0 0 1 1 2 2
> 
> 例子输出：
> 
> 4

#include <iostream>
    
    using namespace std;
    
    
    
    int Count(int n,int m)
    
    {
    
        if(n==m||m==0)
    
            return 1;
    
        else
    
            return Count(n-1,m)+Count(n-1,m-1);
    
    }
    
    
    
    int main()
    
    {
    
        int a,b,c,d,m,n,result1,result2,sum;
    
        cin>>a>>b>>c>>d>>m>>n;
    
        result1=Count(c-a+d-b,c-a);
    
        result2=Count(m-c+n-d,m-c);
    
        sum=result1*result2;
    
        cout<<sum<<endl;
    
        return 0;
    
    }

> 在这道题目中，从(a,b)点到(c,d)点的非降路径数，就相当于从c-a+d-b个元素中选择c-a个元素的组合数，因为每一步只能向右或者向下走，所以总共需要走c-a+d-b步，其中有c-a步向右走。同理，从(c,d)点到(m,n)点的非降路径数，就相当于从m-c+n-d个元素中选择m-c个元素的组合数。所以，从(a,b)点经过(c,d)点到(m,n)点的非降路径数，就是这两个组合数的乘积。

#### 3. (程序题)简单组合： ####

> 计算C(n,m)的值，C(n,m)代表从n个元素中选取m个元素的方法数，其中有1<= m <= n<= 65。
> 
> 输入：
> 
> 输入数据有多组，每组数据一行，有2个整数分别为n和m。
> 
> 输出：
> 
> 输出从总共n个元素中选出m个元素共有多少种方法?
> 
> 例子输入：
> 
> 2 2
> 
> 4 2
> 
> 例子输出：
> 
> 1
> 
> 6

一般解法

#include <iostream>
    
    using namespace std;
    
    long long  Count(long long n,long long m)
    
    {
    
        if(n==m||m==0)
    
            return 1;
    
        else
    
            return Count(n-1,m)+Count(n-1,m-1);
    
    }
    
    int main()
    
    {
    
    long long n,m,result,sum;
    
    while(cin>>n>>m)
    {
    
        sum=Count(n,m);
    
        cout<<sum<<endl;
    
    }
    
        return 0;
    
    }

> 计算从n个元素中选取m个元素的组合数。它使用了递归的方法，利用了组合数的性质：
> 
> ![C\_n^m=C\_\{n-1\}^m+C\_\{n-1\}^\{m-1\}][C_n_m_C_n-1_m_C_n-1_m-1]

问题

> 上述代码中的 `Count` 函数使用了递归方式计算组合数，对于大的输入值可能会导致栈溢出或运行时间较长。对于较大的组合数计算，推荐使用动态规划或组合数公式进行计算。

![a675017c2e52445d87d755f040d76473.png][]

#include <iostream>
    using namespace std;
    
    long long combination(int n, int m) {
        long long dp[66][66] = {0};
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        return dp[n][m];
    }
    
    int main() {
        int n, m;
        while (cin >> n >> m) {
            long long result = combination(n, m);
            cout << result << endl;
        }
        return 0;
    }

> `dp` 是一个二维数组，用于保存计算过程中的中间结果。`dp[i][j]` 表示从 `i` 个元素中选择 `j` 个元素的组合数。![C\_n^m=C\_\{n-1\}^m+C\_\{n-1\}^\{m-1\}][C_n_m_C_n-1_m_C_n-1_m-1]

#### 4. (程序题)小兔的棋盘 ####

> 小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧 ！
> 
> 输入：
> 
> 多组输入，每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
> 
> 输出：
> 
> 对于每个输入数据输出路径数，具体格式看Sample。
> 
> 例子输入：
> 
> 1
> 
> 3
> 
> 12
> 
> \-1
> 
> 例子输出：
> 
> 1 1 2
> 
> 2 3 10
> 
> 3 12 416024

#include <iostream>
    using namespace std;
    
    typedef long long LL;
    
    LL a[71][71],i,j,n;
    
    
    
    int main() {
    
      for(int i=0;i<=70;i++)
            a[i][i]=a[i][0]=1;
    
            for(i=2;i<=70;i++)
    
                for(j=1;j<=70;j++)
                    a[i][j]=a[i-1][j-1]+a[i-1][j];
    
     int t=0;
    
     LL ans=0;
    
     while(cin>>n&&n!=-1)
    
        {
    
          t++;
    
          ans=a[2*n][n]*2;
    
          ans=ans/(n+1);
    
          cout<<t<<" "<<n<<" "<<ans<<endl;
    
        }
    
    
    
      return 0;
    
    }

![7bc02f1e940b4fffb2ba7d3e7d5d7474.png][]

[ans_C_c-a_d-b_c-a]: https://latex.csdn.net/eq?ans%3DC_%7Bc-a&plus;d-b%7D%5E%7Bc-a%7D
[C_n_m_C_n-1_m_C_n-1_m-1]: https://latex.csdn.net/eq?C_n%5Em%3DC_%7Bn-1%7D%5Em&plus;C_%7Bn-1%7D%5E%7Bm-1%7D
[a675017c2e52445d87d755f040d76473.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/208d88a1637748ad949861ad9e859670.png
[7bc02f1e940b4fffb2ba7d3e7d5d7474.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/8048189721be42bdbf5faf67b76cb2e8.png