CS201 – Spring 2001

Prof. Hartman

Homework #6

Due Friday, March 9th by 4:00 pm

Recommended Self-Review problems in Chapter 4, pp291-292: 4.1-5 (yes, all of them)

Homework to be turned in (remember that all programs must follow the guidelines from handout #3.

1. (20 pts) Finding Primes - The following is an easy method of finding all primes from 1 to n.

a) Create an array with all elements initialized to 1 (1 means "might be prime"). Any number that is prime will have a 1 in its subscripted element when the method ends. If an element has a 0 with the method ends, then the corresponding number is a multiple of some smaller number.

b) Starting with the element with array subscript 2, every time you find an element that has value 1, loop through the rest of the array, turning all multiples of the subscript to 0.

For example, there will be a 1 in the array element with subscript 2, so we set all the later elements with subscripts that are a multiple of 2 (subscripts 4, 6, 8, 10, etc.) to 0.

Next we see that the element with array subscript 3 has a 1 in it. So we set all the later elements with subscripts that are a multiple of 3 (subscripts 6, 9, 12, 15, etc.) to 0.

Array element 4 is 0, so we skip it and go on to element 5, etc.

When you have completed this process for every element in the array, all subscripts (starting with 2) whose element contains a 1 are prime; those that have a 0 are not prime.

Create a program that uses this algorithm to print all primes from 1 to n, where n is a number the user enters. Try the program on 100, and include this run in your sample runs.

2. (20 pts) TIC-TAC-TOE

Create a program that will allow 2 users to play tic-tac-toe with one another. The program should alternate between the X-player and the O-player, giving them one turn each until either player has won or the game ends in a tie. Players will enter their coordinates as two integers in the range 0-2 (or 1-3, however you have your columns set up) where the first number is the row coordinate and the second is the column. The program should check for a winner or a tie at the end of each move by each player.

The program should also output the tic-tac-toe board after each move before asking for input. If a space is empty on the board, your program should output a space. An example of the output might be

...
 
X O
 X
X O O
 
Player X enter row and column coordinates: 0 1
 
X X O
 X
X O O
 
Player O enter row and column coordinates: 1 2
 
X X O
 X O
X O O
 
Player O wins!
 

3. (10 pts) Reverse a string

Write a program that will allow the user to enter a string, and then print it out in reverse order. (Even if you already know C and know of functions that will help you here, do not use any of them. I want you to do this completely on your own. You may use cout and cin only.)