lab3.dvi

CS105 Lab 3 Due 12:30 9/24/97
1. Create a recursive function count
up
to(cpstring start, cpstring end, cpstring k) that
will print out (using cout) all the numbers from start to end in base k. For example,
count
up
to(\132", \200", \4") should print 132, 133, and 200. You should use your functions
from lab 2 to do the counting. You should do this without using a loop, even if you
know how to use loops already. You may assume that start and end both represent valid
numbers in base k (that is, you won't get 57 base 4), that start is not after end (that is,
you won't have to count from 23 to 10), and that k will be 2, 3, or 4. Put the function call
count
up
to(\132", \200", \4") into your main function to demonstrate that count
up
to
works for this example.
2. Create a function valid
coloring(cpstring number) to see if the number represented by \number"
corresponds to a valid coloring of the map of NY, CT, RI, and MA from lab 1 (you
only have to worry about these 4 states, not the whole graph from lab 1). You can associate
a number with a coloring the way we did in lecture in the first week of class, with the rightmost
digit corresponding to node (state) 0, the next digit corresponding to node 1, etc. For
example, \1202" is a valid coloring (NY and RI can be the same color), but \1001" is not
(CT and RI must be different colors, and NY and MA must be differint colors). Have your
main function demonstrate this function by showing the results of the above two tests right
after it does the counting.
3. Create a function colorable(cpstring k) that uses the valid
coloring function to see if the graph
can be colored with k colors. This function could look a lot like your answer to Question
1, except that it checks the validity of a coloring rather that printing a number. Your
function should not depend on the actual connections in the graph (that is, if we changed
our valid
coloring function so that MA was not connected to NY or RI, colorable(\2") should
be true), but you can assume the graph will have exactly 4 nodes . You can also assume
that k will be 2, 3, or 4. Have your main function output the results of colorable(\2") and
colorable(\3").
0 1 2 3 0 = NY 1 = CT 2 = RI 3 = MA