CS 113

HOMEWORK 2

Due: Friday, September 8, 2000

WARNING: The input for all the programs should be just asking for numbers or phrases, without the program printing anything (except the output of course); so do not print something like "Give me three numbers>", before you ask for the numbers.

In this problem you are to generate a triangular wave form according to specified numbers.

The input will contain three integers (K, L, M). The first one is the number of peaks. The second is the "inter-peaks" height. The third one is the peaks height. Look at the sample for more details.

0<K<10
1<L<10
1<L<=M<10

For the output of your program, you will be printing wave forms as show in the example. No blank lines, leading or trailing space should exist.

5 3 5

#
##
###
####
#####
####
###
####
#####
####
###
####
#####
####
###
####
#####
####
###
####
#####
####
###
##
#

2
2
2

#
##
##
#

Note: These represent two executions of the program.

Write a program which outputs, for each given integer N, N greater or equal than 1, less or equal to 300, the ascending sequence of all reduced fractions from [0,1] having the denominator not greater than N. A fraction is reduced if its nominator and denominator are relatively primes. The input will be a series of integers N. The output should be as in the example.

Note: By giving 0 (or negative numbers) as input the program should end.

Input	Output
6 7 0	N=6 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1 --- N=7 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1 ---

Note: This represents a single execution of the program.

This problem is somewhat difficult. To make it easier I intend to give the algorithm for solving it in class; if I forget to do so next Monday remind me... I want to give people who want to figure out the algorithm by themselves a chance to do so over the weekend. 

3. Crypto

Assume that we place all English capital letters into a 5x5 matrix as follows (M & N both cover the central square):

If we rotate the matrix 90 degrees clockwise then we get a 5x5 matrix on which the letters are placed on different spots than they originally were.

We define a mono-alphabetic cryptographic system as follows:

• for each letter (except M and N) we substitute each letter by the letter that moves into its place when the matrix is rotated 90 degrees clockwise. E.g. we substitute A by V, I by G etc.
• for M and N we just substitute one for the other.

So as an example assume that our original word was MOTHER; it becomes NHILAT when encrypted with this mono-alphabetic substitution function.

Write a program that reads encrypted text and outputs the original text. The input should contain the number of lines that are to be read at the beginning, followed by the encrypted text.

Note that only capital letters should be encrypted and decrypted; the rest of the symbols should remain the same!

Here is some sample input and output:

SAMPLE EXECUTIONS OF THE PROGRAMS