A201/A597 Introduction to Programming I (4/3 cr.)

CSCI A201/A597
Problem Set Six

Second Summer 2000

Your problem will be randomly distributed to you by logging in to QuizSite. Due date is Wednesday July 19, at 11:59pm. Solutions to be posted here Thursday July 20, at noon.

The series of pipes in Advanced Topic 6.5 (page 248) has one final problem: The output file contains upper- and lowercase versions of the same word, such as "The" and "the". Modify the procedure, either by changing one of the programs or, in the true spirit of piping, by writing another short program and adding it to the series.

2.	Currency conversion. Write a program that asks a user to enter today's exchange rate between U.S. dollars and the Euro. Then the program reads U.S. dollar values and converts each to Euro values. Use 0 (zero) as a sentinel to denote the end of inputs.

Write a program that asks the user to enter today's exchange rate between U.S. dollars and the Euro. Then the program reads U.S. dollar values and converts each to Euro values. Use 0 (zero) as the sentinel value to denote the end of dollar inputs. Then the program reads a sequence of Euro amounts and converts them to dollars. The second sequence is terminated by the end of the input file.

Random walk. Simulate the wandering of an intoxicated person in a square street grid. Draw a grid of 10 streets horizontally and 10 streets vertically. Represent the simulated drunkard by a dot, placed in the middle of the grid to start. For 100 times, have the simulated drunkard randomly pick a direction (east, west, north, south), move one block in the chosen direction, and redraw the dot. After the iterations, display the distance that the drunkard has covered. (One might expect that on average the person might not get anywhere because the moves to different directions cancel another out in the long run, but in fact it can be shown that with probability 1 the person eventually moves outside any finite region).

Projectile flight. Suppose a cannonball is propelled vertically into the air with a starting velocity v₀. Any calculus book will tell us that the position of the ball after t seconds is

s (t) = -0.5 g t² + v₀ t

where g = 9.81^m/_sec² is the gravitational force of the earth. No calculus book ever mentions why someone would want to carry out such an obviously dangerous experiment, so we will do it in the safety of the computer.

In fact we will confirm the theorem from calculus by a simulation. In our simulation, we will consider how the ball moves in very short time intervals deltaT. In a short time interval the velocity v is nearly constant, and we can compute the distance the ball moves as

deltaS = v * deltaT

In our program we will simply set

double deltaT = 0.01;

and update the position by

s = s + v * deltaT;

The velocity changes constantly -- in fact, it is reduced by the gravitational force of the earth. In a short time interval,

v = -g * deltaT

and we must keep the velocity updated as

v = v - g * deltaT;

In the next iteration the new velocity is used to update the distance.

Now run the simulation until the cannonball falls back onto the earth. Get the initial velocity as an input (100 ^m/_sec is a good value). Update the position and velocity 100 times per second, but print out the position only every full second. Also print out the values from the exact formula

s (t) = -0.5 g t² + v₀ t

for comparison.

What is the benefit of this kind of simulation when an exact formula is available? Well, the formula from the calculus book is not exact. Actually, the gravitational force diminishes the further the cannonball is away from the surface of the earth. This complicates the algebra sufficiently that it is not possible to give an exact formula for the actual motion, but the computer simulation can simply be extended to apply a variable gravitational force. For cannonballs, the calculus-book formula is actually good enough, but computers are necessary to compute accurate trajectories for higher-flying objects such as ballistic missiles.

Most cannonballs are not shot upright but at an angle. If the starting velocity has magnitude v and the starting angle is

, then the velocity is actually a vector with components

In the x-direction the velocity does not change. In the y-direction the gravitational force takes its toll. Repeat the simulation from the previous exercise, but store the position of the canonball as a Point2D variable. Update the x and y positions separately, and also update the x and y components of the velocity separately. Every full second, plot the location of the cannonball on the graphics display. Repeat until the cannonball has reached the earth again.

This kind of problem is of historical interest. The first computers were designed to carry out just such ballistic calculations, taking into account the diminishing gravity for high-flying projectiles and wind speeds.

