Switch to full style
For C/C++ coders discussions and solutions
Post a reply

compute binomial coefficients

Thu Apr 23, 2009 1:36 am

I have to take c++ as part of my degree plan but I can't figure out this language. Can anyone help with this code PLEASE?
Code:
/* Program to compute binomial coefficients         */
/*                                                  */
/* Inputs: (keyboard)                               */
/*   Two positive integers (n & k)                  */
/*                                                  */
/* Output:                                          */
/*   Corresponding binomial coefficient (nCk)       */
/*                                                  */
/* Algorithm: see attached description              */
/****************************************************/
#include <iostream>
using namespace std ;
int binomial(int n, int k) ; // function prototype

int main()
{
   int n, k ;   // parameters for the binomial number
   int result ;   
   cout << endl ;
   // read in n & k   
   cout << "Enter n (positive integer) :  " ;
   cin >> n ;
   cout << "Enter k (positive integer) : " ;
   cin >> k ;
   result =  NEED TO WRITE FUNCTION CALL HERE
   cout << "Binomial number " << n << "C" << k
        << " = " << result << endl ;
   return (0) ;
}
// ********************************************************
int binomial(int n, int k)
/* Computes the binomial coefficient nCk */
/*                                       */
/* Inputs:                               */
/*    n, k (integers)                    */
/*                                       */
/* Output:                               */
/*    binomial coefficient nCk (integer) */
{
   int numerator, denominator ;
   int i ; // needed to compute numerator & denominator
   
ALL THIS STUFF NEEDS TO BE CHANGED

if ( ? ) Write if-test
   {
     return( ? ) ; Write return value
   }
   else
   {
      denominator =  ?  ; Write initial value
      for (i =   ? ; i <=   ? ; i = i+1)
        denominator =  ?  *   ? ;
        Write code to compute numerator, along similar lines
      return ( ? ) ; Write return value
   }
}




Re: compute binomial coefficients

Sat Aug 08, 2009 7:21 pm

What is your problem in this code . it is C++ for compute binomial coefficients .

which to run you need to replace
NEED TO WRITE FUNCTION CALL HERE

with

binomial(n,k) .

Re: compute binomial coefficients

Fri Aug 14, 2009 4:19 am

we define the binomial coefficients by:

(x+y)^n = sum(k=0,n, nCk x^(n-k) y^k)

and we want to show that:

nCk = (n!)/(n-k)!k!

is true. So let's use induction on n.

Base case: n = 1. (x+y)^1 = x+y, so 1C0 = 1C1 = 1!/1!0! = 1!/0!1!.

Inductive step: suppose nCk = (n!)/(n-k)!k! for some n and all 0 ≤ k ≤ n. We'll show it's true for n+1 and all 0 ≤ k ≤ n+1. So

(x+y)^(n+1) = (x+y)(x+y)^n = (x+y)sum(k=0,n, nCk x^(n-k) y^k)

So multiply through and note that the coefficient on x^(n+1-k) y^k is:

for k = 0: 1 = (n+1)!/(n+1)!0!
for k = n+1: 1 = (n+1)!/0!(n+1)!
for 1 ≤ k ≤ n: nCk + nC(k-1)

So we want to show that nCk + nC(k-1) = (n+1)!/(n+1-k)!k!. So:

n!/(n-k!)k! + n!/(n+1-k)!(k-1)! = [n!(n+1-k)+n!k]/(n+1-k)!k! = n!(n+1)/(n+1-k)!k! = (n+1)!/(n+1-k)!k!

Re: compute binomial coefficients

Fri Aug 14, 2009 12:29 pm

good information .

Post a reply
  Related Posts  to : compute binomial coefficients
 compute area of the circle.     -  
 compute number of files in directory     -  
 Program to compute commission using two methods     -  
 Compute FFT (Fourier Transform) in ITK for a 2d image     -  
 loop to compute the tuition in ten years     -  
 compute maximum and minimum values, also scaling factor.     -