The binomial coefficient C(n, k) for n >= k , is defined as n! / k!(n-k)! (this

Question

The binomial coefficient C(n, k) for n >= k , is defined as n! / k!(n-k)! (this is called the factorial definition). However, it can also be defined recursively as: C(n, 0) = 1 for n >= 0 C(n, n) = 1 for n >= 0 C(n, k) = C(n-1, k) + C(n-1, k-1) for n > k > 0.

Part 1: The function binomial_i(n) uses an iterative algorithm to compute the coefficients C(n, 0), C(n, 1), C(n, 2), ..., C(n, n) from the factorial definition. Write this function in C++.

Part 2: The function binomial_r(n) computes C(n, 0), C(n, l), ..., C(n, n) recursively. Write this function in C++.

Explanation / Answer

CODE :

Part1 :

#include<stdio.h>

int min(int a, int b);

// Returns value of Binomial Coefficient C(n, k)

int binomialCoeff(int n, int k)

{

    int C[n+1][k+1];

    int i, j;

    // Caculate value of Binomial Coefficient in bottom up manner

    for (i = 0; i <= n; i++)

    {

        for (j = 0; j <= min(i, k); j++)

        {

            // Base Cases

            if (j == 0 || j == i)

                C[i][j] = 1;

            // Calculate value using previosly stored values

            else

                C[i][j] = C[i-1][j-1] + C[i-1][j];

        }

    }

    return C[n][k];

}

// A utility function to return minimum of two integers

int min(int a, int b)

{

    return (a<b)? a: b;

}

/* Drier program to test above function*/

int main()

{

    int n = 5, k = 2;

    printf ("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k) );

    return 0;

}

Part2 :

#include<iostream>

using namespace std;

// Returns value of Binomial Coefficient C(n, k)

unsigned long int binomialCoeff(unsigned int n, unsigned int k)

{

    unsigned long int res = 1;

    // Since C(n, k) = C(n, n-k)

    if (k > n - k)

        k = n - k;

    // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]

    for (int i = 0; i < k; ++i)

    {

        res *= (n - i);

        res /= (i + 1);

    }

    return res;

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.