The Fibonacci sequence is defined by the following rule. The first two values in the sequence are 1 and 1. Every subsequent value is the sum of the two values preceding it. For example, the third value is

1 + 1 = 2

the fourth value is

1 + 2 = 3

and the fifth is

2 + 3 = 5

If f _n denotes the n^th value in the Fibonacci sequence, then

f₁ = 1
f₂ = 1
f_n = f_{n - 1} + f_{n - 2} if n > 2

Write a program that prompts the user for n and prints the n^th value in the Fibonacci sequence.

Hint: There is no need to store all values for f_n. You only need the last two values to compute the next one in the series:

fold1 = 1;
fold2 = 1;
fnew = fold1 + fold2;

8. Write a program that prints a bar chart from a data set. The program should be a graphics applet that prompts the user for the values, all to be entered into a single option dialog, separated by spaces (for example 40 60 50). Assume all values are between 0 and 100. Then draw a bar chart like this:

Mean and standard deviation. Write a program that reads a set of floating-point data values from the input. When the end of file is reached, print out the count of the values, the average and the standard deviation. The average of a data set

where

is the sum of the input values. The standard deviation is

However, that formula is not suitable for our task. By the time you have computed the mean, the individual x_i are long gone. Until you know how to save these values, use the numerically less stable formula

You can compute this quantity by keeping track of the count, the sum, and the sum of squares as you process the input values.

10.	Write a graphical applet that prompts a user to enter a number `n` and that draws `n` circles with random center and random radius.

11.	Factoring of integers Write a program that asks the user for an integer and then prints out all its factors. For example, when the user enters 150, the program should print 2 3 5 5

12.

Prime numbers Write a program that prompts the user for an integer and then prints out all prime numbers up to that integer. For example, when the user enters 20, the program should print.

Recall that a number is a prime number if it is not divisible by any number except 1 and itself.

13.

The best known iterative method for computing the roots of a function f (that is, the x-values for which f (x) is 0) is Newton-Raphson approximation. To find the zero of a function whose derivative is also known, compute

x_new = x_old - f (x_old) / f ^'(x_old)

For this exercise, write a program to compute n^th roots of floating-point numbers. Prompt the user for a and n, then obtain

by computing a zero of the function

f (x) = xⁿ - a

14.	Write a graphical applet that displays a checkerboard with 64 squares, alternating white and black.

15.	Write a program that reads a series of floating-point numbers and prints The maximum value The minimum value The average value

16.

The game of Nim.

This is a well-known game with a number of variants. We will consider the following variant, which has an interesting winning strategy. Two players alternately take marbles from a pile. In each move, a player chooses how many marbles to take. The player must take at least one but at most half of the marbles. Then the other player takes a turn. The player who takes the last marble loses.

You will write a program in which the computer plays against a human opponent. Generate a random integer between 10 and 100 to denote the initial size of the pile. Generate a random integer between 0 and 1 to decide whether the computer plays smart or stupid. In stupid mode, the computer simply takes a random legal value (between 1 and n/2) from the pile whenever it has a turn. In smart mode the computer takes off enough marbles to make the size of the pile a power of two minus 1 -- that is, 3, 7, 15, 31, or 63. That is always a legal move, except if the size of the pile is currently one less than a power of two. In that case, the computer makes a random legal move.

You will note that the computer cannot be beaten in smart mode when it has the first move, unless the pile size happens to be 15, 31, or 63. Of course, a human player who has the first turn and knows the winning strategy can win against the computer.

17.

The value of e^x can be computed as the power series

Write a program that computes e^x using this formula. Of course, you can't compute an infinite sum. Just keep adding values until an individual summand (term) is less than a certain threshold. At each step, you need to compute the new term and add it to the total. Update these terms as follows:

term = term * x / n;

18.

Program the following simulation: Darts are thrown at random points onto the square with corners (1 ,1) and (-1, -1). If the dart lands inside the unit circle (that is, the circle with center (0, 0) and radius 1), it is a hit. Otherwise it is a miss.

Run this simulation and use it to determine an approximate value for .