程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 組合c(m,n)的計算方法

組合c(m,n)的計算方法

編輯:C++入門知識

問題:求解組合數C(n,m),即從n個相同物品中取出m個的方案數,由於結果可能非常大,對結果模10007即可。

方案1:

暴力求解,C(n,m)=n*(n-1)*...*(n-m+1)/m!,n<=15

 

[cpp]
int Combination(int n, int m) 

    const int M = 10007; 
    int ans = 1; 
    for(int i=n; i>=(n-m+1); --i) 
        ans *= i; 
    while(m) 
        ans /= m--; 
    return ans % M; 

int Combination(int n, int m)
{
 const int M = 10007;
 int ans = 1;
 for(int i=n; i>=(n-m+1); --i)
  ans *= i;
 while(m)
  ans /= m--;
 return ans % M;
}
方案2:

打表,C(n,m)=C(n-1,m-1)+C(n-1,m),n<=10,000

 

[cpp] 
const int M = 10007; 
const int MAXN = 1000; 
int C[MAXN+1][MAXN+1]; 
void Initial() 

    int i,j; 
    for(i=0; i<=MAXN; ++i) 
    { 
        C[0][i] = 0; 
        C[i][0] = 1; 
    } 
    for(i=1; i<=MAXN; ++i) 
    { 
        for(j=1; j<=MAXN; ++j) 
        C[i][j] = (C[i-1][j] + C[i-1][j-1]) % M; 
    } 

int Combination(int n, int m) 

    return C[n][m]; 

const int M = 10007;
const int MAXN = 1000;
int C[MAXN+1][MAXN+1];
void Initial()
{
 int i,j;
 for(i=0; i<=MAXN; ++i)
 {
  C[0][i] = 0;
  C[i][0] = 1;
 }
 for(i=1; i<=MAXN; ++i)
 {
  for(j=1; j<=MAXN; ++j)
  C[i][j] = (C[i-1][j] + C[i-1][j-1]) % M;
 }
}
int Combination(int n, int m)
{
 return C[n][m];
}


方案3:

質因數分解,C(n,m)=n!/(m!*(n-m)!),C(n,m)=p1a1-b1-c1p2a2-b2-c2…pkak-bk-ck,n<=10,000,000

 

[cpp]
#include <cstdio>  
const int maxn=1000000; 
#include <vector>  
using namespace std; 
bool arr[maxn+1]={false}; 
vector<int> produce_prim_number() 

        vector<int> prim; 
        prim.push_back(2); 
        int i,j; 
        for(i=3;i*i<=maxn;i+=2) 
        { 
                if(!arr[i]) 
                { 
                        prim.push_back(i); 
                        for(j=i*i;j<=maxn;j+=i) 
                                arr[j]=true; 
                } 
        } 
        while(i<maxn) 
        { 
                if(!arr[i]) 
                        prim.push_back(i); 
                i+=2; 
        } 
        return prim; 

//計算n!中素數因子p的指數  
int cal(int x,int p) 

        int ans=0; 
        long long rec=p; 
        while(x>=rec) 
        { 
                ans+=x/rec; 
                rec*=p; 
        } 
        return ans; 

//計算n的k次方對m取模,二分法  
int pow(long long n,int k,int M) 

        long long ans=1; 
        while(k) 
        { 
                if(k&1) 
                { 
                        ans=(ans*n)%M; 
                } 
                n=(n*n)%M; 
                k>>=1; 
        } 
        return ans; 

//計算C(n,m)  
int combination(int n,int m) 

        const int M=10007; 
        vector<int> prim=produce_prim_number(); 
        long long ans=1; 
        int num; 
        for(int i=0;i<prim.size()&&prim[i]<=n;++i) 
        { 
                num=cal(n,prim[i])-cal(m,prim[i])-cal(n-m,prim[i]); 
                ans=(ans*pow(prim[i],num,M))%M; 
        } 
        return ans; 

int main() 

        int m,n; 
        while(~scanf("%d%d",&m,&n),m&&n) 
        { 
                printf("%d\n",combination(m,n)); 
        } 
        return 0; 

