二项式系数是组合数学中十分重要的基本知识,各种应用都少不了他.今天做了两个题,顺便总结下:
这个是我们了解到的最基本的形式,当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数列。
这里有两道题,简单看一下:
很纯的题目,就是让求组合数:下面是关键代码:
//如果没有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; }
姐!怎么不能插表情 = =。。。
我把那个插件停用了…正在寻找替代品…
😀 这个好。。不过。。那个你最常用的那个泪眼汪汪的表情没有捏。。
😐
➡ 有了 哈哈
😀
好奇怪啊,我也换到SyntaxHighlighter了,可是怎么工具条里只有一个帮助额。。。
换成syntaxhighlighter2.x版本的,,后台可以选择版本的…