lab2.dvi

CS105 Lab 2 Due 12:30 9/17/97
In this lab youwill develop a function to count using a String of digits to represent a number in
any base. In a later lab, you will have a chance to use this function as the basis for a function to
check k-colorability of a graph by enumerating all possible colorings.
Start by copying the \CS105 Pro ject" pro ject from the sample files folder in the CS105 folder on
the CS/Math server, and modify this pro ject as shown below. When you are done, rename the
folder with your name and the lab number, and drop it in the homework drop.
1. Create a function String next
digit(String digit, String k) for single-digit counting
in base k. For example, next
digit(``2'', ``4'') should produce ``3'', and
next
digit(``3'', ``4'') and next
digit(``2'', ``3'') should both produce ``0''.
2. Create a function bool carry(String digit, String k) for determining if it is necessary
to \carry" information into the next column when counting in base k. For example,
carry(``2'', ``4'') should produce false, and carry(``3'', ``4'') should produce
true.
3. Create a function String next
number(String number, String k) for counting in base
k (its ok to limit k to 4). For example, next
number(``2'', ``4'') should produce ``3'',
next
number(``3'', ``4'') should produce ``10'', and next
number(``133'', ``4'')
should produce ``200''. You can solve this problem by writing a single recursive function
(if you are already familar with using loops in C++, you are allowed to use a loop instead,
but we won't be covering this topic in class for another week or two). Note that the result
of counting can be defined recursively as:
 the concatenation of all but the last digit with next
digit(last
digit, k) if
carry(last
digit, k) is false, and
 the concatenation of the next number after the number represented by all but the last digit,
with a \0", if carry(last
digit, k) is true.
For example, if we're using base 4, the first rule tells us that the number after 312 is
the concatenation of 31 and 3; the second rule tells us that the number after 313 is the
concatenation of 32 (the number after 31) and 0.
1. Finally, your main function should read in a String representing a sequence of digits in base
4, and print out the next number in base 4.
1