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

相关概念 

在离散数学中，组合数是一种用于计算从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 
 
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<
 
    }
 
    return 0;
 
}

直接用书上P199公式吧

本质是求组合数，数据非常友好，但是你直接阶乘会溢出的，所以我们求组合数要用递推式

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 
 
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<
 
    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 
 
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<
 
}
 
    return 0;
 
}

计算从n个元素中选取m个元素的组合数。它使用了递归的方法，利用了组合数的性质：

问题

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

#include 
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 个元素的组合数。

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 
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<" "<" "<
 
    }
 
 
 
  return 0;
 
}