Thursday, 26 March 2015

Play With Binomial coefficient

Binomial Series has Very important role in mathematics .
Today we are going to discuss different approach of finding binomial coefficient .

 Mathematical Formula to find binomial Coefficient

Directly implement this mathematical formula  to find Binomial Coefficient

C-Program:
1. //Direct Approach to find Binomial Coefficient
2. //Beginner 2 Computer Science
3. #include<stdio.h>
4. #include <string.h>
5. int BinomialCoeff(int n,int r){
6.         /*
7.            Direct Approach
8.            coeff=n!/((n-r)! * r!)
9.            !-> stands for factorial
10.            ie. 5!= 5*4*3*2*1
11.         */
12.         int max(int a,int b){
13.                 if(a>b)
14.                     return a;
15.                 else
16.                     return b;
17.         }
18.         int min(int a,int b){
19.                 if(a<b)
20.                     return a;
21.                 else
22.                     return b;
23.         }
24.
25.         int i,mx,mn;
26.         int coeff=1;
27.         //nC0 & nCn
28.         if(r==0 ||n==r)
29.             return 1;
30.
31.         mx=max((n-r),r); //max of r & n-r
32.         mn=min((n-r),r); //min of r & n-r
33.
34.         //calculating coeff=n!/mx!
35.         for(i=mx+1;i<=n;i++){
36.                 coeff=coeff*i;
37.         }
38.
39.         //calculate coeff=coeff/mn!
40.         for(i=2;i<=mn;i++){
41.                 coeff=coeff/i;
42.     }
43.         return coeff;
44. }
45. int main()
46. {
47.   int n=5,r=3;
48.   printf("==> %d\n",BinomialCoeff(n,r));
49.   return 0;
50. }

Recursive Approach :

 Recursive Approach to calculate binomial Coefficient
 Recursion Tree for Binomial Coefficient

C-Program for Finding Binomial Coefficient using recursive Approach :

1. //Recursive Approach for finding Binomial Coefficient
2. //C99 Program
3. #include<stdio.h>
4. #include <string.h>
5. int BinomialCoeff_Recur(int n,int r){
6.         /*
7.           recursive Approach
8.           when r=0 or r==n return 1 //base case
9.           else coeff=coeff=coeff+BinomialCoeff_Recur(n-1,r)+BinomialCoeff_Recur(n-1,r-1);
10.           return coeff
11.         */
12.         int coeff=0;
13.
14.         if(r<=0 || r==n){ //termination case
15.                 return 1;
16.         }
17.         if(r<){
18.              //recursive call
19.             coeff=coeff+BinomialCoeff_Recur(n-1,r)+BinomialCoeff_Recur(n-1,r-1);
20.         }
21.         return coeff;
22. }
23. int main()
24. {
25.   int n=5,r=3;
26.   printf("==> %d\n",BinomialCoeff_Recur(n,r));
27.   return 0;
28. }

Dynamic Programming Approach:

We gonna use bottom top approach & store result which may need in future .
 Dynamic Programming Approach for finding Binomial Coefficient

C-Program for finding Binomial Coefficient using Dynamic Programming Approach:

1. //Dynamic Programming Approach for finding Binomial Coefficient
2. // C Program
3. //Beginner 2 Computer Science
4. #include<stdio.h>
5. #include<string.h>
6. int BinomialCoeff_DynamicProgramming(int n,int r){
7.         /*
8.         **** this code is for C99
9.         ******Need <string.h>
10.         Need To fallow bottom top approch
11.         & Store value of each calcution may need in future
12.         */
13.         int min(int a,int b){
14.                 if(a<b)
15.                     return a;
16.                 else
17.                     return b;
18.         }
19.
20.         int mtrx[n+1][r+1];
21.         int i,j;
22.
23.         if(n==|| r==0){ //Special Case
24.                 return 1;
25.         }
26.         else if(r>n){
27.                 return 0;
28.         }
29.
30.         //This is Special Fuction Supported in C99
31.         memset(mtrx,0,sizeof(mtrx)); //now for all i,y mtrx[i][j]=0
32.
33.         //Calculation for binomial coefficient
34.         for(i=0;i<=n;i++){
35.                 for(j=0;j<=min(i,r);j++){
36.                         if(j==0 || j==i)
37.                             mtrx[i][j]=1;
38.                         else
39.                             mtrx[i][j]=mtrx[i-1][j-1]+mtrx[i-1][j];
40.                 }
41.         }
42.         return mtrx[n][r];
43. }
44. int main()
45. {
46.   int n=5,r=3;
47.   printf("==> %d\n",BinomialCoeff_DynamicProgramming(n,r));
48.   return 0;
49. }

Please Suggest if Found Any Bug
Thank U

1 comment:

1. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in Data Science with Python , kindly contact us http://www.maxmunus.com/contact
MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.