D100 Programming Exercises 4

Tutorial Deadline: Mon, 31st October 2005, Hand-in Deadline: Tues, 1st November 2005.

Purpose: More programming practice: working with files, abstraction using methods and top-down programming.



Marking: The question sheet is binary marked PASS or FAIL.
The deadline for each coursework is the day of your tutorial session. One question from the set of core questions will be chosen and announced shortly before the session, which you must print out and bring to the tutorial for peer marking and discussion. After the tutorial, you will have until the next day (Tuesday – 12 noon) to address any issues that were raised in the tutorial session and adapt your code accordingly. Then hand in a final version of that question only for marking to JJ in the departmental office.

Do your printing on the laser printer (a4ps) Staple the sheets together with a completed coursework cover sheet at the front.

NOTE: You must keep all marked work as it forms a record of your progress. At the end of the course you are required to re-submit all work.

See the additional notes on the web about file IO.

Example Questions and Answers

The following are examples of questions and answers, to show how the Java syntax works, and to illustrate the kinds of programs you should be writing. There are further examples in the text book.

Example 4.1 Write a program that inputs an integer, calls a method to find the sum of the integer's digits, and displays the result.

Hint: % is the division operator that returns the remainder. The expression a%b returns the remainder when a is divided by b. Try using it to divide by 10.

Answer: 

 
/**
...
 */
public class SumDigits 
{ 
  public static void main(String[] args) 
  { 
    KeyboardInput in = new KeyboardInput(); 
    System.out.print("Type an integer: "); 
    int n = in.readInteger(); 
    System.out.print("The sum of the digits of: " + n); 
    System.out.println(" is: " + sumOfDigits(n)); 
  } 
 
  public static int sumOfDigits(int n)
  {
    int sum = 0; 
    n = Math.abs(n); 
    while (n > 0) 
    { 
      sum += n % 10; 
      n /= 10; 
    } 
    return sum;
  }
}

Does the program work correctly with negative integers? Copy, compile and run the program to find out.

Example 4.2 Write a program that asks for the name of a text file, reads each line of text in the file, and displays the text on the screen.

 
/**
...
 */
public class PrintFile
{
  public static void main(String[] args)
  {
    KeyboardInput in = new KeyboardInput() ;
    System.out.print("Enter filename: ") ;
    String filename = in.readString() ;
    FileInput fileIn = new FileInput(filename) ;
    String s = fileIn.readString() ;
    while(!fileIn.eof())
    {
      System.out.println(s) ;
      s = fileIn.readString() ;
    }
    fileIn.close() ;
  }
}

This uses the FileInput class (see the notes or web page).

Example 4.3 Write a program that uses a method to display a multiplication table, given an integer between 2 and 12 inclusive. The program should ask the user which table to display and reject any invalid request.

Notes: With most of the previous exercise programs you only really thought and planned in terms of a single statement sequence. However, now you know how to write methods, you want to update your strategy and first consider the design in terms of methods.



Here is list of steps for designing a method:
1. Write the javadoc comment to go before the method. What does the method do?
2. Write down the input to the method (in English). What information does the method require to do its job?
3. Write down the result of the method (in English). What, if any, answer do you want the method to give you back?
4. Write down the method declaration. The list of parameters comes directly from (2) above - they are the input to the method. The return type comes directly from (3) above - it specifies the type of the output from the method.
5. Finally, implement the body of the method.

Another important method design principle is that each method should be cohesive — that is, it should focus on doing one, and only one, well-defined chunk of behaviour needed by the program. Following this principle, the main method can focus on initializing the program and then calling other methods one by one according to a high-level sequential description of the program.

Lets think what methods we might use to break the task in Example 4.3 down. There are two distinct tasks here that we can perform sequentially:
i) Get a number from the user.
ii) Print out the multiplication table for that number.
This immediately provides a structure for our main method if we encapsulate these tasks into separate methods.

