CSc 301 Lab Programming Problems


Problem L1

Write a program to compute the greatest common divisor (GCD) of two integers.  The GCD is the largest integer which evenly divides both numbers.  That is, for two numbers I and J, the GCD is the largest number which produces a zero remainder when divided into both I and J. For example, the GCD of 21 and 35 is 7.  Your program should read two whole (non-zero) numbers per line from standard input (without prompting) and send the GCD to standard output, one per line. Process all lines of input until standard input is closed.

Problem L2

One method for determining prime numbers is called the Sieve of Eratosthenes.  Write down as many integers as you want to process, say 1 to 100.

    1  2  3  4  5  6  7  8  9  10 ...

Starting at 2, we know every multiple of 2 is not prime, so cross out every second number. This gives us

    1  2  3  4  5  6  7  8  9  10   ...

Then move to the next not crossed out number, 3. Cross out every multiple of 3.

    1  2  3  4  5  6  7  8  9  10   ...

Move to the next not crossed out number, 5. Cross out every fifth number, and so on. When you reach 50, the numbers not crossed out are prime. Write a program to implement this algorithm to find the primes from 1 to 100 using an array.  Output the primes on one line with a single blank between each number.

Problem L3

One classic method for composing secret messages is called a square code.  The spaces are removed from the english text and the characters are written into a square (or rectangle).  For example, the sentence "If man was meant to stay on the 
ground god would have given us roots" is 54 characters long, so it is written into a rectangle with 7 rows and 8 columns. 

                ifmanwas
                meanttos        
                tayonthe
                groundgo
                dwouldha
                vegivenu
                sroots

The coded message is obtained by reading down the columns going left to right.   For example, the message above is coded as:

imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn  sseoau

In your program, have the user enter a message in english with no spaces between the words.  Have the maximum message length be 81 characters. Display the encoded message.   Your program should read the message on one line from standard input (without prompting) and send the results to standard output.
Here are some more examples:

haveaniceday
hae and via ecy
feedthedog
fto ehg ee  dd
chillout
clu hlt io

Problem L4

An n x n matrix that is filled with the whole numbers 1, 2, 3, .. n2 is a magic square if the sum of the elements in each row, in each column, and in the two diagonals is the same value.   Here is a magic square where n = 3:

8
 1
 6
3
 5
 7
4
 9
 2

Write a program that reads n2 numbers from standard input and tests whether they form a magic square when put into matrix form.  The value of n is NOT an input to the program; n must be determined from the number of inputs.

For example, the input that creates the example matrix above is   8 1 6 3 5 7 4 9 2.

The output is a single word, "true" if the input produces a magic square, "false" otherwise.

Your program may assume that each input token is a whole number.

Your program must verify:
  1. The proper number of input values was provided.
  2. Each of the numbers between 1 and n2 occurs exactly once in the input.
  3. When the numbers are arranged in a matrix,
    1. the sum of the rows,
    2. columns,
    3. and diagonals
      must be the same value.

Provide four test cases; one where each of criteria 1,2,3 above fail, and one where they all pass.


Problem L5

Write a program that reads a value of n from standard input and generates a magic square of n x n size. Begin by placing a 1 in the center square of the top row, then incrementally placing subsequent numbers in the square one unit above and to the right. The counting is wrapped around, so that falling off the top returns on the bottom and falling off the right returns on the left. When a square is encountered that is already filled, the next number is instead placed below the previous one and the method continues as before.  (Described here as "the Siamese method.")

Your program may assume the input is an integer.  This method only works for positive odd numbers, so if the input is invalid, do nothing.

Send the results to standard output, one row of the square per line, with one blank between numbers.


Problem L6

Write a program will read time log data and create a summary of times in each phase and the total time.

09:27 10:03   30    DESIGN   initial design
14:29 15:03   34   CODE        code method one
19:19 19:34   14   CODE   code method two
12:16 13:18   62   COMPILE    two errors
16:42 16:50   8    COMPILE  
07:48 11:01   193    TEST      unit testing
00:00 00:00  -10   Interrupt  
17:57 18:34   37   TEST      system testing

A time log contains blank delimited fields:  start time, stop time, delta time, phase, and an optional comment.

The input is read from standard input.  Your program may ignore the first two fields and the comment.

The output is an alphabetically ordered list of phases and the total time in that phase.  The last time shows the total time in all phases.  A single blank separates the phase name from the number of minutes.

CODE 48
COMPILE 70
DESIGN 30
Interrupt -10
TEST 230
TOTAL 368

Unfortunately we don't know in advance what the phase names are or how many there might be.  So create them dynamically as the input data is processed. (You may assume there will NOT be a phase named "TOTAL").


Problem L7

Chocolate Bar Weights

Problem L8

Write an application to compute the results of an election.

The input to the program is the number of votes for each of c candidates in p precincts, where  1 < c < 10 and 1 <= p < 256.

Input is read from standard input.  Each line of input contains the precinct number in the first field, followed by the votes for each candidate (in order). The precinct data is unordered.

Write a program to do the following:

a. Read the raw vote totals from standard input that contains one line for each precinct. You may assume the input data is correctly formatted.

b. Display a neat table with headings that organizes the data so it is sorted by precinct number.

Each candidate is identified by an upper case letter, starting at 'A'. The vote counts should be right-justified.
Example:

          Candidate  Candidate  Candidate  Candidate
Precinct      A          B          C          D
  21         192        48         206        37
  35         186        12         121       218
  64         114        21         408        39
  65         267       113         382        29
  72         147        90         312        21


c. Compute and display the total number of votes received by each candidate and the percent of the total votes cast.
Example:

Candidate   Votes     Percent
  A          906        31%
  B          284        10%
  C         1429        48%
  D          344        12%


d. If any one candidate received over 50% of the votes, the program should print  a message declaring that candidate the winner.

e. If no candidate received 50% of the votes, the program should print a message declaring a run-off between the two candidates receiving the highest number of votes; the two candidates should be identified by their letter names.

Problem L9

Jolly Jumpers



Problem Z1

Write a program to read a list of whole numbers.  Find the product of all the positive numbers, the sum of all the negative numbers, and the count of the number of zeros. Your program should read the list of numbers from standard input (without prompting), one per line. The results are sent to standard output.  Order the results: product, sum, count and leave one blank between them. Assume the input contains only whole numbers, and the number begins in the first column of each line.


Problem Z2


Implement the following class and its one static method.

public class DaysInFebruary
{
/** Calculate the number of days in February of a given year, considering leap years. The Gregorian calendar uses the following rules to determine a leap year:
Every year that is exactly divisible by four is a leap year, except for years that are exactly divisible by 100; the centurial years that are exactly divisible by 400 are still leap years. For example, the year 1900 is not a leap year; the year 2000 is a leap year.

@param year integer representing calendar year.
@pre 1582 <= year <= 10000
@return integer value of number of days in February
*/
public static int calculate(int year)


Problem Z3

Recall from number theory, a composite number is one that is not prime.

Write a method to find the longest run of consecutive composite numbers between two integers (inclusive).

Name your class LongRun. There is one public method:

public int findLongestRun(int start, int end)

This method returns the length of the longest run of consecutive composite numbers between start and end.

Here are the first thirty positive numbers with prime numbers underlined, to help you visualize the problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

For example, the longest run between 7 and 13 is 3 (the sequence 8-9-10).

Assumptions:
    start > 0
    end > start