Problem Solving in Java, Part I

Introduction

The past labs involving Java have examined some mechanics of Java classes and objects. This lab takes a fresh look at the role of these classes and objects in solving problems. The lab also utilizes simple input in Java and introduces the syntax for conditionals and some loops in Java.

Example: Piles of Magazines and Bills

In an early lab on object-oriented programming, we studied a stack as a simple example of a class or abstract data type. The reading for this lab expands this discussion of stacks to issues related to Java. The reading also mentions that Java has a built-in Stack class, and this is described through on-line documentation at http://java.sun.com/j2se/1.4.2/docs/api/index.html.

Program StackExample.java shows a simple example of Stacks used in Java.

1. Copy the Java program StackExample to your account, compile and run it, and check the output.

2. In the Java code, three items are pushed onto the billPile, but the program tries to pop four items from the stack. Explain what happens.

3. Compare the various sections of the Java code with the corresponding main sequence of events for the Scheme lab.

   1. stackExample.java creates three new objects, magPile, billPile, and out. To what extent are the creation of magPile and billPile analogous in the two languages? Why is out or its equivalent needed in Java, but not in Scheme?

   2. To what extent are the sequence of stack operations parallel in the two languages?

   3. In the Java program, two lines containing a top operation are commented out. What happens if these two lines are included? For example, does the program compile? Does it run? Describe briefly.

   4. Using the Java documentation described above, replace the top method invocation by the correct method name from the documentation. Recompile, run, and check that the program now works appropriately.

Approximating Pi

Problem

Consider a square of side 2 in the plane, centered at the origin, so the square extends one unit along each axis in each direction.

Suppose a point P is picked at random in the square. What is the likelihood that P also will be within a circle of radius 1, centered at the origin?

Program ~walker/java/examples/mathComputations/approxPi.java provides a solution to this problem. While several parts of this program are familiar, both the conditionals and the looping involve some Java constructs which have not yet been introduced in this course.

4. Copy the Java program approxPi.java to your account, compile it, run it for several values of N, and check the output.

5. Review how each part of this program implements the solution outline above.

Additional Practice

The following exercises provide practice with conditional (if) statements and loops. Details for these constructs are discussed in the reading for this lab and illustrated in program approxPi.java.

6. Consider the following Scheme code to compute the sum of the numbers from N to 1:

   
   (do ((sum 0 (+ sum I))
        (I N (- I 1)))
       ((<= I 0) sum))
   )
   
   

   Write the corresponding loop as a Java for loop. As in Scheme, the body of the for loop will be null. Remember to separate multiple clauses in the initialization or update sections by commas.

7. Solve the following problem using the various ideas of random numbers, conditionals, and looping discussed in this lab.

   Family Size Simulation: A couple decides that they want to raise at least one boy and one girl. They decide to keep having children until they have one child of each gender, and then stop having children. Assume that having a boy or a girl is equally likely, and assume the gender of one child has no influence on the gender of the next. Investigate how many children such a couple could expect to have.

   Partial Solution: In the simulation, the gender of a child for a couple could depend on a random number generator. For example, you might decide that the child might be a boy if a random number were less than 0.5, and a girl otherwise. The overall program might proceed according to the following outline:

   1. Repeat for 20 couples:
      1. Initialization: Set the number of boys and number of girls to 0.
      2. Continue until there is at least one boy and one girl:
         1. Determine gender of next child.
         2. If child is a boy, increase number of boys by 1.
         3. If child is a girl, increase number of girls by 1.
      3. Print number of boys, number of girls, and total number of children.

8. Modify the previous program to simulate the family size for 1000 couples. In this modification, do NOT print the size of each couple's family. Rather, keep track of the minimum, maximum, and average family sizes.

Extra Credit

As an extra credit option, consider this graphical extension for the simulation to approximate Pi. Suppose we want to plot the points in a window as well as to count how many points are in the unit circle. To do this, we would need a graphical window.

While we could try writing such a window class from scratch, such an effort could require considerable time and effort. Instead, we will use a class, called Plane.java, developed by Mr. Rebelsky.

9. Copy files ~walker/153/java/SimpleInput.java, ~walker/153/java/Plane.java, ~walker/153/java/Point.java, and ~walker/153/java/JustPlaneFun.java to your account..

10. Using the above Point class, re-code the simulation program, using Point and its methods instead of variables x and y. (You will need only the Point constructor that uses two parameters and the distanceFromOrigin method.)

11. Compile and run JustPlaneFun.java. As you will see, this program plots points on a plane. Read through the Plane class to learn how this is done. Note that the size of the plane may be adjusted by using a non-default constructor. Since we want a place with x and y values between -1 and 1, one such declaration could be
    Plane pln = new Plane (-1, -1, 1, 1).
    If you want to scale the values, of course, you could multiple each of these values by an appropriate scaling factor.

12. Using Plane.java, add code to approxPi.java to plot the points as they are generated. In writing your code, read the methods in Plane.java to determine how to turn off the printing of coordinates. (For simulations of any size, the diagram of points will be hard to read if both points and their coordinates are printed.)

    Hint: Once you examine the methods of Plane.java, the actual new coding for this step will be rather short.

Work To Turn In:

• Commentary for steps 2, 3.
• Code segment for step 6.
• Complete code (with full testing) for step 7, 8.
• Extra Credit: Complete code (with full testing) for step 12.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-java-prob.sol-1.shtml

created April 16, 2000 last revised April 12, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.