Now lets use our design steps to write a method to perform the first task:

1. What does the method do?
Reads an integer between 2 and 12 from the user.

2. What is the input to the method?
The method needs no information to perform its task.

3. What is the output of the method?
The method should return the value input by the user, which is an integer.

4. What is the method declaration? 

 
public static int getMultiplier()

5. Implement the method.

See full program listing below.

Try following the same steps to design the method for the other task and see how close you get to the other method in the full listing below.

Rather than having to consider the entire statement sequence in the program at one go, we are now concerned only with small portions at a time. This has divided a larger and more complex design problem into a collection of smaller, and more easily designed, components. Further each component has a well-defined interface by which it connects to other components. The interface is the name of the method and its parameter list, i.e. the number and types of the parameters. The design of each method is now straightforward. Method printTable needs a loop and output statements to display a multiplication table, while getMultiplier asks the user to enter a value and checks it is within the supported range. If it is, the value is returned, otherwise an error message is displayed and the user is asked for another value. 

 
/**
...
 */
public class MultiplicationTable 
{
  public static void main(final String[] args) 
  {
    int multiplier = getMultiplier();
    printTable(multiplier);
  }
 
  /**
   * Reads an integer between 2 and 12 from the user.
   */
  public static int getMultiplier() 
  {
    KeyboardInput in = new KeyboardInput ();
    System.out.print("Which table (2-12)? ");
    int x = in.readInteger();
    while ((x < 2) || (x > 12)) 
    {
        System.out.println("Cannot display that table, try again");
        x = in.readInteger();
    } 
    return x;
  }
 
  /**
   * Displays multiplication table for n.
   */
  public static void printTable(final int n) 
  {
    int counter = 1;
    System.out.println("The " + n + " times table");
    while (counter < 13) 
    {
      System.out.print(counter + " x " + n);
      System.out.println(" = " + counter * n);
      counter = counter + 1;
    }
  }
}


Example 4.4 Write a program that determines whether a word or sentence is a palindrome. (A palindrome reads backwards the same way as forwards, for example: ‘Able was I ere I saw Elba’.) Spaces are considered as significant.

Notes: The problem statement gives little information about designing the program, so we definitely need to do some thinking and planning before trying to write code. First of all we need an algorithm to test whether a string is a palindrome. This turns out to be easy:

make a copy of the string
reverse the order of the characters
compare the copy with the original to see if they are the same

Now that we know that it’s possible to check for a palindrome, the next step is to consider the overall sequence of events that should take place when the program runs. This gives:

 
input string to test
make a copy
reverse the copy
check against the original
display answer

Next we want to determine what methods are required and allocate behaviour to them. We could bundle everything into a single method but that would violate our cohesion guidelines. Instead, we identify the following methods:

 
String getInput() // Get the input string to be tested
void testForPalindrome(String s) // Check if s is a palindrome
boolean reverseCheck(String s1, String s2) // Is s2 the reverse of s1?
String reverse(String s) // Return the reverse of the argument String

This may seem more methods than necessary. That could turn out to be true but at this stage we are deliberately breaking the overall behaviour down into minimally sized methods to get a good feel for the design. Methods can be combined and behaviour re-allocated later if it seems appropriate.

With the methods identified, each can be considered in turn to design its method body. Method getInput is easy as it simply requests input and returns the resulting string. TestForPalindrome is also straightforward, it just needs to call the reverseCheck method with the same string for both parameter values. reverseCheck is a bit more interesting as the decision has been made to make it more general purpose than is strictly necessary for this version of the program. The idea for check is that it can actually test any two strings to see if they are the reverse of each other. TestForPalindrome will call it with the same string for both arguments since it checks for self-reversed strings. reverseCheck works by reversing one string and then doing a string comparison using the compareTo method in the String class.

