New Page 1

Program 2 - January 22

For the second programing assignment, we will focus on procedural programming in C++, using the features that make it a "better C". In doing this use standard programming techniques (not classes) but try to use some of the other new features of C++ we have discussed in class.

Main Assignment

Choose one of the following assignments from the text. Of course, you're always free to do several of them. In each case, read the problem description in the textcarefully, since it includes some hints as to how to proceed. I give some hints here, but I won't repeat what the text already tells you.

Since these programs are more complex than the first one, you may choose to use multiple files for your code. You can either zip the files together or attach all the files to your email. However, if you do more than one problem, and there are multiple files in some of them, please send me separate emails.

Exercise 4.24 (Knight's Tour)

This is a great exercise in array manipulation as well as problem analysis. The text doesn't specify what output to produce, but you should at least display the array of moves you were able to make. Show the layout of the board with numbers representing the first location, second location, etc. and print out how many moves you were able to make.

In the access method, you can calculate the array of accessible squares manually and type it in your program. A better approach would be to have the program initialize it by looking at each square and calculating how many other squares are accessible from it.

For extra credit, you may also do 4.25 or 4.28.

Exercise 4.26 (Eight Queens)

Another exercise in use of arrays and logical thinking. For output, display an 8 by 8 array with a 'Q' showing where the queens are and a '+' or '*' for the empty squares.

For extra credit, you may also do 4.27 or 4.35. Exercise 4.35 - solving the problem recursively - is a bit of a challenge. One approach would be to use a recursive descent algorithm - similar to what is used in playing chess. What this means is that for each Queen (1 to 8) you will pick a square which allows winning and not one that fails. Write a routine that takes the queen number, row and column and returns true if the move wins the game. The routine should try placing the Queen on each available square and return true if the game is won. Of course, the routine will only be able to give a direct answer for the eighth queen. For anything else, it will need to make a series of recursive calls for the next queen, and so on. For more extra credit, you can translate this recursive routine into a very simple iterative routine that solves the problem.

Look at each square and

Exercise 5.35 (Pig Latin)

This exercises all of your knowledge of string processing. You will need to read in a sentence, split it into words using strtok, translate each word using the rules of Pig Latin, and output the translation. You can make the program better by allowing users to enter multiple line sentences - terminate input by scanning for a period, or by getting an empty line. For extra credit, allow translation to work both ways.

Exercise 5.46 (Writing a Check Amount in Words)

This is harder than it seems at first glance. The rules for word display of numbers are fairly complex. You will need to set some maximum size that you handle (at least a billion) and maintain an array of multipliers and values for the three digit groups - a thousand, a million, a billion, etc. Note that there is lots of room here for subdividing into functions. For example, to write out
One Hundred Seventy Three Thousand Five Hundred Twelve
the two parts in bold ought to be calculated by the same routine. You can do this either recursively or iteratively.

Hint: First decide how many special cases there are and draw a diagram of how your functions will call one another.

Hint: How do you validate input of numbers? In a real-world program, we would probably have a set of records with amounts already in them, rather than allowing a user to type things in. The data entry would normally be done using some sort of UI that allows users to type values into boxes (e.g. Windows). Here are three approaches you can take to simulating this with C++ stream I/O:

Read in a line as a string and then parse and validate it yourself, giving appropriate error messages (not necessary for this assignment)
Read the line as a string and ignore anything following the number - i.e. use atod or atol. Invalid input will give you a zero value - just give a message and try again
Use stream input to read in a number followed by the rest of the line as a string - which should be empty.

Special Assignment

The following assignment is suggested to those who didn't "get" the recursive function assignment we did last week. Think of it as a second chance. Note however, that you can't do this one without also doing one of the main assignments.

Exercise 4.32 (Palindromes)

What's recursive about a palindrome? Well, if the first and last letter match, and either there is nothing between them or what is between is also a palindrome, then we have a palindrome.