Java, Java, Java: Special Topic: What Can Be Computed?

9. Control Structures

9.12. Special Topic: What Can Be Computed?

Did you ever wonder whether there are problems that cannot be solved by a computer, no matter what kind of control structures are used? Well, back in 1939, in his seminal paper titled “On Computable Numbers,” Alan Tur- ing proved that indeed there are an infinite number of unsolvable prob- lems. Prior to this, mathematicians and logicians thought all problems could be solved. So Turing’s proof was quite a blow!

To help him prove this point, Turing defined an abstract computer, which has come to be known as a Turing machine. A Turing machine has an alphabet of symbols; a read/write head; an infinitely long tape on which the read/write head can write symbols, and from which it can also read symbols; and a control unit, which controls the movement and action of the read/write head. Note that the Turing machine elements correspond to key components of a real computer—although Turing in- vented this concept a decade before the first computers were developed. The read/write head corresponds to a computer’s central processing unit (CPU). The tape corresponds to the computer’s memory. And the control unit corresponds to the computer program.

A Turing machine represents a purely abstract concept of computa- tion. It represents the pure idea of an algorithmic solution to a problem. Equipped with this concept, Turing was able to prove that there are un- solvable problems—that is, problems for which no algorithm can arrive at a solution.

One such problem is the halting problem. This problem asks whether an algorithm can be devised to determine whether an arbitrary program will eventually halt. If there were such an algorithm, it could be used to detect programs that contain infinite loops, a service that might be really helpful in an introductory computing lab, among other places! But, alas, there can be no such algorithm.

Here’s an outline of a proof that shows that the halting problem is un- solvable. (This particular version of the proof was suggested by J. Glenn Brookshear in Computer Science: An Overview, Benjamin-Cummings, 1985.) Suppose you had a program, P, that solves the halting problem. That is, whenever P is given a self-halting program, it sets a variable isTerminating to true, and otherwise it sets isTerminating to false. Now let’s create a new version of P, named P′, which is identical to P except that right after where

P sets isTerminating to true or false, P′ contains the following loop:

In other words, if the input to P is a self-terminating program, then P will enter an infinite loop and it won’t terminate. Otherwise, if a non- self-terminating program is input to P , P will skip the loop and will terminate.

Now what if we give a representation of P to itself. Will it halt? The answer generates a contradiction: If P is a self-terminating program, then when it is input to itself, it will not terminate. And if P is not self- terminating, when it is input to itself, it will terminate. Because our as- sumption that P solves the halting problem has led to a contradiction, we

CHAPTER 6 • Chapter Summary285

have to conclude that it wasn’t a very good assumption in the first place. Therefore, there is no program that can solve the halting problem.

The topic of computability is a fundamental part of the computer sci- ence curriculum, usually taught in a sophomore- or junior-level theory of computation course.

Technical Terms

conditional loop counting loop

do-while statement infinite loop initializer

limit bound loop body

loop bound

loop entry condition nested loop postcondition precondition priming read repetition structure

sentinel bound unit indexing updater

while statement zero indexing

CHAPTER SUMMARY

Summary of Important Points

A repetition structure is a control structure that allows a statement or sequence of statements to be repeated.

All loop structures involve three elements—an initializer, a loop entry condition or a loop boundary condition, and an updater.

When designing a loop, it is important to analyze the loop structure to make sure that the loop bound will eventually be satisfied.

The for statement has the following syntax:

for ( initializer ; loop entry condition ; updater )

for loop body ;TABLE 6.2 A summary

The while statement takes the following form:

while ( loop entry condition )

loop body ;

The do-while statement has the following general form:

loop body ;

while ( loop entry condition) ;

of various loop bounds

BoundExample

Countingk < 100

Sentinelinput != 9999

Flagdone != true

Limitamount < 0.5

When designing a loop, it is important to analyze the loop structure to

make sure that the loop bound will eventually be satisified. Table 6.2 summarizes the types of loop bounds that we have identified.

Structured programming is the practice of writing programs that are built up from a small set of predefined control structures—the sequence, selection, repetition, and method-call structures. An important feature of these structures is that each has a single entry and exit.

A precondition is a condition that must be true before a certain code segment executes. A postcondition is a condition that must be true when a certain code segment is finished. Preconditions and postconditions should be used in the design, coding, documentation, and debugging of algorithms and methods.

SOLUTIONS TO

SELF-STUDY EXERCISES

SOLUTION 6.1 Identify the syntax error in the following for loop statements:

Commas are used instead of semicolons in the header.

There shouldn’t be 3 semicolons in the header

SOLUTION 6.2 Identify those statements that result in infinite loops:

Infinite loop because k is never incremented.

Infinite loop because k is always odd and thus never equal to 100.

SOLUTION 6.3 Your sister is learning to count by fours. Write a for loop that prints the following sequence of numbers: 1, 5, 9, 13, 17, 21, 25.

SOLUTION 6.4 What value will j have when the following loop terminates? An- swer: j will be undefined when the loop terminates. It is a local variable whose scope is limited to the loop body.

SOLUTION 6.5 Write a nested for loop to print the following geometric pat- tern:

SOLUTION 6.6 Identify the syntax error in the following while structures:

a.,

b.,

SOLUTION 6.7 Determine the output and/or identify the error in each of the following while structures.

a.,

Output: infinite loop prints 0 0 0 0 0...

b.,

Output: unpredictable since k’s initial value is not known

SOLUTION 6.8 Your younger sister is now learning how to count by sixes. Write a while loop that prints the following sequence of numbers: 0, 6, 12, 18, 24, 30, 36.

SOLUTION 6.9 If N is even, divide it by 2. If N is odd, subtract 1 and then divide it by 2. This will generate a sequence that is guaranteed to terminate at 0. For example, if N is initially 15, then you get the sequence 15, 7, 3, 1, 0. Write a method that implements this sequence using a while statement.

SOLUTION 6.10 Identify the syntax error in the following do-while structures:

a.,

b.,

SOLUTION 6.11 Your sister has moved on to counting by sevens. Write a

do-while loop that prints the following sequence of numbers: 1, 8, 15, 22, 29,

36, 43.

SOLUTION 6.12 Write a method to input and validate pizza sales.

SOLUTION 6.13 Write a method to input and validate pizza sales using the numbers 1, 2, and 3 to represent pizzas at different price levels.

SOLUTION 6.14 For each of the following problems, decide whether a counting loop structure, a while structure, or a do-while structure should be used, and write a pseudocode algorithm.

Printing the names of all the visitors to a Web site could use a counting loop because the exact number of visitors is known.

Validating that a user has entered a positive number requires a do-while

structure in which you repeatedly read a number and validate it.

Changing all the backslashes ( ) in a Windows Web page address, to the slashes (/) used in a Unix Web page address.

Finding the largest in a list of numbers requires a while loop to guard against an empty list.

SOLUTION 6.15 Identify any errors in the following switch structures (if there is no error, specify the output):

a.,

b.,

c.,

SOLUTION 6.16 A switch statement to print ice cream flavors:

SOLUTION 6.17

SOLUTION 6.18 Identify the pre- and postconditions on j and k where indicated in the following code segment:

SOLUTION 6.19 Identify the pre- and postconditions for the following method, which computes xn for n >= 0.

EXERCISE 6.1 Explain the difference between the following pairs of terms:

Counting loop and conditional loop.

For statement and while statement.

While statement and do-while statement.

Zero indexing and unit indexing.

Sentinel bound and limit bound.

Counting bound and flag bound.

Loop initializer and updater.

Named constant and literal.

Compound statement and null statement. EXERCISE 6.2 Fill in the blank.

EXERCISES

Note: For programming exercises, first draw a UML class diagram describing all classes and their inheritance relationships and/or associations.

The process of reading a data item before entering a loop is known as a.

A loop that does nothing except iterate is an example of.

A loop that contains no body is an example of astatement.

A loop whose entry condition is stated as (k < 100 || k >= 0) would be an example of anloop.

A loop that should iterate until the user types in a special value should use a

bound.

A loop that should iterate until its variable goes from 5 to 100 should use a

bound.

A loop that should iterate until the difference between two values is less than

0.005 is an example of abound.

EXERCISE 6.3 Identify the syntax errors in each of the following:

for (int k = 0; k ¡ 100; k++) System.out.println(k)

for (int k = 0; k ¡ 100; k++); System.out.println(k);

int k = 0 while k ¡ 100 System.out.println(k); k++;

int k = 0; do System.out.println(k); k++; while k ¡ 100 ;

EXERCISE 6.4 Determine the output and/or identify the error in each of the following code segments:

for (int k = 1; k == 100; k += 2) System.out.println(k);

int k = 0; while (k ¡ 100) System.out.println(k); k++;

for (int k = 0; k ¡ 100; k++) ; System.out.println(k);

EXERCISE 6.5 Write pseudocode algorithms for the following activities, paying particular attention to the initializer, updater, and boundary condition in each case.

a softball game

a five-question quiz

looking up a name in the phone book

EXERCISE 6.6 Identify the pre- and postconditions for each of the statements that follow. Assume that all variables are int and have been properly declared.

int result = x / y;

int result = x

int x = 95; do x /= 2; while(x ¿= 0);

EXERCISE 6.7 Write three different loops—a for loop, a while loop, and a do-while loop—to print all the multiples of 10, including 0, up to and including 1,000.

EXERCISE 6.8 Write three different loops—a for loop, a while loop, and a

do-while loop—to print the following sequence of numbers: 45, 36, 27, 18, 9, 0,

−9, −18, −27, −36, −45.

EXERCISE 6.9 Write three different loops—a for loop, a while loop, and a

do-while loop—to print the following ski-jump design:

EXERCISE 6.10 The Straight Downhill Ski Lodge in Gravel Crest, Vermont, gets lots of college students on breaks. The lodge likes to keep track of repeat visitors. Straight Downhill’s database includes an integer variable, visit, which gives the number of times a guest has stayed at the lodge (1 or more). Write the pseudocode to catch those visitors who have stayed at the lodge at least twice and to send them a special promotional package (pseudocode = send promo). (Note: The largest number of stays recorded is eight. The number nine is used as an end-of-data flag.)