This leaves reverse, which requires a bit more work. The basic strategy here is to unpack the original string character by character and reassemble the characters in the reverse order to create a new string. To find out how to extract individual characters from a string we need to return the documentation for class String. This shows that there is a method declared as char charAt(int index), which returns the character at position index, counting from 0 as the position of the first character. The String documentation also shows a method int length() that returns the number of characters in a String. With these methods we can construct a loop to access each character in turn:

 
 
// Given some String s
int position = 0;
while (position < s.length()) { // Characters run from 0 to length-1
  ...s.charAt(position) ; // Get the character and do something with i
 
        position = position + 1 ; // Move to next character
}


Building the new string requires a search of the J2SDK documentation to find a method to join a char to a String. The String class does not provide one, so we start looking at other classes. It turns out there is a class Character, whose objects represent characters, that can be used to create a String from a single char using an expression like:

 
// Given a char c
... new Character(c).toString() ...

The toString() method converts from a Character object to a String object. The two strings can then be concatenated using the + operator.

We now have all the pieces ready to write the program. However, a review of the problem statement to check we are still answering the right question highlights a problem: the sample palindrome is only a palindrome if the case of the letters is ignored, if the case of the letters is significant then the sample string is not a palindrome. If our current design was applied to this sample string, it would not be accepted as a palindrome. Given that the string was supplied as an example of a palindrome, it must be that case is not significant. We therefore need to address this in our design.

The answer to the problem is to convert all the characters in the input string to lower case before testing to see if it is a palindrome. A further search of the String class documentation provides the solution in the form of a method declared as String toLowerCase(), which returns a lower case version of the string it is called for. Calls to the method can be inserted appropriately to cause case to be non-significant.

 
/**
...
 */
public class Palindrome 
{
  public static void main(final String[] args) 
  {
    testForPalindrome(getInput()) ;
  }
 
  /**
   * Does the palindrome test and displays the result.
   */
  public static void testForPalindrome(final String s) 
  {
    if (reverseCheck(s.toLowerCase(), s.toLowerCase())) 
    {
      System.out.println("String is a palindrome.") ;
    } 
    else  
    {
      System.out.println("String is not a palindrome.") ;
    }
  }
 
  /**
   * Checks to see if the two argument Strings are the reverse of each
   * other. Returns true if they are and false otherwise..
   */
  public static boolean reverseCheck(final String s1, final String s2) 
   {
    String s = reverse(s2) ;
    if (s1.compareTo(s) == 0) {
      return true ;
    } 
    else  
    {
      return false ;
    }
  }
 
  /**
   * Returns a String which is the reverse of the argument String
   */
  public static String reverse(final String s) 
  {
    String result = new String() ;
    int position = 0 ;
    while (position < s.length()) 
    {
      result = new Character(s.charAt(position)).toString() + result ;
      position = position + 1 ;
    }
    return result ;
  }
 
  /**
   * Gets user to input a String.
   */
  public static String getInput()  
  {
    KeyboardInput in = new KeyboardInput () ;
    System.out.print("Enter text to check: ") ;
    return in.readString() ;
  }
 
}

Core questions

Q4.1 Write a program that consists of the following methods:

Q4.2 Write methods to do the following:

Include the methods in an interactive program that lets the user select which conversion to perform, and then inputs a value and displays the result.

An interactive program means one that displays a simple text menu, such as:

1. Convert inches to centimetres
2. Convert yards to metres.
3. Convert miles to kilometres.
4. Quit

and then asks the user to type in a value from 1 to 4 to select which action to take. A loop will continually redisplay the menu until the user selects Quit (number 4) to terminate the program.

Notes: The conversion methods should take the value to be converted as a parameter and return a result. They should not do any input or display the result. Add additional methods if they will help structure the program.

Q4.3 Write a program to input an integer and display the result of calling a method that takes an integer parameter and returns the value formed by swapping each pair of digits in the parameter, starting from the least significant. For example, if the method is called with 232563 it would return 325236, or 1804982 returns 1089428. In the second case, the most significant digit, the "1", has no digit to swap with so remains in the same position. The method that performs this operation can be broken down further into three operations:

