Nested for-loops
The following function takes an integer n, it prints all size two
subsets of {0, 1, ..., n-1}.
If n < 2 it prints nothing.
//PRE: n > 1.
//POST: All size two subsets of {0, 1, ..., n-1} have been printed on
// the standard output.
void print_two(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
cout << "{ " << i << ", " << j << "}" << endl;
}
}
}
}
Implement and test the function to convince yourself that it works.
Improve
Improve the function print_two so that it doesn't need the if-statement. It should only use the doubly nested for-loops. Make sure it only prints sets of size two. The set {0,0} is a set of size 1.
Does the outermost for-loop need to go from 0 to n-1?
Chris thinks the number of size two subsets of {0, 1, ..., n-1} is the same
as the number of handshakes required for n students to meet.
Do you think so? If so, can you give an intuitive argument why they are
the same?
Recall, from the previous lab, the number of handshakes is n(n-1)/2.
Add code to print_two() to see if this is true. You can do this by creating a
variable in the function that counts the number of sets printed. Once it's
done printing, you can compare this value with the formula to see if the results
match.
Triple
Analogous to print_two create a function called print_three. Using a triply nested for-loops, it should print all size three subsets of {0, 1, ..., n-1}. Be sure to have appropriate PRE and POST comments.
I'm sure you can imagine how to print all subsets of size 4, 5, and so on. Later in this course we will learn a powerful technique called backtracking. With backtracking we can print subsets of arbitrary sizes without using nested for-loops.
Base n
Implement a function called print_base_n. This function should take two integers n, b.
It returns nothing, but prints the number b. The function need only
work for base 2 to 10. Make sure you indicate this limitation as a precondition. What other conditions
should be added to your precondition?