Calculate nCm

/* *********************************************** */
/* Input : Two integer number n m */
/* Return : The nCm */
/* *********************************************** */
double nCr(int n,int m){
 int k;
 register int i,j;
 double c,d;
 c=d=1;
 k=(m>(n-m))?m:(n-m);
 for(j=1,i=k+1;(i<=n);i++,j++){
 c*=i;
 d*=j;
 if( !fmod(c,d) && (d!=1)){ 
 c/=d;
 d=1;}}
 return c;
}
/* A sample main function */
int main(void)
{
 int n,m;
 while(scanf("%d%d",&n,&m)!=EOF)
 printf("%.0lf\n",nCr(n,m));
 return 0;
}

Another way to calculate the nCm by using the Pascal’s triangel

#include<stdio.h>
#define MAXTRI 50
unsigned long int pas[MAXTRI][MAXTRI];
void pascals(int n)
{
register int i,j;
 pas[0][0]=1;
 pas[1][0]=pas[1][1]=1;
 for(i=2;i<=n;i++)
 {
 pas[i][0]=1;
 for(j=1;j<i;j++)
 {
 pas[i][j]= pas[i-1][j-1]+pas[i-1][j];
 }
 pas[i][j]=1;
 }
}
main(void)
{
 pascals(10);
 int n,m;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
 printf("%lu",pas[n][m]);
 }
 return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s