首页 > 代码库 > 一般的排列组合计数公式

一般的排列组合计数公式

2024-07-24 17:03:05   217人阅读

 在n个不同的元素中：

    若取 r 个按次序排列， 则成为从n中取r个排列，其排列数为：P( n, r )=( n! ) / ( n-r )!  。

    如取出 r 个二不考虑起次序，则称为 从n中取 r 个组合， 其组合数为：C( n, r ) = ( n! )/[ ( r! ) *( n-r )! ] 。

 

 进行阶乘运算的数值较大， 直接计算分子和分母的话，效率低切容易溢出。

   一 ： 采取：连乘 r 个整商法

       C( n, r ) = [ (n-r-1) / r ] * [ (n-r-2)/(r-1) ] * ..........* [ n / 1 ]  .

  二： 二项式洗漱公式法

      C( j, i ) =  C( j, i-1) + C(j-1, i-1 ) .

     通过 i, j 的双重循环直接递推 c[i][j] ;

  样题：

  POJ  2249

        因为常用blockcodes编译代码，所以对于大的数据类型会选择 long long,  对于这道题，用了__int64类型（因为不常用，所以不能出错）

       复习一下：定义 __int64 ( 双下划线+int+64 )   输出：printf("I64d\n", a);     I64d    !!!!

       

Binomial Showdown
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 18112 Accepted: 5514

Description

In how many ways can you choose k elements out of n elements, not taking order into account? 
Write a program to compute this number.

Input

The input will contain one or more test cases. 
Each test case consists of one line containing two integers n (n>=1) and k (0<=k<=n). 
Input is terminated by two zeroes for n and k.

Output

For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 231. 
Warning: Don‘t underestimate the problem. The result will fit into an integer - but if all intermediate results arising during the computation will also fit into an integer depends on your algorithm. The test cases will go to the limit. 

Sample Input

4 210 549 60 0

Sample Output

625213983816

Source

Ulm Local 1997
 
     采用 分整式连乘的方法
      
    C ( n, k ) = (n-k+1)/k  *   (n-k+2)/(k-1)  * ......  * ( n)/1  .
 
 
#include <stdio.h>#include <string.h>#include <stdlib.h>__int64 work(__int64 n, __int64 k){	if(k>n/2)		k = n-k; //减少枚举量（剪枝）
	__int64 a=1, b=1; //代表分子和分母	int i;	for(i=1; i<=k; i++)  //循环k次运算	{		a=a*(n-i+1); //分子		b=b*i;		if(a%b==0) //说明能整除，进行整数商处理		{			a=a/b;			b=1;		}	}	return a/b;}int main(){	int n, k;	while(scanf("%d %d", &n, &k)!=EOF)	{		if(n==0  )		{			break;		}		printf("%I64d\n", work(n, k) );	}	return 0;}

　　

一般的排列组合计数公式


联系
我们