|
|
发表于 2005-9-28 01:27:33
|
显示全部楼层
给出上下文让译者有参考依据
Graded Problems: Iteration
--------------------------------------------------------------------------------
Example 3.1.1 Solving 10 sets of equations
Suppose it is required to solve 10 pairs of simple simultaneous equations of the form
alx + bly = c1
a2x + b2y = c2
where each of a1, bl, cl, a2,b2, c2 is supplied as data-.
The data for the complete program will consist of 60 numbers. The first set of 6 will represent a1, bl, cl, a2,b2, c2 for the first set of equations, the next set of 6 will define the second pair of equations and so on. The program therefore takes the form
Perform 10 times
the following task :
read a1, bl, cl, a2,b2, c2;
solve the simultaneous equations;
print results;
end of task.
The task can be coded simply (see exercise 16 in Conditionals chapter).
Example 3.1.2 Solving N sets of equations
It is imperative that the program is given information about the number of pairs of equations to be solved. Accordingly we shall arrange that the first item of data is the integer N (that is 10 or 4 or whatever) giving this information. This will be followed by 6*N numbers, one set of 6 for each of the N pairs of equations.
The general structure of the program becomes
Read N.
Perform N times
the following task:
.
.
end of task.
Performing the task involves reading data, solving the appropriate equations and then printing the result.
In the examples above, the values that the variables have in one execution of the loop bear no relationship to the values in any other execution. There is no concept of a previously computed value being carried forward for use in the next execution. This ideas the idea of carrying forward values, the idea of iteration will be introduced in the next example.
Example 3.1.3 Finding the largest of a set
A non-empty set of numbers is represented in the data as a positive integer N (the size of the set) followed by N other numbers (the elements of the set). Write a program which prints the largest number in the set.
A solution to this problem is of the form
Read N.
Read the first element and store it in MAX.
Perform N-1 times
the following task:
read an item and store it in ITEM;
if ITEM > MAX then
alter MAX to hold ITEM;
end if;
end of task.
Print out the value of MAX.
Note that as execution progresses, on completion of each execution of the loop body, MAX holds the largest member of the set that has so far been encountered. It follows that when a new item is read it is necessary to compare that item ant MAX and if necessary alter MAX accordingly.
Example 3.1.4 Finding the average of a set of numbers
In this example a set of numbers again appears as some positive integer N followed by N numbers. We want a program, which finds the average of the numbers in the set.
A solution takes the form
Read N.
Set SUM to 0.
Perform N times
the following task:
read an item ant store in X;
add X to the current value of SUM
to produce a new value for SUM;
end of task.
Print SUM divided by N.
Exercises 3.1
1. Code the solutions of examples 3.1.1 to 3.1.4 in a programming language of your choice.
2. Write a program which inputs N followed by the prices of N items. The program should output the price at which each item is offered in a sale. The sale price is calculated as follows. The original price is reduced by 10%, the resulting quantity raised to the nearest pound and then 1 penny subtracted from it. If the resulting quantity is less than the original price then the new price is output, otherwise the old price is output together with a warning message.
3. Write a program which inputs N followed by N pairs of numbers. The first of each pair represents the price of an item on a menu, the second the quantity eaten by a customer. The restaurant imposes a 10% service charge. The output from your program should be an itemised bill.
4. Write a program, which reads N followed by N numbers and outputs the positive difference between the two largest numbers.
5. Write a program, which inputs N followed by a set of N numbers and outputs the variance of the set given by
V = [1/N-1] [ ( Summation of xi2 - 2X Summation of xi + NX2 )
where X is the average of the set and i varies from 1 to N.
3.2 Control variables
There are situations in which it is advantageous to have available a control variable (also called "index loop counter", "control constant" and so on) which keeps some sore of record of the number of times a loop body has been executed. We illustrate several cases where this is relevant.
Example 3.2.1 Calculating factorial
Suppose we are required to Write a program which evaluates the factorial function
N! = 1 x 2 x 3 x .....…x N where N is some non-negative integer supplied as data. The following program does what is required.
Read N.
Let PRODUCT be initialised to 1.
Using control variable I starting at 1 and
increasing in steps of 1 to N perform
the following task:
replace PRODUCT by PRODUCT times I;
end of task.
Print the value of PRODUCT.
For each individual value of I the loop body is executed before the next value is considered. At the end of each execution of the loop body PRODUCT has the value 1 x 2 x ...x I. Again the loop body represents the answer to the question:
if at some stage PRODUCT holds the value (I - 1)! how do we then ensure that it receives the value I! ?
Example 3.2.2 Series summation
Suppose we are required to evaluate the following series
Summation of 1/i2 = 1 + 1/22 + 1/32 + …... + 1/1002
Where the summation of i is from 1 to 100
This can be done in the following way.
Let SUM be initialised to 0.
Using control variable I starting at 1 and increasing
in steps of 1 to 100 perform
the following task:
replace SUM by SUM plus 1/I2 ;
end of task.
Print the value of SUM.
Note that the above is very similar to some of .he examples given earlier in section 3.1 on evaluating series of numbers. In this case however the various items to be added are not read from some input file rather they are calculated using the control variable.
The next example combines the ideas outlined in the two above.
Example 3.2.3 Series summation
Consider the problem of evaluating
Summation of 1/i2
Where summation of i is from 1 to 100
A possible program might have the following form
Read X.
Set SUM to 0. Set TERM to 1.
Using control variable I starting at 1 and
increasing in steps of 1 to 100 perform
the following task:
replace TERM by TERM/I;
replace SUM by SUM+TERM;
end of task.
Print the value of SUM.
In this case an accumulated sum of terms is calculated in the usual way. Note that on each circuit of the loop TERM changes. One term is obtained from the previous one by dividing by I. This explains the alteration to TERM within the program.
The examples given so far involve the use of control variables which start at 1 and progress in steps of 1 to some upper limit. There are cases where it is inconvenient to be restricted to such a rigid format. Many programming languages permit arbitrary starting values ant arbitrary (possibly negative) increments. Consider the following example.
Example 3.2.4 Testing for primality
Write a program which reads some positive integer N and determines whether or not it is prime. (An integer is prime provided it exceeds 1 and is divisible only by itself and 1.)
We adopt a solution which proceeds as follows: first look at whether N is even and greater than 2, if so take appropriate action; if N is odd then it is sufficient to test if N is divisible by 3,5,... .
Read N.
If N is even and N>2 then
set PRIME to false;
otherwise
set PRIME to true;
using control variable I starting at 3 and
increasing in steps of 2 to N-l perform
the following task:
if N is divisible by I
set PRIME to false;
end of task;
end if.
Print an appropriate message depending on the value of PRIME.
This solution can be improved on in at least two ways: firstly it is usually unnecessary to go as far as N - l; secondly if ever PRIME is set to false the loop can be terminated immediately. The latter possibility is dealt with later in section 3.4. So far as the former is concerned we note that if both P and Q are greater than the square root of N then
P x Q > N. So, if N is not prime one of its factors must be less than its square root.
Example 3.2.5 Nested multiplication
Consider the task of evaluating the polynomial
ANXN + AN-lXN-1+ ... + A2X2 + A1X + A0
given the quantities AN, AN-l, ... ,A2, A1, A0 together with a value of X.
A polynomial of this kind can be evaluated using the obvious approach:
Read X. Read N.
Set SUM to 0.
-Using control variable I starting at N and
decreasing in steps of l to 0 perform
the following task:
read A;
replace SUM by SUM + A x XI;
end of task;
Print SUM.
Use the process of nested multiplication to program.
Here the polynomial can be restructured and on each circuit of the loop we successively evaluate
AN
ANX + AN-l
(ANX + AN-l) X + AN-2
Note that each line is obtained from the previous by multiplying by X and adding in the value of the next coefficient. Thus we have
Read X. Read N.
Set SUM to 0.
Perform N+1 times
The following task:
read A;
replace SUM by SUM x X + A;
end of task.
Print SUM.
Note that we do not need a control variable.
Exercises 3.2
1. Code the solutions of examples 3.2.1 to 3.2.5 in a programming language of your choice.
2. In a certain country Sales Tax is charged on cars at the following rate
Net Price Rate
<$2000 15%
$200>$3000 $300 (flat rate)
>$3000 10%
Write a program which prints out net price, Sales Tax and gross price for net prices between $1000 and $4000 in steps of $250.
3. Given that 1 metre = 39.37 inches and that there are 12 inches in a foot, write a program which outputs a conversion table. For each metric distance from 5.0 metres to 10.0 metres in steps of 0.2 metres, your program should output the metric distance and its British equivalent in feet and inches. Round British distances to the nearest inch. Your table should start
Metres Feet Inches
5.0 16 5
5.2 17 l
. . .
4. Write a program which given the day of the week on which the first of a month falls, together with the number of days in the month, prints out a calendar for the month in the form shown below.
Mo Tu We Th Fr Sa Su
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
5. If there is a group of n people then the probability that no two of them have the same birthday is
q= 365/365 x 364/365 x 363/365 x ... x 365-n+1/365
The probability that at least two people have the same birthday is therefore
p = l - q
Write a program to evaluate p and output p and n for values of n from 2 to 70.
3.3 While loops and iteration
Example 3.3.l Counting spaces
A piece of text is terminated by the special character #. Write a program to count the number of spaces and non-spaces which occur.
The following program does as required.
Set the integer variables SPACES and NONSPACES to 0.
Read character into CH.
While CH is not # perform
the following task:
if CH holds a space then
add l to SPACES;
otherwise add 1 to NONSPACES;
end if;
read character into CH;
end of task.
Print the values of both SPACES and NONSPACES;
Each circuit of the loop is preceded by an instruction which reads the next character from the input stream. If this is not the # character the loop body is executed, otherwise control passes to the statement after the loop.
Example 3.3.2 Finding a square root
If xn is a close approximation to the square root of A then a better one is xn+l given by
Xn+1 = |
|