Hint: Look at example 4.1. You can break down or build up an integer by dividing or multiplying by 10.

Q4.4 Write a program to read in a positive integer, n, and a file name, then generate n random integers in the range 1 to 10 inclusive, and write out n, followed by all the random numbers to a file with the specified file name. The format of the file should look like this:

n
random number 1
random number 2
:
:
random number n

Use the FileOutput class to open and write the file. Read the documentation to see how it is used.
Don't forget to use methods to organise the code in your program.

Hints: Using FileOutut is similar to using KeyboardInput. Copy the text into a file called FileOuput.java and compile it to create FileOutput.class.
The .class file needs to be in the same directory as the program you are working on. Copy FileOutput.class to all directories containing programs that need to use it.
The way to generate random numbers was shown in exercises 3.


Q4.5 Write a program that reads in a text file and prints it out with all occurrences of the sequence of characters "int" replaced by "long".

Adapt your program so that the name of the file, the string to be replaced and the replacement string are all specified on the command line. Flags should tell the program which argument is which so that:

% java ReplaceString -f Program.java -r int -w long

prints out the text file Program.java with all occurrences of "int" replaced by "long", as does:

% java ReplaceString -w long -r int -f Program.java

Q4.6 Write a program that asks for the name of a text file, then counts the number of characters, words and lines in the file and finally displays the result. As always, identify and use appropriate methods.

Q4.7 Write a program that inputs a double value and displays the sum of its digits.
Don't forget to use methods to organise the code in your program.

Q4.8 Write a method to test if an integer of type long is a prime number. The method should return a boolean value. Test your method by writing a test program that reads an integer typed at the keyboard and states whether the integer was prime.

Using your prime method, write a program that finds as many of the prime numbers that can be represented by an integer of type long as you can. What is the limitation?

Notes: This is not quite as easy as it might appear, especially if you want the program to produce results quickly. Search the web for information about prime numbers and algorithms for finding them - there are some excellent web sites.

Additional Questions

Q4.9 Write a program that asks for a URL and displays the raw text of the corresponding web page. Hint: Check out class URL in the Java documentation.

Q4.10 Modify the drawing program from Q3.10 to save and load drawings.
Hint: You will need to store details of the shapes that are displayed in a data structure as they are drawn. The data structure can then be loaded and saved.

Q4.11 The Mandelbrot set is defined to be the set of complex numbers, c, for which the series, z(j), j = 0, 1, 2, ... does not diverge, i.e., become bigger and bigger and bigger as we increase j. The series z(j) is defined by the following iterative relationship between consecutive elements of the series:
z(j+1) = z(j)*z(j) + c. And
z(0) = 0 + 0i
Use methods and top down programming to produce a plot that illustrates this set using the drawing techniques you have learnt, by associating each point in your drawing window with a particular complex number c and filling that point in if c belongs to the Mandelbrot set.

Hint 1: a complex number can be represented by two double's, a and b, so that for example, c = a + bi, where i is the square root of -1. Multiplication of two complex numbers (a + bi) and (c + di) gives another complex number (or pair of real numbers): (ac - bd) + (ad + bc)i. You could write two methods one that computes the real part of the multiple (ac - bd) and one that computes the imaginary part (ad + bc), or you could read ahead on classes and objects and do it properly... for now the former is fine.

Hint 2: A simple test of divergence is to choose a fixed real valued number T and then see if the modulus of z(j), for any j less than some integer N (e.g. 100), is greater than T. In fact it can be shown mathematically that if any z(j) is greater than 2 then the series will diverge, so here we can set T equal to 2. If there is a z(j) greater than T (note that you can stop calculating as soon as you find one) then assume the series diverges, if not assume it doesn't so c is in the Mandelbrot set.

Hint 3: A sensible range over which to plot the set is all the complex numbers with both real and imaginary part between -2 and +2.