C++进阶课程第2期——排列与组合1

大家好，我是清墨，欢迎收看《C++进阶课程——排列与组合》。

 啊，上一期我们的情况啊也是非常好的，今天直接开始！

排列（Arrange）

与上期一样啊，我们先了解一下排列的概念。 

排列是指将一组事物按照一定的顺序进行摆放的方式。在数学中，排列是指从一组事物中选取若干个进行组合，并按照特定的顺序进行排列的方法。

至于怎样表示呢就用表示从n个元素中选择m个元素进行排列，所有的方案数。

是n的全排列，结果是n的阶乘（n!）。

计算：     =     。

组合（Combination）

组合是从给定的元素集合中选取一些元素的方式。在组合中，选取的元素的顺序是不重要的，也就是说，(1,2,3)和(3,2,1)被视为相同的组合。 

至于怎样表示呢就用表示从n个元素中选择m个元素进行组合，所有的方案数。

计算： =

海题——杨辉三角

题目描述

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

 

上面的图形熟悉吗？如果还没看出来它的特点的话，不妨再调整一下格式：

     11 11 2 11 3 3 11 4 6 4 1
1 5 10 10 5 1

是不是看出这些数字的特点了？这是大名鼎鼎的杨辉三角。

今天，我们试着来输出 n 行的杨辉三角数字。

输入格式 1 个正整数：n。

输出格式 相应层数的杨辉三角数字。

样例

输入数据 1

6

输出数据 1

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

 

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[111][111];
int main(){cin>>n;a[1][1]=1;a[2][1]=1;a[2][2]=1;for(int i=3;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=a[i-1][j]+a[i-1][j-1];}}for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cout<<a[i][j]<<" ";}cout<<endl;}return 0;
}

 杨辉三角有什么用呢，先买个管子，进入例题。

例题1.派水果

 题目描述

若一位母亲手里有 m 个相同的苹果，还有 n 个相同的梨，在 m+n 天内分给她的小孩，每天分 1 个水果，有多少种不同的分派方案?。

输入格式 两个整数 m 和 n ( 1≤m,n≤32)。

输出格式 一个整数。结果不超出 max long long

样例

输入数据 1

2 3

 

输出数据 1

10

分析题目 

本题确定了苹果的位置就可以确定梨的位置，又因为苹果和梨都相同，所以不用考虑顺序。

只用求 或  就可以了。

所以=。

但是，直接计算必须会超，在我们计算32的阶乘时，就会溢出。

“e+35”！10的35次方，超出了long long范围，那要怎样计算呢？

找规律 

我们不妨试试小点的C。

用原本的代码计算小一点的。

#include<bits/stdc++.h>
using namespace std;
long long ans1=1,ans2=1,n,m;
int main(){cin>>n>>m;n+=m;for(long long i=n;i>=n-m+1;i--){ans1*=i;}for(long long i=m;i>=1;i--){ans2*=i;}cout<<ans1/ans2;return 0;
}

得 ：

=1

=1 

=2 =1

=3 =3 =1

=4 =6 =4=1

有点感觉了吗？

1
1         1
1         2 1
1         3 3 1
1         4 6 4 1

杨辉三角！

代码

写得代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[11100][11000],m;
int main(){cin>>n>>m;n+=m;a[1][1]=1;a[1][2]=1;for(int i=2;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=a[i-1][j]+a[i-1][j-1];}}cout<<a[n][n-m+1];return 0;
}

所以杨辉三角可不只是数学游戏和海题，在实际应用中有大用。例如在计算组合方案数的时候，C(n, m) = C(n-1,m) + C(n-1, m-1)，从而避免了组合公式中的除法运算（除法运算的计算机代码要复杂很多，远远没有加法容易处理）。

我们下期再见。