大家好，我是清墨，歡迎收看《C++進(jìn)階課程——排列與組合》。

?啊，上一期我們的情況啊也是非常好的，今天直接開(kāi)始！

排列（Arrange）

與上期一樣啊，我們先了解一下排列的概念。?

排列是指將一組事物按照一定的順序進(jìn)行擺放的方式。在數(shù)學(xué)中，排列是指從一組事物中選取若干個(gè)進(jìn)行組合，并按照特定的順序進(jìn)行排列的方法。

至于怎樣表示呢就用表示從n個(gè)元素中選擇m個(gè)元素進(jìn)行排列，所有的方案數(shù)。

是n的全排列，結(jié)果是n的階乘（n!）。

計(jì)算：? ???=? ? ?。

組合（Combination）

組合是從給定的元素集合中選取一些元素的方式。在組合中，選取的元素的順序是不重要的，也就是說(shuō)，(1,2,3)和(3,2,1)被視為相同的組合。?

至于怎樣表示呢就用表示從n個(gè)元素中選擇m個(gè)元素進(jìn)行組合，所有的方案數(shù)。

計(jì)算：?=

海題——楊輝三角

題目描述

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

?

上面的圖形熟悉嗎？如果還沒(méi)看出來(lái)它的特點(diǎn)的話，不妨再調(diào)整一下格式：

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

是不是看出這些數(shù)字的特點(diǎn)了？這是大名鼎鼎的楊輝三角。

今天，我們?cè)囍鴣?lái)輸出 n 行的楊輝三角數(shù)字。

輸入格式?1 個(gè)正整數(shù)：n。

輸出格式?相應(yīng)層數(shù)的楊輝三角數(shù)字。

樣例

輸入數(shù)據(jù) 1

6

輸出數(shù)據(jù) 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;
}

?楊輝三角有什么用呢，先買個(gè)管子，進(jìn)入例題。

例題1.派水果

?題目描述

若一位母親手里有?m?個(gè)相同的蘋果，還有?n?個(gè)相同的梨，在?m+n 天內(nèi)分給她的小孩，每天分?1?個(gè)水果，有多少種不同的分派方案?。

輸入格式?兩個(gè)整數(shù)?m 和?n?(?1≤m,n≤32)。

輸出格式?一個(gè)整數(shù)。結(jié)果不超出?max long long

樣例

輸入數(shù)據(jù) 1

2 3

?

輸出數(shù)據(jù) 1

10

分析題目?

本題確定了蘋果的位置就可以確定梨的位置，又因?yàn)樘O果和梨都相同，所以不用考慮順序。

只用求?或??就可以了。

所以=。

但是，直接計(jì)算必須會(huì)超，在我們計(jì)算32的階乘時(shí)，就會(huì)溢出。

“e+35”！10的35次方，超出了long long范圍，那要怎樣計(jì)算呢？

找規(guī)律?

我們不妨試試小點(diǎn)的C。

用原本的代碼計(jì)算小一點(diǎn)的。

#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

有點(diǎn)感覺(jué)了嗎？

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

所以楊輝三角可不只是數(shù)學(xué)游戲和海題，在實(shí)際應(yīng)用中有大用。例如在計(jì)算組合方案數(shù)的時(shí)候，C(n, m) = C(n-1,m) + C(n-1, m-1)，從而避免了組合公式中的除法運(yùn)算（除法運(yùn)算的計(jì)算機(jī)代碼要復(fù)雜很多，遠(yuǎn)遠(yuǎn)沒(méi)有加法容易處理）。

我們下期再見(jiàn)。