二项式系数 – Binomial Coefficients

于 2011年01月31日 发布在 算法&&ACM 跳到评论

二项式系数是组合数学中十分重要的基本知识,各种应用都少不了他.今天做了两个题,顺便总结下:

这个是我们了解到的最基本的形式,当k=0时,上式值为1,当k>n时,值为0;

帕斯卡三角中的每个数相当于顶上两侧数的加和,也可以用组合的思想来解释这个公式:

从n个人中选出k个人,我们先看其中的A某,如果他不在这k个人中,那么就相当于从n-1个人中挑出k个人,如果他在这k个人中,那么剩下的k-1个人就要从n-1个人中挑选.根据加法原理,总的数量就是这两种情况的和.

二项式定理,高中时候就很熟悉的东西,当x=1,y=1时候可以得到:

还有一个公式用的很多:

他可以用来证明下面的公式,

二项式系数的最大值为:

帕斯卡三角(杨辉三角)有很多性质,懒得用公式打出来了,就画了一个图:

横竖斜方向上的数字都有性质:

横:加和为2的N次方         竖:某一列从1开始到数字A的和等于A右下角的数

斜(蓝色):从1开始到A的和,等于A下边的数。

斜(褐色):所有斜线上的数字加和排列起来是fibonacci数列。

这里有两道题,简单看一下:

zoj 1938  Binomial Showdown

很纯的题目,就是让求组合数:下面是关键代码:

//如果没有if语句,会超时
long long qiu( long long a,long long b )
{
    long long i,sum = 1;
    if( a-b < b ) b = a-b;
    for( i = 0; i < b; i++ )
        sum *= ( a - i ),sum/=i+1;
    return sum;
}

poj 3219 Binomial Coefficients
本题是让求出组合数除2的余数,如果把结果求出来,再进行运算肯定会超时。
由于我们只是需要知道结果跟2的关系,求出n,k,n-k,的2的阶数a,b,c,如果a == b+c,显然结果是个奇数,反之是偶数:

#include<iostream>
#include<cstdio>

using namespace std;
int count( int x )
{
    int sum = 0;
    while( x )
        x /= 2,sum += x;
    return sum;
}

int main(void)
{
    int n,k;
   
    while( cin >> n >> k )
    {
        if( count(n) == count(k) + count(n-k) ) 
            cout << 1 << endl;
        else 
            cout << 0 << endl;
    }
    return 0;
}

本文共有 9条评论 | 沙发:文章评论

  1. 小媛说道:

    姐!怎么不能插表情 = =。。。

  2. 小媛说道:

    :-D 这个好。。不过。。那个你最常用的那个泪眼汪汪的表情没有捏。。

  3. 墨画的留白说道:

    好奇怪啊,我也换到SyntaxHighlighter了,可是怎么工具条里只有一个帮助额。。。

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)