Binomial numbers (or binomial coefficients) are important positive integers that arise frequently in computing and mathematics. A function to compute binomial coefficients will have two inputs: n and k. The corresponding coefficient is written as nCk.
/* pseudocode for Binomial Coefficients */
int binomial(int n, int k)
{
If (n < k) Then return (0)
Else
{
Set denominator = 1*2*...*k
Set numerator = (n-k+1)*(n-k+2)*...*(n-1)*n
return (numerator / denominator)
} // else
End if
}
Here are some additional notes:
1. Because binomial numbers are integers, the return type should be int, and the two parameters, n and k, are also integers.
2. We have used the notation
1*2*…*k
to indicate the product of consecutive numbers. For example,
1*2*…*5
is actually
1*2*3*4*5 = 120
Similarly,
6*7...*10 = 6*7*8*9*10 = 30,240
3. Part of the challenge in this exercise is to figure out how to compute this product. You should review the for loop in module 3, and recall how for loops are written in C++. Also review the programming exercise on exponentiation in module 3.
4. You can use integer division in line 7 above—it turns out that if numerator and denominator are computed as shown above, denominator will always evenly divide numerator.
To test this function, you must write a driver (in the code template given below, the driver is the main function).
You should design a suitable test suite and test your program using it. The test suite is part of the materials that you will be submitting.
Code Template for Exercise 1
/****************************************************/
/* File: name of your file with the source code */
/* */
/* Created by: give your name */
/* Date: give the date */
/* */
/* 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 = ?? Write the function call ;
cout << "Binomial number " << n << "C" << k
<< " = " << result << endl ;
return (0) ;
}
// ********************************************************
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
�� if (?? Write if-test)
{
���� return(??) ;
�� }
�� else
{
����� denominator = ?? ; // initial value
����� for (i = ?? ; i <= ?? ; i = i+1)
������� denominator = ?? * ?? ;
����� write code to compute numerator, along similar lines
����� return (??) ;
�� } // else
}
Anyone know how to do this? I got the compiler ready!
To compute binomial coefficients using the given pseudocode, you can follow these steps:
1. Initialize the variable `numerator` to 1, as it will hold the product of consecutive numbers from `(n-k+1)` to `n`.
2. Initialize the variable `denominator` to 1, as it will hold the product of consecutive numbers from 1 to `k`.
3. Check if `n` is less than `k`. If it is, return 0 as per the pseudocode.
4. Use a for loop to calculate the `denominator` and `numerator` using the formulas provided in the pseudocode. The for loop should iterate from `1` to `k`.
- In each iteration, update the `denominator` by multiplying it with the current value of `i` (e.g., `denominator = denominator * i`).
- Also, update the `numerator` by multiplying it with the current value of `n - (k - 1) + i` (e.g., `numerator = numerator * (n - (k - 1) + i)`).
5. After the loop, return the integer division of `numerator` and `denominator` (e.g., `return numerator / denominator`).
Replace the placeholder `??` with the appropriate code in the given code template to complete the implementation of the `main` function and the `binomial` function.
Here's the updated code template with the necessary modifications:
```cpp
#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 = binomial(n, k);
cout << "Binomial number " << n << "C" << k
<< " = " << result << endl;
return (0);
}
// ********************************************************
int binomial(int n, int k)
{
int numerator = 1, denominator = 1;
int i;
if (n < k)
{
return 0;
}
else
{
for (i = 1; i <= k; i++)
{
denominator = denominator * i;
numerator = numerator * (n - (k - 1) + i);
}
return numerator / denominator;
}
}
```
You can now compile and run this code to compute the binomial coefficient `nCk` based on user input.
To implement the binomial coefficient function, you can follow these steps:
1. Define the function prototype before the main function, as shown in the code template provided.
2. Implement the binomial function after the main function, following the pseudocode provided.
3. In the binomial function, check if `n` is less than `k` using an if-statement. If `n` is less than `k`, return 0 since it is not possible to calculate the binomial coefficient in this case.
4. Inside the else block, initialize the variables `numerator` and `denominator` to 1.
5. Use a for loop to calculate the `denominator` by multiplying `i` starting from 2 up to `k`.
6. Calculate the `numerator` by using another for loop starting from `n-k+1` up to `n`, multiplying each value with the previous ones.
7. At the end of the function, return the division of `numerator` by `denominator`.
8. In the main function, prompt the user to enter the values of `n` and `k`.
9. Call the `binomial` function with the provided values of `n` and `k` and store the result in the `result` variable.
10. Finally, print the result of the binomial coefficient calculation.
Here's the modified code template with the implementation steps explained:
```cpp
#include <iostream>
using namespace std;
int binomial(int n, int k); // function prototype
int main()
{
int n, k;
int result;
cout << endl;
// read in n & k
cout << "Enter n (positive integer): ";
cin >> n;
cout << "Enter k (positive integer): ";
cin >> k;
result = binomial(n, k); // function call
cout << "Binomial number " << n << "C" << k
<< " = " << result << endl;
return 0;
}
int binomial(int n, int k)
{
int numerator = 1;
int denominator = 1;
int i;
if (n < k)
{
return 0;
}
else
{
// Calculate the denominator
for (i = 2; i <= k; i++)
{
denominator *= i;
}
// Calculate the numerator
for (i = n - k + 1; i <= n; i++)
{
numerator *= i;
}
return (numerator / denominator);
}
}
```
Replace the `??` placeholders in the code template with the appropriate values according to the provided instructions and pseudocode. After implementing and compiling the code, you will be able to use the `binomial` function to compute binomial coefficients for given values of `n` and `k`.