CSC 180 Notes for Tutorial #6 Wednesday 23 October Monday 28 Oct designing a program for computing combinations. ================================================ In mathematics you have learned that the total number of different combinations of n numbers, taken k at a time, can be represented by C( n, k ). And you may have learned that the value of C( n, k ) is given by the formula n! / ( k! x (n-k)! ), where j! stands for j factorial, the product of the first j positive integers. Problem: You are to develop a program that asks the user to enter two integers, n and k, and prints C( n, k ). < NOTE TO TAs: Your goal in tutorial is to develop such a program in a "top-down" fashion. Try to get the students to identify the "subproblems" to be solved (and therefore the functions to be defined), what the parameters to the functions should be, and what the return type should be for the functions. Do NOT use recursion to compute the factorials! They don't know about recursion yet. > < NOTE TO TAs: Everything below that is posed as a question should be asked to the students and see if you get any interesting answers before telling them. > GIVE THEM A FEW MINUTES to think about the structure of the program ... and then try to get them to say something like .... First approach to solving the problem 1. prompt the user for integer input n and k and read it in 2. compute C(n,k) and print the result. (They will be tempted to start to calculate factorials early on, but try to stop them and suggest that "factorials" are details that they don't need at the very beginning - they are best left as details in the calculation of C(n,k).) At this point now, we have enough details to write the main program, even though we haven't specified how to compute combinations! The calculation of combinations will be left to be done in a subprogram - or function. What should the parameters to the combination function be? Well, ask yourself the question, what do you have to tell the function? We need to tell it n and k ... so these should be the parameters. What do we expect the get back from the combination function? The final result, which is an integer value. This suggests then that the prototype of our combination functions should be: int combinations( int n, int k ) Our main program can now be written: int main() { int n, k; printf("Enter n and k:"); scanf("%d %d", &n, &k); printf("C(%d,%d) = %d\n", n, k, combinations( n, k )); return 0; } Now we have a complete main program. It is short enough that we can read it through and convince ourselves that if the combinations function is written correctly, the main program will be correct. Now onto the problem of calculating combinations( n, k ). Well, we know that C(n,k) = n! / ( k! x (n-k)! ). And j! = (1)(2)(3)...(j) This is such a simple formula that it would be tempting to just write everything out now. But the factorial is a math function, and we use it three times in calcualting C(n,k). If we just wrote out the program at this stage, we would end up writing out the statements for computing factorials 3 times. The would be rather tedious, and it invites errors to crop in, because the more times you repeat something, the more likely you are to make a careless error. This suggests that we should write a separate function for computing factorials. What do we need to tell the function? Only the number whose factorial we want to compute. This suggests that our factorial function will only have 1 parameter - lets call it j. What do we need to get back from the factorial function? The value of j! This suggests that we need to return an int value, and the prototype of the factorial function should be: int factorial ( int j ) Now we are in a position to write the combinations function. We can simply write: int combinations( int n, int k ) { return factorial( n ) / ( factorial( k ) * factorial ( n-k ) ); } NOTE: We need to be careful with the grouping in the denominator a/b*c means (a/b)*c not a/(b*c) Since we want a term of the form a/(b*c), we need to use parentheses to group the terms properly. But: Why don't we need to convert to floating-point numbers to get the division correct? Because the result is integer. Have we forgotten anything? Yes. What if n or k are negative? The factorial function isn't defined for negative parameters. It makes sense to define C(n,k) = 0 when n and/or k are negative, since we can't choose a negative number of items or choose from a negative number of items. Have we forgotten anything else? Yes. What if k is bigger than n? We would ask for a factorial of a negative number. k are negative? For this reason, we should update the combinations function to read: int combinations( int n, int k ) { int result; if ( (n < 0) || (k < 0) || (n < k) ) { result = 0; } else { result = factorial( n ) / ( factorial( k ) * factorial ( n-k ) ); } return result; } (The variable result is introduced so that we can avoid having multiple return statements in the function.) Now we need to fill in the details on the factorial function, which has the prototype int factorial( int j ). At this point, we can fill in all of the details, because we have a simple math formula for computing factorials. We need to accumulate the products of the first j positive integers. We can write: int factorial( int j ) { int product = 1; int i; for ( i=1; i<=j; i++ ) { product = product * i; } return product; } Note: Product accumulators are initialized to 1, while sum accumulators are initialized to 0. (There is another way to calculate factorials that we will talk about later that uses a technique called recursion.) Altogether, then, we have the complete program: int factorial( int j ) { int product = 1; int i; for ( i=1; i<=j; i++ ) { product = product * i; } return product; } int combinations( int n, int k ) { int result; if ( (n < 0) || (k < 0) ) { result = 0; } else { result = factorial( n ) / ( factorial( k ) * factorial ( n-k ) ); } return result; } int main() { int n, k; printf("Enter n and k:"); scanf("%d %d", &n, &k); printf("C(%d,%d) = %d\n", n, k, combinations( n, k )); return 0; } Note: the functions have gone into the file in such a way that a function is defined before it is used. If you prefer to have the main function first, you can do so, but you should put the prototype declaration: int combinations( int, int ); int factorial( int ); before the main function in the file. 2. designing test cases for testing the program in 1. ===================================================== Now that we have a program for computing C(n,k) how should we test it to verify that it is a correct program? GIVE THEM A FEW MINUTES TO THINK ABOUT TEST CASES. We could test it with random values of n and k, but that would not convince us that the program works for "difficult" cases that may not crop up under random testing. We need to ask ourselves: what sorts of values can n have? And then what sorts of values can k have? And then generate test cases from the cross product of the cases. We have : (1) n can be less than 0 (2) n can be 0 (3) n can be greater than 0 And then (A) k can be less than 0 (B) k can be 0 (C) k can be greater than 0 (D) k can be equal to n (E) k can be less than n (F) k can be greater than n This suggests 18 different test classes: (1,A), (2,A), (3,A) (1,B), (2,B), (3,B), etc. Specific examples would be: -1 -1 0 -1 1 -1 -1 0 and so on. It would be tedious to type all of the input into the program in an interactive mode. For this reason, you could type all of the test cases into a file, named say, test_data. The file can be given as input to the file by using the command: % a.out < test_data The < symbol means take all of the data from the given file instead of interactively from the keyboard. If you have much time left, try to develop an other algorthm with them in a top-down fashion for solving a favourite problem of yours.