#include <cstdio>
const int maxn=1000000;
#include <vector>
using namespace std;
bool arr[maxn+1]={false};
vector<int> produce_prim_number()
{
        vector<int> prim;
        prim.push_back(2);
        int i,j;
        for(i=3;i*i<=maxn;i+=2)
        {
                if(!arr[i])
                {
                        prim.push_back(i);
                        for(j=i*i;j<=maxn;j+=i)
                                arr[j]=true;
                }
        }
        while(i<maxn)
        {
                if(!arr[i])
                        prim.push_back(i);
                i+=2;
        }
        return prim;
}
//計算n!中素數因子p的指數
int cal(int x,int p)
{
        int ans=0;
        long long rec=p;
        while(x>=rec)
        {
                ans+=x/rec;
                rec*=p;
        }
        return ans;
}
//計算n的k次方對m取模,二分法
int pow(long long n,int k,int M)
{
        long long ans=1;
        while(k)
        {
                if(k&1)
                {
                        ans=(ans*n)%M;
                }
                n=(n*n)%M;
                k>>=1;
        }
        return ans;
}
//計算C(n,m)
int combination(int n,int m)
{
        const int M=10007;
        vector<int> prim=produce_prim_number();
        long long ans=1;
        int num;
        for(int i=0;i<prim.size()&&prim[i]<=n;++i)
        {
                num=cal(n,prim[i])-cal(m,prim[i])-cal(n-m,prim[i]);
                ans=(ans*pow(prim[i],num,M))%M;
        }
        return ans;
}
int main()
{
        int m,n;
        while(~scanf("%d%d",&m,&n),m&&n)
        {
                printf("%d\n",combination(m,n));
        }
        return 0;
}


方案4:

Lucas定理,將m,n化為p進制,有:C(n,m)=C(n0,m0)*C(n1,m1)...(mod p),算一個不是很大的C(n,m)%p,p為素數,化為線性同余方程,用擴展的歐幾裡德定理求解,n在int范圍內,修改一下可以滿足long long范圍內。

 

[cpp] 
#include <stdio.h>  
const int M = 10007; 
int ff[M+5];  //打表,記錄n!,避免重復計算  
 
//求最大公因數  
int gcd(int a,int b) 

    if(b==0) 
        return a; 
    else 
        return gcd(b,a%b); 

 
//解線性同余方程,擴展歐幾裡德定理  
int x,y; 
void Extended_gcd(int a,int b) 

    if(b==0) 
    { 
       x=1; 
       y=0; 
    } 
    else 
    { 
       Extended_gcd(b,a%b); 
       long t=x; 
       x=y; 
       y=t-(a/b)*y; 
    } 

 
//計算不大的C(n,m)  
int C(int a,int b) 

    if(b>a) 
    return 0; 
    b=(ff[a-b]*ff[b])%M; 
    a=ff[a]; 
    int c=gcd(a,b); 
    a/=c; 
    b/=c; 
    Extended_gcd(b,M); 
    x=(x+M)%M; 
    x=(x*a)%M; 
    return x; 

 
//Lucas定理  
int Combination(int n, int m) 

    int ans=1; 
    int a,b; 
    while(m||n) 
    { 
             a=n%M; 
        b=m%M; 
        n/=M; 
        m/=M; 
        ans=(ans*C(a,b))%M; 
    } 
    return ans; 

 
int main(void) 

    int i,m,n; 
    ff[0]=1; 
    for(i=1;i<=M;i++)  //預計算n!  
    ff[i]=(ff[i-1]*i)%M; 
     
    scanf("%d%d",&n, &m); 
    printf("%d\n",func(n,m)); 
     
    return 0; 

#include <stdio.h>
const int M = 10007;
int ff[M+5];  //打表,記錄n!,避免重復計算

//求最大公因數
int gcd(int a,int b)
{
    if(b==0)
  return a;
    else
  return gcd(b,a%b);
}

//解線性同余方程,擴展歐幾裡德定理
int x,y;
void Extended_gcd(int a,int b)
{
    if(b==0)
    {
       x=1;
       y=0;
    }
    else
    {
       Extended_gcd(b,a%b);
       long t=x;
       x=y;
       y=t-(a/b)*y;
    }
}

//計算不大的C(n,m)
int C(int a,int b)
{
    if(b>a)
 return 0;
    b=(ff[a-b]*ff[b])%M;
    a=ff[a];
    int c=gcd(a,b);
    a/=c;
    b/=c;
    Extended_gcd(b,M);
    x=(x+M)%M;
    x=(x*a)%M;
    return x;
}

//Lucas定理
int Combination(int n, int m)
{
    int ans=1;
 int a,b;
 while(m||n)
 {
          a=n%M;
  b=m%M;
  n/=M;
  m/=M;
  ans=(ans*C(a,b))%M;
 }
 return ans;
}

int main(void)
{
    int i,m,n;
 ff[0]=1;
 for(i=1;i<=M;i++)  //預計算n!
 ff[i]=(ff[i-1]*i)%M;
 
 scanf("%d%d",&n, &m);
 printf("%d\n",func(n,m));
 
 return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved