Assignment 3 - Calculating Combinations
This assignment will give you a chance to work with loops.
Description of Calculating a Factorial
The first task in this assignment is to figure out how to use a for-loop to calculate a factorial. Consider calculating 4!.
4! = 1 x 2 x 3 x 4
How can we use a loop to compute this? Consider the following integer variable fact:
int fact = 1;
and the loop control variable i, in the following for-loop
for (int i = 1; i <= 4; i++)
Keep in mind that i will take on each value 1 – 4. What can you do with each value of i in the body of the loop to “build up” the value of 4! in the variable fact? Here is the idea. Before we get to the for-loop, fact starts off as 1.
The first time through the for-loop, multiply fact by i, which has the value 1, to get the new value of
fact which is still 1 because 1 x 1 = 1.
The second time through the for-loop, i = 2. Again, multiply the value of i to fact to get the new value of fact, which is now 2 because 1 x 2 = 2.
The third time through the for-loop, i = 3. Again, multiply the value of i to fact to get the new value of fact, which is now 6 because 2 x 3 = 6.
The fourth and final time through the for-loop, i = 4. Again, multiply the value of i to fact to get the new value of fact, which is now 24 because 6 x 4 = 24.
After the for-loop ends, the variable fact contains the value of 4! How could you calculate 7! ? 12! ? Think about it. All you would have to do is make a small change to the for-loop.
Calculating a Number of Combinations
Once you know how to write code to calculate a factorial, it is easy to extend your program to calculate a numbers of combinations. But what is a combination? Consider the following example. Suppose we have 5 distinct items, let's say the letters a – e:
a b c d e
Suppose I want to pick 3 letters from the five. One way to do this is to pick a, b, and e: a b e This is called a combination of 3 items picked from 5. Note that a e b, e b a, etc all count as the same combination. Order does not matter.
The question is how many different combinations of 3 letters can be selected from the 5? The answer is 10, and here they are:
a b c a b d a b e a c d a c e a d e b c d b c e b d e c d e
There is a formula for making this calculation: the number of combinations of m things taken from n is written
C(m, n) = n!
m! (n – m)!
For our example, the number of combinations of 3 things taken from 5 is written C(3,5) = 5! = 5! = 120 = 10
3! (5 – 3)! 3! x 2! 6 x 2
Calculate the following combinations (answers provided) to make sure you understand how to use the above formula:
C (2, 7) = 21
C (4, 12) = 495
C (6, 10) = 210
Write a program called Combination.java to calculate C(5, 11). Note: we should be able to replace the numbers 5 and 11 in your program with different numbers to calculate different factorials. For example, we should be able to replace 5 with 6 and 11 with 9 to calculate C(6, 9). In fact, you are required to have these two assignment statements at the beginning of your program:
int m = 5; int n = 11;
DescriptionIn this final assignment, the students will demonstrate their ability to apply two majorconstructs of the C programming language – Fu
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of