Algorithm for Binomial Numbers
Task
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:
Because binomial numbers are integers, the return type should be int, and the two parameters, n and k, are also integers.
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
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.
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) */<![endif]>
{
int numerator, denominator ;
int i ; // needed to compute numerator & denominator <![endif]>
if (?? Write if-test)
{
return(??) ;
}
else
{
denominator = ?? ; // initial value <![endif]>
for (i = ?? ; i <= ?? ; i = i+1)
denominator = ?? * ?? ; <![endif]>
write code to compute numerator, along similar lines<![endif]>
return (??) ;
} // else
}
Heh i have thes ame problem
really nice 10Q a lot
ou need to perform the following actions for this CheckPoint assignment:
- Modify the Inventory Program by adding a button to the GUI that allows the user to move to the first item, the previous item, the next item, and the last item in the inventory. If the first item is displayed and the user clicks on the Previous button, the last item should display. If the last item is displayed and the user clicks on the Next button, the first item should display.
- Add a company logo to the GUI using Java graphics classes.
The given pseudocode is for a function that computes binomial coefficients, which are represented as nCk and are important positive integers in computing and mathematics. The function takes two inputs, n and k, and returns the corresponding binomial coefficient.
To implement this algorithm in C++, you can use the provided code template. Here are the steps to modify the code template to compute the binomial coefficient:
1. Replace the question marks with the appropriate function call:
```cpp
result = binomial(n, k);
```
2. Implement the binomial function below the main function. Update the function signature to specify the return type and include the parameter types and names:
```cpp
int binomial(int n, int k)
```
3. Add the missing if condition in the binomial function to check if n is less than k. If true, return 0:
```cpp
if (n < k) {
return 0;
}
```
4. Compute the denominator by initializing it with 1 and then multiplying it with consecutive numbers from 1 to k inside a for loop:
```cpp
int denominator = 1;
for (int i = 1; i <= k; i++) {
denominator *= i;
}
```
5. Compute the numerator by initializing it with (n-k+1) and then multiplying it with consecutive numbers from (n-k+2) to n inside a for loop:
```cpp
int numerator = n - k + 1;
for (int i = n - k + 2; i <= n; i++) {
numerator *= i;
}
```
6. Return the result of integer division of numerator by denominator:
```cpp
return numerator / denominator;
```
With these modifications, the code will compute the binomial coefficient and print the result.
To test the program, you can design a test suite by considering various test cases with different values of n and k. For example, you can test with small values like n=5 and k=2, and larger values like n=10 and k=3. Validate the output of the program with the expected binomial coefficient obtained manually.