menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】组合数学之杨辉三角形
2020-04-07 | 【OI】 | 2 条评论 | 181 次阅读 | 347字

    作为一名oier,也不能总是写那一些“不务正业”的文章。今天,我就和大家谈一谈在组合数与杨辉三角当中我踩到的坑。还不是oier或高中学历以下的小伙伴们就可以先退场了,话不多说,正文开整!
1.gif
    众所皆知,杨辉三角形其实就是组合数。但是,这个“就是”二字有一些猫腻。下面,我先放出我们平常输出杨辉三角形的代码:

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

    然后,假设我们输入10,那么输出是这样子的:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

    看到输出结果之后,你很兴奋,迫不及待地想交程序。但是,骚年,别急。你以为这时候Cij(这里会有一点看不清,大家凑合着看一看就好了)就等于f [i] [j]了吗?图样图森破,你想想,我们拿C41举例,对应的f [4] [1]=1。这怎么可能呢?四个里边挑一个,才一种情况?不应该是4种吗?说得对。所以说,对应了组合数的杨辉三角,应该被裁切成这样子才是正确的:

1
2 1
3 3 1
4 6 4 1
5 10 10 5 1
6 15 20 15 6 1
7 21 35 35 21 7 1
8 28 56 70 56 28 8 1
9 36 84 126 126 84 36 9 1
10 45 120 210 252 210 120 45 10 1

    那么,最终求Cnm的代码长啥样呢?别急,现在就放出来:

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int a,b;
int f[maxn][maxn];
int main()
{
    cin>>a>>b;
    for (int i=0;i<=1000;i++)
    for (int j=0;j<=1000;j++)
    if (j==0||i==j) f[i][j]=1;
    else f[i][j]=f[i-1][j]+f[i-1][j-1];
    cout<<f[a][b]<<endl;
    return 0;
}

    好,本篇【OI】到此就告一段落了。我是Stephen Zeng,如果有什么写的不好的地方或者你有什么建议或感想,欢迎在评论区畅所欲言。我们下篇文章再见!
拜拜ヾ(?ω?`)o

None
发表评论
已有 2 条评论
textsms
account_circle
email
link
    Stephen Zeng
    Stephen Zeng 博主
    April 7th, 2020 at 09:29 am

    这个坑坑了我好久

      Stephen Zeng
      Stephen Zeng 博主
      April 7th, 2020 at 09:30 am

      :qq23: :orz11:

arrow_back 上一篇
arrow_forward 下一篇