EXERCISE 6.11 Modify your pseudocode in the previous exercise. In addition to every guest who has stayed at least twice at the lodge receiving a promotional package, any guest with three or more stays should also get a $40 coupon good for lodging, lifts, or food.

EXERCISE 6.12 Write a method that is passed a single parameter, N, and dis- plays all the even numbers from 1 to N.

EXERCISE 6.13 Write a method that is passed a single parameter, N, that prints all the odd numbers from 1 to N.

EXERCISE 6.14 Write a method that is passed a single parameter, N, that prints all the numbers divisible by 10 from N down to 1.

EXERCISE 6.15 Write a method that is passed two parameters—a char Ch and an int N—and prints a string of N Chs.

EXERCISE 6.16 Write a method that uses a nested for loop to print the follow- ing multiplication table:

EXERCISE 6.17 Write a method that uses nested for loops to print the patterns that follow. Your method should use the following statement to print the patterns: System.out.print(’#’).

EXERCISE 6.18 Write a program that asks the user for the number of rows and the number of columns in a box of asterisks. Then use nested loops to generate the box.

EXERCISE 6.19 Write a Java application that lets the user input a sequence of consecutive numbers. In other words, the program should let the user keep en- tering numbers as long as the current number is one greater than the previous number.

EXERCISE 6.20 Write a Java application that lets the user input a sequence of integers terminated by any negative value. The program should then report the largest and smallest values that were entered.

EXERCISE 6.21 How many guesses does it take to guess a secret number be- tween 1 and N? For example, I’m thinking of a number between 1 and 100. I’ll tell you whether your guess is too high or too low. Obviously, an intelligent first guess would be 50. If that’s too low, an intelligent second guess would be 75. And so on. If we continue to divide the range in half, we’ll eventually get down to one number. Because you can divide 100 seven times (50, 25, 12, 6, 3, 1, 0), it will take at most seven guesses to guess a number between 1 and 100. Write a Java Swing program that lets the user input a positive integer, N, and then reports how many guesses it would take to guess a number between 1 and N.

EXERCISE 6.22 Suppose you determine that the fire extinguisher in your kitchen loses X percent of its foam every day. How long before it drops below a certain threshold (Y percent), at which point it is no longer serviceable? Write a Java Swing program that lets the user input the values X and Y and then reports how many weeks the fire extinguisher will last.

EXERCISE 6.23 Leibnitz’s method for computing π is based on the following convergent series:

π111

4 = 1 − 3 + 5 − 7 + · · ·

How many iterations does it take to compute π to a value between 3.141 and 3.142 using this series? Write a Java program to find out.

EXERCISE 6.24 Newton’s method for calculating the square root of N starts by making a (nonzero) guess at the square root. It then uses the original guess to calculate a new guess, according to the following formula:

No matter how wild the original guess is, if we repeat this calculation, the algo- rithm will eventually find the square root. Write a square root method based on this algorithm. Then write a program to determine how many guesses are required to find the square roots of different numbers. Uses Math.sqrt() to determine when to terminate the guessing.

EXERCISE 6.25 Your employer is developing encryption software and wants you to develop a Java Swing Program that will display all of the primes less than N, where N is a number to be entered by the user. In addition to displaying the primes themselves, provide a count of how many there are.

EXERCISE 6.26 Your little sister asks you to help her with her multiplication and you decide to write a Java application that tests her skills. The program will let her input a starting number, such as 5. It will generate multiplication problems ranging from from 5 1 to 5 12. For each problem she will be prompted to enter the correct answer. The program should check her answer and should not let her advance to the next question until the correct answer is given to the current question.

EXERCISE 6.27 Write an application that prompts the user for four values and draws corresponding bar graphs using an ASCII character. For example, if the user entered 15, 12, 9, and 4, the program would draw

EXERCISE 6.28 Revise the application in the previous problem so that the bar charts are displayed vertically. For example, if the user inputs 5, 2, 3, and 4, the program should display

EXERCISE 6.29 The Fibonacci sequence (named after the Italian mathematician Leonardo of Pisa, ca. 1200) consists of the numbers 0, 1, 1, 2, 3, 5, 8, 13,... in which each number (except for the first two) is the sum of the two preceding numbers. Write a method fibonacci(N) that prints the first N Fibonacci numbers.

EXERCISE 6.30 The Nuclear Regulatory Agency wants you to write a program that will help determine how long certain radioactive substances will take to de- cay. The program should let the user input two values: a string giving the sub- stance’s name and its half-life in years. (A substance’s half-life is the number of years required for the disintegration of half of its atoms.) The program should re- port how many years it will take before there is less than 2 percent of the original number of atoms remaining.

EXERCISE 6.31 Modify the CarLoan program so that it calculates a user’s car payments for loans of different interest rates and different loan periods. Let the user input the amount of the loan. Have the program output a table of monthly payment schedules.

The next chapter also contains a number of loop exercises.

Chapter 7