Introduction To Computers and Programming
Introduction To Computers and Programming
Introduction To Computers and Programming
using
C++ and MATLAB
Alex F. Bielajew
The University of Michigan
Department of Nuclear Engineering and Radiological Sciences
2927 Cooley Building (North Campus)
2355 Bonisteel Boulevard
Ann Arbor, Michigan 48109-2104
U. S. A.
Tel: 734 764 6364
Fax: 734 763 4540
email: bielajew@umich.edu
c 20002011 Alex F Bielajew
Revision: June 29, 2011
Preface
This book arises out of a course I teach, a four-credit (52 hour), freshman-level course
Introduction to Computers and Programming being taught in the College of Engineering at
the University of Michigan. The book is in reasonably rough shape at this stage. It was
assembled from my lecture notes several years ago and is under constant revision. I may
never nish it! A wise person once said, Old age happens when you dwell more on the past
than on the future. By this denition, I have found eternal youth, insofar as this book is
concerned.
My educational objectives are quite simple. This is not really a course in computing. It
is a course in thinking, technical thinking, logical thinking, about formulating a problem,
a mathematical problem, a physics problem, a game, and then, executing a solution and
making it work. I consider the computer and the ability to program it as a kind of
laboratorya laboratory to investigate practically, the theories and ideas of other technical
courses. It is possible, for example, to teach a lot of Calculus to students without ever
mentioning the word, and there are several examples throughout this book.
This course is not about syntax. Hence, the book introduces the minimum amount syntax
to get through a problem. Indeed, I even keep some syntax hidden, to encourage students
to discover their own algorithms. So, if you are thinking of using this book as a technical
reference in C++ or Matlab, I anticipate that you will be disappointed.
The greatest value in this book, if there is any to be found, is in the exercises, problems and
projects at the back of almost every chapter. The ideal way to learn a computer language
is to learn a little syntax and then try it out on a computer. The ideal way to think is
not to read about it, but to actually do it! The book reects this. The material in the
chapters, separated from the exercises, is worse than useless, for reading the material and
not doing the problems is just a waste of time. Do the problems! Moreover, dont ask me
for the solutions! There is much more pedagogical value in a well-posed question than a
well-articulated answer.
OK, Ill step o my soap box now!
Several professors and many students have contributed to the ideas put into this book.
Professor James Holloway and I have had endless discussion on the general problem of
teaching algorithmic thinking to freshman. We still have not come to any conclusions except
i
ii
that it is highly challenging and rewarding. As for how it actually gets done, well, to be sure
it is a work-in-progress. I spent a very enjoyable term co-teaching this course (the rst time
I taught it) with Professor Ken Powell. Thanks, Ken, for nursing me through that rst year!
Both Jamess and Kens diverse computational backgrounds are reected to some degree in
this book.
I owe a debt of gratitude to the dozens of Graduate Student Instructors who have taught
with me on this course. One of them, Dan Osborne, deserves special recognition. He is one of
the most gifted and committed teachers I have ever encountered. Dan and I spent hour after
hour discussing the challenges of teaching computing and thinking skills to undergraduates.
To the 5000 or so undergraduates, mostly freshmen, who have taken my course: Every time
I teach this course I learn something newabout computing, about teaching, about the joy
of making an early deection in a students career.
Finally, I am one of those people who tends to see the forest, instead of the trees. Consequently, spelling and sentence structure usually yield to an enthusiasm to present the material
in an interesting way. Its not my only fault, but maybe my most visible one. To this end,
please inform me if you spot any errors. I am also deeply indebted to my wife-to-be, Linda
Park, for her unimaginable attention to detail, her proofreading and suggestions. Linda,
every time you undertake a proofreading project on my behalf, my mind boggles, truly.
AFB, June 29, 2011
Contents
1 Introduction to the course
1.1
1.2
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Data representations
2.1
2.2
2.3
Binary arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4
10
2.4.1
Whole numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.4.2
Real numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
11
2.5.1
12
2.6
13
2.7
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.5
23
3.1
What is an algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.2
Flowchart representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.3
Pseudocode representation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.4
. . . . . . . . . . . . . . . . . .
25
3.5
25
iii
iv
CONTENTS
3.6
26
3.7
27
3.8
Some examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.8.1
3.8.2
29
3.8.3
33
3.8.4
36
40
3.9.1
40
3.10 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
3.11 Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
3.9
49
4.1
49
4.2
52
4.3
55
4.4
57
4.5
59
4.6
60
4.7
Logical expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
4.7.1
66
4.7.2
67
4.8
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
4.9
Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
5 Loops
83
5.1
83
5.2
86
5.3
89
CONTENTS
5.4
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5
Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6 Early AbstractionFunctions
94
123
6.1
6.2
6.3
6.4
6.4.2
6.5
6.6
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.7
Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
167
7.4
7.3.2
7.3.3
7.3.4
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
199
Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
8.1.1
8.1.2
vi
CONTENTS
8.1.3
8.2
8.3
8.2.2
Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.3.1
8.3.2
8.3.3
8.3.4
8.3.5
8.3.6
8.3.7
8.3.8
8.3.9
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
8.5
Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
9 Miscellaneous Topics
9.1
239
. . . . . . . . . 246
9.2
9.3
9.4
9.4.2
9.4.3
9.5
9.6
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
CONTENTS
10 A Potpourri of Applications
vii
267
271
367
. . . . . . . . . . . . . . . . . . . . . . . . 367
viii
CONTENTS
12.1.3 Making titles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
12.1.4 Axis labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
12.1.5 Dierent line styles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
12.1.6 Point plots, plotting with point symbols . . . . . . . . . . . . . . . . 372
12.1.7 Plotting more than one thing at once . . . . . . . . . . . . . . . . . . 377
12.1.8 Subplots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
12.2 Three dimensional graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.2.1 Plot3 plots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.2.2 Mesh plots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.2.3 Axis labelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
12.2.4 meshc and meshz plots . . . . . . . . . . . . . . . . . . . . . . . . . . 382
12.2.5 Surface plots using surf . . . . . . . . . . . . . . . . . . . . . . . . . . 382
12.2.6 Surface plots using surfc . . . . . . . . . . . . . . . . . . . . . . . . . 383
12.2.7 Surface plots using sur . . . . . . . . . . . . . . . . . . . . . . . . . 383
12.2.8 Contour plots using contour . . . . . . . . . . . . . . . . . . . . . . . 384
12.2.9 Contour plots using contour3 . . . . . . . . . . . . . . . . . . . . . . 384
12.2.10 Contour plots using pcolor . . . . . . . . . . . . . . . . . . . . . . . . 384
12.2.11 Contour plots using contourf . . . . . . . . . . . . . . . . . . . . . . . 385
12.2.12 Contour plots with labels . . . . . . . . . . . . . . . . . . . . . . . . . 385
13 Miscellaneous topics
387
CONTENTS
13.4 Summary of the Course
ix
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
405
413
417
421
CONTENTS
Chapter 1
Introduction to the course
Computers are stupid. They only give answers.
Computers are blindly faithful. They only do what you tell them to do.
Computers are dumb. They do not do what you want them to do.
1.1
In our College of Engineering you will encounter faculty and sta who might otherwise have
been called Mathematicians, Physicists, Chemists and Biologists.
What is a computer?
Again, we appeal at rst to some standard reference texts.
American Heritage Dictionary
1. One (a person) who computes.
Some of the best examples:
- Richard Feynmans computersteams of people working out calculations during the
Manhattan Project
- Calculation of ballistics tables for WWII
- Calculation of sine/cosine/logarithm tables
2. A device (a machine) that computes, especially a programmable electronic machine
that performs high-speed mathematical or logical operations or that assembles, stores,
correlates, or otherwise processes information.
Oxford English Dictionary
1. One who computes; a calculator, reckoner; spec. a person employed to make calculations in an observatory, in surveying, etc. (Earliest reference 1646).
2. A calculating-machine; esp. an automatic electronic device for performing mathematical or logical operations; freq. with dening word prexed, as analogue, digital,
electronic computer (see these words). (Earliest reference 1897).
McGraw-Hill Encyclopedia of Science and Technology
A device that receives, processes, and presents information. The two basic types of
computers are analog and digital. Although generally not regarded as such, the most
prevalent computer is the simple mechanical analog computer, in which gears, levers,
ratchets, and pawls perform mathematical operations for example, the speedometer
and the watt-hour meter (used to measure accumulated electrical usage). The general
public has become much more aware of the digital computer with the rapid proliferation
of the hand-held calculator and a large variety of intelligent devices, ranging from
typewriters to washing machines.
Our denition A device that
1. accepts some form of input (usually disorganized or of some highly specic nature),
2. responds to this input information in a pre-determined (programmed) way,
3. produces some form of output (usually more organized or coherent than the input)
Some common examples of computers
Personal: Wristwatch, electronic car keys, phone, radio, GPS device, calculator, laptop...
In the home: Stove, refrigerator, freezer, microwave oven, clocks and timers, toaster,
coee machine, thermostat, washer and dryer, TVs, DVD/Blu-Ray players, audio
equipment ... the list is endless.
Automotive: fuel delivery, air/fuel mixture, spark advance, brakes (ABS), traction control, suspension adjustment, climate control, navigation, parking assist, lane variation
warning, proximity warnings, computer-controlled driving (coming soon)...
Mechanical analog computers: Wind-up clocks, toys, mechanical calculators...
Electrical analog computers: Integrators, dierentiators, dierential equation solvers,
Christmas light ashers (cheap ones!)...
Digital computers: Calculators, PDAs, Palm computers, laptops, desktops, minicomputers, mainframe computers....
Digital computers?
Digital computers are the simplest of all! They only understand two things, which we
label 1 and 0, or on or o, but more precisely, states of high or low voltage.
Computers switch between these two states very, VERY quickly. Modern run-of-the-mill
digital computers can throw about 100 billion switches per second! Thats enough to write
about 10 million pages of text in one second.
The input is rarely a collection of 0s and 1s, 011110000110... It can be in the form of
text that is converted to 0s and 1s or voltage that is digitized with an analog-todigital converter. (Musical recording, for example.)
The output is similarly rarely a collection of 0s and 1s. It can be 1D data (words,
numbers), 2D data (functions, charts, pictures, music), 3D data (video, surfaces, timeevolving functions)...
The processing or computing or programming part is what the bulk of the course
is concerned with. The programming responds to the input in some pre-determined
way. In some digital computers the programming is xed, for example, a digital clock
or a digital thermometer. In the most interesting cases, the program can be changed.
In this course we will learn to program programmable digital computers.
1.2
Problems
1. In the broad denition of computer in this chapter, how many computers can you
nd: On yourself? In your room? In a car? In your home?
2. A typical 3rd grader is a lot smarter than any computer. They can read, do simple
math, play a musical instrument, memorize poetry and write stories. Generally, with
sucient motivation, they will also do as they are told. How many ways could you
instruct a 3rd grader to determine the value of without the aid of a computer or
calculating device?
Chapter 2
Data representations
2.1
bit The digital computer processing hardware is made up of transistors, each of which can
exist in only one of two possible states, a state of high voltage or low voltage.
This state of high/low (or on/o) is represented abstractly as 1/0 (one/zero). A bit
is some piece of microscopic (usually!) hardware that can exist in either of these two
states as determined by a programmer or computer designer. In addition to the voltage
states in a transistor in a computers memory chips or processing chips, there are many
others forms: magnetic domains in a oppy disk, hard disk or magnetic tape, pits
in a CD or DVD, holes in paper tape or computer cards. Nowadays, there are billions
or trillions of bits of various forms in a typical computer. A bit may be simple, but
it is usually so small, typically well below a micrometer across (1 micrometer = 106
m), that we can conceive of cramming billions of them into a relatively small volume
of space. Some bits, particularly those in the processing chips of a computer, can also
be made to change states very rapidly, well under one nanosecond. (1 nanosecond =
109 s.) So, we can do a lot of dierent things with lots of bits in a very short span of
time.
nibble A nibble is a collection of 4 bits. A nibble can be in one of 24 = 16 separate
combinations of bits.
byte A byte is a collection of 2 nibbles, or 8 bits. A byte can be in one of 28 = 256
separate combinations of bits. This is enough to, for example, associate with each
unique pattern one of the characters of the English alphabet (upper and lower case)
plus all the common special characters we may use, for example, in writing English
prose or a technical document, e.g. !$&(),:; ?. And, there would be lots of room left
over to make other interesting associations.
7
word A word is a collection of bytestypically 4 for 232 = 4, 294, 672, 296 possible combinations. We can do a lot with all the dierent representations of words. We will
see, later in the lecture, how whole numbers can be associated with the various word
patterns.
The notion that many bits can conspire, in very large numbers, to produce wonderfully
intricate objects is illustrated in the following pictures of my dog, Matilda Skip Bielajew II.
(Yes, that is her real name!) The rst picture was generated from a le that was about 12
Megabytes, containing 96 million bits. It looks like real life. Yet, even when we zoom a little,
we start to see the eects of the underlying bit structure. Look at how her whiskers appear
jagged. Under extreme magnication (one of her whiskers, again) we see that the picture is
made up of at, uniformly colored tiles. Each one of these tiles is represented by 24 bits,
8 bits each for red, green and blue intensity, that, to all appearances, aords an apparently
uniform transition of color from tile to tile.
2.2
Decimal
assignment
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
We will use this particular representation in doing some simple arithmetic in the exercises
and the assignments.
2.3
Binary arithmetic
Let us pretend that we have to do some arithmetic (additions and multiplications) using only
binary numbers. The numbers 2,3,....9 do not exist! Only 0 and 1 exist. We also assume
that the operations of addition and multiplication are commutative (i.e. independent of the
order of the mathematical operation).
The addition of ctional binary numbersbase-2 arithmetic looks like:
10
0
1
10
11
10
.
.
1111
.
.
.
?
1
1
1
10
=
=
=
=
=
?
10
1
1
10
+ 0
= ?
+ 10
+ 11
+ 10
= 11
= 100
= 100
The multiplication of
0
?
=
1
?
=
10
10 =
10
11 =
11
11 =
.
.
.
1111 111 =
.
.
.
ctional
?
10
11
1001
111
1111 = 1101001
The arithmetic procedure is analogous to the more familiar base-10 system (that arose simply
because of our anatomy10 ngers). Additions of columns of numbers, subtraction, multiplication, the procedure of long division, can be accomplished by analogous procedures.
There is no limit to how long a ctional base-2 number can be and we may have to carry
along some extra information with each numberits sign.
2.4
2.4.1
Humans are usually quite awful at doing binary arithmetic. If you are doing such a calculation, you can check by converting the binary numbers into their decimal equivalents.
In general, to convert a whole binary number to a whole decimal number, consider a binary
number of the form:
bn bn1 bn2 b2 b1 b0 ,
11
where the bi s are either 0 or 1. We compute a decimal number using the following formula:
d10 = bn 2n + bn1 2n1 + bn2 2n2 b2 22 + b1 21 + b0 20 .
For example, the result of the two more dicult calculations above can be checked as follows:
101102 = 1 24 + 0 23 + 1 22 + 1 21 + 0 20 = 24 + 22 + 21 = 1610 + 410 + 210 = 2210
is the result of one of the additions [11112 (1510 ) + 1112 (710 )] above, while
11010012 = 26 + 25 + 23 + 20 = 6410 + 3210 + 810 + 110 = 10510
is the result of one of the multiplications [11112 (1510 ) 1112(710 )] above. Note that the
subscript 2 indicates a binary or base-2 number while the subscript 10 indicates a
decimal number.
2.4.2
Real numbers
2.5
12
32 bits is common (4294967296 possibilities). Soon, 64 bits (about 181018 ) will be the
standard. Some computers nowadays permit hardware 64-bit integer arithmetic.
Let us consider 32-bit computers onlythe most common type of hardware available today.
In the course of doing an arithmetic calculation, any bits that are set beyond the 32-bit
boundary are lostthey fall into the bit bucket and disappear.
2.5.1
A string of 32-bits can represent many things but we will focus on hexadecimal, unsigned
and signed integers. These signed integers must also carry information as to the sign of the
number. Historically, there have been several ways to do this. The industry has settled
on twos-complement arithmetic because it simplies the process of adding positive, negative or mixed numbers. In this scheme, to negate a signed integer, one takes the complement
(change all the 1s to 0s and all the 0s to 1s) of the binary representation and adds 1 to it.
This is seen in the table at the end of this chapter.
Lets give the notation i to the complement of the integer i. So, for any i,
i + i = 11111111111111111111111111111111. That is:
any 32-bit pattern
+ complement of the above
= 11111111111111111111111111111111
and
11111111111111111111111111111111
+ 00000000000000000000000000000001
= 00000000000000000000000000000000
since the 33rd bit can not be set! In twos-complement arithmetic the expression i j is
calculated as i + j + 1. So you see, computers can not really add and subtract, they can only
add (and take complements)!
A few examples help illustrate the simplicity of the twos-complement scheme. Consider a
4-bit representation of the number 310 = 00112 and 410 = 01002 . There are two tricks you
should apply here: a) every time you see a negative sign in front of a bit pattern, i, to be used
in a calculation, convert it to a positive sign, change i to i + 1 and do the binary addition,
and, b) if a nal result has a leading order (leftmost) bit set to 1, it is a negative number,
so, extract the minus sign and convert the resultant bit pattern j to j + 1.
310 + 410 = 00112 + 01002 = 01112 = 710
310 410 = 00112 01002 = 00112 + 11002 = 11112 = 00012 = 110
310 410 = 00112 01002 = 11012 + 11002 = 10012 = 01112 = 710
13
See how easily it all worked out! This is why the twos-complement approach has been
adopted. In order to handle negative integers one can convert them to their twos-complement
counterparts and add. Otherwise, special circuitry would have to be developed for handling
negative numbers and that would be less ecient.
2.6
32-bit computers can represent 232 = 4, 294, 672, 296 dierent things but ONLY 4, 294, 672, 296
dierent things. Now we consider the conventional assignments to unsigned and signed
integers. There is also the hexadecimal representation that is associated with every 4-bit
sequence, as indicated in the table below.
The unsigned integers associate the decimal number 0 to a string of 32 0 bits. The rest are
formed by the addition by 1 in either binary or decimal. The maximum unsigned integer,
therefore, is 4, 294, 672, 295. Adding a one to this causes all the 32 bits to go back to zero,
exactly as if you had cycled the odometer in your car! Its the same principle. There is
no 33rd bit, so you can imagine it just falls o the end.
The signed integers have the same sequence as the unsigned integers up to 231 1 =
2147483647 which is the bit pattern 01111111111111111111111111111111. Adding a one
to this gives a bit pattern of 10000000000000000000000000000000 which is interpreted as
231 = 2147483648. Note that these two are complements of each other and that they add
up to
11111111111111111111111111111111, which has the interpretation -1, consistent with the
twos-complement scheme described above.
14
2.7. PROBLEMS
2.7
15
Problems
010
011
110
001
100
001
16
Do your calculations in binary arithmetic and SHOW YOUR WORK! Quote your
results of your calculations in binary, integer, unsigned and hexadecimal integer representations.
(a) What is the sum of the integers 2 and 3?
(b) What is the sum of the integers -2 and -3?
(c) What is the sum of the integers -8 and -8?
(d) What is the product of the integers 2 and 3?
(e) What is the product of the integers -2 and -3?
(f) What is the product of the integers -8 and -8?
2.7. PROBLEMS
17
18
C D E F
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
0 X X X
9 X X
4 X
1
2.7. PROBLEMS
19
-3
-2
-1
20
2.7. PROBLEMS
21
22
1111
1000
1011
0010
0010
1110
1111
0110
0011
0000
0110
1010
0000
0011
1100
1101
1101
1111
0100
0111
1101
1000
0100
0011
1110
1001
1011
1001
0001
0010
0001
0001
1000
1100
0111
0111
1110
1110
1111
1000
0010
1100
0011
0001
0011
0011
1101
1011
1001
1101
0100
1110
1111
1000
1111
1010
hex
0100
1011
0000
0111
0101
1110
0010
1011
0000
0101
0110
0010
0001
0111
1111
0000
0100
0011
1011
0010
1010
1111
0111
0010
0001
1011
0011
0110
0110
1011
0111
1110
0111
1101
X
1101
X
0000
X
1101
X
1000
X
1000
X
0011
X
0101
X
0000
X
0011
X
0001
X
1111
X
0000
X
1011
X
0101
X
1101
X
0110
X
0001
X
0111
X
1101
X
1010
X
0111
X
1111 9A03FA6F
Chapter 3
Algorithms and Pseudocodes
In this chapter we introduce algorithms and ways with which algorithms can be represented.
At the end of the chapter, we also talk a little about computer architecture, as a way of
illustrating the operations that can happen inside a computer, when a part of an algorithm
is executed.
3.1
What is an algorithm?
24
3.2
Flowchart representation
START
STEP 1
STEP 2
STEP 3
STOP
The above gure is a representation of a simple sequence of 3 steps with a beginning and an
end. The START and STOP are represented by circles. A sequence step is represented by
a rectangle. The logic ow is indicated by lines and arrows. This kind of representation is
called a owchart or schematic diagram. It looks a lot like a circuit diagram in electronics.
3.3
Pseudocode representation
An algorithm is a well-dened description of actions and their ordering. Pseudocode is another way of expressing the actions and ordering to be taken place on a computer in an
exact way. Yet, pseudocode does it in an informal way, without getting bogged-down in the
details or syntax of a particular computer language like C++, MATLAB or something else.
Two programmers should be able to agree on pseudocode and write functionally equivalent
computer programseither in the same computer language or in dierent ones. Pseudocode
can be written in any human language in the form of an ordered (or numbered) list. For
example, a pseudocode representation of the above owchart would be:
START = Step 1 = Step 2 = Step 3 = STOP
A more conventional representation has the instruction ow (also called logic ow) going
from top to bottom:
25
START
Step 1
Step 2
Step 3
STOP
3.4
A conditional instruction or statement, also called a decision instruction, a branch or decision statement, is one in which a decision is made and the logic ow can follow dierent
paths, depending on the answer. In pseudocode it can be represented as follows:
IF such-and-such THEN DO
this-and-that
OTHERWISE DO
something-else
One could do the same thing with a owchart, and it would look like:
YES
THIS
&
THAT
SUCH
&
SUCH
NO
SOMETHING
ELSE
Note that we have introduced a new shape to handle the case where, depending on the input,
a decision is made and the logic ow can follow two dierent paths. This is represented by a
diamond shape. A branch statement or a decision statement is characterized by only one
path in and always two paths out.
3.5
A nal ingredient is needed before we complete our abstract discussion of algorithms the
ability for a statement to transfer control not to the next statement, but somewhere else in
26
ITEM 3
JUMP TO
ITEM 3
3.6
It can be shown that the 3 constructs of sequencing, branching and looping, are all that one
needs to construct any computer algorithm! Thus, the theory of algorithmic ow boils
down to understanding just these three things. There are many, many ways of expressing
these three things in a computer language like C++ or Matlab. But remember that it all
boils down to just sequencing, branching and looping. These are the three pillars of
algorithmic design!
Of course there is a lot of other stu to be considered to make a computer language useful.
Well see a lot of this in the course. However, as far as the ow of logic goes, we have done
it all at this point! You can now go and write an algorithm to do anything you want and
express it in either pseudocode or owchart form.
3.7
27
3.8
Some examples
28
3.8.1
3.8.2
29
Denitions: x is an unknown real number, A, B, C are xed constants that can take on any
valid real value. We are trying to nd the values of x for which Ax2 + Bx + C is zero. If we
plot the function f (x) = Ax2 + Bx + C, a parabola, it can look as shown in the gure below,
for certain choices of A, B, and C. The x-axis can intersect the curve f (x) = Ax2 + Bx + C
only 0, 1 or 2 times, depending on the values of A, B, and C.
NO SOLUTION
X
1 SOLUTION
X
2 SOLUTIONS
X
+
A
4A2 4A2 A
= 0
= 0
= 0
= 0
N.B.
A = 0
30
x2 +
=
=
=
=
x =
x =
B2
C
2
4A
A
B 2 4AC
4A2
B 2 4AC
(2A)2
B 2 4AC
N.B. B 2 4AC 0
2A
B
B 2 4AC
2A
2A
2
B B 4AC
A = 0, B 2 4AC 0
2A
So, under some circumstances, (A = 0, B 2 4AC > 0), we have two solutions:
B + B 2 4AC
B B 2 4AC
and x =
x=
2A
2A
corresponding to the last case in the preceding gure.
What if A = 0, B 2 4AC = 0? We have one solution:
x=
B
2A
31
32
START
IS
B2-4AC >- 0
?
NO
SOLUTION
STOP
Y
IS
A =/ 0
?
IS
B =/ 0
NO
SOLUTION
STOP
IS
B2-4AC = 0
?
X = -C / B
X = -B / (2A)
PRINT X
PRINT X
STOP
B2-4AC
X 1 = -B +
2A
B2-4AC
X 2 = -B -
2A
STOP
PRINT ( X 1 , X 2 )
STOP
Note that, although there is no reason to expect it, the owchart designer expects that
there will be two real solutions every time. This is reected in the owchart by this case
running vertically down the page, with the exceptions hanging o to the right. This makes
the owchart particularly easy to read.
3.8.3
33
Before you read this section, if you have never had any experience with programming, the
statement S = S + 1 should justiably seem to be completely wrong, since mathematically
it is equivalent to saying 0 = 1! Just cancel the Ss from either side! So, if this is the case,
kindly go and read the next section An aside on computer architecture and then come
back. Although mathematical statements and computer code statement may look the same,
they are completely dierent. Mathematics expresses an idea, while a line of computer code
represents an operation, or a set of individual operations.
34
START
N FIXED NUMBER
S IS UNKNOWN
S=1
S=S+2
S=S+3
.
.
.
S=S+i
.
.
.
S=S+N
PRINT S
STOP
35
START
N FIXED NUMBER
i = 1; S = 1
i=i+1
S=S+i
NO
i=N?
YES
PRINT S
STOP
There is an even better way! There is a mathematical solution to this that was discovered
by Gauss (Karl Friedrich Gauss (17771855 AD)) as a schoolboy!
S=
N(N + 1)
2
36
If N is even:
S =
=
=
=
3.8.4
Problem: Compute P = k N .
A very, VERY, dumb way (but one that works):
START k is an integer or a real (xed), N is an integer (xed) and P is an integer or a real
number (unknown)
P = k
P = P k
P = P k
.
.
.
P = P k (for the ith statement)
.
.
.
P = P k (for the Nth statement)
PRINT(P)
END OF ALGORITHM
Here is the ow chart for the very, VERY, dumb way:
37
START
N FIXED NUMBER
k FIXED NUMBER
P IS UNKNOWN
P=k
P=P*k
P=P*k
.
.
.
P=P*k
.
.
.
P=P*k
PRINT P
STOP
38
End of loop:
PRINT(P)
END OF ALGORITHM
START
i=i+1
P=P*k
NO
i=N?
YES
PRINT P
STOP
39
N FIXED
k FIXED
P = 1 (PRODUCT)
N>
- 1?
(N < 1)
NO
PRINT P
YES
YES
N=N/2
k=k*k
N even
?
NO
N=N-1
P=P*k
STOP
40
3.9
3.9.1
MEMORY
ADDER
CPU
R1 R2 R3 R4
00000000000000000000000000000000
S: 00000000000010010000100000100000
00000000000000000000000000000000
00000000000000000000000000000000
C: 00000000000000000000000000000001
00000000000000000000000000000000
00000000000000000000000000000000
3.10. PROBLEMS
41
3.10
Problems
42
For which of the following inputs will the algorithm say YES?
(a) 28
(b) 36
3.10. PROBLEMS
43
(c) 54
(d) 81
What property of the input is the algorithm determining?
6. Summing the squares
Describe an algorithm in either pseudocode or owchart form, to sum the squares of
the integers up to and including some N, where N is an input to the algorithm. That
is,
S = 12 + 22 + 32 + + N 2
where S is the sum. You must express your algorithm in terms of a loop that is traversed
N times. (There is a closed mathematical expression S = N(N + 1)(2N + 1)/6 that
you must not exploit in your algorithm. Pretend the closed mathematical expression
does not exist.) Make sure to declare and initialize all the variables you use.
7. Dont you love triangles?
A number N is called triangular if you can take N little asterisks and make an
equilateral triangle from them. For example, here are the rst few triangular numbers:
*
* *
3
*
* *
* * *
6
*
* *
* * *
* * * *
10
*
* *
* * *
* * * *
* * * * *
15
*
* *
* * *
* * * *
* * * * *
* * * * * *
21
Here is an algorithm that is attempting to detect triangularity in the input. But it has
a bug. Fix the algorithm.
START
OUTPUT Enter a positive integer
INPUT N
i=1
S=0
WHILE (S < N)
i=i+1
S =S+i
END WHILE
IF (S = N)
OUTPUT Triangular
44
8. De-Gauss this!
In this chapter we learned Mr. Gausss formula for the computation of the Nth triangular number:
1 + 2 + 3 + ... + N =
N(N + 1)
2
3.10. PROBLEMS
45
where x and N are inputs and S is the sum, an output. You must express your
algorithm in terms of a loop that is traversed N times. Express your algorithm in
terms of pseudocode and a owchart.
11. Lets talk about... the factorials of life
The factorial occurs in many places in mathematics and engineering applications and
life in general. The symbol for the factorial is the exclamation (!) mark. So, we would
call 3!, three factorial. Factorials are easy to calculate.
1! = 1
2! = 2 1
3! = 3 2 1
4! = 4 3 2 1
and so on.
If N is a whole number,
N! = N (N 1) (N 2) 2 1.
Note that N! = N (N 1)!, a neat property of factorials.
You will describe an algorithm to calculate the factorial of N where N is any whole
number greater than 1. You will describe an algorithm as if you were going to program
it on a computer, that is, you will specify a set of instructions that even a machine
can understand. The algorithm should include instructions on how to start and end.
You can assume that the machine on which the algorithm will be implemented can
store variables, loop, do branches, and do simple arithmetic. Express your algorithm
in terms of pseudocode and a owchart.
12. Decay and dissipation
You will describe an algorithm to calculate an approximation to the exponential function, ex . The following sum is a really good approximation to the exponential function,
ex , as long as the right hand side contains enough terms.
S =1
x x2 x3 x4
+
+
+
1! 2!
3!
4!
Let x and N, the number of terms on the right hand side, be inputs to the algorithm
and S, the sum, be the output. Note the use of the factorials in the above sum. Express your algorithm in terms of pseudocode and a owchart. Note that the algorithm
to raise x to a power is given in Chapter 3, Section 5 of the book.
Hint: The most ecient way to solve this problem is to rewrite S in the following
fashion:
S = s0 + s1 + s2 + s3 + s4 +
46
sn =
x
sn1
n
x3 x5 x7
x
+
1!
3!
5!
7!
Let x and the number of terms on the right hand side be inputs to the algorithm and
S, the sum, be the output. Note the use of the factorials in the above sum. Express
your algorithm in terms of pseudocode and a owchart.
14. The rich get richer, the poor get poorer!
The nancial investment rm of Getridge-Quigg, Ann Arbor, has a special deal for
students. If you deposit your money with them they will give you 0.5% interest per
month (a large amount these days) but then they will charge you a $5.00 per month
service charge applied against your account. If you have less than $5.00 in your account,
they take the remainder and your account is closed. So, if you deposited $1000.00 and
leave it there, your account will always have the same balance at the end of the month.
If you deposit more than $1000.00 and leave it there you may gain. Deposit less than
$1000.00 and your account may eventually be reduced to zero.
Write an algorithm that starts with an input of how much is to be deposited. You
intend to leave that money in the account and never add or withdraw from it. Your
algorithm will predict how many months it will take for you to double your money
or to reduce your account to zero. If the balance in your account never changes, you
have to state that as well. Note that Getridge-Quigg rst applies the interest and then
applies the service charge. After every calculation, Getridge-Quigg rounds the result
to the nearest penny. For example, the monthly interest on a balance of $1001.00 is
$5.01 while the monthly interest on a balance of $1000.99 is $5.00. You have to build
this fact into your algorithm.
Express your algorithm in terms of pseudocode and a owchart.
3.11. PROJECTS
3.11
47
Projects
1+c
1c
that you must not employ in your algorithm to determine the total distance traveled.
You have to obtain the solution by developing an algorithm that sums individually
every bounce of the ball.
Some discussion:
A ball made from putty will have c = 0 and an ideal ball (which does not really exist
in reality) would have c = 1. A fresh out-of-the-can tennis ball has c = 0.5 or so, an
old tennis ball has c = 0.25 or so. A ping-pong ball has c = 0.90 or so.
This problem is very much like Xenos paradox. The paradox is that mathematically
the total distance traveled by the ball is nite (as long as c is less than 1) but mathematically the total number of bounces is innite! However, after many bounces the
recovery distance becomes so small that accumulating them really does not matter in
any practical sense any more. If digital computers could really represent real numbers
to innite precision then it would be possible to write an algorithm that accumulates
the distance properly but it would never stop unless we introduced some articial means
of stopping the execution. Part of the purpose of this exercise is to get you thinking
48
Chapter 4
Getting started in C++
4.1
Here is a rst program in C++. You can type it in yourself, or download it from the web
from the lecture note distribution area for this class.
//File: goBlue.cpp
#include <iostream>
using namespace std;
int main(void)
{ cout << "Go Blue!\n";
// Multiple line statement
cout <<
"\n\n\t\"Go\t\t\\\n\t\t\t\tBlue!\"\a\a\a\r";
return(0);
}
There are several common features of every C++ program
Comments Comments start with /* and end with */. For example,
/* This is a comment */
49
50
51
using namespace std; Tells the compiler that we will be using that standard namespace
in the le that contains the line
using namespace std;
All this really means is that standard library les and denitions are being used. It is
possible to dene your own namespaces if you want to make sure that your variables
and denitions do not conict with either the standard ones, or someone elses, someone
working on the same project. For this course, we shall be using the standard namespace
for everything we do. If you go on to work in a professional programming environment,
writing software by teams, you will almost certainly be using your own namespaces.
int main(void){} All C++ programs begin processing at the rst executable statement in
main. The ()s indicate that main is a block of code called a function. The int in
front of main declares main to be a function that is expected to return an integer.
(More on this later.) main is a special function that the operating system recognizes
as the place to begin execution of a C++ program.
The lines of code in between the {}s is called the function body. It is considered good
programming practice to indent the text in the function body by a certain amount of
space. A common recommendation is 3 spaces which is reasonably pleasing to the eye.
We will adopt this convention for this course. In our example, the function body starts
with the statement
cout << "Go Blue!\n";
which instructs the C++ standard library function cout function to print the series
of characters Go Blue! (not including the double quotes) to the screen and then
positions the cursor at the beginning of the next line. This positioning is eected by
a special sequence of characters \n called an escape sequence. Escape sequences are
necessitated when special characters are required or to undo the meaning of special
characters, like the double quote () in the cout statement above. Here is a list of
some commonly used escape sequences employed in cout statements.
\n
\t
\r
\a
\\
\
52
\
Blue!"
Note that the statement starting with cout is terminated with a semicolon (;). This
is a special character in C++ called a delimiter that signies the end of a statement.
There can be more than one statement per line in a C++ code or a single statement
can span several lines. Generally it is considered to be good programming practice
to put at most only one statement per line of code. If a statement is long, put it on
several lines, space things nicely, and indent the carry-over lines 3 spaces relative to
the rst line, like in the example above.
return(0); When this line is encountered, processing in the CPU returns to the operating
system. Since main is a function of the int type, an integer value must be returned
to the process that called it, in this case the O/S. A return value of 0 usually means
normal execution, by convention. A return other than 0 can be treated as an error
condition by the O/S. For example, if your program had prompted for user input and
the user typed in something that the program was not prepared to process, one could
signify this to the O/S by returning a 1, for example,
return(1);
You can have as many returns as you need in a C++ code, just as you can have many
stop points in an algorithm.
4.2
Now that we have created a program, we have to tell the computer what to do with it! After
all, computers only understand binary code and our program is written (coded) in terms of
characters.
To compile the program, which we will call goBlue.cpp, the following statement on a unix
machine attempts a compilation:
53
54
Compile After the preprocessor, the compilation converts the code to object code also
known as binary code. There are actually several stages. The rst is the parsing stage
where the compiler checks the syntax of your code. If this stage is passed successfully
the next stage is the production of the assembly code from the C++ code which is
syntax-error free. Then the assembly code is converted to binary code, also called
object code.
Link After the object code is created the link stage is entered. At this point, references
to functions that may have been referenced in the C++ program are established.
These missing parts, in the form of object code, are either put in place directly where
referenced (this is called static linking) or their transfer locations are established so
that processing can transfer to these locations and be resumed. This is called dynamic
linking. The le created by the linker is called the load module. By default, the load
module is called a.out by the unix operating system. A user can override this name if
desired.
Load The loader takes the load module (usually located on disk) and puts it into memory in
a place where the operating system expects to see executable code. On a unix system
the loading phase is started when a user types the name of the load module resident
on disk.
Run In the run phase, the binary code in the memory-resident load module is transferred to
the central processing unit (CPU) for execution. The load module contains instructions
for the CPU that directs it to assign tasks to the various operational units of the
computer. The load module also contains data and references to data that are to
be operated on. The run phase is where conceptual errors in a computer program
are exposed. Code that has incorrect syntax, and syntax errors are quickly found by
the compilers parser, are usually easy to correct. Code that has correct syntax but
incorrect design are much harder to nd. This is where pseudocode and ow charts
can come to the rescue.
This model of editing, preprocessing, parsing, object-code generation, linking, loading
and running is followed by all computer code-development environments, from the most
simple Go Blue! C++ program to the most complex, like the telephone management
system, international banking systems and the national security systemsirrespective
of the language it is written in. The following gure includes not only the code compilation process, but also describes the whole process of code development. It is general,
and mostly independent of the computer language being employed.
55
THINK
PSEUDO CODE
FLOWCHART
BAD DESIGN
TYPE IT IN / EDIT
STEAL AS MUCH
AS POSSIBLE
1) PRECOMPILING
COMPILE
FAILURE
2) PARSING
3) CREATES OBJECT
LINK / CREATE
LOAD MODULE
RUN
FAILURE
REFINEMENT
SUCCESS!
4.3
Consider the following C++ program that does mathematical operations with two integers:
//File: integerMath.cpp
#include <iostream>
56
57
31, for safety. Beyond the limit of 31 or greater, your compiler may treat the characters
beyond it as signicant or insignicant (i.e. ignores them). For absolute safety, use 31
characters or less. Identiers in C++ are case sensitive so that i1 and I1 are recognized
as dierent variables. Unless your program is very short, you should name your identiers
in some recognizable wayit cuts down on the amount of commenting you have to do. I
also like humpback notation, numberOfStudents, rather than number_of_students. Note
that humpback identiers start with lowercase letters (usually) and new words within the
identier start with an uppercase letter. I nd underscores in the middle of identiers ugly,
wasteful and hard to type.
The statement
int i2 = 2;
is another declaration statement that identies the name i2 and declares it to be a signed
integer initialized to the value 2.
The statement
int iResult;
is another declaration statement that identies the name iResult and declares it to be a
signed integer. In this case the variable is not initialized.
4.4
The statement
iResult = i1 + i2;
contains two mathematical operators, = and +. The operator = is called the assignment
operator . Do not call it the equal sign! The assignment operator assigns the result of
the operation(s) to the right of it to the value of the identier to the left of it, iResult in
this example. = is called a binary operator because it operates on only two quantities, the
variable to the left which gets the assignment and the quantity to the right that provides
the assignment (after the other mathematical operations are completed).
The operator + is called the addition operator . It is also a binary operator and provides the
mathematical sum of the quantities to its left and right.
There are 4 other binary operators to consider now, the subtraction, -, the product, *, the
division, /, and the modulus, %. Of these the division requires special mention with regards
58
to its operation with integers. The integer division returns the integer part of the result. For
example, 5/2 = 2, not 2.5. The remainder of a division can be obtained from the modulus
function %. Thus 5 % 2 = 1.
The various mathematical operations, when employed within the same statement, follow
certain ordering rules. These are called the rules of precedence. The *, / and % operations
take precedence over + and -. *, / and % have the same precedence, and + and - have the
same precedence as well. For operators with the same precedence, the order of operation is
left to right. For example,
1 + 10 * 5 - 9 / 3 = 1 + 50 - 3 = 48
If a programmer desires a dierent interpretation of the above statement or wishes to make
the operation clearer, parentheses may be employed. Parentheses take precedence over *, /,
%, + and -. Inner parentheses are evaluated rst. For example,
(1 + (10 * 5) - (9 / 3)) = 1 + 50 - 3 = 48
is operationally equivalent to the above. However,
((1 + 10) * (5 - 9)) / 3 = (11 * (-4))/3 = -44/3 = -14
is quite dierent.
Summarizing, the order of precedence is
Order
0
1
2
3
Symbol
Operation
Comments
()
parentheses
inner ones evaluated rst
(unary) negation (unary minus)
RL evaluation
*/%
product, division, modulus
LR evaluation
+addition, subtraction
LR evaluation
The statement
cout << "5 + 2 = " << iResult << "\n";
prints the characters 5 + 2 = to the screen then the value of iResult and then sends
the newline escape sequence. There are more exible ways of printing things to the screen
and we shall encounter these shortly. Note how we can cascade the << operator for cout.
An equivalent way of accomplishing the same thing would be:
cout << "5 + 2 = ";
cout << iResult;
cout << "\n";
59
which is a little harder to read. Break up your output statement like this only for neatness
and readability.
4.5
Consider the following C++ program that does mathematical operations with two oats:
//File: floatMath.cpp
#include <iostream>
using namespace std;
int main(void)
{ cout << "Input the 1st floating point number: ";
float f1; // Declare the 1st float
cin >> f1; //and read it in
cout << "Input the 2nd floating point number: ";
float f2;
cin >> f2;
float fResult = f1 + f2; // sum
cout << f1 << " + " << f2 << " = " << fResult << "\n";
fResult = f1 - f2; // difference
cout << f1 << " - " << f2 << " = " << fResult << "\n";
fResult = f1 * f2; // product
cout << f1 << " * " << f2 << " = " << fResult
<< "\n";
if (0 == f2)
{ cout << "Division by zero not permitted!\n";
return(1);
}
else
{ fResult = f1 / f2; // division
cout << f1 << " / " << f2 << " = " << fResult << "\n";
return(0);
}
}
60
4.6
The if/else if/else construct is one of the most important programming features of C++
and common to many computer languages. It has a single-choice form called if, a doublechoice form called if/else and multiple-choice forms if/else if and if/else if/else.
The general form of the if/else if/else is:
if (logical expression 1 )
{
STATEMENT BODY 1
}
else if (logical expression 2 )
{
STATEMENT BODY 2
}
else if (logical expression 3 )
{
STATEMENT BODY 3
61
}
.
.
.
else if (logical expression N + 1 )
{
STATEMENT BODY N + 1
}
else
{
STATEMENT BODY N + 2
}
There are many forms of the if/else if/else construct:
The else if (logical expression) { STATEMENT BODY } is optional
The else { STATEMENT BODY } is also optional, independent of the above
If the STATEMENT BODY consists of one and only one statement, then the surrounding
{}s are optional. (It can help with clarity of programming to keep them, however.
Their use is highly recommended.)
Note the use of indenting, optional but highly recommended
At most one and only one of the STATEMENT BODY s can execute within an if/else
if/else construct can be executed
Processing control passes to the statement immediately following the if/else if/else
construct after execution of one of the STATEMENT BODY s.
If the if/else if or if form is used, it may happen that none of the logical conditions is satised. In this case processing control passes to the statement following the
construct.
if/else if/else constructs can be nested within each other
This is the ow chart for the if construct:
62
?
F
F
?
?
T
T
63
F
?
?
T
T
4.7
Logical expressions
if (1)
cout << "This would always print,\n";
else if (0)
cout << "whereas this would NEVER print\n";
Here are some of the logical operators and their order of precedence
64
Symbol
Operation
Comments
()
parentheses
inner ones evaluated rst
(unary) !
negation (unary NOT)
RL evaluation
<=,<
less than or equal, less than
LR evaluation
>,>=
greater than, greater than or equal
LR evaluation
==,!=
equivalent to, not equivalent to
LR evaluation
Lets return to the example of solving the quadratic equation, Ax2 + Bx + C = 0 that we
studied in owchart and pseudocode form in Lecture 3. If we look at the pseudocode on
page 7 of Lecture 3 we see that the ifs are nested and we would probably, at rst try, write
a code that looked something like the following, using only ifs and elses:
//File: quadratic.cpp
#include <iostream>
#include <cmath>
using namespace std;
int main(void)
{ float a,b,c; // Declare the constants...
cout << "\n"
"We will solve for x in Ax*x + B*x + C = 0\n"
"=========================================\n"
"\n";
cout << "Input A,B,C: ";
cin >> a >> b >> c; //...and read them in
cout <<
"Calculating roots (x) of the equation\n"
<< a << "*x*x + " << b << "*x + " << c << " = 0...\n";
if (0 > b*b - 4*a*c) //b*b - 4*a*c is less than 0
{ cout << "No solution since b*b-4*a*c < 0\n";
return(0);
}
else // b*b - 4*a*c is >= 0
{ if (0 != a)
{
cout <<
"Soln 1 = " << (-b + sqrt(b*b - 4*a*c))/(2*a) << ", "
65
66
0
<< "\n";
4.7.1
Here are more of the logical operators and their order of precedence:
Precedence Symbol
Operation
0 (rst)
(,)
parentheses, paired
1
(unary) !
negation (unary NOT)
2
<=,<
less than or equal, less than
2
>,>=
greater than, greater than or equal
3
==,!=
equivalent to, not equivalent to
4
&&
logical AND
5 (last)
||
logical OR
Comments
LR evaluation
RL evaluation
LR evaluation
LR evaluation
LR evaluation
LR evaluation
LR evaluation
The AND and OR operators work as follows. Imagine that two logical expressions evaluates
to either T (TRUE) or F (FALSE). This is the result of the && and ||s operating on them.
67
(T
(T
(F
(F
(T
(T
(F
(F
&&
&&
&&
&&
||
||
||
||
T)
F)
T)
F)
T)
F)
T)
F)
==
==
==
==
==
==
==
==
T
F
F
F
T
T
T
F
Sometimes these tables are dicult to remember, at least as abstract concepts. This is
helped somewhat if we substitute numerical values for T (1) and F (0).
(1
(1
(0
(0
(1
(1
(0
(0
&&
&&
&&
&&
||
||
||
||
1)
0)
1)
0)
1)
0)
1)
0)
==
==
==
==
==
==
==
==
1
0
0
0
1
1
1
0
Once we do this we realize that the result of (A && B) is the lower value of either A or B. The
result of (A || B) is the higher value of either A or B. It is no more complex than that! And
this is, in fact, how the electronic circuitry works in a computer during the interpretation of
logical expressions.
Some examples:
int i = 5;
if (0 < i && 10 > i)
cout << i << " is a positive, single digit integer\n";
if (0 > i || 10 <= i)
cout << i << " is either negative, or has more than one digit\n";
4.7.2
It is possible to mix arithmetic and logical expressions. Usually it is done where a logical
expression is expected, such as within an if/if else/else construct. It is also possible to
mix these operators elsewhere, where a regular statement is expected. Dont do it unless
you really, really have to for some purpose!
68
When logical operators and arithmetic operators are mixed in a single expression, the order
of precedence is as follows. Above all, the contents of parentheses are evaluated starting with
the innermost. Then the arithmetic operators get interpreted in the order already discussed.
Finally, the logical operators get interpreted in the order already discussed. Here is the table
for precedence for both arithmetic and logical expressions.
Precedence
0 (rst)
1
2
3
4
4
4
5
6
7 (last)
Symbol
( )
(unary) - !
* / %
+ <=,<
>,>=
==,!=
&&
||
=
Operation
parentheses, paired
negation
multiply, divide, modulus/remainder
add, subtract
less than or equal, less than
greater than, greater than or equal
equivalent to, not equivalent to
logical AND
logical OR
assignment
Comments
LR evaluation, innermost rst
RL evaluation
LR evaluation
LR evaluation
LR evaluation
LR evaluation
LR evaluation
LR evaluation
LR evaluation
RL evaluation
When in doubt, use parentheses. When not in doubt, use parentheses anyway. The
person reading your code may have forgotten all but the rst rule of precedence, parentheses
are interpreted rst. This will make your code more readable and understandable.
In fact, that is the convention I have adopted in almost all of my programming, put parentheses around every logical sub-expression in any logical expression that contains more than
one logical operators. I also put parentheses around any arithmetical sub-expression in a
mixed arithmetic/logical expression.
Heres an example of a mixed arithmetic and logical expression. Use the rules of precedence
stated above to see how the following statement is evaluated:
if (i*j == i*i + j*j || i - j <= i*i - j*j && i + j <= i*i + j*j) ...;
The ordering of && and || is also quite important. For example, using the rules of precedence
the above could collapse to 1 || 1 && 0 which is 1 or TRUE. However, if you mistakenly
thought that the || is evaluated rst, you would guess that the answer should be 0 or FALSE,
and that is the wrong answer in this case.
4.8. PROBLEMS
4.8
69
Problems
=
=
=
=
=
=
1 + 2*3/4+5;
1.0 + 2.0 + 3.0/4.0 + 5.0;
(1 + 2)*3/4 + 5;
(1.0 + 2.0)*3.0/4.0 + 5;
1 + 2 + 3/4 + 5;
1 - (static_cast<int>(6*5/4.0*3))/2;
70
0;
0)
<< "The conditional expression was TRUE\n";
int i = 0;
if (0 != i)
4.8. PROBLEMS
71
y
y
y
y
y
y
y
y
y
72
4.9. PROJECTS
4.9
73
Projects
74
4.9. PROJECTS
75
76
4.9. PROJECTS
unix-prompt> a.out
Bit b0: 0
Bit b1: 1
Bit b2: 0
Bit b3: 1
Bit b4: 0
5-bit bit pattern is: 0 1 0 1 0
Bit pattern represent an even unsigned integer
Bit pattern represent a positive signed integer
Unsigned integer representation is: 10
Complement 5-bit bit pattern is: 1 0 1 0 1
Signed integer representation is: 10
unix-prompt> a.out
Bit b0: 1
Bit b1: 1
Bit b2: 1
Bit b3: 1
Bit b4: 0
5-bit bit pattern is: 0 1 1 1 1
Bit pattern represent an odd unsigned integer
Bit pattern represent a positive signed integer
Unsigned integer representation is: 15
Complement 5-bit bit pattern is: 1 0 0 0 0
Signed integer representation is: 15
unix-prompt> a.out
Bit b0: 1
Bit b1: 1
Bit b2: 1
Bit b3: 0
Bit b4: 1
5-bit bit pattern is: 1 0 1 1 1
Bit pattern represent an odd unsigned integer
Bit pattern represent a negative signed integer
Unsigned integer representation is: 23
Complement 5-bit bit pattern is: 0 1 0 0 0
Signed integer representation is: -9
unix-prompt> a.out
Bit b0: 1
Bit b1: 0
77
78
4.9. PROJECTS
79
10101
x
11
-----...is the same as the addition...
10101
+01010
-----11111
>
Here is another example of running the code:
> a.out
What do you want to do?
Type a 0 if you want to add two 5-bit strings
Type a 1 if you want to multiply a 5-bit string by a 2-bit string
(0 or 1): 0
Enter the 1st 5-bit binary number to be added: 1 0 1 0 1
Enter the 2nd 5-bit binary number to be added: 1 0 0 1 1
10101
+10011
-----01000
>
6. Change for the good
You will write a program that will accept an input, a real number between 0.00 and
19.99 inclusive. This represents the change in dollars from the purchase of an item
using a $20 bill. You will write a C++ program that will calculate the most ecient
form that the change may be given in terms of $10, $5, and $1 bills plus quarters,
dimes, nickels and pennies.
Heres an example of how it should work. Note that the program was run twice. The
rst time the input was 19.94, the second time 16.26. Note how the program correctly
uses singular (One penny) and plural (Four $1 bills).
80
4.9. PROJECTS
81
82
Chapter 5
Loops
Loops are the third and nal programming element we need to write any algorithm. The
C++ language provides three easy ways to do this, the while, do/while and for loops.
5.1
84
CHAPTER 5. LOOPS
It puts your computer in a state known formally as hung, as in, Jeepers, I think
my computer is hung. It is NOT a compliment! Hung computers are put out of their
misery by a variety of desperate measures, increasing in severity. At the very worst,
the power has to be shut down, a really nasty, last resort for a hung computer.
F
T
STATEMENT BODY
85
Sum = Sum + i;
}
cout <<
"Sum of " << N << " digits is " << Sum
<< "...according to Gauss: " << N*(N+1)/2 << "\n";
return(0);
}
Heres a more compact (but dangerous way) to do it:
//File: gaussAgain.cpp
#include <iostream>
using namespace std;
int main(void)
{ cout << "Input N: ";
int N;
cin >> N;
int i = 0, Sum = 0;
while (i = i + 1 <= N) Sum = Sum + i; //NO, NO, NO!
cout <<
"Sum of " << N << " digits is " << Sum
<< "...according to Gauss: " << N*(N+1)/2 << "\n";
return(0);
}
This is dangerous because if you forgot the parentheses around the i = i + 1 part of the
conditional, you would generate an innite loop! Dont believe me? Try it! Um, wait, this
is a forever loop! OK, try it, but <CNTL>-C out of it after a few seconds.
The point istry to make your coding as easy to interpret as possible. Dont be too clever.
Dont save space just for the purpose of saving space at the expense of clarity. In the old days
of computing, memory and disk space were very expensive and precious. Programmers prided
themselves at making things very compact. Those days are, happily, long gone. However,
there still are people who do this. Maybe they think that an electron is as expensive as a
Higgs boson1 .
1
Electrons are essentially free. There are countless numbers of them in everyday things, like water. The
86
CHAPTER 5. LOOPS
5.2
Higgs boson is very expensive. Physicists are spending billions to nd it. It has not been found yet, but
almost! The rst person to nd it will win the Nobel Prize for physics.
87
STATEMENT BODY
T
F
The only thing that really distinguishes a do/while loop from a while loop is that the
do/while loop evaluates the conditional at the end of the STATEMENT BODY and the while
loop evaluates it at the beginning. while loops are often used when incrementing a counter
and using (and usually updating) the counter within the statement body. do/while loops
are useful if you always want to process the STATEMENT BODY at least once. Because of this,
loops that accept input from the keyboard (or a le) make good use of the do/while loop
especially when the input is terminated using a sentinel.
Here is an example of sentinel controlled output for calculating the average of student grades.
The sentinel for stopping is when the input for a grade is less than zero. Even the cruelest
professor does not hand out a negative grades (even though it is legal)! So, this is a good
sentinel to use for this application.
//File: grades.cpp
#include <iostream>
using namespace std;
88
CHAPTER 5. LOOPS
int main(void)
{ int nStudents = 0, grade, sumGrades = 0;
do
{ cout << "Input a grade: ";
cin >> grade;
if (0 > grade) cout << "Grade < 0, end of input.\n";
else
{
nStudents = nStudents + 1;
sumGrades = sumGrades + grade;
}
}while (0 <= grade);
if (0 < nStudents)
cout << nStudents
<< " grades were read in. "
<< "The class average is: "
<< sumGrades/nStudents
<< "\n";
return(0);
}
Note that the above calculates the average as sumGrades/nStudents, the result of an integer
division. This may not be completely fair as an average of, say, 79.9 should not really be
reported as 79.
The way to x this is to make the following changes:
1. Add the following #include in the pre-processor area of the code:
#include <iomanip>
2. Modify the cout statement as follows:
cout <<
<<
<<
<<
<<
<<
<<
nStudents
" grades were read in. "
"The class average is: "
setw(5) //Set field width to 5
setprecision(3) //3 digits of precision
static_cast<float>(sumGrades)/nStudents
"\n";
89
The code in its entirety can be found in the lectures area on the web. It is called grades1.cpp.
There are two new features in the cout statement. One is the introduction to the unary
cast operator static_cast<float>(expression) which converts sumGrades temporarily
(and internally) to a oat and the resulting calculation takes place as if it were a divide using
oats alone. It is not necessary to make the same conversion for nStudents. The division
of a oat by an integer or an integer by a oat always results in a oating point calculation
as the integer participating is promoted to a oat.
The general form of the cast operator is
static_cast<type_name>(expression) //Dont forget the parentheses!
to change expression to the type type_name. So, oats can be changed to ints and viceversa. It is possible to change among other types of variables that we will encounter later.
The other new feature is the use of a eld width and precision to modify the output of
the oat. The function setw(m) sets aside m spaces to print. The function setprecision(n)
prints n signicant digits. These functions are dened in the iomanip (I/O stream manipulator) library le. Hence, we had to include this le, else the compiler would have complained.
Note how these functions are employed. setprecision() only has to be set once. The
stream handlers remember it. However, setw() has to be set for every item!
There is another commonly used stream manipulator called fixed. We will not use it much.
5.3
The for loop is similar to the while loop except that the syntax makes explicit the initialization, the looping condition and the loop counter modication. This form is generally
preferred if the loop is to be performed in a systematic fashion, to a well-dened termination
criterion with a regularly-spaced or easy-to-calculate loop counter indexing.
The general form of a for loop is:
for (expression 1; logical expression; expression 2)
{
STATEMENT BODY
}
Some features of the for loop:
If the STATEMENT BODY consists of one and only one statement, then the surrounding
{}s are optional. (It can help with clarity of programming to keep them, however.
Their use is highly recommended.)
90
CHAPTER 5. LOOPS
Note the use of indenting.
Processing control passes to the statement immediately following the for construct
after condition tested by the logical expression fails.
for loops (in fact, any repetition loop) can be nested within each other.
The logical expression is intended to provide the condition for which the execution
of the for loop terminates. This logical expression can mix arithmetic and logical
operators to make for compact coding. (This is not really recommended for novice
programmers and often makes code hard to read.)
The STATEMENT BODY will not be executed if the logical expression is false initially.
expression 1 is intended to initialize the loop counter (or index). Its use is optional.
However, in this case the initialization of any counters (should they be used) should
be done beforehand.
The use of the logical expression is also optional. If not provided, the STATEMENT
BODY is always entered. Another way of exiting the loop has to be provided otherwise
the loop is innite.
The two ;s in the denition of the for loop are NOT optional. Leaving one or both
out will result in a compilation error.
91
EXPRESSION 1
F
T
STATEMENT BODY
EXPRESSION 2
92
CHAPTER 5. LOOPS
int screenHeight;
cin >> screenHeight;
for (int i = 10;
{
// Next line
for (int j =
cout << i <<
}
i >= 0 ; i = i - 1)
should waste about 1 second
0; j <= loopsPerSecond; j = j + 1) ;
"\n";
93
94
CHAPTER 5. LOOPS
5.4
Problems
1. Flowcharts revisited
Draw the owchart representation (using lines, arrows, rectangles, diamond-shapes,
and words) for the following looping constructs:
(a) the for-loop:
for (i = 10; i > 0; i = i - 1){Sum = Sum + i;}
(b) the do/while loop:
do{cin >> oddNumber; odd = oddNumber%2}while(!odd);
(c) the while loop:
while (different){z = x; y = x; x = temp; different = x - y;}
2. Loop tests
(a) How many times is the following loop body executed?
int i = 0;
do
{ i = i + 1;
} while (i < 0);
(b) How many times is the following loop body executed?
int i = 0;
while(i < 0)
{ i = i + 1;
}
(c) How many times is the following loop executed?
int i = 3;
while(i)
{ i = i - 1;
}
(d) How many times is the following loop body executed?
int i = 0;
while(i <= 0)
{ i = i - 1;
}
(e) How many times is the following loop executed?
5.4. PROBLEMS
95
int j = 1;
do
{ j = -2*j + 1;
}while(j != 0);
(f) How many times is the following loop body executed?
for(int i = 0; i < 10; i = i + 2)
{ cout << "i = " << i << "\n";
}
3. Predict the output
The examples of code given below all compile correctly. Predict the output that the
code would produce if you compiled and ran it.
(a) int N =
if (N =
cout
else
cout
0;
0)
<< "The conditional expression was TRUE\n";
<< "The conditional expression was FALSE\n";
(b) int f;
for(f = 0; f <= 10; f = f + 2)
cout << f%10;
cout << "\n";
(c) int i = 0, Sum = 0, N = 3;
do
{ i = i + 1;
Sum = Sum + i;
}while(i <= N);
cout << "Sum = " << Sum << "\n";
(d) int i = 0;
if (0 != i)
cout << "Statement 1\n";
cout << "Statement 2\n";
cout << "Statement 3\n";
(e) int j = 0;
if (0 < j);
{ j = j + 1;
}
cout << "j = " << j << "\n";
(f) int i = 2, j = -2;
while (j <= i)
96
CHAPTER 5. LOOPS
{
if (j < 0)
cout << "i is " << i << ".";
cout << " j is " << j << ".\n";
i = i - 1;
j = j + 1;
}
4. Loop drills
(a) Convert the following code containing a do/while loop to a code containing a
while loop in such a way that the execution of the code is identical.
int j = 0;
do
{ j = j + 1;
cout << j << "\n";
}while (j <= 10);
cout << j << "\n";
(b) Convert the following code containing a while loop to a code containing a do/while
loop in such a way that the execution of the code is identical.
int j = 10;
while (j > 0)
{ j = j - 2;
cout << j << "\n";
}
cout << j << "\n";
(c) Consider the following code:
#include <iostream>
using namespace std;
int main(void)
{ int x = 1;
for (int i = 1; i <= 10 ; i = i + 1)
{ x = x*2;
cout << x << " ";
}
cout << endl;
return 0;
}
5.4. PROBLEMS
What does the above code print to the screen when you run it?
Draw the ow chart for the for loop in the above program.
(d) Consider the following code:
#include <iostream>
using namespace std;
int main(void)
{ int i = 5;
do
{ i = i - 1;
cout << i << " ";
}while(i);
cout << endl;
return 0;
}
What does the above code print to the screen when you run it?
Draw the ow chart for the do{}while(); loop in the above program.
(e) Consider the following code:
#include <iostream>
using namespace std;
int main(void)
{ int i = 13;
while(i%2)
{ i = i/3;
cout << i << " ";
}
cout << endl;
return 0;
}
What does the above code print to the screen when you run it?
Draw the ow chart for the while(){}; loop in the above program.
(f) Consider the following code:
#include <iostream>
using namespace std;
97
98
CHAPTER 5. LOOPS
int main(void)
{ for (int i = 1; i <= 2; i = i + 1)
for (int j = 1; j <= 3; j = j + 1)
cout << i << "," << j << endl;
return 0;
}
What does the above code print to the screen when you run it?
Draw the ow chart for the nested for loops in the above program.
5. Think Like a Computer
Consider the following C++ code.
#include <iostream>
#include <cmath>
using namespace std;
int main(void)
{ float x;
cout << "Input x (must be positive): ";
cin >> x;
int i = 0;
const int NMax = 1000;
const float SMALL = 0.0001;
float xPower = 1.0, lastTerm, Sum = 0.0;
do
{ i = i + 1;
xPower = x*xPower;
lastTerm = xPower/i;
Sum = Sum + lastTerm;
}while (i < NMax && lastTerm > SMALL);
if (i == NMax)
cout << "Series did
else
{
cout << "i
=
<< "x
=
<< "lastTerm =
<< "Sum
=
}
not converge\n";
"
"
"
"
<<
<<
<<
<<
i << "\n"
x << "\n"
lastTerm << "\n"
Sum << "\n";
5.4. PROBLEMS
99
return 0;
}
(a) What series is being summed by this code? Sum = x + (you provide the rest)
(b) If the user inputs -1.0 for x, what will be printed out by this code?
(c) If the user inputs 0.0 for x, what will be printed out by this code?
(d) If the user inputs 1.0 for x, what will be printed out by this code?
(e) If the user inputs 0.0001 for x, what will be printed out by this code?
(f) If the user inputs 0.001 for x, what will be printed out by this code?
(g) If the user inputs 0.01 for x, what will be printed out by this code?
(h) If the user inputs 0.1 for x, what will be value of i that is printed out by this
code? (A hand calculator may help.)
6. Think Like a Computer Again
Consider the following C++ code.
#include <iostream>
#include <cmath>
using namespace std;
int main(void)
{ float x;
cout << "Enter x: ";
cin >> x;
int n = 0;
float lastTerm;
const float EPSILON = 0.001;
float sign = 1;
float denominator = 1;
float total = 1;
while(n <= 1 || lastTerm > EPSILON)
{ n = n + 1;
if (n/2*2 == n)
{ denominator = denominator*n*(n - 1);
lastTerm = pow(x,n)/denominator;
sign = -sign;
total = total + sign*lastTerm;
cout << "Term " << n << " is " << lastTerm << "\n";
100
CHAPTER 5. LOOPS
}
}
cout << "The total is " << total << "\n";
return 0;
}
(a) If you input 0.01 for x, what will be printed out?
(b) If you input 1.0 for x, what will be printed out? (A hand calculator may help.)
(c) What is another condition for the if statement that gives the same result?
(d) What is the formula this program is implementing?
5.4. PROBLEMS
101
(b) Conversion part: Convert the program in the rst part of this question to use
a do-while loop rather than a for loop. Write your solution in the space below.
8. Predict and convert again
(a) Prediction part: If you compiled and ran this program, exactly what would the
output look like?
#include <iostream>
using namespace std;
int main(void)
{ const int maxTerms = 8;
const int x = 2;
int term = 1;
int sum = 1;
cout << "Sum = 1";
for (int i = 1; i <= maxTerms; i = i + 1)
{ term = -term*x;
if (0 != i%3 && 0 != i%4 )
{ if (0 > term) cout << " - " << -term;
else cout << " + " << term;
sum = sum + term;
}
}
cout << " = " << sum << "\n";
return 0;
}
(b) Conversion part: Convert the program in the rst part of this question to use
a while loop rather than a for loop. Write your solution in the space below.
9. Fix the bugs
Consider the following C++ code. It is an attempt to do the sum:
S = 1 x2 + x4 x6 + x8 x10
The code has errors that the compiler detects as indicated in the comment lines. Fix
them. The code also has conceptual errors in some lines, also indicated by comments.
Conceptual errors are those that compile without error but do not provide correct
answers upon execution. Fix these as well.
102
CHAPTER 5. LOOPS
#include <iostream>
using namespace std;
int main(void)
{ float x;
cout << "Input x: ";
cin >> x;
float Sum, p; // Conceptual errors on this line
int N = 10;
do
{ i = i + 2; // Compiler detects error on this line
p = p*x; // Conceptual errors on this line
Sum = Sum + p;
}while(i <= N); // Compiler detects error on this line
cout << "Sum = " << Sum << "\n";
return 0;
}
2!
3!
4!
5!
2
The code has errors that the compiler detects as indicated in the comment lines. Fix
them. The code also has design aws in some lines, also indicated by comments.
Design aws are those that compile without error but do not provide correct answers
upon execution. Fix these as well. The corrected code should be able to compile and
calculate the above sum.
5.4. PROBLEMS
103
1
2
3
4
5
is
is
is
is
is
a queen of spades.
a 3 of spades.
an ace of diamonds.
a king of diamonds.
a 7 of clubs.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main(void)
{ srand(time(NULL));
for(int nCards = 1; nCards <= 5; nCards = nCards + 1)
{ int rank = rand()%13 + 1;
// You fill in the rest
.
.
.
.
} // End of the for loop over the 5 cards
return 0;
} // End of the main routine
104
CHAPTER 5. LOOPS
5.4. PROBLEMS
105
program that will accept a positive oat for the starting balance and output how much
money you will have at the end of each year. The program stops when your money
has at least doubled.
Heres an example of how it works:
% a.out
Input the starting balance: 1000
After
After
After
After
After
After
After
After
After
After
After
After
After
After
After
%
year
year
year
year
year
year
year
year
year
year
year
year
year
year
year
1, balance = 1050
2, balance = 1102.5
3, balance = 1157.62
4, balance = 1215.51
5, balance = 1276.28
6, balance = 1340.1
7, balance = 1407.1
8, balance = 1477.46
9, balance = 1551.33
10, balance = 1628.89
11, balance = 1710.34
12, balance = 1795.86
13, balance = 1885.65
14, balance = 1979.93
15, balance = 2078.93
106
CHAPTER 5. LOOPS
currentMonth = (startMonth + i) % 12;
calculates the month, given a starting month and a number of months elapsed. For
example, if you start in January (Month 1), 13 months later it is February (Month 2).
5.4. PROBLEMS
red% a.out
Input an odd
Input an odd
Input an odd
Input an odd
***********
*********
*******
*****
***
*
red%
107
positive
positive
positive
positive
int:
int:
int:
int:
-1
0
2
11
108
CHAPTER 5. LOOPS
*
**********
*
*
**********
*
*
**********
*
*
**********
*
*
**********
*
*
**********
*
*
**********
*
*
**********
*
*
**********
*
*
**********
*
*
********** *
*
********** *
*
***********
*
**********
*
*********
*
********
*
*******
*
******
*
*****
*
****
*
***
*
**
****************************************
You ...
must use for-loops, some nested, some not.
may not use arrays. (Ignore this statement of you do not know what an array is.)
must only use cout statements that have only single character strings, for example,
cout << "*";. Something like cout << "**"; or cout << " *"; is not permitted. Spaces are counted as a character. For example, the top line would made
correctly as follows:
const int width = 4;
for (int i = 1; i <= width; i = i + 1) cout << "*";
cout << endl;
rather than the following which is not allowed,
cout << "**************************************************";
The width and length of the drawing are exactly 40 characters.
5.4. PROBLEMS
109
110
CHAPTER 5. LOOPS
You must only use cout statements that have only single character, for example,
cout << "*";. Something like cout << "**"; or cout << " *"; is not permitted. Spaces are counted as a character.
test = 1000
4*4 = 5*5 = 25
12*12 = 13*13 = 169
15*15 = 17*17 = 289
24*24 = 25*25 = 625
+ 21*21 = 29*29 = 841
+ 35*35 = 37*37 = 1369
40*40 = 41*41 = 1681
+ 45*45 = 53*53 = 2809
+ 60*60 = 61*61 = 3721
+ 63*63 = 65*65 = 4225
+ 56*56 = 65*65 = 4225
+ 55*55 = 73*73 = 5329
+ 84*84 = 85*85 = 7225
+ 77*77 = 85*85 = 7225
+ 80*80 = 89*89 = 7921
+ 72*72 = 97*97 = 9409
+ 99*99 = 101*101 = 10201
5.5. PROJECTS
5.5
111
Projects
1. Something loopy to do
Write a C++ program that converts any unsigned integer to any base between 2 and
9.
Heres an example of how it should work for an input of 126:
unix-prompt> a.out
Input the base to convert to between 2 <= b <= 9: 7
Input any positive unsigned int: 126
Decimal 126 converted to base 7 is 240
unix-prompt>
112
CHAPTER 5. LOOPS
iii. Test to see if xi and yi are identical to x0 and y0 . If they are not you will
continue with step (b-iv.) Otherwise you will want to transfer control to the
the rst statement following the input/stepping loop, step (c).
iv. Increment the step counter N.
v.
vi.
vii.
viii.
5.5. PROJECTS
113
114
CHAPTER 5. LOOPS
mathematically, or you can run your program for dierent values of N until you
detect that something is wrong. How do you know that something has gone
wrong? Turn in a description of how you found the answer.
(c) Calculating the exponential of a number
The exponential function, called ex is one of the most common functions in all of
mathematics. One way of calculating it is to use the following:
1
x x2 x3 x4 x5
xn
e = + +
+
+
+
+
0! 1! 2!
3!
4!
5!
n!
x
an innite series, one that never stops. Mathematically, the above expression for
ex is exact for any x from minus innity to plus innity. However, to get an
accurate calculation from a computer requires some work. Here is what you have
to do:
i. Write a C++ program to compute ex . Your program should try to compute
it by summing the nite series
ex =
1
x
x2 x3 x4 x5
xN
+ +
+
+
+
+
0! 1! 2!
3!
4!
5!
N!
where N is some integer that you, the programmer, will set. Be careful
that you do not set N too high, otherwise, as indicated in the previous two
problems, your answer may not make sense. N should also be great enough
so that your answer is as accurate as it can be. Turn in your code.
ii. Discuss over what range of x you expect your program to provide a reasonably
accurate answer. Turn in your discussion in such a way that pleases your Lab
Instructor.
You can check your results with a calculator. Else, if you read ahead, you can
check your program using the C++ math function exp(x).
5.5. PROJECTS
115
116
CHAPTER 5. LOOPS
Input must be > 4 or < 1000000
Keep trying!
Input the first integer: 1000000
Input the second integer: 1
Input must be > 4 or < 1000000
Keep trying!
Input the second integer: 4
Looking for all the prime numbers between 4 and 1000000 inclusive
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime
53 is prime
59 is prime
61 is prime
67 is prime
71 is prime
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime
.
.
.
999953 is prime
999959 is prime
999961 is prime
999979 is prime
999983 is prime
There were 78496 prime numbers between 4 and 1000000 inclusive
5.5. PROJECTS
117
5. Wheres Waldo?
It is a little known fact that Waldo Schtinklebaum, the character of the infamous
Wheres Waldo? game was a student here at the University Michigan. He started
o his career in Civil Engineering. He was notorious for 1) being a lousy dresser, 2)
having no sense of direction (why he was always getting lost), 3) and being indecisive.
In fact, after partying all night at the Frats, Waldo would often lose his way back
to his dorm. Hed leave the party, forget which way his dorm was, take a step in a
random direction, change his mind and his direction and take another step. This is not
a bad approach to getting where you want to go, except that it can take a very long
time to reach your destination. Waldo sometimes ended up walking around randomly
until the morning when someone would take pity on him and lead him back home. In
fact, Waldos meanderings led to his second career. Shortly after graduation, Waldo
participated in the infamous Spring running event that takes place in the late evening
on the last day of Winter term. On this day, Waldo changed his manner of dress
permanently. Despite his motivation to run in the correct direction, Waldo ended up
in the Kresge Eye Center were his vision was corrected and he donned the hospital
greens of a medical doctor. Waldo is now an optometrist working in Livonia under an
assumed name. His specialty is treating children who have gone cross-eyed staring at
the puzzles that bears his former name.
Your project is to write a program that imitates Waldos after-party mission to get
home. A pseudocode description of the solution is given below.
Pseudocode for Waldos mission
Waldo starts his journey at location (x, y) = (0, 0), the front door of the Frat
house, the center of the universe that Waldo is in. Waldos universe is a 2dimensional plane that measures 2020, that is 10 x 10 and 10 y 10.
Waldos home is a 2 2 square in the upper right hand corner, 8 x 10 and
8 y 10.
Declare a variable called stillWalking and give it an initial value of 1 (true),
which means that Waldo is still trying to nd his way home on foot.
Declare another variable called atHome and give it an initial value of 0 (false)
which means that Waldo has not yet found his way home.
Declare another variable called stepsToTry and give it an initial xed value of
1000. Waldo hopes to get home before 1000 steps. If he doesnt, you will either
tell him to keep going and try another 1000 steps, or to give up and sleep on the
nearest park bench.
WHILE (stillWalking)
FOR-LOOP until 1000 steps are taken and while Waldo has not yet reached
home.
DO (Loop for choosing the direction of the step)
118
CHAPTER 5. LOOPS
Take a proposed step of unit length in a random direction. (See note
on the next page.)
WHILE (endpoint of the step is outside of Waldos universe)
Take the step.
If Waldos new location is within the square dened as his home, set
atHome to true.
END FOR-LOOP
IF (atHome), print out the total number of steps that Waldo has taken and
stop the program.
ELSE, read in a new value for stillWalking. If the user inputs a non-zero
value for stillWalking, Waldo will try to take another 1000 steps, otherwise,
if the user inputs a zero value for stillWalking the logical condition of the
outer WHILE loop will be false.
END WHILE
End the program.
Note 1: Taking a step in a random direction
To use random numbers, you must
#include <cstdlib>
in the preprocessor area for the code. Then, an expression of the form:
rand()
will produce a random int between 0 and RAND MAX inclusive, where RAND MAX is a big
positive number dened in cstdlib. This random int must be converted to a random
double that lies between 0 and 2. This can be done via the following statement:
double angle = 2*PI*rand()/RAND_MAX;
where PI can be declared and initialized (earlier in the program) by
const double PI = 4*atan(1.0);
Using the above atan() function requires the use of
#include <cmath>
in the preprocessor area. Finally, x and y displacements can be generated by the
statements:
5.5. PROJECTS
119
dx = cos(angle);
dy = sin(angle);
where dx and dy are doubles. This is one of Waldos steps. You should use exactly
this order of displacement statements in your solution.
Example use of the program
red% a.out
Will Waldo make it home? Press <RETURN> to continue.
Waldo is still lost after taking 1000 steps
Continue playing? (Input "0" to stop): 1
Waldo is still lost after taking 2000 steps
Continue playing? (Input "0" to stop): 1
Waldo made it home after taking 2552 steps!
Note 2: Making it really sort of random (optional topic)
If you have followed the above instructions carefully, you will notice that every execution of the program is exactly the same. Moreover, the solution of your colleagues,
at least those who followed the instructions carefully, will also get Waldo home in the
same number of steps (assuming you all are using the same type of computer). In this
case, it is a desirable thing because, it allows your GSIs to grade your assignment
quickly. This makes your GSIs happy because most GSIs would volunteer to undergo
a frontal lobotomy rather than grade. (I used to be a GSI and I know that I would.)
Happy GSIs give out better grades, its a fact of life. Im digressing again...
If you want to make each play of the game dierent, do the following. In the preprocessor area of your code,
#include <ctime>
Then, in your code before your rst use of rand(), put in the following expression:
srand(time(NULL));
Thats how I generated the dierent solutions that are shown in graphical form on the
next page. The expression time(NULL) gives the number of seconds since the start of
the epoch, January 1, 1970, 12:00am GMT. This is considered to be the start of the
modern computer age.
Note that you can also seed the random number generator rand() using the following
statement:
120
CHAPTER 5. LOOPS
srand(someInt);
where someInt is an int that you can choose. If you choose the same someInt every
time, the game will be the same. Dierent someInts result in dierent games. Try it!
Some things to think about (optional)
These are some things to think about. Dont hand answers to these to your GSIs.
However, feel free to speak to them or me (the Prof) about it.
Why did I conne Waldo to a 20 20 universe?
Is Waldo always guaranteed to make it home if he tried long enough?
If I took away the walls of the universe, on average how far away would Waldo be
from his starting point after a certain number of steps.
If you took away the walls, would Waldo always guaranteed to make it home if
he tried long enough?
Graphical output of Waldos meanderings on next page
Waldo is there. Can you see him?
5.5. PROJECTS
121
Wandering Waldo
First example
Waldo
gets
inspired!
Home
Wandering Waldo
Second example
122
CHAPTER 5. LOOPS
Chapter 6
Early AbstractionFunctions
6.1
Let us consider an implementation of the al-Kashi algorithm. This algorithm computes the
X N where N is any integer, positive, negative or non-zero. Here is what the C++-code
looks like (This code is called alKashi.cpp on the lecture distribution area on the course
website):
//File: alKashi.cpp
#include <iostream>
using namespace std;
int main(void)
{ cout << "A calculation of X (float) to the power of N (int) \n";
float X; // The float to be raised to a power
int
N; // Power to be raised to
cout << "Input X (float) and N (int): ";
cin >> X >> N;
float result; // The result of the calculation
{
124
if (0 > N)
{ //This "trick" allows us to calculate for negative powers!
n = -N;
x = 1/X;
}
result = 1; // Initial value
while(1 <= n)
{ if (0 == n % 2)
{ n = n/2;
x = x*x;
}
else
{ n = n - 1;
result = result*x;
}
}
} // End of the scope block
cout << X << " to the power " << N << " = " << result << "\n";
return(0);
}
The above example introduces a new concept in C++-programming, that of a block, or
code block. A block is any set of statements enclosed by a set of curly brackets {...}s.
In the above example,
{ //Open a new "scope" or "code" block
.
.
.
} // End of the scope block
delimit a code blockthis one associated with the Al-Kashi algorithm. Variables can be
dened within a code block. Those that are dened within them (in this example, float x
and int n) are not known (or dened) outside of the the block. If you tried to do something
with x or n outside of their block, you would get a compilation error, complaining that these
variables were not dened. At least, that will be our understanding of code blocks until we
get to the section called scope rules a little later in the course. We have actually seen
code blocks before. The main routine has one, as well as the if/else if/else construct,
the while and do/while constructs as well as the for loop.
125
Now, suppose that we did not know about the al-Kashi algorithm and coded the algorithm in
a more straightforward way (This code is called dumbPower.cpp on the lecture distribution
area on the course website.):
//File: dumbPower.cpp
#include <iostream>
using namespace std;
int main(void)
{ cout << "A calculation of X (float) to the power of N (int) \n";
float X; // The float to be raised to a power
int
N; // Power to be raised to
cout << "Input X (float) and N (int): ";
cin >> X >> N;
float result; // The result of the calculation
{
126
Indeed, as far as the main routine is concerned, it does not really care about the contents of
the code block! All it really wants is the answer. It can think of the algorithm to compute
the power in a very abstract way. All main really needs to do is to give the scope block the
variables X and N.
What we really, REALLY want is a routine that is independent of the specic calculational
technique that is used to obtain X N . In fact there is. There is a function in the C++
standard math library that does this. It is called pow. If we use this information we can
write a much more compact code (This code is called power0.cpp on the lecture distribution
area on the course website.):
//File: power0.cpp
#include <iostream>
#include <cmath>
using namespace std;
int main(void)
{ cout << "A calculation of X (float) to the power of N (int) \n";
float X; // The float to be raised to a power
int
N; // Power to be raised to
cout << "Input X (float) and N (int): ";
cin >> X >> N;
float result; // The result of the calculation
result = pow(X,N);
cout << X << " to the power " << N << " = " << result << "\n";
return(0);
}
Note the use of
#include <cmath>
that helps with the interpretation of the statement:
result = pow(X,N);
127
This is a much more abstract and powerful implementation of the previous two examples.
It allows the main routine to be concerned with only the input and output of the various
parameters, X, N, and the answer. The main routine in this case is much more general.
Let us pretend that we are now in the infancy of the C++-language, and that the pow function
does not exist. However, we require this functionality repeatedly in our applications. But,
we do know about al-Kashis algorithm. Wanting to be ecient, we would code the al-Kashi
algorithm into a C++-function and employ it as follows (This code is called power1.cpp on
the classcodes distribution area):
//File: power1.cpp
#include <iostream>
using namespace std;
float pow(float x, int n)
{ float result; // The result of the calculation
//An implementation of the al-Kashi algorithm
if (0 > n)
{ n = -n;
x = 1/x;
}
result = 1;
while(1 <= n)
{ if (0 == n % 2)
{ n = n/2;
x = x*x;
}
else
{ n = n - 1;
result = result*x;
}
}
return result;
}
int main(void)
{ cout << "A calculation of X (float) to the power of N (int) \n";
128
Now we note a few important things. There are a lot of things to remember about functions
and we are only going to scratch the surface.
In our use of functions, the function denitions and the main routine go in one le.
(They can be put into dierent les but it becomes more complicated.)
The function denitions go at the top of the le, after the pre-processor directives but
before the denition of the main routine. (They can be put after the main routine but
it becomes more complicated.)
The functions denitions should go before they are used in any other function, including
main. (Again, we can use another ordering, but it becomes more complicated.)
Functions, the way we have used them so far, can return only one thing via the statement
return expression.
The expression in the return line must evaluate to a data type that is specied in
the denition of the function, in this example, float pow()...
The parameters in the function denition, in this example, (float x, int n), must
be declared.
The variables in the function call, in this example, X,N from mains function call
result = pow(X,N);
are not changed by the function. (There is another way to call functions where the
parameters can change. This will be taught later.)
129
Once the function returns to its calling routine, main in this case, the variables in
the functions parameter list and any other variables that it declares, are lost. The
only thing that main has is the return value. (To be absolutely truthful, there are
ways that the calling routine can look at the memory where the function stored things
temporarily, but...its complicated! Moreover, it is almost never done.)
Functions can call other functions.
main is just another function.
If a function does not return anything, its type is void. Example,
void returnNothingFunction(void){}
If a function has no parameters, put void where the parameter list goes, as in the
above example.
Finally, functions are really, really, REALLY important. So it is important to understand them and use them well. We will spend a lot of eort in this course with
functions.
6.2
User-dened functions
130
The function call: The call to the function can be inside of main or another function.
In fact, a function can even call itself. This is called recursion and is discussed in a
later chapter.
Understanding the syntax of these three things is crucial to the successful use of functions.
The general use of a user-dened function is as follows:
/* Opening comments */
.
.
.
// Start of pre-processor directives
.
.
.
// function prototype (if required)
(type) myFunction(variable type list separated by ,s);
.
.
.
// end of pre-processor directives
.
.
.
/* function definition */
(type) myFunction(variable type list and variables separated by ,s)
{
.
.
.
/* Function body with declarations and
executable statements
*/
.
.
.
}
.
.
.
int main (void)
{ // Start of main routine
131
.
.
.
// function usage
...myFunction(list of values separated by ,s)...;
.
.
.
} // End of main routine
132
Forgetting to return a value when (type) indicates that one should be returned results
in unpredictable behavior.
Returning a value when (type) is void causes a syntax error.
Note that
int main (void)
{
.
.
.
}
is a function denition! Its (type) is int. We could have said
main ()
{ .
.
.
}
because functions are assumed to be (type) int unless we state otherwise. main is a
special function in C++ that the operating system knows is the place where to start
processing. Only main has this special status. I always (type) every function that I
dene and you should do the same.
The rules for naming a function, e.g. myFunction, are the same rules as for variables,
i.e. the normal identier naming rules ( 31 alphanumeric characters and the underscore character and NOT starting with a number.)
The argument list in the function prototype is a comma separated list of variable types,
e.g.
void myFunction(float, int, float);
which indicates myFunction will be called and dened with a float, an int, and a
float in that order. Heres another example:
void realQuadraticRoots(float, float, float);
A variable type is required for any non-int. Therefore, declaring a variable position as
an int is optional. However, it is recommended that you declare the variable type for
all members in the parameter list.
133
134
Functions can be created independently by dierent programmers. The only information that has to be agreed upon is the return type, the function names and the
parameter lists. Otherwise, each programmer can do his or her job however he or she
pleases. In a team setting, prototypes are usually decided upon at the design stage.
An example follows.
6.3
(Completed version posted on the ENG101 web site in the lectures area called quadraticRoots.cpp)
A team of 4 people, Prof (the boss) and his graduate 3 students, Bill, Jane and Eugene (the
math expert) are writing a program together.
Prof to Team: Team: We will write a code to solve the quadratic equation! Well patent
it and Ill get rich!
Team to Prof: Yeah, right!
Prof to Bill: Bill, I want you to write a bool function called realQuadraticRoots that
will return an integer, and accept the three oats a, b and c in that order. If there are
no real roots your function has to return the value false. If there are, it has to return
the value true.
Bill to Prof: Um, Prof, whats a bool??
Prof to Bill: Its a variable type that can only have two values, true or false. It is
declared and assigned value as follows:
bool truthOrDare = false;
Bill to Prof: Gotcha, Im on it. By the way, whats my cut?
Prof to Jane: Jane, I want you to write a function called numberQuadraticRoots that
will return an integer, and accept the three oats a, b and c in that order. I will only
call your routine if Bills routine tells me that there are real roots. The integer you
return should contain the number of real roots, either 1 or 2.
135
136
}
Here is what the team produced.
Heres Bills code. Note that the Prof did not fully specify his task and so he let him have
it. He had to nd a way to terminate the program from a subroutine and so he had to go to
the library and do some research. (The Prof never answers e-mail from graduate students!)
Bill learned how to do this with the exit function and other denitions given in cstdlib.
bool realQuadraticRoots(float a, float b, float c)
/*********************************************************************
Purpose:
See if there are real roots
Receives:
Quadratic constants a,b,c in a*x*x + b*x + c = 0
Returns:
true if real roots, false if none
Programmer:
Bill Boole (with attitude)
Start Date:
09/17/00
Remark1:
Needs <iostream>, <cstdlib>
Remark2:
Prof needs to rethink this thing
*********************************************************************/
{ if (0 > (b*b - 4*a*c)) return false;
else if (0 == a && 0 == b)
{ cout << "Prof, you numbskull!\n"
<< "You didnt tell me what to do if a and b are both 0!\n"
<< "Go back and redesign the code!\n";
exit(EXIT_FAILURE);
}
else return true;
}
Heres Janes code. Her job was made easier by Bills code letting her know that there is at
least one solution.
int numberQuadraticRoots(float a,float b,float c)
/*********************************************************************
Purpose:
See if there are real roots
137
Remarks:
Enters this routine knowing that there are roots
*********************************************************************/
{ if (0 == a || (0 == (b*b - 4*a*c))) return 1;
else return 2;
}
Eugene, who thinks hes a genius and a super-geek, likes to do things his own way. He
likes to store all the values his function receives in uppercase variables. Eugene has his own
coding style. Eugene also thinks he is smarter than the compiler and so he played with the
quadratic equation to put it into a form that he thinks will execute faster. (You can verify
for yourselves that what Eugene did was correct mathematically.)
138
6.4
In our present usage of function calls, the parameter lists have contained only values that
are transmitted to the function and stored in internal variables known only to that function.
This is given the name call by value. A function that is called by value operates on the
data it is given (plus whatever else can be transmitted to it by virtue of the rules scope) and
can return to its calling routine at most one value, the return value, in a return statement
of the form:
return returnValue;
This is unsatisfactory and restrictive if we need to return more than one value. An alternate
way of calling functions, a way that can return more than one thing is called call by reference.
This discussion must start, however, with a discussion of the addresses of variables, that is,
where they are stored in a computers (virtual) memory.
6.4.1
We introduce the unary operator called the address operator, &. To see its usage, consider
the following program :
//File: addressLocal.cpp
#include <iostream>
using namespace std;
int main(void)
{ float x = 1.0f;
double y = 3.0;
int
z = 2;
cout <<
"xs
value:
"ys
value:
"zs
value:
return 0;
}
New stu:
The address operator & applied to a variable, for example, &y should be read as the
address of the double y.
139
value: 1
value: 3
value: 2
xs address: 0xbffff734
ys address: 0xbffff72c
zs address: 0xbffff728
When cout prints an address, it prints it out as 0x... which is the hexadecimal (hex)
representation. The leading 0x is there just to tell you that what follows is in hex.
Note the the address stack grows from a large address towards smaller addresses.
Note the the operating system (a Linux installation in this case) puts the rst variable it
encounters (in this case a 32-bit float) at address 0xbffff734. (This address, once converted to an integer number, is something in excess of 3 billion.) This is the address in bytes,
one byte being 8 bits. A 32-bit machine has a virtual address space of 232 , or 4,294,967,296
bytes, often abbreviated as 4GB. Above this address, starting at 0xbffff738 in this case
(This boundary is machine and O/S dependent) is where the program environment resides (well discuss that later) and above that still is where the operating system resides (the
kernel) occupying the upper reaches of address space up to the 4GB limit.
The next variable, a double is 64-bits or 8 bytes in length. Note that its address is smaller
(by 8 bytes). The address space that is provided for local variables is called the stack frame
and it grows downwards. Note where the next variable is located.
Each function creates its own stack frame for putting its local variables into memory, releasing
it when the function terminates. This is what is meant by the stack getting destroyed when
a function terminates. The next function call will use this space for its own stack frame.
The executable program, the load module is at the bottom of the address space, starting at
byte 0. This area is called the text segment. Above the text segment are stored initialized
and uninitialized global variables. Above this is the heap space, the address space where
dynamic memory (memory allocated by the program) is located. It grows upwards. If your
programs and data are so big that your stack frames and heap run into each other, you
either have to redesign your program to use less space or purchase a more expensive 64-bit
computer, one with 264 bytes of array space. (In a few years, most computers will be 64-bit
computers.)
Here another example program that demonstrates that global variables are located at a
dierent place in memory:
//File: addressGlobal.cpp
#include <iostream>
using namespace std;
140
value: 1
value: 3
value: 2
xs address: 0xbffff734
ys address: 0x8049a70
zs address: 0x8049a78
Note how the global variables, y and z in this case, are located starting at a lower address
0x8049a70 (something like 1 billion). Note how the global stack grows up. Note also how
the double, y, occupies 8 bytes.
6.4.2
Imagine for a moment that the pow() does not exist and we wish to write a program that
computes the square and cube of an integer. Moreover, we wish to write a single function
that returns both the square and cube. Using what we have learned so far, we are frustrated
to discover that we can not do it! Instead we have to separate the task into two functions.
Our code would look something like:
//File: returnTwice.cpp
#include <iostream>
using namespace std;
int square(int j)
{ cout << "In function square(), j is located at " << &j << "\n";
return j * j;
}
141
int main(void)
{ int i = 3, iSquared, iCubed;
cout
<< "\n\nIn main():\n"
<< "
i is located at " << &i
<< "\n"
<< "iSquared is located at " << &iSquared << "\n"
<< " iCubed is located at " << &iCubed
<< "\n\n"
<< "Before the call to square and cube:\n"
<< "
i = " << i << "\n"
<< "iSquared = " << iSquared << "\n"
<< " iCubed = " << iCubed << "\n\n";
iSquared = square(i);
iCubed
= cube(i);
cout
<< "\n After
<< "
i
<< "iSquared
<< " iCubed
return 0;
the
= "
= "
= "
}
where I have put in a lot of cout statements to let me know where the variables are stored.
Compiling and running it results in the following output:
In main():
i is located at 0xbffff734
iSquared is located at 0xbffff730
iCubed is located at 0xbffff72c
Before the
i =
iSquared =
iCubed =
142
In function
After the
i =
iSquared =
iCubed =
Note that main()s local variables i, iSquared, iCubed reside in main()s stack frame.
Also note that iSquared and iCubed are not initialized by main() and so the memory
locations of these variables contain nonsense bits, junk left over from the previous use of
those memory locations, whatever process that happened to be. The rst function called
is square(). It has one local variable called j which it locates in its own stack frame,
starting at address 0xbffff728. square() does its work happily and returns the result of
its computation to main() which then called the function cube(). cube() has one local
variable called k which it locates in its own stack frame, starting at address 0xbffff728,
the same address used by square()! Once square() returned to main(), its stack frame
was destroyed and cube() did the most ecient thing, locating its stack frame at the next
available location, the location just vacated by square().
We now introduce the method of call-by-reference. This is best done by example, so, here
is the above program converted to a single function call that has both the usual value
parameters and also something newreference parameters in the functions parameter list.
//File: returnTwoThings.cpp
#include <iostream>
using namespace std;
void squareCube(int j, int& j2, int& j3)
{ cout << "In function squareCube():\n"
<< "j is located at " << &j << "\n"
<< "j2 is located at " << &j2 << "\n"
<< "j3 is located at " << &j3 << "\n";
j2 = j * j;
j3 = j2 * j;
return;
}
int main(void)
{ int i = 3, iSquared, iCubed;
cout
<< "\n\nIn main():\n"
<< "
i is located at " << &i
<< "\n"
143
call to squareCube:
3
134519980
134514715
144
In
j
j2
j3
function squareCube():
is located at 0xbffff720
is located at 0xbffff730
is located at 0xbffff72c
Note the memory locations of the variables local to main() and the fact that squareCube()
thinks that j2 and j3 live in the same place. Note also that in squareCube(), the local
variable j is located at 0xbffff720, 12 bytes below the end of main()s stack frame. Yet,
j, an integer is only 4 bytes long. Can you guess what use squareCube() is making of those
8 bytes of memory?
Finally, note that value parameters and reference parameters can be mixed in any order in the
parameter list. Just make sure, in the function denition, that all the reference parameters
names are preceded by the ampersand, & symbol.
About the only real-life example that I can come up with that relates to this is my relationship
with my stockbroker. I am the main() routine and he, the incompetent bum, is a function
called stockBroker(). Here is his function denition. Ill let you gure out how Im doing
on the stock market.
//File: stockBrokerFunction.cpp
void stockBroker(double myFee, double& alexMoney)
{ double transactionCost = 200.;
while (0 < alexMoney && 0 < myFee)
{ myFee = myFee - transactionCost; //Deduct usual transaction charge
alexMoney = alexMoney * 0.95; //Make a stupid investment
}
return;
}
However, I do want you to notice that I provide him with a fee, myFee which is his to keep.
However, he is playing with my money, alexMoney, a reference parameter, the value of which,
I am unhappy to report, is diminishing rapidly. It is still MY money, but I have given the
stockbroker the ability to change it.
6.5
145
One of the most powerful features of C++ is its implementation of the rules of scope. The
philosophy is that information (data) should be hidden from operational code unless it really
needs to know about the data. This avoids the danger of a program unit changing data that
it is not supposed toeven if it calls the variables by the same name! This is how dierent
people can develop dierent parts of a program and as long as each programmer stays within
his or her assigned duties, data does not get corrupted. C++ has also introduced the concept
of namespace to keep things separate. For this course we will always use: using namespace
std; although it is possible to use a dierent namespace. We will only use the standard
namespace in this course.
There are several hierarchies of scope:
le scope An identier declared outside of any function denition has le scope. That
is, global variables, function denitions and function prototypes (if you use them!)
placed outside of any function apply for the entire le. It is perfectly ne to dene
an int, say, outside of any function or main. This variable can then be used by all
functions and main. If separate les are linked together to form a program, the other
les will not know about le scope identiers outside of their own les.
function scope The only identier that is dened for the entire function is a label (an
identier followed by a colon :), e.g.
ThisIsALabel:
A transfer to a label can be done with the dreaded goto or within the switch statement,
neither of which will be taught in this course.
Labels are dened for the whole function and undened outside of it.
block scope A block is anything within braces, {...}. For example:
{
}
// This is a block
{
}
}
Note the use of optional spacing to delineate the separate blocks in the above.
146
to main
<< ", y = " << y << "\n";
myFn
<< ", y = " << y << "\n";
147
x
x
x
x
=
=
=
=
1,
1,
2,
1,
y
y
y
y
=
=
=
=
2
2
1
2
main declares two oats, x and y and gives myFn their values. myFn happens to call these
variables by the same name (they could have been dierent). myFns job is to switch the
values of these two variables. Within its own scope this has been accomplished but the
switch has not been eected in main. This is because the x and y in main and the x and y
in myFn are dierent.
Consider the following code called scope1.cpp:
//File: scope1.cpp
#include <iostream>
using namespace std;
float x = 1.0, y = 2.0; // Global variables
void myFn(void) // No declarations
{ float z; // Internal to myFn
cout << "myFn:
pre-op x = " << x << ",
z = x; x = y; y = z; // Variable switch
cout << "myFn:
post-op x = " << x << ",
}
int main(void)
{ cout << "main: pre-call x = " << x << ",
myFn(); // Main just calls myFn
cout << "main: post-call x = " << x << ",
return 0;
}
x
x
x
x
=
=
=
=
1,
1,
2,
2,
y
y
y
y
=
=
=
=
2
2
1
1
148
In this example x and y are dened globally (outside of any function). Both main and myFn
can access them and change them. myFns job is to switch the values of these two variables.
Within its own scope this has been accomplished and the switch has been eected in main
as well. This is because the x and y in main and the x and y in myFn are identical.
Consider the following code called scope2.cpp:
//File: scope2.cpp
#include <iostream>
using namespace std;
float x = 1.0, y = 2.0; // Global variables
void myFn(float x, float y) // myFn declares x,y
{ float z; // Internal to myFn
cout << "myFn:
pre-op x = " << x << ", y = " << y << "\n";
z = x; x = y; y = z; // Variable switch
cout << "myFn:
post-op x = " << x << ", y = " << y << "\n";
}
int main(void)
{ cout << "main: pre-call x = " << x << ", y = " << y << "\n";
myFn(x,y); // Main transfers x and y values
cout << "main: post-call x = " << x << ", y = " << y << "\n";
return 0;
}
Compiling and running scope2.cpp results in the following output:
main: pre-call
myFn:
pre-op
myFn:
post-op
main: post-call
x
x
x
x
=
=
=
=
1,
1,
2,
1,
y
y
y
y
=
=
=
=
2
2
1
2
In this example x and y are dened globally (outside of any function). main can access them
and change them. However, myFn denes its own x and y and hence the global ones are
hidden and myFn cannot access them and change them.
Consider the following code called scope3.cpp:
//File: scope3.cpp
#include <iostream>
149
y,
y,
y,
y,
z
z
z
z
=
=
=
=
1,
1,
2,
2,
2,
2,
1,
1,
0
42
1
0
In this example x, y, and z are dened local to main. Within main there is a nested block
that denes its own scope. Since this block does not dene x and y, these variables pass
into the block. However, z is dened within the nested block and the external one is hidden.
However, the nested block has changed the values of x and y when control is passed back to
main.
Consider the following code called scope4.cpp:
//File: scope4.cpp
#include <iostream>
using namespace std;
void myFn(void)
{ float z = 0; // Internal to myFn
cout << "myFn:
pre-op z = " << z << "\n";
150
}
int main(void)
{ cout << "First
myFn(); // Main
cout << "Second
myFn(); // Main
return 0;
}
call to myFn\n";
calls myFn
call to myFn\n";
calls myFn again
0
1
0
1
In this example z is dened locally local to myFn which also initialized it to zero. Every time
myFn is called, z is reset to zero and the executable statements are processed.
Consider the following code called scope5.cpp:
//File: scope5.cpp
#include <iostream>
using namespace std;
void myFn(void)
{ static float z = 0; // Internal to myFn
cout << "myFn:
pre-op z = " << z << "\n";
z = z + 1; // Add to z
cout << "myFn:
post-op z = " << z << "\n";
}
int main(void)
{ cout << "First
myFn(); // Main
cout << "Second
myFn(); // Main
call to myFn\n";
calls myFn
call to myFn\n";
calls myFn again
151
return 0;
}
Compiling and running scope5.cpp results in the following output:
First call to myFn
myFn:
pre-op z =
myFn:
post-op z =
Second call to myFn
myFn:
pre-op z =
myFn:
post-op z =
0
1
1
2
In this example z is dened locally local to myFn which also initializes it to zero but holds it
static. The specier static indicates that this variable is to retain its value when it leaves
a routine, preserving its value for the next entry into the routine. The initialization to zero
is only eective the rst time the routine is entered.
static is called a storage class and is a qualier on the variable type that means that its
value is to be saved, not destroyed when the function ends execution.
Consider the following code called scope6.cpp
//File: scope6.cpp
#include <iostream>
using namespace std;
float max(float u, float v) // function max declares u,v
{ float temp = u;
u = v;
v = temp;
cout << "max: u = " << u << " v = " << v << "\n";
if (u > v)
{ return u;
}
else
{ return v;
}
}
int main(void){
float x = 1.0, y = 2.0, maxxy; // Internal to main
cout << "main: x = " << x << " y = " << y << "\n";
maxxy = max(x, y);
152
}
Compiling and running scope6.cpp results in the following output:
main: x = 1 y = 2
max: u = 2 v = 1
main: max of x and y = 2
main declares two oats, x and y and gives myFn their values. myFn happens to call these
variables by dierent names (they could have been the same as in some of the previous
examples). myFns job is to switch the values of these two variables and determine which
is greater. Within its own scope this has been accomplished but the switch has not been
eected in main. This is because the x and y in main and the u and v in myFn are dierent.
6.6. PROBLEMS
6.6
153
Problems
154
6.6. PROBLEMS
155
return 0;
}
4. Predict the output
What does this code print?
#include <iostream>
using namespace std;
void cyclic(int i, int& j, int k, int& l)
{ int m;
m = i;
i = j;
j = k;
k = l;
l = m;
}
int main(void)
{ int i = 1, j = 2, k = 3, l = 4;
cyclic(i, j, k, l);
cout << "i,j,k,l : " << i << j << k << l << "\n";
return 0;
}
5. Fix the design error(s)
(a) This code attempts to dene a function that returns the maximum of two oats
and orders the two oats in descending order (bigger rst, smaller second). This
code only works some of the time. There is one design mistake that occasionally
leads to incorrect results. Assume that the scanf statement is always executed
correctly. You may not x this using a library function that determines maximum.
#include <iostream>
using namespace std;
float fMax(float f1, float f2)
{ if (f2 > f1)
{ float temp = f2; // f2 is maximum
f2 = f1; f1 = temp; // switch them
return f1;
156
j, int k)
i = j; j = t;}
j = k; k = t;}
i = j; j = t;}
int main(void)
{ int i = 5, j = 3, k = 1;
sort3(i,j,k);
cout << "In ascending order (smallest->largest) "
<< "the three ints are "
<< i << ", " << j << ", " << k << "\n";
return 0;
}
(c) The following code compiles error free. Why wont it work as intended?
#include <iostream>
using namespace std;
float squareCube(float x, float xx)
{ xx = x*x;
return xx*x;
6.6. PROBLEMS
157
}
int main(void)
{ float x = 2.0, xx, xxx;
xxx = squareCube(x,xx);
cout << "Square of x: " << xx << ", Cube of x is " << xxx << "\n";
return 0;
}
6. Roots of the quadratic equation
Write a function that is compatible with the following function call:
bool twoRealRoots = twoRoots(a,b,c,root1,root2);
The function returns true if b2 4ac > 0 and a = 0. Otherwise, it returns false. If
the function returns true, then root1 and root2 contain the roots of the quadratic
equation ax2 + bx + c = 0, which are
b b2 4ac
x1,2 =
2a
function
a:
158
float x, y, r, t;
cout << "x, y: ";
cin >> x >> y;
cout << "x = " << x << " y = " << y << " is in the " << polar(x,y,r,t)
<< ". " << "r = " << r << " t = " << t << " degrees\n";
return 0;
}
The function, polar(), called in the second cout statement above returns a string
that indicates
upper right quadrant if x 0 and y 0
upper left quadrant if x < 0 and y 0
lower left quadrant if x < 0 and y < 0
lower right quadrant otherwise
Afterthe function returns, the float called r contains the radius computed as
r = x2 + y 2. Hint. r = sqrt(x*x + y*y); After the function returns, the float
called t contains the angle in degrees computed as
= 180 tan1 (y/x)/. Hint. Use t = 45*atan2(y,x)/atan(1.0); to calculate this.
Here is an example of how it works:
red% a.out
x, y: 1 1 //User types in "1 1" in response to the "x, y: " prompt
x = 1 y = 1 is in the upper right quadrant. r = 1.41421 t = 45 degrees
9. How many bits to an unsigned int?
The following algorithm may be used to determine the number of bits that are used to
represent an unsigned int:
(a) Starting with an unsigned int initialized to 1, keep multiplying it by 2 until it
equals 0.
(b) The number of times you multiply it by 2 is related to the number of bits used to
represent the unsigned ints.
Write a function that determines the number of bits that are used to represent an
unsigned int on the computer that executes the program. Your function has to be
compatible with the following main routine.
6.6. PROBLEMS
#include <iostream>
using namespace std;
//Function definition goes here
int main(void)
{ cout << "The unsigned int size is " << intSize()
<< " bits on this computer\n";
return 0;
}
Here is how it works:
red% a.out
The unsigned int size is 32 bits on this computer
159
160
6.7
Projects
Math function
log(x), log e (x), ln(x)
exp(x), ex
log10 (x)
sin(x)
cos(x)
x
|x|
Purpose
natural logarithm (base e)
exponential
logarithm (base 10)
sine of x
cosine of x
square root of x
absolute value of x
Example
double x
double x
double x
double x
double x
double x
double x
usage
= 1.;
= 1.;
= 1.;
= 1.;
= 1.;
= 1.;
= 1.;
double
double
double
double
double
double
double
y
y
y
y
y
y
y
=
=
=
=
=
=
=
log(x);
exp(x);
log10(x);
sin(x);
cos(x);
sqrt(x);
fabs(x);
Note that the argument to the trigonometric functions above must be in terms of
radians.
360 (degrees) = 2 (radians).
Write a main program that generates the table on the following page similar to that
shown. In other words, you will have to have a for-loop that somehow generates
the doubles -1.0, -0.9, ..., 1.0, calculate and output x, log(x), exp(x), log10(x),
sin(PI*x), cos(PI*x), sqrt(x), and fabs(x).
Some notes:
Note the argument of the sin() and cos(). You were given the method to
generate a good value for in the Wheres Waldo? project in the previous
chapter.
You will have to use the setw() and setprecision() functions as described in
Chapter 5.
You need one other thing to allow the printing of the redundant trailing zeros.
Put in the statement
cout.setf(ios::fixed);
before your rst use of cout.
Note that the outputs -Infinity and NaN are provided automatically by cout
when the argument to the math library functions is out of range of its denition.
6.7. PROJECTS
x
----1.0
-0.9
-0.8
-0.7
-0.6
-0.5
-0.4
-0.3
-0.2
-0.1
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
log(x)
---------Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-2.302585
-1.609438
-1.203973
-0.916291
-0.693147
-0.510826
-0.356675
-0.223144
-0.105361
0.000000
161
exp(x)
-------0.367879
0.406570
0.449329
0.496585
0.548812
0.606531
0.670320
0.740818
0.818731
0.904837
1.000000
1.105171
1.221403
1.349859
1.491825
1.648721
1.822119
2.013753
2.225541
2.459603
2.718282
log10(x)
---------Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-Infinity
-1.000000
-0.698970
-0.522879
-0.397940
-0.301030
-0.221849
-0.154902
-0.096910
-0.045757
0.000000
sin(PI*x)
---------0.000000
-0.309017
-0.587785
-0.809017
-0.951057
-1.000000
-0.951057
-0.809017
-0.587785
-0.309017
0.000000
0.309017
0.587785
0.809017
0.951057
1.000000
0.951057
0.809017
0.587785
0.309017
0.000000
cos(PI*x)
---------1.000000
-0.951057
-0.809017
-0.587785
-0.309017
0.000000
0.309017
0.587785
0.809017
0.951057
1.000000
0.951057
0.809017
0.587785
0.309017
0.000000
-0.309017
-0.587785
-0.809017
-0.951057
-1.000000
sqrt(x) fabs(x)
-------- ------NaN
1.0
NaN
0.9
NaN
0.8
NaN
0.7
NaN
0.6
NaN
0.5
NaN
0.4
NaN
0.3
NaN
0.2
NaN
0.1
0.000000
0.0
0.316228
0.1
0.447214
0.2
0.547723
0.3
0.632456
0.4
0.707107
0.5
0.774597
0.6
0.836660
0.7
0.894427
0.8
0.948683
0.9
1.000000
1.0
162
6.7. PROJECTS
28 is a perfect number
28 = 1 + 2 + 4 + 7 + 14
.
.
.
163
164
3. Random integration
x sin(x)
1+x
x0 x x1
6.7. PROJECTS
165
x sin(x)
1+x
for 0 x , most of which was coded in the last problem. Use 100,000
samples to estimate the area.
HOW TO WORK ON THIS PROBLEM:
i. Try a few dierent examples for f (x) for which you know the answer (without
knowing calculus!). Good candidates would be:
A. f (x) = x, for 0 x 1.
B. f (x) = 1 x, for 0 x 1.
C. f (x) = x, for 0 x 1/2, f (x) = 1 x, for 1/2 x 1.
ii. Once you are condent that your algorithm works, then try the assigned
function:
x sin(x)
f (x) =
1+x
for 0 x
iii. Write out a pseudocode to help you design your program.
166
Chapter 7
More Variable Types, Data
Abstraction
7.1
We have seen that ints are represented by 32 bit words and that they can only represent
a nite range of integral numbers. A signed integer covers the range 231 i (231 1).
Floating numbers have their own restrictions. One bit is used for the sign of the number, 23
bits represent the mantissa1 (the precision or granularity of the number) and 8 bits are used
to dene the exponent. Consequently, floats have a range of about 1045 to about 10+38
and a resolution of about 1 part in 107 . (The particular oating-point representation can be
dierent on dierent operating systems.)
doubles are represented by 64 bits. 52 for the mantissa, one for the sign and 11 for the
exponent. The granularity is about 2 parts in 1016 and ranges from about 10324 to about
10+308 . (The particular oating-point representation can be dierent on dierent operating
systems.)
Some CPU manufacturers, for example Intel (which provides the CPUs for your laboratory
computers and, if you own them, your home computer or laptop), have adopted an IEEE
standard that represents oating point numbers with 80 bits, doing all the internal calculations at precisions higher than both floats and doubles. This variable type is called
the long double. 64 bits are used for the mantissa, one for the sign and 15 for the exponent. The granularity is about 1 part in 1019 and ranges from about 104965 to about
10+4932 . Other manufacturers have larger representations. For example, the Sun machines
maintained by CAEN have 128-bit long doubles.
1
Actually, it is assumed that the leading bit is always 1, so the representation uses 23 physical bits and
one hidden or virtual bit. All the oating-point numbers have a hidden bit.
167
168
FLOAT 32-BITS
EXPONENT
MATISSA 23 BITS
8 BITS
1 BIT
SIGN
DOUBLE 64-BITS
EXPONENT
11 BITS
MATISSA 52 BITS
1 BIT
SIGN
169
New stu:
1. The statement: float one = 1.0f contains the qualier "f". This means that 1.0 is
a float, typically a 32 bit constant. If the "f" were omitted, the constant would be a
double, typically a 64 bit constant.
Compiling and running precisionFloat.cpp results in the following output:
Converged after 24 iterations
Float resolution = 5.96046e-08
Consider the following code called precisionDouble.cpp:
//File: precisionDouble.cpp
#include <iostream>
using namespace std;
double precision(void)
{ double one = 1.0, e = 1.0, onePlus;
int counter = 0;
do
{ counter = counter + 1;
e = e/2.0;
onePlus = one + e;
}while(onePlus != one);
cout << "Converged after " << counter << " iterations\n";
return e;
}
int main(void)
{ cout << "Double resolution = " << precision() << "\n";
return 0;
}
New stu:
1. The statement
double one = 1.0, e = 1.0;
declares and initializes two doubles.
170
171
Note that what is called Float resolution, Double resolution, or Long double resolution
in the above example outputs from the programs is the number that can NOT be resolved
with respect to 1.
To test the range of a float consider the following code called rangeFloat.cpp:
//File: rangeFloat.cpp
#include <iostream>
#include <iomanip>
using namespace std;
int main(void)
{ float x = 1.0f, x0;
float y = 1.0f, y0;
int counter = 0;
do
{ counter = counter + 1;
x0 = x; x = x*2.0f; // Multiply by 2
y0 = y; y = y/2.0f; // Divide by 2
cout << setw(4) << counter << ": "
<< setw(12) << x << " :: "
<< setw(12) << y << "\n";
}while(x0 != x || y0 != y);
return 0;
}
Compiling and running rangeFloat.cpp results in the following output:
1:
2:
3:
4:
5:
2
4
8
16
32
::
::
::
::
::
0.5
0.25
0.125
0.0625
0.03125
.
.
.
125:
126:
127:
128:
129:
130:
4.25353e+37
8.50706e+37
1.70141e+38
Inf
Inf
Inf
::
::
::
::
::
::
2.35099e-38
1.17549e-38
5.87747e-39
2.93874e-39
1.46937e-39
7.34684e-40
172
.
.
.
147:
148:
149:
150:
Inf
Inf
Inf
Inf
::
::
::
::
5.60519e-45
2.8026e-45
1.4013e-45
0
New stu:
1. The output Inf is the IEEEs way of representing a number that is too large to be
represented. Inf has its own distinctive bit pattern.
2. Note that the floats appear to have more range for small numbers than large
numbers. IEEE allows for a gradual decrease to zero. These numbers below about
6e-39 are called sub-normal, with fewer bits of precision. The leading bits of the
mantissa are padded with zeros for sub-normal numbers.
To test the range of a double consider the following code called rangeDouble.cpp:
//File: rangeDouble.cpp
#include <iostream>
#include <iomanip>
using namespace std;
int main(void)
{ double x = 1.0, x0;
double y = 1.0, y0;
int counter = 0;
do
{ counter = counter + 1;
x0 = x; x = x*2.0; // Multiply by 2
y0 = y; y = y/2.0; // Divide by 2
cout << setw(4) << counter << ": "
<< setw(12) << x << " :: "
<< setw(12) << y << "\n";
}while(x0 != x || y0 != y);
return 0;
}
Compiling and running rangeDouble.cpp results in the following output:
2
4
8
16
32
::
::
::
::
::
173
0.5
0.25
0.125
0.0625
0.03125
.
.
.
1021: 2.24712e+307 :: 4.45015e-308
1022: 4.49423e+307 :: 2.22507e-308
1023: 8.98847e+307 :: 1.11254e-308
1024:
Inf :: 5.56268e-309
1025:
Inf :: 2.78134e-309
.
.
.
1073:
Inf :: 9.88131e-324
1074:
Inf :: 4.94066e-324
1075:
Inf ::
0
To test the range of a long double (at least an IEEE 80-bit one as implemented on my
machine) consider the following code called rangeLongDouble.cpp:
//File: rangeLongDouble.cpp
#include <iostream>
#include <iomanip>
using namespace std;
int main(void)
{ long double x = 1.0L, x0;
long double y = 1.0L, y0;
int counter = 0;
do
{ counter = counter + 1;
x0 = x; x = x*2.0L; // Multiply by 2
y0 = y; y = y/2.0L; // Divide by 2
cout << setw(4) << counter << ": "
<< setw(12) << x << " :: "
<< setw(12) << y << "\n";
}while(x0 != x || y0 != y);
return 0;
174
}
Compiling and running rangeLongDouble.cpp results in the following output:
1:
2:
3:
4:
5:
2
4
8
16
32
::
::
::
::
::
0.5
0.25
0.125
0.0625
0.03125
.
.
.
16382: 2.97433e+4931 :: 3.3621e-4932
16383: 5.94866e+4931 :: 1.68105e-4932
16384:
Inf :: 8.40526e-4933
16385:
Inf :: 4.20263e-4933
.
.
.
16443:
Inf :: 1.45808e-4950
16444:
Inf :: 7.2904e-4951
16445:
Inf :: 3.6452e-4951
16446:
Inf ::
0
Now thats a lot of numbers. Try these example codes on your own machine. If you get
output that is dierent, particularly for the long doubles, Id like to know about it!
7.1.1
1
N
175
7.2
176
The following line declares a character called ch and assigns it the character a
char ch = a;
The following statement contains an error. What is the error?
ch = "a";
Some special characters:
\n is a newline
\t is a horizontal tab
\0 is a null. It means nothing! We have to make a special character that
means nothing!
There are lots of others.
The inner secret of chars? They are really integers!
But, they are really integers but only one byte (8-bits) long.
Thus there can be at most 28 = 256 of them.
The following are all valid statements:
char c;
int i;
i = 65;
c = i;
c = 99;
Consider the program :
//File: chars.cpp
#include <iostream>
using namespace std;
int main(void)
{ for(int i = 0; i < 256 ; i = i + 1)
{ char c = i;
if (i <= 127)
177
cout << "Int " << i << "-->" << c << " in ASCII\n";
else
cout << "Int " << i << "-->" << c << " beyond ASCII\n";
}
return 0;
}
Try running this program and see what it gives you!
The characters corresponding to integers 0127 are the ASCII standard character
set. (ASCII = American Standard Code for Information Interchange) which is universally adopted in English-speaking nations. The printing characters are represented by
ASCII codes 32126. Some of the ASCII codes do special things or represent special
characters. For example, 7 is the alert or bell, 8 is the backspace, 9 is the horizontal tab, 10 is a new line, 11 is a vertical tab, 13 is a carriage return, 127 is
the delete. Note the eect of some of these when running chars.cpp.
The extended ASCII character set corresponding to integers 0255 is internationally adopted and permits many of the characters from some foreign languages to be
represented.
Movement is afoot to accept the UNICODE standard which codes characters in 2
bytes (16 bits) with 216 = 65536 possibilities. This is enough to code not only every
language that exists, but even every language that has ever existed. Even Egyptian
hieroglyphics has a UNICODE representation. There is probably no need to extend
beyond 16-bit representation until we start making contact with extra-terrestrial life
forms, well, at least ones that want to communicate with us for whatever reason.
7.2.1
178
Strings can be read in with cin and printed with cout. The cin operation continues
on the string until it sees a space or a new-line character (hitting the Return key).
Here is an example that will be discussed in class:
//File: string1.cpp
#include <iostream>
#include <string>
using namespace std;
int main(void)
{ string response;
do
{ cin >> response;
cout << response + "\n";
}while (. != response[0]); //Note vector notation
return 0;
}
It is important to understand that the space character is considered by the cin function
to signal the end of a string.
The fact that a space character is considered by the cin operation to signal the end
of a string can sometimes be a nuisance if you want to input spaces. For example, you
might want an entire sentence to be considered a single string. The getline() string
class member function (as declared by <string>) can be used for this purpose. Here
is an example that will be discussed in class:
//File: string2.cpp
#include <iostream>
#include <string>
using namespace std;
int main(void)
{ string sentence;
do
{ getline(cin,sentence);
cout << sentence + "\n";
}while (. != sentence[0]);
return 0;
179
The length() member function returns the length of a string, the number of characters
that it contains. The substr() member function extracts a sub-strings from a string.
Note that strings can be concatenated with the addition operator, although at least
one of the operands must be a string variable. Here is an example that demonstrates
these three new things.
//File: string3.cpp
#include <iostream>
#include <string>
using namespace std;
int main(void)
{ cout << "Type in a string: ";
string r1;
cin >> r1;
cout << "Your response was " << r1.length() << " chars long\n";
cout << "Type in another string: ";
string r2;
cin >> r2;
cout << "Your response was " << r2.length() << " chars long\n";
cout << "Putting them together: " << r1 + " " + r2 << "\n";
cout << "Slicing and splicing them up: "
<< r1.substr(0,2) + r2.substr(4,7) << "\n";
return 0;
}
7.3
7.3.1
So far we have been dealing with individual floats and ints, declaring them individually,
naming them individually, manipulating them one at a time, individually. Individuality is
nice, but sometimes it is more ecient to refer to a group of similar individuals in a collective
manner. In many applications we wish to use data, many of the same type, in some sort of
systematic or regular way.
180
7.3.2
Suppose I wanted to declare variables associated with the individual grades in this class. I
could do the following:
int
int
int
.
.
.
int
gradeForStudent1 = 98;
gradeForStudent2 = 79;
gradeForStudent3 = 88;
gradeForStudent217 = 91;
This is a really dumb, repetitive way to do it! Anything that seems really repetitive for
a human can probably be done in a better way by a machine. C++ allows you to dene
everything at once using the following syntax:
vector<int> gradeForStudent(217);
which declares, in one fell swoop, 217 ints. (We could also have made them floats or
doubles. We can make vectors out of any variable type.) So, we can refer to the collection
of grades by a single identier, gradeForStudent, in a collective fashion.
But we still have work to do. We still have to enter the numbers somehow into the computer
program. One way is through assignment statements:
gradeForStudent[0] = 98; /* 1st student */
181
182
There is one other new thing in the above code snippet, the introduction of the const
qualier to a variable. All this means is that the variable is to be held constant after its
initialization. Any attempt to change it would result in an error. This is a safe way to keep
vector sizes safe from programmer error if they are known to be xed.
The best way to input the numbers is to input them in a separate le and read this le
in during the execution of the code. This would make the code more general and the code
itself would not have to be concerned with having to enter the data faithfully. And, another
program could make use of this data. We will learn how to read and write les later on in
the course.
7.3.3
183
where vector1 was previously dened, creates a new vector called vector2 with the
same size as vector1 and copies all the elements of vector1 to vector2.
Example: Computing averages
Suppose we have a class of 10 students. I want to compute the average grade of a class test.
Here is a way to do it.
//File: sumGradesGood.cpp
#include <iostream>
#include <vector> //Need this to use the vector "class"
using namespace std;
int main(void)
{ const int MaxNoStudents = 10;
vector<int> grade(MaxNoStudents);
int sum = 0;
for (int i = 0; i < grade.size(); i = i + 1)
{ cout << "Grade for student #" << i + 1 << ": "; // Note the "+ 1"
cin >> grade[i];
sum = sum + grade[i];
}
cout << "\nGrade report:\n\n";
for (int i = 0; i < grade.size(); i = i + 1)
cout << "Grade for student #" << i + 1 << ": \t" << grade[i] << "\n";
cout << "Class avg is : " << static_cast<float>(sum)/grade.size() << "\n";
return 0;
}
And here is a sample use of the code:
Grade
Grade
Grade
Grade
Grade
for
for
for
for
for
student
student
student
student
student
#1:
#2:
#3:
#4:
#5:
1
2
3
4
5
184
Grade
Grade
Grade
Grade
Grade
for
for
for
for
for
student
student
student
student
student
#6: 6
#7: 7
#8: 8
#9: 9
#10: 10
Grade report:
Grade
Grade
Grade
Grade
Grade
Grade
Grade
Grade
Grade
Grade
Class
for
for
for
for
for
for
for
for
for
for
avg
student #1:
student #2:
student #3:
student #4:
student #5:
student #6:
student #7:
student #8:
student #9:
student #10:
is : 5.5
1
2
3
4
5
6
7
8
9
10
185
cout << "Grade for student #" << i + 1 << ": "; // Note the "+ 1"
cin >> grade[i];
sum = sum + grade[i];
}
cout << "\nGrade report:\n\n";
for (int i = 0; i < grade.size(); i = i + 1)
cout << "Grade for student #" << i + 1 << ": \t" << grade[i] << "\n";;
cout << "Class avg is : " << static_cast<float>(sum)/grade.size() << "\n";
return 0;
}
A example of its use is:
Number of
Grade for
Grade for
Grade for
Grade report:
Grade
Grade
Grade
Class
for
for
for
avg
student #1:
student #2:
student #3:
is : 7.66667
6
8
9
186
int main(void)
{ vector<int> grade;
double sum = 0, score;
do
{ cout << "Input a students grade: ";
cin >> score;
if (0. <= score && 100. >= score)
{ sum = sum + score;
grade.push_back(score);
}
}while(0. <= score && 100. >= score);
cout << "\nGrade report:\n\n";
for (int i = 0; i < grade.size(); i = i + 1)
cout << "Grade for student #" << i + 1 << ": \t" << grade[i]
<< "\n";
cout << "Class avg is : " << sum/grade.size() << "\n";
return 0;
}
An example of its use is:
Input
Input
Input
Input
Input
a
a
a
a
a
students
students
students
students
students
grade:
grade:
grade:
grade:
grade:
79
60
99
57
-1
Grade report:
Grade
Grade
Grade
Grade
Class
for
for
for
for
avg
student #1:
student #2:
student #3:
student #4:
is : 73.75
79
60
99
57
The new features of the above program is a new member function of the vector class, seen
in the statements:
187
.
.
.
vector<int> grade;
.
.
.
grade.push_back(score);
.
.
.
Note that the rst statement above simply declares a vector without a size! We are free to do
this. All it does is bind the identier grade to a vector variable type. The member function
push back(score) increases the size of the vector by one and initializes the new location
with its argument, in this case, the value of score. There is another member function called
pop back(), with no argument, that reduces a vectors size by one.
7.3.4
Remember that it is usually useful to think of vectors as simple variables. This is especially
true for vectors and functions. Take all the rules you have learned about functions and
variables and apply them to functions and vectors. To demonstrate this, consider the following example that demonstrates numerical integration. All the algorithm does is integrate
a simple function in three dierent ways. First, it puts the function into a vector with a
certain number of points based on an evenly divided mesh, or grid. Then it forms rectangles
in 3 dierent ways, using for its height the left mesh point, the right mesh point and the
midpoint. Can you guess why the midpoint method is so much better?
//File: integrate.cpp
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
double integrateLeft(vector<double> f, vector<double> x)
{ double sum = 0;
for (int i = 0; i < f.size() - 1; i = i + 1)
sum = sum + f[i]*(x[i + 1] - x[i]);
return sum;
188
}
double integrateRight(vector<double> f, vector<double> x)
{ double sum = 0;
for (int i = 0; i < f.size() - 1; i = i + 1)
sum = sum + f[i + 1]*(x[i + 1] - x[i]);
return sum;
}
double integrateMiddle(vector<double> f, vector<double> x)
{ double sum = 0;
for (int i = 0; i < f.size() - 1; i = i + 1)
sum = sum + 0.5*(f[i] + f[i + 1])*(x[i + 1] - x[i]);
return sum;
}
int main(void)
{ cout << "Number of points in the integration mesh: ";
int mesh;
cin >> mesh;
vector<double> f(mesh), x(mesh);
for(int i = 0; i < mesh; i = i + 1)
{ x[i] = static_cast<double>(i)/(mesh - 1);
f[i] = exp(x[i]);
}
double integral = integrateLeft(f, x);
cout <<
"left = \t\t" << integral << " cf " << exp(1.0) - 1.0
<< " diff = " << integral - (exp(1.0) - 1.0) << "\n";
integral = integrateRight(f, x);
cout <<
"right = \t" << integral << " cf " << exp(1.0) - 1.0
<< " diff = " << integral - (exp(1.0) - 1.0) << "\n";
integral = integrateMiddle(f, x);
cout <<
"midpoint = \t" << integral << " cf " << exp(1.0) - 1.0
<< " diff = " << integral - (exp(1.0) - 1.0) << "\n";
return 0;
7.4. PROBLEMS
189
7.4
Problems
190
7.4. PROBLEMS
191
return 0;
}
In the comments of your function, answer the question: Why were min and max given
as reference parameters ?
3. Nothing negative
Complete the program started below. You must complete the function nothingNegative()
which accepts a vector called bothSigns containing positive and negative integers and
returns a vector of equal or lesser length that contains only the non-negative integers
of the vector bothSigns. Here is a function stub and a main routine that you must
use to test your function:
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
vector<int> nothingNegative(const vector<int>& a)
{ //Why can this program, when compiled with just the function stub,
//go into what looks like an infinite loop?
//Answer the question and insert your code after this line.
}
int main(void)
{ int vectorLength = 10;
vector<int> bothSigns(vectorLength);
cout << " Input vector: ";
for (int i = 0; i < vectorLength; i = i + 1)
{ bothSigns[i] = rand()%201 - 100;
cout << "\t" << bothSigns[i];
}
cout << "\n";
vector<int> noNegs = nothingNegative(bothSigns);
cout << " Output vector: ";
for (int i = 0; i < noNegs.size(); i = i + 1)
{ cout << "\t" << noNegs[i];
192
4. Vector manipulations
Write a function that accepts one called-by-reference vector of ints and returns another
vector of ints. Upon entry to the function, the vector in the parameter list can be
any size and contains ints that can have any value. Upon return, the vector in the
parameter list contains only the positive ints (> 0) in the same order. Upon return,
the returned vector contains only the negative ints (< 0) in the same order as they
appeared in the original called-by-reference vector in the parameter list, when the
function was entered.
Here is an example of how it works:
Vector in the parameter list supplied to the function:
0 -6 -8 3 4 -8 0 8 -9 -8 8
That vector after the function returns:
3 4 8 8
Returned vector after the function returns:
-6 -8 -8 -9 -8
5. Push and pop
This is a more challenging version of the previous question. Complete the program
started below. Write a void function that accepts two called-by-reference vectors of
ints. Upon entry to the function, the rst vector can be any size and contains ints
that can have any value. The second vector is empty, its size is 0. Upon return,
the rst vector contains only the positive ints (> 0) in the same order. Upon return, the second vector contains only the negative ints (< 0) in the same order as
they appeared in the original rst vector, when the function was entered. Important:
Do this without declaring any new vectors.
#include <iostream>
#include <vector>
#include <cstdlib>
7.4. PROBLEMS
193
#include <ctime>
using namespace std;
//Function definition goes here...
int main(void)
{ srand(time(NULL));
int size = rand()%20 + 10; //size is a RN between 10 and 29
vector<int> in(size), out;
for (int i = 0; i < in.size(); i = i + 1)
in[i] = rand()%19 - 9; //RN between -9 and +9
cout << "Original vector is size " << in.size() << endl;
for (int i = 0; i < in.size(); i = i + 1)
cout << in[i] << " ";
cout << "\n\n";
extractNegs(in, out);
cout << "Returned vector is size " << out.size() << endl;
for (int i = 0; i < out.size(); i = i + 1)
cout << out[i] << " ";
cout << "\n\n";
cout << "Modified vector is size " << in.size() << endl;
for (int i = 0; i < in.size(); i = i + 1)
cout << in[i] << " ";
cout << "\n\n";
return 0;
}
6. More vector manipulations
Write a function that returns a vector<int> and accepts one called-by-reference
vector<int>. Upon entry to the function, the vector in the parameter list can be
any size and contains ints that are positive, negative and 0. Upon return, the vector
that is returned contains the indices of the original vector whose original values were
negative. Upon return, the original vector in the parameter list is modied so that
it only contains its original positive (> 0) ints in the same order that they appeared
in the original vector. Write your function below or on the next page. It should be
194
7.4. PROBLEMS
195
7. Perfect squares
Complete the program started below. Write a function that returns a vector<int>
and accepts one constant called-by-reference vector<int>. Upon entry to the function,
the vector in the parameter list can be any size and contains ints that are positive
(> 0). Upon return, the vector that is returned contains the indices of the rst vector
whose values are perfect squares.
#include
#include
#include
#include
#include
<iostream>
<vector>
<cstdlib>
<cmath>
<ctime>
196
9. A prime example
Complete the program started below. You must complete the function getPrimes()
that has the vector<int> return type. This function accepts an int called NPrimes
that is the number of consecutive prime numbers starting with 2. The return vector
contains these prime numbers in order.
You must make your function ecient by using something similar to the following test
to eliminate numbers that are not prime:
7.4. PROBLEMS
197
198
cout << "Input the minimum and maximum random int: ";
int minRange, maxRange;
cin >> minRange >> maxRange;
cout << "Input the length of the vector: ";
int vectorLength;
cin >> vectorLength;
vector<int> hasRepeats(vectorLength);
cout << " Vector beforehand: \t";
for (int i = 0; i < vectorLength; i = i + 1)
{ hasRepeats[i] = minRange + rand()%(maxRange - minRange + 1);
cout << hasRepeats[i] << " ";
}
cout << "\n";
noRepeats(hasRepeats);
cout << " Vector afterhand: \t";
for (int i = 0; i < hasRepeats.size(); i = i + 1)
{ cout << hasRepeats[i] << " ";
}
cout << "\n";
return 0;
Chapter 8
More Data Abstraction, Arrays,
Structures
8.1
Arrays
An array is an extension of the vector concept. An array can represent a list of objects with
a single index, for example, Ai , for i = 1, 2, 3...N. For numerical computation, so called
one-dimensional arrays are used to represent lists of objects (e.g. a list of grades). Two
one-dimensional arrays (e.g. x[i],f[x]) can represent a function f (x) by specifying a grid
of points along the x-axis, x[i], or xi , and the function evaluated at those grid points, f[i],
or fi = f (xi ). These are the most common uses of one-dimensional arrays.
Vectors, which we encountered in the previous lecture, are really one-dimensional arrays.
However, arrays are a lower level construct that comes from C. Simply stated, arrays are ordered collections of things you already know about, for example, ints, floats and doubles
with a few special rules related to indexing, initializing and communicating with functions.
A vector, on the other hand, is a standard class in C++ and it comes with powerful member
functions like size(), push back() and pop back(), that operate on the data in vectors. For
this reason, we will not investigate one-dimensional arrays in detail in this course, choosing
instead to focus on the more powerful vector class when dealing with 1-D applications.
The multi-dimensional array is an extension of the one-dimensional array concept. A twodimensional array can be thought of as a grid or table of values, a set of rows and columns,
each with its own value. There are many expressions of these. A two-dimensional array can
represent a checkerboard, a chessboard, the board in game of Battleship or Minesweeper, a
football eld, or the surface of the earth. (Yes, it is two-dimensional, Christopher; its just
not at!) We could think of many examples, there being no limit to human creativity. After
this lecture, you will have enough syntax tools and rules to program a game of chess. With
a little more understanding of atmospheric physics (not programming), after this lecture
199
200
you could write a program that predicts the weather! After only about 20 lectures we have
gotten this far! Now this is getting interesting! You have the tools and the rules, now apply
your creative thinking to design algorithms which themselves are only composed of three
thingsthe three pillars of algorithm design: sequence, branch and loop. It really just boils
down to this. It really is that simple and wonderful.
In more abstract terms, a two-dimensional array can represent a table of objects with two
indices, for example, Ai,j . For numerical computation in science and engineering, twodimensional arrays are used to represent tables of objects as in the examples above. Twodimensional arrays (e.g. x[i][j],f[i][j]) can represent a function of two variables, f (x, y),
by specifying a grid of points in the xy-plane, x[i][j], or xi,j , and the function evaluated
at those grid points, f[i][j], or fi,j = f (xi,j ). However, the most interesting ones for scientists and engineers are square two-dimensional arrays, also called matrices. In this course,
we will restrict our discussion to 2-dimensional arrays. There is nothing new in three and
higher dimensions that we will not see in studying 2-dimensional ones. And, the rules for
one-dimensional arrays can be obtained easily from two-dimensional arrays.
Unfortunately, C++ has not dened a new class to describe these objects. So we will have
to grapple with the more primitive array inherited from C. Later on in the course, we will be
studying Matlab. Matlab is built on two-dimensional arrays as the the fundamental variable
type and has developed a lot of functionality for it, which we will discover later. Matlab is
a very sophisticated program (used by professional engineers worldwide). However, if you
can develop the application in C++, it will always run faster, sometimes much faster. So,
we spend some eort learning how to work with two-dimensional arrays in C++. Besides,
doing so will be an excellent exercise in algorithmic thinkingthe prime reason for teaching
this course.
The ANSI standard calls for arrays of at least 12 dimensions. Believe it or not, there are
actually applications for this!
OK, enough with the sermon, already. Lets dive into the syntax before we learn how to
exploit it for creative expression. Some of the syntax was already introduced above.
8.1.1
8.1. ARRAYS
201
left to right and the rows numbered 0 to NROWS - 1 going down the page. Of course, this
visualization is completely arbitrary but helps serve as a memory aid.
a[0][0]
a[1][0]
a[2][0]
a[0][1]
a[1][1]
a[2][1]
8.1.2
0 0
0 0
0 0
This feature is important to remember as it saves a lot of typing, a particular passion of
mine.
The brace notation may also be used:
const int NROWS = 3;
const int NCOLUMNS = 2;
int a[NROWS][NCOLUMNS] = {{1,2}, {3,4}, {5,6}};
The result is:
202
The brace notation is nice because it may be used to initialize the array a little more suggestively. For example,
const int NROWS = 3;
const int NCOLUMNS = 2;
int a[NROWS][NCOLUMNS] =
{ {1,2},
{3,4},
{5,6}
};
with the same result.
Note the use of nested braces. If a brace is not lled completely, it is lled with zeros. For
example,
const int NROWS = 3;
const int NCOLUMNS = 2;
int a[NROWS][NCOLUMNS] = {{1}, {3}, {5}};
results in
1 0
3 0
5 0
Note that it is important, when initializing arrays in this fashion, to make the array size
declared with ints that are xed with the const qualier. Otherwise the compiler will
complain and not complete. Arrays can be declared anywhere in a program, for example:
const int nrows = 10;
const int ncolumns = 20;
float f[nrows][ncolumns];
However, the array will have to be initialized with executable statements. Also, in contrast
to vectors, arrays are not automatically initialized to zero. It must be done either on the declaration statement or explicitly initialized to zero within executable statements. Otherwise,
the array will contain bit patterns that were left in memory following previous use.
8.1. ARRAYS
203
Heres a small program that demonstrates some of the declaration, initialization and addressing concepts.
//File: whereItsAt.cpp
#include <iostream>
int main(void)
{ const int NROWS = 3;
const int NCOLUMNS = 2;
int a[NROWS][NCOLUMNS] = {{1}, {3}, {5}};
cout << a[0][0] << ":" << a[0][1] << "\n";
cout << a[1][0] << ":" << a[1][1] << "\n";
cout << a[2][0] << ":" << a[2][1] << "\n";
cout
cout
cout
cout
cout
cout
<<
<<
<<
<<
<<
<<
"&a[2][1]:
"&a[2][0]:
"&a[1][1]:
"&a[1][0]:
"&a[0][1]:
"&a[0][0]:
"
"
"
"
"
"
<<
<<
<<
<<
<<
<<
&a[2][1]
&a[2][0]
&a[1][1]
&a[1][0]
&a[0][1]
&a[0][0]
<<
<<
<<
<<
<<
<<
"\n";
"\n";
"\n";
"\n";
"\n";
"\n";
204
and stored. Dierent languages do this in dierent ways! C++s convention is to store it
from the outer index to the inner index, reinforcing the vectors of vectors concept. In our
two-dimensional example this means that all the columns in the rst row are stored, then
all the columns of the second row and so forth.
It is an important performance issue when writing programs to be aware of this storage order
and use the arrays in the most ecient manner. For example, the following program :
//File: fastArray.cpp
int main(void)
{ const int SIZE = 1000;
float a[SIZE][SIZE];
for(int k = 1 ; k <= 100 ; k = k + 1)
for(int i = 0 ; i <= SIZE - 1 ; i = i + 1)
for(int j = 0 ; j <= SIZE - 1 ; j = j + 1)
a[i][j] = 1;
return 0;
}
executes almost twice as fast on my computer than slowArray.cpp which is only dierent
in the ordering of the two for loops:
//File: slowArray.cpp
int main(void)
{ const int SIZE = 1000;
float a[SIZE][SIZE];
for(int k = 1 ; k <= 100 ; k = k + 1)
for(int i = 0 ; i <= SIZE - 1 ; i = i + 1)
for(int j = 0 ; j <= SIZE - 1 ; j = j + 1)
a[j][i] = 1;
return 0;
}
8.1.3
8.1. ARRAYS
//File: 2d.cpp
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
const int SIZE = 24;
const int MAX_PRINT = 24;
void printArray(float a[][SIZE])
{ if (SIZE <= MAX_PRINT)
{ for(int i = 0; i < SIZE; i = i + 1)
{ for(int j = 0; j < SIZE; j = j + 1)
cout << setw(2) << static_cast<int>(a[i][j]) << " ";
cout << "\n";
}
}
else cout << "Array is too big to print.\n";
return;
}
void productArray(vector<float>& y, float O[][SIZE], vector<float> x)
{ for(int i = 0; i < SIZE; i = i + 1)
for(int j = 0; j < SIZE; j = j + 1)
y[i] = y[i] + O[i][j] * x[j];
return;
}
int main(void)
{ /* Initialize the D array */
float D[SIZE][SIZE] = {0};
for(int i = 0; i < SIZE - 1; i = i + 1)
{ D[i][i] = -1;
D[i][i + 1] = 1;
}
// Initialize the I array
float I[SIZE][SIZE] = {0};
for(int i = 1; i < SIZE; i = i + 1)
for(int j = 0; j <= i; j = j + 1)
205
206
}
The output of this program is:
8.1. ARRAYS
The "D" array:
-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The "I" array:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
207
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
208
1
1
1
1
1
1 1
1 1
1 1
1 1
1 1
x
-1.000000
-0.913043
-0.826087
-0.739130
-0.652174
-0.565217
-0.478261
-0.391304
-0.304348
-0.217391
-0.130435
-0.043478
0.043478
0.130435
0.217391
0.304348
0.391304
0.478261
0.565217
0.652174
0.739130
0.826087
0.913043
1.000000
1
1
1
1
1
1
1
1
1
1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
f
d
0.497512
0.258711
0.520009
0.283216
0.544637
0.311375
0.571713
0.343954
0.601622
0.381930
0.634833
0.426560
0.671925
0.479500
0.713621
0.542947
0.760834
0.619879
0.814736
0.714408
0.876859
0.832347
0.949237
0.982116
1.034638
1.176305
1.136925
1.434410
1.261657
1.787930
1.417129
2.290509
1.616304
3.039655
1.880621
4.228182
2.248289
6.283189
2.794654
10.317343
3.691814
20.073689
5.437352
56.080322
10.313904 1031.390381
100.000000
0.000000
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1 1
1 1
1 1
F
0.000000
0.088480
0.135840
0.185554
0.237869
0.293072
0.351500
0.413554
0.479714
0.550560
0.626809
0.709351
0.799320
0.898183
1.007892
1.131120
1.271669
1.435201
1.630704
1.873718
2.194744
2.667557
3.564421
12.260068
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
0
0
0
1
1
0
0
0
0
1
8.2
8.2.1
10
10
10
10
10
10
10
1.0
209
f
D*f
I*f
0.5
0.0
0.5
1.0
Character arrays
One dimensional character arrays
We have seen previously that the string class is really a vector in disguise. One
can also string together characters in a more basic way using one-dimensional arrays.
One should only use this form when it is inconvenient to use the string class, as
in the example we have just been discussing, because there are some special rules
to remember. Moreover, forgetting these rules can lead to problems related to overrunning the boundaries of arrays. Indeed, some of these subtle behaviors are exploited
by destructive computer hackers (the scourge of the computer industry) to break into
computers and cause damage.
So, a character string may be represented as a one-dimensional array of single characters
that terminates with a specic character sentinel, the null character, i.e. \0. See!
There is a use for something that represents nothing! So, we always have to remember
to include this in the one-character array. If we forget to do this and try to interpret a
one-dimensional array of characters as a string, then the code, as it is operating on the
210
8.3. STRUCTURES
211
r, r, e, c, t, !, \0};
print?";
114, 110, 0};
i, s, t, a, k, e};
8.2.2
One can make arrays out of chars. For example, a checkerboard could be represented by:
char checkerboard[8][8];
for (int i = 0; i < 8; i = i + 1)
for(int j = 0; j < 8; j = j + 1)
checkerboard[i][j] = ; //Initialize with spaces
checkerboard[0][0] = R; //Place a red checker on the board
checkerboard[7][0] = B; //Place a black checker on the board
8.3
Structures
So far we have been introduced to many forms of variables that contain only one item of
information, bools, chars, ints, floats and doubles. These are fundamental variable
212
types in C++, useful interpretations of bits and bytes that are pre-dened in the denition
of the C++ language.
We have also seen more complex objectsclasses like vectors and strings.
We have also seen arrays of one and two and more dimensions that are made up of only one
of the above fundamental variables types but contain many items referred to by indexing
within the array.
In many cases, these pre-dened variable types are insucient to elegantly formulate a
solution to an interesting problem. Fortunately, C++ gives the programmer the ability to
make new compound variable types made up of a collection of the existing variable types.
This compound variable type is called a structure.
For example, we could dene a structure representing a person and the elements of the
structure could be a string for the persons name, an int for the persons age, floats for
the persons height and weight, more strings for the persons address and occupation and
so on. Structures are the essential composite data type for databases, which represent a
relatively large component of the software industry.
Another example relates to the car racing application of Assignment 6. Lets say that we
wanted to introduce new, racing-like features into the game, like oil slicks that reduce traction
on the road surface, or the ability to draft behind the opponents car. Every grid point
representing a part of the race track would have to carry more information, the coecient
of friction on the surface, and the direction and number of seconds past the time that a car
passed through it (so that the wind speed could be calculated). While these examples could
be done by separating the information into dierent variables, why not put them together
in a compound variable? After all, they are all related to one other.
8.3.1
8.3. STRUCTURES
8.3.2
213
structs can be dened everywhere although it is conventional to dene them outside of any
programming unit such as main or another function so that all programming units will have
access to this variable type.
8.3.3
The variables within the braces {}s are the members of the structure called Student. In
this case the members dened, as suggested by the naming of the member types, are a string
that will contain a name of a student, an int that will contain the section number of the
student and a oat that will contain the students grade. The use of a struct seems quite
natural in the application because the various things associated with any given student can
be variables of various types.
8.3.4
The structure tag is used with the keyword struct to declare (and optionally initialize)
variables of the structure type. For example, if we had dened the above structure type
Student, in the main routine or elsewhere we could declare and assign as follows:
struct Student
Dan = {"Smith, Dan", 210, 79.8},
Jan = {"Brown, Jan", 201, 89.3};
declares two structures of the Student type called Dan and Jan and assigns them names,
section numbers and grades.
8.3.5
Individual structure members can be assigned values by using the . notation of the form
structureName.structureMember. For example, if we had not made the assignment in the
declaration statement, we could have assigned values as follows:
Dan.name
Jan.name
214
8.3.6
Once dened and declared, we can treat these as regular variables, reassigning them, printing them, manipulating them in various ways. For example, we could make the following
redenitions:
Jan.name = "Smith, Jan"; // Jan and Dan get married!
Jan.section = 210;
// Jan moves over to Dans section (bad idea)
We can also treat a whole structure as a single variable. For example,
Dan = Jan;
reassigns the entire Dan structure, giving each member the values of the Jan structure.
Consult the complete working code called structure0.cpp that manipulates the Dan and
Jan structures.
8.3.7
Structures can be called by value. This means that the structures are copied locally in the
called function and the structures employed by the calling routine remain untouched. Here
is an example called structure1.cpp:
//File: structure1.cpp
#include<iostream>
#include<string>
struct Student{string name; int section; float grade;};
void switchStruct(struct Student a, struct Student b)
{ // I/O statements left out
struct Student temp = a; a = b; b = temp; // Switch a and b
// I/O statements left out
return;
}
int main(void)
{ struct Student
Dan = {"Smith, Dan", 210, 79.8},
Jan = {"Brown, Jan", 201, 89.3};
8.3. STRUCTURES
215
8.3.8
The more conventional way is to use call by reference for structures, saving memory. Here is
the same example as structure1.cpp but using called by reference. It is called structure2.cpp
//File: structure2.cpp
#include<iostream>
#include<string>
struct Student{string name; int section; float grade;};
void switchStruct(struct Student& a, struct Student& b)
{ // I/O statements left out
struct Student temp = a; a = b; b = temp; // Switch a and b
// I/O statements left out
return;
}
int main(void)
{ struct Student
Dan = {"Smith, Dan", 210, 79.8},
Jan = {"Brown, Jan", 201, 89.3};
// I/O statements left out
switchStruct(Dan,Jan);
// I/O statements left out
return 0;
}
8.3.9
Structure arrays
One of the most common uses of structs is to make arrays of them. Lets now dene an
array of structs of the form Student and make each element of the array represent one
of the students of the ENG101 course. Here is how it would be done. The code is called
structure3.cpp. It creates a class of ctitious students, assigns section numbers and grades.
Then it sorts them by name, section or grade, whatever the user wants.
216
//File: structure3.cpp
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<cstdlib>
// Define a structure called Student
const int maxNameLength = 10;
struct Student
{ char name[maxNameLength];
int section;
float grade;
};
bool switchStruct(struct Student& a, struct Student& b)
{ struct Student temp = a; a = b; b = temp; // Switch a and b
return false;
}
void sortStruct(vector<struct Student>& list, bool n, bool s, bool g)
{ bool sorted;
if (n)
{ do
{ sorted = true;
for (int i = 0; i < list.size() - 1; i = i + 1)
{ string string1 = list[i].name;
string string2 = list[i+1].name;
if (string1 > string2)
sorted = switchStruct(list[i],list[i+1]);
}
}while (!sorted);
}
else if (s)
{ do
{ sorted = true;
for (int i = 0; i < list.size() - 1; i = i + 1)
if (list[i].section > list[i+1].section)
sorted = switchStruct(list[i],list[i+1]);
}while (!sorted);
}
else if (g)
8.3. STRUCTURES
{
do
{ sorted = true;
for (int i = 0; i < list.size() - 1; i = i + 1)
if (list[i].grade < list[i+1].grade)
sorted = switchStruct(list[i],list[i+1]);
}while (!sorted);
}
return;
}
int main(void)
{ cout << "How many students in the class? ";
int nStuds;
cin >> nStuds;
vector<struct Student> myClass(nStuds);
for (int i = 0; i < nStuds; i = i + 1)
{ myClass[i].section = 200 + rand()%10;
myClass[i].grade = 0.1*(rand()%1001);
int nameLength = 2 + rand()%(maxNameLength - 2);
for (int j = 0; j < nameLength; j = j + 1)
myClass[i].name[j] = 97 + rand()%26;
myClass[i].name[nameLength - 1] = \0;
myClass[i].name[0] = myClass[i].name[0] - 32;
cout << setw(maxNameLength) << myClass[i].name << ", "
<< myClass[i].section << ", "
<< myClass[i].grade << "\n";
}
bool sortByName = false;
bool sortBySection = false;
bool sortByGrade = false;
cout << "Sort by name (0 (no) or 1 (yes))? ";
cin >> sortByName;
if (!sortByName)
{ cout << "Sort by section (0 (no) or 1 (yes))? ";
cin >> sortBySection;
if (!sortBySection)
{ cout << "Sort by grade (0 (no) or 1 (yes))? ";
cin >> sortByGrade;
}
217
218
8.3.10
int
int
int
int
int
NX = 20;
NY = 7;
STEPS = NY;
NCELL = 1000;
TOTAL = (NX*NY*NCELL);
//
//
//
//
//
x-grid dimensions
y-grid dimensions
# of time steps
# of pairs per cell
total # of pairs
8.3. STRUCTURES
}
}
return;
}
//-------------------------------------------------------------------// This function counts the number of e-s
int countE(struct N grid[][NY])
{ int count = 0;
for (int i = 0; i < NX; i = i + 1)
for (int j = 0; j < NY; j = j + 1)
count = count + grid[i][j].nE;
return count;
}
//-------------------------------------------------------------------// This function counts the number of positive ions
int countP(struct N grid[][NY])
{ int count = 0;
for (int i = 0; i < NX; i = i + 1)
for (int j = 0; j < NY; j = j + 1)
count = count + grid[i][j].nP;
return count;
}
//-------------------------------------------------------------------// This function recombines the e-s and ions
void recombine(struct N grid[][NY], int step)
{ for (int i = 0; i < NX; i = i + 1) // Loop over all rows
{ for (int j = step; j < NY; j = j + 1) // Loop over all columns
{ int nE = grid[i][j].nE;
for (int k = 1; k <= nE; k = k + 1) // Loop over all es
{ for (int l = 1; l <= grid[i][j].nP; l = l + 1)
{ // Potential annihilation with every ion in the cell
if (0 == rand()%2000) // Small chance of annihilation
{ // If there is an annihilation, reduce numbers by 1
grid[i][j].nE = grid[i][j].nE - 1;
grid[i][j].nP = grid[i][j].nP - 1;
break; // Break out of loop, only one life to give!
}
}
}
219
220
}
//-------------------------------------------------------------------/* This function shifts the electrons to the right and counts how
many are collected. Note that, depending on the step, we can start
at the y index where the number of e-s is non-zero.
*/
int tStep(struct N grid[][NY], int step)
{ int escaped = 0;
for (int i = 0; i < NX; i = i + 1)
{ escaped = escaped + grid[i][NY-1].nE;
for (int j = NY - 2; j >= step; j = j - 1)
grid[i][j+1].nE = grid[i][j].nE;
grid[i][step].nE = 0;
}
return escaped;
}
//-------------------------------------------------------------------// This function prints out the grid
void fGrid(struct N grid[][NY],int step){
resultsOnFile << "Step: " << step << "\n";
for (int i = 0; i <= NX - 1; i = i + 1)
{ for (int j = 0; j <= NY - 1; j = j + 1)
resultsOnFile << "|" << setw(5) << grid[i][j].nE
<< "," << setw(5) << grid[i][j].nP;
resultsOnFile << "|\n";
}
return;
}
//-------------------------------------------------------------------//-------------------------------------------------------------------//--------------------------- Main routine --------------------------//-------------------------------------------------------------------int main(void)
{ struct N grid[NX][NY];
// grid is an N struct
8.3. STRUCTURES
221
conditions
setw(2) << 0
<< setw(6) << countE(grid)
<< setw(6) << countP(grid)
" << setw(6) << 0 << "\n";
resultsOnFile.open("N.dat");
fGrid(grid, 0); // Write the grid to file
// Loop over time steps, set = to NY grid size
int tEsc = 0; // Total number of escapees
for (int step = 0; step < STEPS; step = step + 1)
{ recombine(grid, step); // Recombine e- & ions
int nEsc = tStep(grid, step); // Take a time step
cout << "Step " << setw(2) << step + 1
<< " : nE = " << setw(6) << countE(grid)
<< " : nP = " << setw(6) << countP(grid)
<< " : nEsc = " << setw(6) << nEsc << "\n";
fGrid(grid, step + 1); // Write grid, next step
tEsc = tEsc + nEsc; // Sum total escapes
}
resultsOnFile.close(); // Close the file
cout << "Chance of survival = " << setprecision(3)
<< static_cast<float>(tEsc)/TOTAL << "\n";
return 0;
}
//--------------------------------------------------------------------
222
8.4
Problems
...
Hint: Use for loops to do this. Supply the parameter lists for the three functions.
Answer the following question:
Why is the return vector always full of zeros?
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
const int ROWS = 5; // Set to 5 but can be anything
const int COLS = 4; // Set to 4 but can be anything
void print(/* Supply parameter list*/
{//Supply code for this function...
}
void randomFill(/* Supply parameter list*/
{//Supply code for this function...
}
vector<int> mMult(/* Supply parameter list*/
{//Supply code for this function...
8.4. PROBLEMS
223
}
int main(void)
{ int a[ROWS][COLS]; // Declare the array
randomFill(a); // Fills array with rand()%10 ints
print(a); // Prints the array
vector<int> x(COLS); // Declare a vector
// Multiply the vector x by the array a, returning y
vector<int> y = mMult(a,x);
// Print the result
for (int i = 0; i < ROWS; i = i + 1) cout << y[i] << endl;
return 0;
}
2. Making arrays of various types
Consider the following main routine:
int main(void)
{ int I[SIZE][SIZE]
int U[SIZE][SIZE]
int L[SIZE][SIZE]
int H[SIZE][SIZE]
=
=
=
=
{0};
{0};
{0};
{0};
ident(I);
upper(U);
lower(L);
hatch(H);
print(I);
print(U);
print(L);
print(H);
return 0;
}
The 5 functions called by main() produce the output shown following, when SIZE =
10. Write the 5 functions that complete this program. Your program has to work for
any SIZE greater than 0.
(Output from the completed program, when SIZE = 10)
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
224
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
8.4. PROBLEMS
225
sums the rows and columns putting the results into two separate vectors, sumRows, a
vector ROWS in length containing the sum of each row, and sumCols, a vector COLS in
length containing the sum of each column: The function print() prints the array to
cout and the vectors as shown in the example below. Note, pretty formatting is not
important, but the numbers have to be correct. Supply the parameter lists for the
three functions.
Example use:
>
2
3
1
3
9
a.out
2 1 3
2 3 0
3 0 0
1 3 1
- - 8 7 4
3
2
1
2
8
:
:
:
:
11
10
5
10
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
const int ROWS = 4; // Set to 4 but can be anything
const int COLS = 5; // Set to 5 but can be anything
int main(void)
{ int a[ROWS][COLS];
randomFill(a);
vector<int> sumRows(ROWS);
vector<int> sumCols(COLS);
sumRowsAndCols(a,sumRows,sumCols);
print(a,sumRows,sumCols);
return 0;
}
4. More vectors and arrays
Consider the following main routine:
const int ROWS = 10; //Constant defined as global
226
int main(void)
{ int a[ROWS][COLS] = {0};
vector<int>
for(int i =
vector<int>
for(int i =
r(ROWS);
0; i < r.size(); i = i + 1) r[i] = rand()%4; // 0 <= r[i] <= 3
c(COLS);
0; i < c.size(); i = i + 1) c[i] = rand()%4; // 0 <= c[i] <= 3
outerProduct(a,r,c);
print(a,r,c);
return 0;
}
Write the two functions outerProduct() and print(). outerProduct() computes
the outer product of two vectors, as follows:
a[i][j] = r[i]*c[j];
where r[i] and c[j] are vectors. print() prints out the vectors and array as shown
below. You do not have to concern yourself with pretty formatting, but the numbers
should come out in the order shown. Your program has to work for any positive values
for ROWS and COLS.
Here is how it works:
red% a.out
v:
1 0 2 2 3 2 1 2
---------------r[0]: 3| 3 0 6 6 9 6 3 6
r[1]: 1| 1 0 2 2 3 2 1 2
r[2]: 0| 0 0 0 0 0 0 0 0
r[3]: 3| 3 0 6 6 9 6 3 6
r[4]: 1| 1 0 2 2 3 2 1 2
r[5]: 3| 3 0 6 6 9 6 3 6
r[6]: 3| 3 0 6 6 9 6 3 6
r[7]: 1| 1 0 2 2 3 2 1 2
r[8]: 1| 1 0 2 2 3 2 1 2
r[9]: 1| 1 0 2 2 3 2 1 2
5. Complex structs
This problem uses a struct dened as follows:
8.4. PROBLEMS
227
228
8.5
Projects
8.5. PROJECTS
229
Here is an example of a typical play of the game. Your computer output does not have
to look exactly as follows. However, you have to follow the above rules explicitly.
Number of enemy ships? 1
Size of the enemy ships? (<= 10) 4
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
Bombs
away
away
away
away
away
away
away
away
away
away
away
away
away
away
#
#
#
#
#
#
#
#
#
#
#
#
#
#
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
i
i
i
i
i
i
i
i
i
i
i
i
i
i
j:
j:
j:
j:
j:
j:
j:
j:
j:
j:
j:
j:
j:
j:
3
7
4
3
9
6
2
2
2
3
3
3
4
5
4
2
1
6
2
0
6
7
5
6
7
5
4
3
230
8.5. PROJECTS
231
The starting grid in a one-person game (note prompt for acceleration at bottom):
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXFFFFFFX
Horizontal and vertical acceleration (-1,0,1):
To start the programming, write a working main routine and a function called initRace
that initializes the grid to the given starting conguration, and a function called
printRace that prints the grid. The walls and barriers have to be exactly as shown
in the gure on the last page. The barrier on the left is 20 columns wide and 35 rows
high. The barrier on the right is 25 columns wide and 35 rows high.
232
8.5. PROJECTS
User input: (0,1),(0,1)(0,1),(0,1),(0,1),(1,1),(1,1),(1,1),(1,1),(1,1)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XO
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X O
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
O
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
O
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
O
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
XXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXFFFFFFX
Crashed after 10 seconds
Note the car buried in the wall! (Ouch!)
233
234
8.5. PROJECTS
Richard Petty, eat your heart out!
(Solution by Ali Mehmet Kutman, Fall 2000 ENG101/CoE student at UoM)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XO
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
O
O
X
X
XXXXXXXXXXXXXXXXXXXX
O
O
X
X
XXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
O
O
X
XO
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
OXXXXXXXXXXXXXXXXXXXXXXXXXO
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
XO
XXXXXXXXXXXXXXXXXXXX
O XXXXXXXXXXXXXXXXXXXXXXXXX O
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X O
XXXXXXXXXXXXXXXXXXXX
O
XXXXXXXXXXXXXXXXXXXXXXXXX O
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
O
XXXXXXXXXXXXXXXXXXXX
O
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX O
X
X
O XXXXXXXXXXXXXXXXXXXX O
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
O
O
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
O
O
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX O
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX O
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
X
XXXXXXXXXXXXXXXXXXXXXXXXX
X
Finished after 31 seconds (Can anyone beat Alis 31 second solution?)
235
236
MACHINE
=======
? ? ? ?
------0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
8.5. PROJECTS
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
237
238
Chapter 9
Miscellaneous Topics
9.1
The C++ standard library, <cstdlib>, provides a way of producing a random number, actually a pseudo random number using the rand() function. The rand() function produces
a pseudo random integer between 0 and RAND MAX, inclusive. The constant RAND MAX is also
dened in <cstdlib>.
Here is an example program, called rand0.cpp that calls rand(). Note the inclusion of
<cstdlib>.
//File: rand0.cpp
#include <iostream>
#include <iomanip>
#include <cstdlib> // Need this for the rand() function
int main(void)
{ cout << "RAND_MAX = " << RAND_MAX << "\n\n";
cout << "The first 10 random numbers are...\n";
for(int i = 1; i <= 10; i = i + 1)
cout << "Random number "
<< setw(2)
<< i << " = "
<< rand() // Random int between 0 and RAND_MAX inclusive
<< "\n";
return 0;
}
239
240
241
242
int main(void)
{ cout << "RAND_MAX = " << RAND_MAX << "\n\n";
srand(time(NULL)); // Seed the random number generator
cout << "The first 10 random numbers are...\n";
for(int i = 1; i <= 10; i = i + 1)
cout << "Random number "
<< setw(2)
<< i << " = "
<< rand() // Random int between 0 and RAND_MAX inclusive
<< "\n";
return 0;
}
Try running rand2.cpp and verify that you get dierent numbers every time. This unique
start-up feature is very useful for programming games, in order to produce a game that starts
dierently every time.
The interesting uses of rand() involve making decisions based on the output of rand() and
this simulates random behavior. In many applications you can use the modulus function to
do this. For example,
card = rand() % 13 + 1
has a one in 13 chance of being a one, a one in 13 chance of being a two, etc. Thus, you
could use the above statement to simulate the random dealing of cards and you could assign
a one to an ace, a 2 to a deuce, 11 to a jack, etc. If you were dealing with a nite
series of cards, however, you would have to take some care that you do not deal, say, 5 aces
and that would require some extra care with the coding. We wont go into further detail
here on this topic except to say that dealing 5 aces can get you into BIG trouble in certain
circumstances.
Another way of using random numbers, more common to scientic disciplines, is to convert
the random integer to a random double or oat, usually converted so that the number lies
between 0 and 1 (may be inclusive or exclusive of one or both of the endpoints).
Here is an example code, called rand3.cpp, that converts the random integer to a double
between 0 and 1 inclusive:
//File: rand3.cpp
#include <iostream>
#include <iomanip>
#include <cstdlib> // Need this for the rand() and srand() functions
#include <ctime> // Need this for the time() function
243
int main(void)
{ cout << "RAND_MAX = " << RAND_MAX << "\n\n";
srand(time(NULL)); // Seed the random number generator
int nRandoms = 10;
cout << "The first " << nRandoms << " random numbers are...\n";
for(int i = 1; i <= nRandoms; i = i + 1)
{ double randomDouble = rand()/static_cast<double>(RAND_MAX);
cout << "Random number "
<< setw(2)
<< i << " = "
<< randomDouble // Random double between 0 and 1 inclusive
<< "\n";
}
return 0;
}
Heres an example of its use:
RAND_MAX = 2147483647
The first 10 random numbers are...
Random number 1 = 0.174225
Random number 2 = 0.130327
.
.
.
Application: Calculating by throwing darts
If you are as bad a dart player as I am, throwing a dart at a circular object is truly a random
process. Imagine that you have a circle inscribed in a square. It is easy to show that the
ratio of the area of the circle to the area of the square is /4. This suggests a way to estimate
what is by throwing darts! However, it only works well if you are a bad dart player, like
me.
Set up a circular dartboard on a wall. Draw a square on the wall so that the circle dening
the dartboard touches each side of the square only once. Now start throwing the darts
(badly). Ignore all the darts that land outside of the square. Throw a lot of darts! Count
the ones that land on the dartboard and all the ones that land within the square. The ratio
should be close to /4. And, your estimate gets better the more darts you throw. Warning:
244
Dont do this in your dorms. Dont do this at home. Try it outside against a fence
or something and make sure that other people, pets, your mothers favorite vase, etc. do not
get damaged.
A much safer way is to do it with a computer code. The following code, called randomPi.cpp
calculates by random sampling:
//File: randomPi.cpp
#include <iostream>
#include <cstdlib> // Need for rand() and srand()
#include <cmath> // Need for pow() and atan()
#include <ctime> // Need for time()
/* Define a conversion function that converts the int returned from
rand() to a double between -1.0 and 1.0 inclusive
*/
#define MYRAND (2.*rand()/RAND_MAX - 1.)
int main(void)
{ int nDarts = 10000; // Number of darts to throw
int nInside = 0; // Counter for those that land inside
srand(time(NULL)); // Seed the random number generator
for(int i = 1; i <= nDarts; i = i + 1)
{ double xDart = MYRAND;
double yDart = MYRAND;
if (pow(xDart,2) + pow(yDart,2) <= 1.0) nInside = nInside + 1;
}
double pi = 4.0*nInside/nDarts; // Estimate for Pi
double Pi = 4.0*atan(1.0); // This is how you can get a very
// accurate estimate of the real Pi!
cout << "The estimated value of Pi is " << pi << "\n";;
cout << "The true value of Pi is " << Pi << "\n";;
return 0;
}
There are a few new features in this program that you have not seen before.
The statement
#define MYRAND (2.*rand()/RAND_MAX - 1.)
245
in the pre-processor area replaces every occurrence of MYRAND throughout the rest of
the le with (2.*rand()/RAND_MAX - 1.). This happens before compilation. It is
exactly as if you took an editor, looked for every occurrence of MYRAND and pasted in
its replacement (2.*rand()/RAND_MAX - 1.). You can be as creative as you wish with
#define s, but make sure that you understand this as a cut and pasting procedure.
Generally, you should avoid #define s because the C++ parser does not help you
much with syntax errors. But, #define s are a part of the language and using them
can make life a lot easier sometimes. Just be careful with them.
The expression (2.*rand()/RAND_MAX - 1.) produces a random double between -1
and 1 inclusive. Why? rand() produces an int between 0 and RAND_MAX, inclusive.
Following the rules of precedence and the rules of variable type promotion multiplying
it by 2. produces a random double between 0. and 2.*RAND_MAX. Dividing
by RAND_MAX produces a random double between 0. and 2.. Finally, subtracting
1. from it produces a random double between -1. and 1.. There is a lot going
on in this simple-looking expression.
When you throw a dart on a 2-dimensional board, you are really choosing randomly
an x-coordinate and a y-coordinate. So the statements:
double xDart = MYRAND; double yDart = MYRAND;
pick a random point in a square dened by the corners:
(x, y) = (1, 1), (1, 1), (1, 1), (1, 1).
The pow() function, part of the standard library <cmath>, takes the power of the rst
argument to degree of the second argument. For example, pow(x,3) computes x3 .
So, the statement:
if (pow(xDart,2) + pow(yDart,2) <= 1.0) nInside = nInside + 1;
computes x2 + y 2 and compares it to 1. If x2 + y 2 1, the dart has landed in the circle
and it is counted.
Finally, the standard library math function atan(), also part of <cmath> computes
the arc tangent of its argument, assumed to be in radians. Since tan1 (1) = /4,
4.0*atan(1.0) is a very accurate determination of , as good as the math library can
provide, at least for a double.
Heres what 20,000 points tossed at a circle look like, generated by the program above.
246
9. MISCELLANEOUS
TOPICS
20000 random CHAPTER
points within
a square
n(inside circle)/n(total) = /4
9.1.1
The same idea may be used to integrate functions by random sampling. The following code,
called randomIntegrate.cpp integrates exp(x) for 0 x 1.
//File: randomIntegrate.cpp
#include <iostream>
#include <iomanip>
#include <cstdlib> // Need for rand() and srand()
#include <cmath> // Need for exp(), the exponential function
// and abs(), the absolute value function
/* Define a conversion function that converts the int returned from
rand() to a double between 0.0 and 1.0 inclusive
*/
#define MYRAND (static_cast<double>(rand())/RAND_MAX)
247
int main(void)
{ int nDarts = 1000000000, under = 0;
double Ans = 1 - exp(-1);
for(int i = 1; i <= nDarts; i = i + 1)
{ double xDart = MYRAND;
double yDart = MYRAND;
if (yDart <= exp(-xDart)) under = under + 1;
if (0 == i%1000000) // Every million times
{ double ans = static_cast<double>(under)/i;
cout << setiosflags(ios::fixed) << setprecision(8)
<< "#" << setw(10) << i
<< ": I = " << setw(10) << ans
<< ", Delta = " << abs(1 - exp(-1) - ans) << "\n";
}
}
return 0;
}
There are several new features in this code:
The standard math library functions dened in <cmath>, exp(), for the exponential
ex and abs() for the absolute value, are used.
setiosflags(ios::fixed) allows oating point numbers to print with trailing zeros,
nice for formatting. This only has to be done once.
setw() sets the width of the output of the following item. It has to be set every time!
setw() is dened in <iomanip>.
setprecision() set the precision of the following number. setprecision() is also
dened in <iomanip>.
The output of the above program looks like:
#
#
#
#
#
.
.
.
1000000:
2000000:
3000000:
4000000:
5000000:
I
I
I
I
I
=
=
=
=
=
0.63213700,
0.63193800,
0.63197933,
0.63180525,
0.63187300,
Delta
Delta
Delta
Delta
Delta
=
=
=
=
=
0.00001644
0.00018256
0.00014123
0.00031531
0.00024756
248
The program operates very much like the program that found by random sampling. We
nd an x and a y randomly. However, the only dierence is that we count only those points
that fall under the function as contributing to the area under the curve. The area under the
curve is the fraction of points that fall under the curve, times the area of the rectangle. In
the above example, the area of the rectangle is 1. If the rectangle did not have unit area,
how would you know what to multiply by? Thats what you have to gure out in assignment
4!
9.2
This is called the bubble or sinking sort technique because small items bubble to the top
and large items sink to the bottom. The technique involves looping through an array
looking at pairs of values in order. If the upper item is bigger than the lower item, they
are switched. Then the next pair is considered. The lower item of the previous pair is
the upper item of the current pair. The iteration continues until you can go through the
entire array and no pair is switched.
For example, imagine that you have the following array {3, 2, 1} that you want sorted in
ascending order. We will use the convention that parentheses surround the pair under
consideration.
Here is how it would work:
Loop
Loop
Loop
Loop
1:
2:
3:
4:
Change, continue
Change, continue
Change, continue
No change, stop
Here is some boiler plate pseudocode that gets the job done:
bool whileThingsAreChanging = true;
while(whileThingsAreChanging)
{ whileThingsAreChanging = false; //Assume that the list is sorted
for(/* appropriate for-loop parameters */) //Careful!
{ //Loop through the list in an order fashion in one direction
//Compare adjacent pairs of things
//If the pair is out of order, switch them and set
// whileThingsAreChanging to true
}
//When the for loop completes, either nothing has changed and
//whileThingsAreChanging has remained false, or something changed and
//whileThingsAreChanging was changed to true
249
}
//When the execution arrives here, the list is sorted.
9.3
Sometimes in mathematics, there are very compact ways of writing rules for generating
complicated things. For example, the factorial can be written out explicitly as:
N! = N (N 1) (N 2) 3 2 1
or, it can be written more compactly as
N! = N (N 1)! N >= 0 where 0! 1
where N is an integer.
Mathematicians prefer the second expression because it is better dened (no assumptions
about what means) and it also suggests a mechanism or process for calculating N! C++
mimics this by providing the programmer a mechanism called recursionthe ability for a
function to call itself. Here is how the factorial can be calculated using this technique.
//File: recursiveFactorial.cpp
#include <iostream>
int factorial(int n)
{ if (0 == n) return 1;
else return (n * factorial(n - 1));
}
int main(void)
{ cout << "N? ";
int N;
cin >> N;
cout << N << "! = " << factorial(N) << endl;
return 0;
}
Note how compact the coding is, and how similar it is to the second mathematical denition.
Note also how the 0! is coded in the if statement. This is critical to stop the recursion process.
Try writing out the stack frames for a simple case, say 5!, to see how this works.
There are a few simple, general guidelines for using recursion:
250
Successive calls to functions should represent progressively simpler cases. (For example,
(N 1)! is simpler than N!)
There is an end to the recursion, the base case, that does not involve a recursive
call. (For example 0! = 1)
If a function calls itself more than once, and the nesting level gets deep, the calculation can be very inecient. (See the following example.)
Recursion is a great way to crash a computer or a program! If you do not program the
stopping criterion correctly, you will cause your stack to collide with your heap, and
your program will be in a heap of trouble.
To illustrate the third point above, consider the calculation of the Fibonacci numbers dened
as follows.
f (N) = f (N 1) + f (N 2) N > 0 where f (1) 1 f (2) 1
where N is an integer. The code can be written using recursive calls as follows:
//File: recursiveFibonacci.cpp
#include <iostream>
int fibonacci(int n)
{ if (1 == n || 2 == n) return 1;
else return (fibonacci(n - 1) + fibonacci(n - 2));
}
int main(void)
{ cout << "N? ";
int N;
cin >> N;
cout << "Fibonacci(" << N << ") = " << fibonacci(N) << endl;
return 0;
}
The fibonacci function calls itself twice. This is a NO, NO! unless N is quite small, like
less than 30. Dont believe it? Try calculating f (1000)!
Although the above program is elegant and compact, we sometimes have to give up clarity for
eciency, yet another compromise we must sometimes make. Here is how one can program
the Fibonacci numbers using loops.
251
//File: loopFibonacci.cpp
#include <iostream>
int fibonacci(int n)
{ if (1 == n || 2 == n) return 1;
else
{ int fMinus2 = 1;
int fMinus1 = 1;
int f;
for (int i = 3; i <= n; i = i + 1)
{ f = fMinus2 + fMinus1;
fMinus2 = fMinus1;
fMinus1 = f;
}
return f;
}
}
int main(void)
{ cout << "N? ";
int N;
cin >> N;
cout << "Fibonacci(" << N << ") = " << fibonacci(N) << endl;
return 0;
}
Its ugly but its fast. Try comparing the speed of execution of the above two methods. You
will be surprised at the dierence.
Recursion relations play a big role in mathematics and consequently there are many examples
that could be coded in C++ and used as examples. However, another important use of
recursion relations relates to graphics. The following example recursively splits a line into
two smaller segments chosen randomly but with the same total length. This is a very simple
model of how a tree grows. The output of this program is the total number of branches
according to the users input of the largest branch length and the smallest branch length.
//File: tree.cpp
#include <iostream>
#include <cstdlib>
int tree(float L, float LMin)
{ if (L <= LMin) return 0;
252
}
int main(void)
{ cout << "LTotal, LMin? ";
float LTotal, LMin;
cin >> LTotal >> LMin;
cout << "Number of branches = " << tree(LTotal, LMin) << endl;
return 0;
}
There are two companion programs that will be demonstrated in class that provide graphical
output from this program. These are called treeGraphics.cpp and anotherTree.cpp,
both posted on the web. In class, the close connection to fractals will be evident from the
graphical output. Fractals are interesting not only mathematically, but have great uses in
communications, encryption and virtual cinematography!
Before closing the section on recursion, it is worthwhile to note that this technique is also
used in numerical simulation, something the author of this lecture is passionate about. In
fact, the coding in the tree programs shares a lot in common with, to cite a few examples,
scattering of light in the atmosphere, the movement of neutrons in a nuclear reactor, the
scattering of electrons and photons in the human body during diagnostic X-ray procedures
or treatment of cancer with radiotherapy beams. Just a few of the details are dierent. In
order to nd out what these details are, you will have to take a later course in numerical
simulation.
9.4
9.4.1
Why les?
Except for a few cases where we generated random data using quasi-random numbers,
so far we have been getting data into our programs by typing input at the keyboard
and any output that our programs have generated has gone to the computer screen.
This is really only useful for limited amounts of data, either on the input side or the
output side.
253
A large quantity of data is handled more easily and more reliably with les.
Moreover, the same data les can be used by more than one program.
How is data organized?
Computers only know about bits - binary digits, 0s and 1s. These are the only
fundamental data types understood by computer hardware.
Humans, on the other hand, are more comfortable with characters - and these, as we
have come to know are usually represented by 8 bits, a byte, by computers.
Characters can be combined into eldscombinations of characters that have some
unique meaning, like a oating-point number, an integer, a string of characters representing a persons name, etc
Character elds can be gathered into recordsof related elds, for example, a persons
name, social security number, age, salary, etc as many elds as are needed for a given
application.
Records can be combined into lescollections of records all somehow related, that
can be accessed by a computer program for some application.
Files are collected in directories. A single directory usually contains les with related data. Directories can also contain sub-directories with their own les and subdirectories. It is useful to think of a tree structure of directories. Each sub-directory
is another branch of the tree. The root directory is the trunk of the tree.
The disk on a computer can contain several such trees or partitions. The disk
controller, a hardware component in a computer, works with the operating system to
organizing or manage the les on the disk.
A single computer can contain several disks. Some computers, le servers, can house
many.
These disks (or portions of them) may be shared across networks with other computers either nearby (Local Area Networks [LANs]) or over long distances (Wide Area
Networks [WANs]).
The ability to connect computers and their data together makes possible the establishment of the World Wide Web [WWW], which permits access to some of the data that
resides on a computer connected to the network. This data can be made available to
anyone who knows its Uniform Resource Locator [URL]. The URL not only gives the
internet address of the data, but also conveys some information about what form the
data is in.
254
255
It is possible in C++ to redirect any or all of the stdin, stdout or stderr les.
We will demonstrate how to do this only as required for some specic purpose. It is
operating-system dependent.
It is possible in C++ to dene, create and read other les. Just keep in mind that
C++ creates these as streams and lets the operating system handle all the other details
of le management.
9.4.2
256
3. Before writing to the user-dene output stream, it must be opened using the .open()
output le object member function. For example,
myOutputFile.open("someData.dat");
opens the output le stream object called myOutputFile. It also connects the output le identier myOutputFile with a le called someData.dat. Data going to
myOutputFile will be written physically in the le someData.dat located on the computers hard disk (usually). In this example, the le someData.dat would reside in the
same subdirectory as the load module that was used to start the program assuming
that the user started the program with a statement like:
> a.out
You can also use relative or absolute path names for the parameter of the .open()
member function. For example, a typical unix system usage would be:
myOutputFile.open("~/Private/someData.dat");
and a Dos/Win usage:
myOutputFile.open("C:\\eng101\\hw\\hw6\\hw6.dat");
Can you guess why there are double backslashes above?
Warning! If the parameter of the .open() function refers to an existing le,
that le will be destroyed unless 1) it is write-protected, or 2), you take
special care to see if it exists before opening it. (More on this later.)
4. Always check to see that the le was opened successfully using the .fail() member
function. The .fail() member function returns a true when the le open failed. For
example,
if (myOutputFile.fail())
{ //File open fail
return 1; // Return to calling function with abnormal termination code.
}
257
5. Write to the output stream. Remember it is just a stream, just like cout, but with
your own identier. For example,
int i = 1, j = 2;
myOutputFile << i << ", " << j << endl;
6. When you are nished writing to the le, close the le using .close member function.
For example,
myOutputFile.close();
The .close() member function disconnects the output stream object, in this case,
myOutputFile, with the physical le, in this case, someData.dat. Although the termination of a program will properly close all les that it opened, it is a good idea to
close les as soon as you are nished with them. This frees up some system resources
for other programs and in the event of a system crash, closed les are left intact or
may be recovered more easily. Files left unclosed during a system crash may be left
incomplete. (This is somewhat system dependent and dependent upon how sudden
the crash is. Power failures are particularly nasty in this regard.)
Here is an example called fileOutput.cpp that illustrates all these concepts, plus a few
other concepts.
//File: fileOutput.cpp
#include <iostream>
#include <fstream>
using namespace std;
int main(void)
{ ofstream myOutputFile; // Create an output file object
cout << "What filename do you want to write to: ";
char fileName[20]; // 1D array of chars
cin >> fileName;
myOutputFile.open(fileName); //Connect the stream to the file
if (myOutputFile.fail())
{ // File could not be opened
cerr << "File called " << fileName << " could not be opened.\n";
258
}
This code makes use of the .eof() member function which tests to see if and end-of-le
(EOF) marker has been received in the stream that it is referring to, in this case, cin.
.eof() returns true if the EOF has been received and false otherwise. Note how this is
exploited in the above example. This is how you can control le input with an EOF sentinel.
On UNIX systems, EOF is signaled with a <RETURN><CNTL>-d, on MS systems by <CNTL>-z.
Note as well how the lename was obtained by inputting a 1D character array from the
keyboard. It would seem sensible to use a string class object to accomplish this, but many
compilers do not support the use of a string object as an argument to the .open() member
function.
9.4.3
Reading from sequential access les follows the same 6 steps except for the use of the
declaration ifstream rather than ofstream and the direction of the data as indicated
by the symbols << for output and >> for input! Thats all there is to remember.
Here is an example called fileInput.cpp that reads the output created by the previous
example:
//File: fileInput.cpp
#include <iostream>
259
#include <fstream>
using namespace std;
int main(void)
{ ifstream myInputFile; // Create an input file object
cout << "What filename do you want to read from: ";
char fileName[20]; // 1D array of chars
cin >> fileName;
myInputFile.open(fileName); //Connect the stream to the file
if (myInputFile.fail())
{ // File could not be opened
cerr << "File called " << fileName << " could not be opened.\n";
return 1; // Return to O/S with abnormal return code
}
else
cout << "File called " << fileName << " was successfully opened.\n";
bool keepReading = true; // Keep reading if true
do{
float x, y; // Two floats
myInputFile >> x >> y;;
if (myInputFile.eof()) keepReading = false; // End of file detected
else cout << x << " " << y << endl;
}while(keepReading);
cout << "End of input detected\n";
myInputFile.close(); //Disconnect the stream from the file
return 0;
}
260
261
}while(keepReading);
cout << "End of input detected\n";
myOutputFile.close(); //Disconnect the stream from the file
return 0;
}
9.5
Most unix commands are written in C or C++. For example, if you have ever listed the
contents of a directory, you have probably used the command ls. If you just type in ls
at the unix command prompt, you get a list of les that currently reside in your current
working directory. If you type in ls *.cpp you will get a listing of all the les that end in
.cpp. If you type ls -l, you get a long listing of les with information about ownership
and permissions for each le. The command is written in C and so you should wonder, How
did the programmer do that?.
The programmer did it by using command line arguments. Heres an example code that
exploits command line arguments:
//File: commandLine.cpp
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{ cout << "argc = " << argc << endl;
cout << "This programs name is: " << argv[0] << endl;
for (int i = 1; i < argc; i = i + 1)
{ cout << "Argument " << i << " is: " << argv[i] << endl;
}
return 0;
}
Note the new way of declaring the main routine:
int main(int argc, char* argv[])
{ .
262
}
When main is called, argc contains the number of tokens (think of these as words) on
the line that ran the program. For example, if you invoked the program with
a.out word anotherWord
argc would be 3.
argv[] is an array of addresses. (The * qualier on a variable means that the identier
contains one or more addresses.) These addresses contain the addresses of the starts of the
tokens of the command line. Resident at these addresses is the start of the one-dimensional
character arrays that contain the tokens. In the above example, the rst token is the name
of the executable le (usually a.out in our examples). The second token would be word and
the third and last token in this example would be anotherWord.
heres a program that can open a le based on a token given to it on the command line:
//File: fileOpen.cpp
#include <iostream>
#include <fstream>
using namespace std;
int main(int argc, char* argv[])
{ ofstream myOutputFile; // Create an output file object
char fileName[20];
if (argc == 1)
{ cout << "What filename do you want to write to: ";
cin >> fileName;
myOutputFile.open(fileName);
}
else if (argc == 2)
{ myOutputFile.open(argv[1]);
}
else
{ cerr << "Usage: a.out [filename]\n";
}
263
if (myOutputFile.fail())
{ // File could not be opened
cerr << "File could not be opened.\n";
return 1; // Return to O/S with abnormal return code
}
myOutputFile.close(); // Disconnect the stream from the file
return 0;
}
If only one token is detected, the user is prompted to input a lename. If two tokens are
detected, the second is used as a lename. If there are more than two tokens, the program
stops and prints an error message.
264
9.6
Problems
1. Double factorials
Write a recursive function that returns the double factorial as a function of its int
argument N.
This is how the double factorial is calculated:
N!! = N (N 2) (N 4) (2 or 1)
The algorithm stops when a reduction by 2 leaves a number that is equal to 1 or
2.
You may assume that N > 2 and you do not have to concern yourself with the
fact that there is a nite (usually 32) number of bits to represent ints.
Your function must be compatible with the main routine below.
#include <iostream>
using namespace std;
//Function goes here
int main(void)
{ cout << "N: ";
int N;
cin >> N;
cout << N << "!! = " << doubleFactorial(N) << endl;
return 0;
}
Here is an example of how it works:
red% a.out
N: 5
5!! = 15
2. Sorting structs
This problem uses a struct dened as follows:
struct Student {int studentNumber; float finalGrade;};
9.6. PROBLEMS
265
266
Chapter 10
A Potpourri of Applications
10.1
Lets say you were looking for a place where a function is zero in some interval. And lets also
suppose that the only thing you knew about the function was that it is monotonic (either
always increasing or decreasing) and that it crossed the axis only once.
In fact, you have seen such a function (in disguise) in Assignment 4. You were asked to nd
the maximum of the function:
x sin(x)
f (x) =
.
1+x
The derivative of this function is:
f (x) =
sin(x)
x cos(x)
.
+
2
(1 + x)
1+x
f (x) has the properties mentioned above for certain ranges of its argument. So, nding the
zero of f (x) is exactly the same as nding the position of the extremum (in this case the
maximum) of f (x). The solution you discovered to nd the maximum of f (x) involved a
laborious search over the function. The algorithm about to be described, call the binary
chop or mid-point bisection method, works much more eciently, as we shall see with only
about 40 iterations. The pseudocode for the algorithm is:
1. Start with an initial guess for an x0 and an x1 such that the function is zero for some
x0 x x1 . From the properties of the function, we know that the sign of f (x0 ) is
dierent from the sign of f (x1 ).
2. Evaluate the function at the mid-point, xm = (x0 + x1 )/2.
3. If f (xm ) < ! , where ! is the convergence criterion, xm is the estimated zero of the
function and the algorithm can stop. Otherwise,
267
268
269
270
However, cerr would still print to the screen so that the user would know something had
gone wrong. If the error message had been written to cout, the user would not know until
he or she opened to le.
Another example is:
red% a.out < myInput > myOutput
which reads cin from the le called myInput rather than the keyboard. Note that the le
names are arbitrary. The names myOutput and myInput are just examples.
Chapter 11
Programming in MATLAB
11.1
A taste of MATLAB
Chapter 11: Basic info, logical operators, logic ow control, functions (read now)
Chapter 12: 2D and 3D graphics
Chapter 13: Some applications
What is MATLAB?
An interpreted computer language
The name of the program that interprets MATLAB language
Central ideaall data is represented by 2D arrays of doubles
Data types and variables:
Names of variables? Same as ANSI C++
Types of variables and declarations?
C++: Many types, MUST declare
MATLAB: 1 type (2-D arrays of doubles) only and dont declare
A MATLAB demo:
271
272
Statements
ANSI C++: Terminated by a semicolon
MATLAB: Terminated by and end-of-line (carriage return)
unless you put a ... at the end of the line to continue
Can also terminate with a ; which suppresses the echo of the statement
Flow controlwhile loops
ANSI C++:
i = 0;
while(i<10)
{ i = i + 1;
}
MATLAB:
i = 0;
while(i<10)
i = i + 1;
end
273
if (i <= 10)
j = 0;
else
k = 0;
end
Example of summing the integers, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
ANSI C++:
int main(void)
{ int i = 0, s = 0;
while(i < 10)
{ i = i + 1;
s = s + i;
}
cout << s << "\n");
return 0;
}
MATLAB:
i = 0;
s = 0;
while(i < 10)
i = i + 1;
s = s + i;
end
disp(s)
Scripts and functions
Scripts (or script M-les) are MATLAB statements in a le that the MATLAB interpreter will execute
Functions (or function M-les) are used to implement functions.
Function names are derived from le names.
11.2
Arrays in Matlab
The idea: 2-D arrays of doubles are the fundamental data type
274
Size
Bytes
10x1
80
Class
double array
z = zeros(5,3)
z =
0
0
0
0
0
>>
whos
Name
x
z
0
0
0
0
0
0
0
0
0
0
Size
10x1
5x3
Bytes
80
120
Class
double array
double array
275
>> whos
Name
x
Size
Bytes
1x10
80
10
Class
double array
Note that the upper limit, 10, is not reached because the next number in the
series would overrun it.
linspace creates a 1D array with uniformly spaced elements.
x = linspace(a,b,N)makes N equally spaced points between a and b inclusive.
(The statement x = a:(b-a)/(N-1):b seems to accomplish the same thing BUT
round-o errors may cause the end-point b to be excluded! DO NOT USE the x
= a:(b-a)/(N-1):b form!)
An example:
276
0.5000
0.7500
1.0000
Literal creation:
Create an array with one row and 3 columns:
>> x = [1.0,5.2,9.7]
x =
1.0000
5.2000
9.7000
>>
Create an array with 2 rows and 3 columns:
>> y = [1.0,5.2,9.7;3.4,9.3,10.7]
y =
1.0000
3.4000
5.2000
9.3000
9.7000
10.7000
>>
Array indexing
Simple indexing
x(i) refers to the ith element of array x
There is no o-by-one nonsense!
x = ones(1,10) = x = [1,1,1,1,1,1,1,1,1,1]
x(1) is the rst element of array x
x(10) is the last element of array x
Array indices go from 1 to the number of rows/columns
>> x = [3,5;7,9]
x =
3
7
5
9
=
=
=
=
3
7
5
9
=
=
=
=
row
row
row
row
277
1,
2,
1,
2,
column
column
column
column
1
1
2
2
Slice indexing
The : symbol as an array index means the whole row or the whole column.
Example,
>> x = [1,2;3,4;5,6]
x =
1
3
5
2
4
6
>> y = x(:,2)
y =
2
4
6
>> z = x(1,:)
z =
1
278
3
5
4
6
Saving an array to a le
sindat is a 2 row, 1000 column array created and saved this way:
%ch11e1.m
sindat = zeros(2,1000);
sindat(1,:) = linspace(0,2*pi,1000);
sindat(2,:) = sin(sindat(1,:)); % Note: array operation!
save sindat -ascii -double
Reading an array from a le
The following reads sindat in and plots it.
%ch11e2.m
clear
load sindat
x = sindat(1,:);
y = sindat(2,:);
plot(x,y) % Simple plotting function
pause % Pauses until any keystroke is given
close % Closes the figure
plot(x,y.^2) % Note: ".^2" means element by element squaring operation
pause
close
plot(y,x)
pause
close
Summary
zerosCreate and initialize an array and ll the array with 0.0s
onesCreate and initialize an array and ll the array with 1.0s
clearClear variables from memory
whosList current variables, long form
linspaceCreate a 1D array with uniformly spaced elements
11.3. LOOPS
279
11.3
Loops
11.3.1
280
i = 1:10;
sum = 0;
for j = 1:length(i) % length(array) is a MATLAB function that gives the length
sum = sum + j;
end
disp(sum);
Heres a weird way of doing the same thing:
i = [1,2,3,4,5;6,7,8,9,10];
sum = 0;
for j = i % j is set to the columns of i
sum = sum + j(1) + j(2);
end
disp(sum);
Why does this work?
The number of columns of i is 5 and so, the loop is executed 5 times. But on each iteration,
y is set to a column of x, in this case a column vector with two values which are summed
with the statement sum = sum + j(1) + j(2);. Weird! But it works and illustrates the
more general form of the looping index.
Some useful functions
size gives the number of rows and the number of columns as a two-element row vector.
For example (using the i array above):
>> size(i)
ans =
2
5
If you want to capture both the number of rows and columns, use the following:
>> [nRows,nColumns]=size(i)
nRows =
2
nColumns =
5
length gives the maximum of the number of rows and the number of columns. For example
(using the i array above):
11.3. LOOPS
281
>> length(i)
ans =
5
error error(string) displays the string and causes an error exit from an M-le to the
keyboard. If the string is empty, no action is taken.
Heres an example of an integration script using length and error.
% Area under f as a MATLAB script
% Assumes that f and x already exist
if (length(x) ~= length(f))
error( x and f are different lengths. Stopping.)
end
sum = 0;
for j = 1:(length(f)-1)
sum = sum + 0.5*(f(j) + f(j + 1))*(x(j+1) - x(j));
end
disp(sum);
Heres a 2D plotting example:
N = 100;
f = zeros(1,N);
x = linspace(-5*pi,5*pi,N);
for i = 1:N
if (x(i) == 0)
f(i) = 1;
else
f(i) = sin(x(i))/x(i);
end
end
plot(x,f);
Heres a 3D plotting example (using the above f):
g = zeros(N,N);
for i = 1:N
for j = 1:N
g(i,j) = f(i)*f(j);
282
end
surf(x,x,g);
11.3.2
11.4
expression1 is true
expression1 is false and expression 2 is true
expression1&2 are false and expression 3 is true
283
New function:
rand provides an array of uniformly distributed random numbers between 0 and 1.
11.5
Class
double array
double array
72 bytes
284
>> cv = zeros(10,1);
>> whos
Name
Size
Bytes Class
cv
10x1
80 double array
rv
1x8
64 double array
s
1x1
8 double array
Grand total is 19 elements using 152 bytes
matrix An N by M matrix in MATLAB is an N M array. For example:
>> a = rand(3,4);
>> whos
Name
Size
Bytes Class
a
3x4
96 double array
cv
10x1
80 double array
rv
1x8
64 double array
s
1x1
8 double array
Grand total is 31 elements using 248 bytes
>> a
a =
0.7382
0.9355
0.8936
0.8132
0.1763
0.9169
0.0579
0.0099
0.4057
0.4103
0.3529
0.1389
11.6
Operators in MATLAB
11.6.1
Operation
Inner expression
Exponentiation
Multiplication, x y
Division, x/y, y\x
Addition, x + y
Subtraction, x y
Assignment
Symbol
(,)
^
*
/,\
+
=
Example
(1+2)/3
2^3
x*y
y/x = x\y
x + y
x - y
y = x
Precedence
Highest
Medium high
Moderate
Moderate
Medium low
Medium low
Lowest
285
>> a = 2*ones(2)
a =
2
2
2
2
>> b = a/4
b =
0.5000
0.5000
0.5000
0.5000
>> a*b
ans =
2
2
2
2
>> a+b
ans =
2.5000
2.5000
11.7
2.5000
2.5000
Operation
Pointwise exponentiation
Pointwise multiplication
Pointwise division
Here are some examples:
>> x = 2*ones(2)
x =
2
2
2
2
>> y = [0,1;2,3]
y =
0
1
2
3
>> x.*y
ans =
0
2
4
6
>> x.^y
Symbol
.^
.*
./,.\
Example
x.^y
x.*y
y./x = x.\y
Expansion
x(i,j)^y(i,j)
x(i,j)*y(i,j)
x(i,j)/y(i,j)
286
ans =
1
4
>> x.\y
ans =
2
8
0
1.0000
11.7.1
Symbol
< , <=
> , >=
==
~=
& , |
~
0.5000
1.5000
Note that these operators work on arrays and can return arrays. The relational operators
operating on arrays is not discussed in this course; we will be using them as if they always
operate on scalars. Therefore, in this sense, they behave exactly as the analogous operators
in C++,
There are some dierences in notation with C++ (~= vs. !=, & vs. &&, | vs. ||, ~ vs.
!) However, the biggest dierence with respect to C++ is the dierence in the order of
precedence of the operators. Note that even some textbooks are confused on this issue. Here
is the current state of the order of precedence of the MATLAB operators. Note that for
MATLAB Version 5.3 and lower, the precedence table is dierent!
Operation
Symbol
Inner expression
( )
Transpose, Exponentiation
^ .^
Unary plus and negation
+ - ~
Multiplication, division
.* .\ ./ * \ /
Binary addition, subtraction
+ Colon operator
:
Relational logical operators < <= > >= == ~=
Logical AND
&
Logical OR
|
Assignment
=
Precedence
0 (Highest)
1
2
3
4
5
6
7
8
9 (Lowest)
For more complete information, issue help precedence. This is what you get:
PRECEDENCE
MATLAB has the following precedence for the built-in operators when
evaluating expressions (from highest to lowest):
1. transpose (.), power (.^), complex conjugate
transpose (), matrix power (^)
2. unary plus (+), unary minus (-), logical negation (~)
3. multiplication (.*), right division (./), left
division (.\), matrix multiplication (*), matrix right
division (/), matrix left division (\)
4. addition (+), subtraction (-)
5. colon operator (:)
6. less than (<), less than or equal to (<=), greater than
(>), greater than or equal to (>=), equal to (==), not
equal to (~=)
7. logical AND (&)
8. logical OR (|)
Starting in MATLAB 6.0, the precedence of the logical AND (&)
and logical OR (|) operators now obeys the standard relationship
(AND being higher precedence than OR) and the formal rules
of boolean algebra as implemented in most other programming
languages, as well as Simulink and Stateflow.
Previously MATLAB would incorrectly treat the expression:
y = a&b | c&d
as:
y = (((a&b) |c) &d);
It now correctly treats it as:
y = (a&b) | (c&d);
287
288
The only case where the new precedence will impact the result
obtained is when | appears before & within the same expression
(without parentheses). For example:
y = 1 | x & 0;
In MATLAB 5.3 and earlier, this statement would yield 0,
being evaluated as:
y = (1 | x) & 0;
In MATLAB 6.0 and beyond, this expression yields a 1 as the result,
being evaluated as:
y = 1 | (x & 0);
We strongly recommend that you add parentheses to all expressions of
this form to avoid any potential problems with the interpretation
of your code between different versions of MATLAB.
NOTE: A feature has been provided to allow the system to produce an
error for any expression that would change behavior from the old to
the new interpretation:
feature(OrAndError, 0)
feature(OrAndError, 1)
11.8
M-les
11.8.1
Script M-les
%
%
%
%
MATLAB commands may be stored in a le and executed. These les are called script
M-les. Any commands that you can enter in the MATLAB command window can be
entered in a le with a lename that is arbitrary except that it should contain the extension
.m, for example myMatlabScript.m. Script M-les may be created with your favorite editor
11.8. M-FILES
289
290
11.8. M-FILES
disp(If you lose, you lose everything!)
disp(Its best to quit while youre ahead.)
disp(Press any key to start.)
disp(Good luck)
disp( )
pause
money = 0;
repeat = input(Play? (0 = no, 1 = yes) :);
while(repeat)
disp(Spin....)
pause(1)
if (rand < prob)
disp(BANG! You LOSE!)
return
else
disp(Click! You WIN!)
money = money + 1;
disp(sprintf(Your gain is $%g,money))
end
repeat = input(Repeat? (0 = no, 1 = yes) :);
end
disp(sprintf(Your gain was $%g,money))
disp(End of Game)
disp( )
Heres a typical play of the game:
>> russianRoulette
With each spin you could win $1.
If you lose, you lose everything!
Its best to quit while youre ahead.
Press any key or mouse button to start.
Good luck!
Play? (0 = no, 1 = yes) :1
Spin....
291
292
11.8.2
1 = yes) :1
1 = yes) :1
1 = yes) :1
1 = yes) :1
1 = yes) :1
1 = yes) :1
1 = yes) :1
Function M-les
11.8. M-FILES
293
294
If the second line of the le is a comment, it is used by MATLAB to look for functions
and functionality using the lookfor MATLAB function.
Comment lines following contiguously are copied to the screen when you type
help functionName
You can have more than one function in a function M-le. However, only the rst (the
primary function) is available to other M-les and the command window. The others
are called subfunctions and cannot be used by other functions, scripts or the command
window.
Here is an example called quadRoots.m:
function [root1,root2] = quadRoots(A,B,C)
%QUADROOTS quadRoots returns the two real roots of A*x^2 + B*x + C = 0
%
% The two roots are root1 = (-B + sqrt(B^2 -4*A*C))/(2*A)
%
root2 = (-B - sqrt(B^2 -4*A*C))/(2*A)
%
% An error is detected if 4*A*C > B^2 (imaginary roots)
% A warning is issued if 4*A*C = B^2 (identical roots)
%
% The blame? BLIF <bielajew@umich.edu>
% This version 1.1, last modified November 27, 2000
% Warranty? None. Take it or leave it.
% Copyright: Regents of the University of Michigan
if 4*A*C > B^2
error(Roots would be imaginary. Get real!)
elseif 4*A*C == B^2
warning(Roots will be the same, degenerate)
end
root1 = (-B + sqrt(B^2 -4*A*C))/(2*A);
root2 = (-B - sqrt(B^2 -4*A*C))/(2*A);
return % This is optional
11.9. PROBLEMS
11.9
295
Problems
296
11.9. PROBLEMS
297
8. True or false?
(a) The 3 statements
clear all; x = 1.0; i = &x;
are ALL valid MATLAB statements.
(b) The 3 statements
clear all; x = 1; i = i & x;
are ALL valid MATLAB statements.
(c) The set of statements
clear all; a = 2*ones(2,2); b = a/4; c = a*b; disp(c)
prints
1 1
1 1
to the screen.
to the screen.
298
1
0
-1
0
0
0
1
0
-1
0
0
0
1
0
-1
0
0
0
1
0
(b) The following code is supposed to sum the squares of the matrix elements of a
random 10 by 10 array and then divide the sum by the number of elements. It
does not work as intended.
clear all;
N = 10;
s = rand(N);
s2 = s*s;
for i = 1:N for j = 1:N sum = sum + s2(i,j); end; end
disp(sum/N^2)
11.9. PROBLEMS
for i = N/4:3*N/4
for j = N/4:3*N/4
a(i,j) = 0;
end
end
(a) Write it without the use of for or while loops.
(b) If the variable N was set to 4 instead of 100, what would the array look like?
11. Think like a computer
Write the output that the following MATLAB code produces.
clear all;
z = ones(6);
z(3:4,:) = 0;
z(:,3:4) = 0;
disp(z);
12. Think like a computer again
Consider the following script M-le.
sign = 1;
for i = 1:5
x(i) = i - 3;
y(i) = sign*i;
sign = -sign;
end
plot(x,y);
Draw the plot that would result from executing this script.
13. Think like a computer again
Write the output that the following MATLAB code produces.
clear all;
z = -ones(7); % Dont miss the minus sign!
z(2:3,2:3) = 1; z(2:3,5:6) = 4;
z(5:6,2:3) = 2; z(5:6,5:6) = 3;
z(4,4) = 0;
disp(z);
299
300
11.9. PROBLEMS
b=rand(1,50)*100;
[ind,y] = nearest(b(50),x);
fprintf(The nearest value to %f is b(%i)=%f\n,x,ind,b);
301
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
302
%
%
%
%
%
%
Array size
Allocate memory for f
Make a linspace for x
Calculate f(x)
Plot it
Line
Line
Line
Line
Line
Line
001
002
003
004
005
006
11.9. PROBLEMS
303
304
Read through the rest of the MATLAB code and understand what it is trying to
do. The bottom part is for placing the stars.
Write the function star(x,y,r). x and y are the points that dene the center of
the star, and r is its radius. Notice that the 5 points on a star are all located on a
circle centered at x and y with radius r. If you drew lines from the center to the
points of the star, those lines would be separated by 72 degrees, (72 = 360/5).
To draw the star, imagine that the top point of the star is numbered 1, the one
to its right 2, and so on. You can make a star easily by drawing a line from point
1, to 4, to 2, to 5, to 3 and back to 1. Heres an example of star(1,3,2).
You might nd it useful to to use the sin() and cos() functions. The argument
to these functions should be expressed in radians. In MATLAB, the conversion
from degrees to radians is given by: rads = pi*a/180, where a is an angle in
degrees and rads is the same angle expressed in radians.
You should use the plot() function using white solid lines. Here are the details:
PLOT
Linear plot. PLOT(X,Y) plots vector Y versus vector X.
Various line types, plot symbols and colors may be obtained with
PLOT(X,Y,S) where S is a character string made from one element
from any or all the following 3 columns:
b
blue
point
solid
11.9. PROBLEMS
305
4.5
3.5
2.5
1.5
1
1
0.5
g
r
c
0.5
green
red
cyan
1.5
o
x
+
circle
x-mark
plus
2.5
:
-.
--
dotted
dashdot
dashed
.
.
.
For example, PLOT(X,Y,c+:) plots a cyan dotted line with a plus
Your function has to respond sensibly to the lookfor and help functions.
%FLAG flag Solution to Stars and Stripes forever
clear all
%Code to make the flag without stars below
306
11.9. PROBLEMS
307
(a) This function has one input argument, the initial guess for x.
(b) This function has two output arguments, the nal approximation of the xvalue at which the zero is found, and the number of steps it took to nd
it.
(c) Set a convergence criterion of ! = 106 .
(d) Initialize the number of iterations to zero.
(e) Carry out the following steps until the absolute value of f (x) < ! where f is
the function you are zeroing, and x is your current approximation of the zero.
Calculate an approximation to the derivative of the function at this point,
from
f (x + !) f (x !)
f (x) =
2!
Calculate a new approximation to the zero, from
x = x f (x)/f (x)
Update the number of steps that you have taken through the loop.
(f) Return to main
Function M-le f
(a) This function has one input argument, x.
(b) This function has one output argument, y.
(c) The relation is
y = x2 sin(x)/x;
23. Temperature along an iron bar
Consider an iron bar 100 cm long. One end of it is xed at 0 C while the other end is
xed at 100C. You must plot the temperature as a function of the distance between
its end-points by dividing the bar into 1000 elements and using only the following
information:
The temperature of the elements at either end is xed. That is,
TBar(1) = 0; TBar(1000) = 100;
Except for the xed endpoints, the temperature in any element is determined as
the average of its neighbors. That is,
TBar(i) = 0.5*(TBar(i-1) + TBar(i+1))
The solution is obtained by iteration within a while loop until the average temperature in the bar, sum(TBar)/1000, changes by less than 0.01 C from the average
temperature in the bar from the previous iteration.
308
11.9. PROBLEMS
309
310
11.9. PROBLEMS
311
1.8
1.6
50
1.4
40
1.2
1
30
0.8
0.6
20
0.4
10
0.2
10
20
30
40
50
60
312
0.9
12
0.8
0.7
10
0.6
8
0.5
0.4
0.3
4
0.2
0.1
10
15
20
25
30
35
40
11.9. PROBLEMS
313
(d) The color of the background is established by giving it a numerical value of 0.0.
(e) The color of the inner rectangle is established by giving it a numerical value of
0.7.
29. Array striping
Write the MATLAB code that generates the array that produces the following plot. It
should work for any response to user inputs (see example below).
20
15
10
10
15
20
25
30
35
40
The array contains the data 0 (black stripe) or 1 (white stripe) in a pattern that
produces the above gure. The following response to the prompts produced the output
shown:
Number of stripes: 8
Number of Rows: 24
>>
30. Basket weaving
Write the MATLAB code that generates the array that produces the following basketweave plot.
The array contains the data 0 (background), 0.6 (vertical dark grey stripes), or 1
(horizontal light grey stripes) in a pattern that produces the above gure. The following
response to the prompts produced the output shown above:
314
0
0
1
0
0
0
(a) Write a function called littleEye() that does the same thing except the 1s are
on the minor diagonal. Example:
>> littleEye(3,4)
ans =
0
0
0
11.9. PROBLEMS
0
0
315
0
1
1
0
0
0
You should do this by having littleEye() call eye() and manipulating array
indices using slice indexing.
(b) Write another function called cross() that sums eye() and littleEye(), except
that the maximum element returned can not be greater than 1. Example:
>> cross(3,3)
ans =
1
0
0
1
1
0
1
0
1
You can avoid using for loops by using the min() function. For example, if A is
a scalar and B is a matrix, C = min(A,B) returns a matrix C that has no value
greater than A.
32. A smooth operation
Consider the following MATLAB script M-le that calls the function called smooth.
NH = input(Horizontal size of plot: );
NV = input(Vertical size of plot: );
a = rand(NV,NH);
avgChng = 1;
while(avgChng > 0.001)
[a,avgChng] = smooth(a);
plotIt = a;
plotIt(NV+1,:) = 0; % Increase the number of rows by 1
plotIt(:,NH+1) = 1; % Increase the number of columns by 1
pcolor(0:NH,0:NV,plotIt)
colormap(gray)
colorbar
pause(0.01)
end
When a user types lookfor smooth the following is received:
316
Smooth a 2D array
11.9. PROBLEMS
317
where A, B, C and D are scalars, are given by the procedure below (attributed to
Francois Viete, 1615). You will code this algorithm into a MATLAB function called
cubeRoots.m where A, B, C and D are arrays:
If A = 0 the above is not a cubic equation, it is a quadratic equation. Assume
that there exists a function called quadraticRoots.m somewhere on the MATLAB
path that operates on arrays in the same way that cubicRoots.m does and will
return real roots if they exist and NaNs otherwise. Else,
Dene a, b, c as follows: a = B/A, b = C/A, c = D/A.
Dene Q = (a2 3b)/3, R = (2a3 9ab + 27c)/54.
If R2 > Q3 there are no real roots and so the 3 roots are NaNs. Else,
a/3
3
+ 2
= 2 Q cos
a/3
3
2
= 2 Q cos
a/3
3
x1 = 2 Q cos
x2
x3
where the MATLAB cos(u) and sqrt functions return an array the same dimensions as u but with its elements being the cos and of the elements of
u.)
Some notes:
Your function cubeRoots.m must accept four input arrays, A, B, C and D, all
with identical dimensions. Consequently, you must be careful with your use of
MATLAB operators.
Your function returns three arrays containing either NaNs or roots of the cubic
equation.
Your function must respond sensibly to the MATLAB lookfor and help functions.
To make a variable into a NaN, assign it as follows: root = NaN;
34. Random, Rotated, Really
Write a MATLAB code that executes the following 5-step pseudocode. Each step is
illustrated by a working example.
318
0.4660
0.4186
0.8462
0.5252
0.2026
0.6721
0.8381
0.0196
(c) Rotate the array counter-clockwise. The rst column becomes the last row, the
second column becomes the second-to-last row and so on. Example:
a =
0.2026
0.4660
0.0153
0.6721
0.4186
0.7468
0.8381
0.8462
0.4451
0.0196
0.5252
0.9318
(d) Set to zero any array element that has a greater column index than row index.
Example:
a =
0.2026
0.4660
0.0153
0
0.4186
0.7468
0
0
0.4451
0
0
0
(e) Change the sign of any array element that has a value less than 1/2. Example:
a =
-0.2026
-0.4660
-0.0153
0
-0.4186
0.7468
0
0
-0.4451
0
0
0
11.9. PROBLEMS
319
Returns the smallest absolute dierence that exists between any two array elements.
Returns the indices of the two closest elements.
Responds sensibly to the lookfor and help functions
Note: abs(x) returns the absolute value of all the elements of x.
Heres a working example:
>> lookfor correlate
CORRELATE correlate, finds the smallest difference between two array elements
>> help correlate
CORRELATE correlate, finds the smallest difference between two array elements
Returns the difference and array indices of the two closest elements
Programmer: Alex Bielajew 12/12/00
Problem on Final Exam for Eng101/200, Fall 00
>> A = rand(3,4)
A =
0.9501
0.4860
0.4565
0.4447
0.2311
0.8913
0.0185
0.6154
0.6068
0.7621
0.8214
0.7919
>> [d,i1,j1,i2,j2] = correlate(A)
d =
0.0086
i1 =
2
j1 =
4
i2 =
3
j2 =
1
36. Minesweeper initialization
Consider the MATLAB script M-le started below:
320
11.9. PROBLEMS
1
0
1
-1
321
2
2
4
3
2
-1
-1
-1
>>
37. This problem is a mineeld
Consider the MATLAB script M-le started below:
%LANDMINE landmine: A game of landmine
clear all
echo off
clc
R = input(Number of rows in the grid: );
C = input(Number of columns in the grid: );
pMine = input(Probability that a tile contains a mine: );
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Your part goes here.
% Write your code on the following page(s).
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
showGrid = grid;
showGrid(R+1,:) = -1;
showGrid(:,C+1) = 1;
pcolor(0:C,0:R,showGrid)
header = sprintf(\\fontsize{20}There were %d survivors\n,nSurvived);
title(header)
axis off
322
11.9. PROBLEMS
323
(b) If a player wants to move outside the bounds of the array, then the player
disappears from the game. The penalty for cowardice is severe. (Set that
array element to 0.)
(c) If the array element that the player wants to move to is empty (0), the player
moves there. (The +1 or -1 gets written into the new array element. The old
array element is set to 0.)
(d) If the array element that the player wants to move to is a player of the same
type, then nothing happens.
(e) If the array element that the player wants to move contains an Opposite, then
they ght. Three things can happen, all with equal chance:
i. Mutual destructionboth players perish. (Both array elements get set
to 0.)
ii. The Positive player wins and the Negative player is eliminated from the
game. (The new location gets set to +1 and the old location gets set to
0.)
iii. The Negative player wins and the Positive player is eliminated from the
game. (The new location gets set to -1 and the old location gets set to
0.)
When the while loop ends, there are 3 possible outcomes. Provide a message that
indicates how the game ended and the number of remaining players.
Heres an example of running the code.
>> war
Number of rows in the game: 10
R =
10
Number of columns n the game: 12
C =
12
The game starts with 64 +s and 56 -s
The -s have annihilated the +s. There are 17 -s remaining.
>>
39. Gaussian sum Write a MATLAB function M-le, called gauss(), that is called as
follows:
s = gauss(N) % where N in some integer
Your gauss.m responds to the lookfor and help functions as follows:
324
11.9. PROBLEMS
325
10
12
14
16
18
20
326
11.10. PROJECTS
11.10
327
Projects
T array
the number of rows by 1
the number of columns by 1
Plot it
Increasing the row and columns by 1 is necessary to get MATLAB to show the
walls and the window, otherwise only the interior of the room would show.
(d) Inside a while loop, the i,jth cell gets it value from its neighbors, via an averaging
relation of the form:
T(i,j) = (oldT(i+1,j) + oldT(i-1,j) + oldT(i,j+1) + oldT(i,j-1))/4;
328
Finally, Figure 3 shows a dierent starting position with the ending results shown in
Figure 4. This is a terrible solution! Not only is the variation worse, but the register
is so hot that you would burn yourself if you got close to it!
11.10. PROJECTS
329
60
30
50
25
40
20
30
15
20
10
10
5
10
15
20
25
30
Figure 11.1: Typical starting condition for the 3232 room with a register on the right wall
at T = 65 C.
330
30
60
25
50
20
40
15
30
20
10
10
10
15
20
25
30
Figure 11.2: Final result for a 3232 size room starting with the conguration of Figure 1.
avg
avg
In this case, Tnal
= 21.1514 and Tnal
= 5.39824.
11.10. PROJECTS
331
100
30
90
80
25
70
20
60
50
15
40
30
10
20
5
10
10
15
20
25
30
Figure 11.3: Another starting condition for the 3232 room with a register in one of the
corners at T = 105C.
332
100
30
90
25
80
70
20
60
50
15
40
10
30
20
5
10
10
15
20
25
30
Figure 11.4: Final result for a 3232 size room starting with the conguration of Figure 3.
avg
avg
In this case, Tnal
= 21.1643 and Tnal
= 6.1069.
11.10. PROJECTS
333
1000
30
800
600
25
400
200
20
0
15
200
400
10
600
5
800
10
15
20
25
30
1000
334
= linspace(1000,0,N - 15*N/32);
= linspace(1000,0,N - 15*N/32);
linspace(0,-1000,N - 15*N/32);
linspace(0,-1000,N - 15*N/32);
establish a linear change in the voltage from the electrodes to the upper left and
lower right hand corners, so that these points at the upper left and lower right are
zero. Note the use of the transpose operator in two of the above statements.
(c) If you then type a <RETURN> in the MATLAB command window, the gure on
the previous page is replaced by a shading interp version and a second window
pops up which will be empty. Now you have to start some programming.
(d) Inside the while loop, the i,jth cell gets it value from its neighbors, via a relation
of the form:
V(i,j) = (oldV(i+1,j) + oldV(i-1,j) + oldV(i,j+1) + oldV(i,j-1))/4;
where oldV is the voltage array after the previous pass through the while loop.
You have to program this in the appropriate place in the while loop and you have
to make sure that you do not violate the boundaries of the array. You can use
for loops to do this although it is much more ecient to use slice indexing as
in the determination of the initial conditions above.
(e) In the above averaging procedure, you may have overwritten some of the array
that was meant to be xed by the initial conditions. So, you had better make
sure that you x these up in the appropriate place in the while loop.
(f) The while loop is executed until the voltage array does not change by a signicant
amount. Code to test for this is provided.
11.10. PROJECTS
335
(g) After the voltage array is calculated, you calculate the magnitude of the electric
eld from it. The magnitude of the x-component of the electric eld is obtained
from:
Ex(i,j) = V(i+1,j) - V(i,j);
while the magnitude of the y-component of the electric eld is obtained from:
Ey(i,j) = V(i,j+1) - V(i,j);
The magnitude of the electric eld is obtained from a relation of the form
E(i,j) = sqrt(Ex(i,j)*Ex(i,j) + Ey(i,j)*Ey(i,j));
Be very careful of the array bounds!
(h) Then the magnitude of the electric eld is plotted as provided by the template.
(i) If you get everything correct, the nal results look like:
120
100
80
60
40
20
20
40
60
80
100
120
336
120
100
80
60
40
20
20
40
60
80
100
120
Figure 11.7: Electric eld grid corresponding to the voltage in the previous gure.
11.10. PROJECTS
337
70
68
66
64
62
60
58
56
58
60
62
64
66
68
70
72
Figure 11.8: A zoom in on the previous picture to show the details of the arc. Even on a
ne 128128 grid you can see evidence of the digitization of the grid.
338
N = 32;
% Array size, should be divisible by 32: 32, 64, 96, 128,...
V = zeros(N); % Creates Voltage array and sets its values to 0
% Sets initial values of the V array
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
V(1:15*N/32,1:15*N/32) = 1000;
% High voltage "point"
V(17*N/32+1:N,17*N/32+1:N) = -1000; % Low voltage "point"
% Linear ramps along edges from the high voltage point
V(1,15*N/32+1:N) = linspace(1000,0,N - 15*N/32);
V(15*N/32+1:N,1) = linspace(1000,0,N - 15*N/32);
% Linear ramps along edges from the low voltage point
V(N,1:17*N/32) = linspace(0,-1000,N - 15*N/32);
V(1:17*N/32,N) = linspace(0,-1000,N - 15*N/32);
% Plot the initialized array
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The following lets all the cells of V be printed,
% useful for making sure the array got initialized OK.
% Without this, the Nth row and column of V would not
% be displayed.
% Should NOT do it this way if using shading interp
plotV = V;
% Copy the V array
plotV(N+1,:) = 0; % Increase the number of rows by 1
plotV(:,N+1) = 0; % Increase the number of columns by 1
pcolor(1:N+1,1:N+1,plotV); % Plot it
colorbar;
pause;
tic;
11.10. PROJECTS
339
field
Ex
Ey
E
340
3. Battleship revisited
You will write MATLAB code that will allow you to play the game Battleship! on
your computer. There is only one ship, the size of the ship is 4 units and you only
have 25 bombs. Otherwise the game rules are exactly the same as for the Battleship
program discussed in Chapter 8.
However, you must use graphical output to show the status of the game board (with
the ship hidden) and use the mouse to generate the bomb drops.
Hints:
Initializing the game grid
N = 10;
showBoard = zeros(N); % Make the board, value of zero for "open sea"
For more explanation:
>> help zeros
Drawing the game grid If you have an array called showBoard, here is how to display it:
plotBoard = showBoard; % Makes a copy of showBoard into plotBoard
plotBoard(N + 1,:) = 0; % Boosts number of rows in plotBoard by 1, assigns 0s
plotBoard(:, N + 1) = 0; % Boosts number of columns in plotBoard by 1
figure(1); % Working with figure 1
pcolor(0:N,0:N,plotBoard); % Make the plot
axis off % Turn of axis labeling (may want to leave on during debugging)
11.10. PROJECTS
341
342
4. Swarm ball
This project was inspired by my 7-year-old daughters soccer team, The Muggles. If you
have ever watched a group of 7-year-olds play soccer, it bears very little resemblance to
the game called soccer. It resembles more closely what would should be called swarm
ball.
In swarm ball, the object of the game is to surround the ball with as many of your
5 other teammates as possible, for the chances of moving the ball in the direction of
the opponents goal is proportional to the number of your team surrounding the ball.
Of course, the other team has a similar strategy. So, around the ball is a swarm of
players all kicking at the poor thing. The ball usually blurts out in one direction and
the swarm reassembles around the ball. Goaltenders, while still a part of swarm ball,
are almost completely irrelevant. The ball is always rolling on the ground. Would you
bend down to pick up a soccer ball surrounded by 24 ailing feet? I think not.
So, this projects task is to program a simulation of swarm ball with the following
requirements.
(a) A 2-dimensional array, called field, contains the game, the players, the ball and
the goalposts. The width and length of the eld are dened by:
fieldWidth = 31; % Width of the field
fieldLength = 41; % Length of the field
(b) The following values of the elements of field determine what that point occupies.
Use the following as it gives a sensible rendition when field is plotted using
pcolor:
grass = 0.5; % Grass color
ball = 0.62; % Soccer balls color
red = 0.8; % Reds team color
blue = 0.2; % Blues team color
redGoal = 0.7; % Reds goal color
blueGoal = 0.4; % Blues goal color
boundary = 0; % Field boundary
(c) Dene the eld, the boundaries and the goals as follows:
field = zeros(fieldWidth,fieldLength);
field(2:fieldWidth-1,2:fieldLength-1) = grass;
field(10:22,1) = redGoal;
field(10:22,end) = blueGoal;
(d) Dene the starting position of the game using the following indices:
ballX = 21;
ballY = 16;
11.10. PROJECTS
343
344
11.10. PROJECTS
345
346
vy,0 +
2
vy,0
+ 2Gy0
d = vx,0tight
For example, if we use y0 = 3 (ft), vx,0 = vy,0 = 250/ 2 (ft/s), and G = 32.174
(ft/s/s) we get d = about 1950 feet for the distance! The inputs are realistic and so
we know that air resistance must play a big role. However, knowing that there is an
exact answer in the case of no wind resistance will serve as an important test of our
stepping algorithm described later.
11.10.2
tance
In this case, the equations of motion are dierent because the accelerations are not
constant. In this case they are:
11.10. PROJECTS
347
where D is a measure of the resistance of the air. The total air resistance is proportional
to v 2 and points in the direction opposite to the instantaneous direction of the ball.
The drag factor is related to the physical characteristics of the ball (or projectile) and
has the form:
1
D = CD,ball air Aball /mball
2
where air air is the density of the air, Aball is the cross sectional area of the ball, mball
is the mass of the ball and CD,ball is the drag coecient, a unitless quantity. For
smooth spheres, CD,ball is always very close to 0.5. However, for a baseball its closer
to 0.35 because of the seams. A pitcher can also change CD,ball by adding a little extra
to it (saliva, vaseline) or taking a little away (cutting the ball). Baseballs that are
newly manufactured have a shine that is rubbed o before the start of the game by the
umpires and occasionally by the pitchers. This IS legal. All they are doing is making
the CD,ball a little bit smaller to make the pitches faster.
The D for a major-league baseball can be worked out easily form the above relations.
Use D = 0.0019285 and G = 32.174 for this problem.
11.10.3
2
2
ax,i = Dvx,i1 vx,i1
+ vy,i1
2
2
ay,i = Dvy,i1 vx,i1
+ vy,i1
G
348
11.10. PROJECTS
349
3.5
3
25
2.5
20
1.5
15
1
0.5
10
0
5
0.5
10
15
20
25
30
Figure 11.9: Two chambers and a pipe (evacuated, value = 0) surrounded by walls (solid,
value = -1).
together with a pipe. The ones I made were made up of 2D arrays and look like those
depicted in rst gure. In my example I used chambers that were 30 units high and 10
units wide. The pipe was 16 units high and 10 units wide. (A unit is the width of
350
3.5
3
25
2.5
20
1.5
15
1
0.5
10
0
5
0.5
10
15
20
25
30
11.10. PROJECTS
351
6
30
5
25
4
20
15
10
10
15
20
25
30
Figure 11.11: After 2000 time steps, 73 molecules have stuck to the cold wall in the cold
trap and 27 are still free.
352
8
30
6
25
5
20
4
15
2
10
1
10
15
20
25
30
Figure 11.12: After about 8000 time-steps all the molecules have stuck to the cold wall of
the cold trap.
11.10. PROJECTS
353
You must write a MATLAB script M-le that does the following:
(a) Prompt the user for:
i. Chamber height and width
ii. Connecting pipe height and width.
The pipe height must be less than or equal to the chamber height and greater
than 0.
iii. The number of molecules to simulate.
(b) Display the initial geometry as in rst gure.
(c) Place the molecules in the left chamber and display the initial conguration as in
the second gure.
(d) Execute the time steps until all the molecules stick to the right most wall. Display
the nal conguration as in fourth gure as well as the number of time-steps it
took to do the simulation.
Some hints:
When testing your code, use geometries with just a few cells for height and width
and just a few molecules. This will allow the simulations to complete quickly and
will test the more subtle parts of the code, the wall collisions and the action of
sticking to the cold wall.
When testing your code, make lots of use of visual output. Put in some graphical output for some or all of the time-steps with a pause statement following
the graphics instruction. For example, the third gure shows some intermediate
graphical output. This is a very valuable way of debugging the operation of your
code.
You may need the following MATLAB function in your code (it is not mentioned
in the book!) to place the molecules randomly at the start. Using help uint32:
UINT32 Convert to unsigned 32-bit integer.
I = UINT32(X) converts the elements of the array X into unsigned
32-bit integers. X can be any numeric object (such as a DOUBLE). The
values of a UINT32 range from 0 to 4294967295. Values outside this
range are mapped to 0 or 4294967295. If X is already an unsigned
32-bit integer array, UINT32 has no effect.
.
.
.
See also ...UINT8, UINT16, INT8, INT16, INT32.
354
N
i=j
Gmj (xi xj )
[(xi xj )2 + (yi yj )2 ]3/2
1
Interestingly enough, at the dawn of the 20th century, theoretical physicists actually thought that we
could do this. Then, quantum mechanics came along and things got a lot more uncertain.
11.10. PROJECTS
355
ayi =
N
i=j
Gmj (yi yj )
[(xi xj )2 + (yi yj )2 ]3/2
where G is the gravitational constant (6.673 1011 nt-m2 /kg2 ). Note that the sum
N
i=j excludes the ith object, as an object (being point-like) does not exert any gravitational force on itself.
11.10.5
If we assume that any object feels a constant acceleration over a small time interval, t,
then we may construct a stepping algorithm as described in the following pseudocode:
(a) Start with time t = 0.
At t = 0 the starting conditions:
xi (0), yi (0), vix (0), viy (0) for i = 1, 2, 3 N
are known.
(b) Calculate the acceleration at the start of the step for each particle in the system:
axi (t) =
N
i=j
ayi (t)
N
i=j
(c) Estimate the positions and velocities at the end of the timestep assuming constant
acceleration.
1
xi (t + t) = xi (t) + vx,i (t)t + ax,i(t)(t)2
2
1
yi (t + t) = yi(t) + vy,i (t)t + ay,i (t)(t)2
2
vx,i (t + t) = vx,i(t) + ax,it
vy,i (t + t) = vx,i(t) + ay,i t
(d) Increment the time at the end of the timestep, t = t + t.
(e) If the total time to evolve the universe has been reached, stop. Otherwise go back
to step 2.
There are a few subtleties you will have to think about.
356
Velocities? Work these out for yourself assuming that the heavier partner is
stationary and the fact that the Earth goes around the Sun once per year and
the Moon goes around the Earth once per month. If you want the data on other
planets, do a little research. I found the above numbers by surng the web.
Is my evolution realistic?
Only in the limit that t 0. You will nd that the above equations, the
longer you iterate them will increasingly violate the physical laws of the conservation of energy and momentum. There appears to be no satisfactory solution to
this problem although there are better algorithms than the one presented above.
Discussion of this would take us far beyond the scope of this course.
How do I check that my algorithm is reasonable?
Here are some suggestions:
Set G = 0 and verify that your objects travel in straight lines.
The two-object case has an exact mathematical solution. You can use this
to check your results. Almost every introductory physics book discusses this
solution.
Here is an example of the Earth and Moon executing one orbit around the Sun. In
this case, I used a timestep of 3600 seconds and 365.25 24 timesteps.
11.10. PROJECTS
357
x 10
yaxis (m)
xaxis (m)
10
5
x 10
Figure 11.13: This is the wobble of the center of mass of the Sun.
358
Earths orbit
11
x 10
1.5
yaxis (m)
0.5
0.5
1.5
2
2
1.5
0.5
0.5
xaxis (m)
1.5
2
11
x 10
11.10. PROJECTS
359
10
x 10
7
6.5
yaxis (m)
5.5
4.5
3.5
2.5
1.2
1.25
1.3
1.35
1.4
1.45
xaxis (m)
1.5
1.55
1.6
1.65
11
x 10
Figure 11.15: This is part of the combined orbit of the Earth and the moon.
360
8. Re-Mastermind
You will write MATLAB code, a simpler version of the Mastermind program of Chapter
8, one in which you, the user, try to guess the 4 hidden numbers.
You already know the rules of the game. Only, in the case, to make things simpler, the
uncovered numbers are represented by 0s rather than ?s. (Mixing characters and
numbers in MATLAB is a bit of a pain.)
And, the game continues until you either quit, or win. Pretty simple, huh?
Hints:
How the computer nds the hidden numbers
answer = floor(9*rand(1,4) + 1);
Confused? Try:
>> help rand
>> help floor
How can you input 4 numbers at once?
guess = input(Input your guess (1 <= [a,b,c,d] <= 9), [0,0,0,0] to quit: );
The above line prompts the user for input (See next page.) and the user can type
in the elements of a row vector.
Confused? Try:
>> help input
An example play of the game is on the following page.
11.10. PROJECTS
>> MasterMind
Input your guess
uncovered =
0
0
board =
1
1
Input your guess
uncovered =
0
0
board =
1
1
2
2
Input your guess
uncovered =
0
0
board =
1
1
2
2
3
3
Input your guess
uncovered =
0
0
board =
1
1
2
2
3
3
4
4
Input your guess
uncovered =
0
5
board =
1
1
2
2
3
3
4
4
5
5
Input your guess
uncovered =
0
5
board =
1
1
2
2
3
3
4
4
5
5
6
5
Input your guess
uncovered =
7
5
board =
1
1
2
2
3
3
4
4
5
5
6
5
7
5
ans =
You win!
361
1
1
(1 <= [a,b,c,d] <= 9), [0,0,0,0] to quit: [2,2,2,2]
2
1
1
2
2
(1 <= [a,b,c,d] <= 9), [0,0,0,0] to quit: [3,3,2,3]
2
1
2
2
(1 <=
1
2
3
[a,b,c,d] <= 9), [0,0,0,0] to quit: [4,4,2,4]
1
2
2
2
(1 <=
1
2
3
4
[a,b,c,d] <= 9), [0,0,0,0] to quit: [5,5,2,5]
1
2
2
2
2
(1 <=
1
2
3
4
5
[a,b,c,d] <= 9), [0,0,0,0] to quit: [6,5,2,6]
1
2
2
2
2
2
(1 <=
1
2
3
4
5
6
[a,b,c,d] <= 9), [0,0,0,0] to quit: [7,5,2,6]
1
2
2
2
2
2
2
1
2
3
4
5
6
6
362
11.10. PROJECTS
363
hold on
pcolor(0:Cols,0:Rows,show)
shading flat
plot(...you figure out the arguments...)
It should look like this2 ...
30
25
20
15
10
10
15
20
25
30
35
40
(0
(0
(0
(0
=
=
=
=
no,
no,
no,
no,
1
1
1
1
=
=
=
=
yes)
yes)
yes)
yes)
1
1
1
1
364
30
25
20
15
10
10
15
20
25
30
35
40
11.10. PROJECTS
365
The beams decay (or attenuate) exponentially from the surface with a decay
constant of 15 cm. So, if a surface tile has energy energy value 1, at depth i,
where i represents the depth in centimeters, the value should be exp(-i/15).
Note that the beams should cover the entire extent of the tumor.
(e) If that was the whole story, cancer would be beaten! Unfortunately, radiation
spreads, the tumor does not get a full dose and the healthy tissue can get damaged.
A simple model of this spreading is to repeatedly average the energy value as
follows:
Ai,j = (Ai1,j + Ai+1,j + Ai,j1 + Ai,j+1 )/4
Perform this averaging 5 times (perform the operation on the array and then
repeat the process 4 more times) to produce a result that looks like the following
gure.
30
25
20
15
10
10
15
20
25
30
35
40
Open ended questions. (Optional.) Solve these and collect numerous Nobel prizes for
medicine and physics!
Model a real 3-dimensional person rather than the simple geometry above.
366
Chapter 12
Graphics
12.1
12.1.1
A basic plot
15
x = linspace(-pi,pi,1000);
y = (x.^2).*sin(20*x) + x;
plot(x,y)
pause % Use a "pause" statement to stop
close % Closes the figure
10
15
4
12.1.2
%
%
%
%
%
%
%
%
%
Choose from:
b: blue
g: green
r: red
c: cyan
m: magenta
y: yellow
k: black
w: white
367
368
plot(x,y,b) % blue
10
10
15
4
15
plot(x,y,g) % green
10
10
15
4
15
plot(x,y,r) % red
10
10
15
4
15
plot(x,y,c) % cyan
10
10
15
4
369
15
plot(x,y,m) % magenta
10
10
15
4
15
plot(x,y,y) % yellow
10
10
15
4
15
plot(x,y,k) % black
10
10
15
4
15
plot(x,y,w) % white
% White!!!!!
10
10
15
4
370
12.1.3
Making titles
Plotting white on white is dumb!
15
10
10
15
4
12.1.4
Axis labels
Same boring plot!
15
10
yaxis
% Axis labels
plot(x,y,k)
xlabel(This is the x-axis);
ylabel(\fontsize{16}y-axis)
title(...
\fontsize{20}\it Same boring plot!)
10
15
4
12.1.5
0
This is the xaxis
0.9
% A different 2D example
0.8
0.7
u = linspace(-3, 3, 1000);
v = exp(-u.^2);
plot(u,v)
title(The bell shaped curve)
0.6
0.5
0.4
0.3
0.2
0.1
0
3
371
plot(u,v,k:)
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
3
plot(u,v,g-.)
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
3
plot(u,v,r--)
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
372
plot(u,v,b-)
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
3
s = linspace(0.01, 6, 20);
t = log(gamma(s));
plot(s,t)
title(...
\fontsize{20}The log\Gamma(x) function)
xlabel(\fontsize{20}x)
ylabel(\fontsize{20}y)
12.1.6
%
%
%
%
%
%
%
%
%
%
%
373
plot(s,t,k:.)
4
plot(s,t,g-.o)
4
1
5
plot(s,t,r--x)
4
374
plot(s,t,b-+)
4
plot(s,t,k:*)
4
plot(s,t,g-.S)
4
375
5
plot(s,t,r--d)
4
plot(s,t,b-V)
4
plot(s,t,k:^)
4
376
plot(s,t,g>)
4
plot(s,t,r<)
4
plot(s,t,bp)
4
377
5
plot(s,t,kh)
4
12.1.7
P0
P1
P2
P3
0.8
0.6
0.4
0.2
0
0.2
0.4
0.6
0.8
1
1
0.8
0.6
0.4
0.2
0.2
0.4
0.6
0.8
378
1
0.8
% Another way
hold on % Dont erase when drawing new plot
plot(x,f0,k-)
plot(x,f1,k:)
plot(x,f2,k-.*)
plot(x,f3,k--o)
axis([-1,1,-1,1.1]) %[xmin,xmax,ymin,ymax]
legend(P0,P1,P2,P3)
0.6
0.4
0.2
0
0.2
0.4
0.6
0.8
1
1
0.8
0.6
0.4
0.2
0.2
0.4
0.6
0.8
P0
P1
P2
P3
1
0.8
12.1.8
0.6
0.4
0.2
0
0.2
0.4
0.6
0.8
1
1
0.8
0.6
0.4
0.2
0.2
0.4
0.6
0.8
Subplots
1)
2)
3)
4)
Plot 1
Plot 2
1
1.5
0.5
0.5
0.5
0
1
0.5
0.5
1
1
0.5
Plot 3
0.5
0.5
Plot 4
0.5
0.5
0
0
0.5
0.5
1
0.5
0.5
1
1
0.5
379
12.2
12.2.1
Plot3 plots
35
30
25
20
15
10
5
0
1
0.5
1
0.5
0
0
0.5
0.5
1
12.2.2
Mesh plots
1
% Mesh plots
0.5
[x,y,z] = sphere(30);
mesh(x,y,z)
0.5
1
1
0.5
1
0.5
0
0
0.5
0.5
1
0.5
1
1
0.5
1
0.5
0
0
0.5
0.5
1
380
grid on
0.5
1
1
0.5
1
0.5
0
0
0.5
0.5
1
0.5
1
1
0.5
1
0.5
0
0
0.5
0.5
1
0.5
1
1
0.5
1
0.5
0
0
0.5
0.5
1
12.2.3
381
Axis labelling
0.5
0.5
1
1
0.5
1
0.5
0
0
0.5
0.5
1
xaxis
0.5
0.5
1
1
0.5
1
0.5
0
0
0.5
0.5
1
yaxis
xaxis
This is a mesh plot
% Provide a title
title(\fontsize{20}This is a mesh plot)
0.5
0.5
1
1
0.5
1
0.5
0
0
0.5
yaxis
0.5
1
xaxis
382
12.2.4
meshc
meshz
10
10
8
6
4
2
0
0
2
5
4
6
10
4
2
4
2
0
2
0
2
2
4
2
4
10
8
6
12.2.5
4
2
0
2
[x,y,z] = peaks(30);
surf(x,y,z)
title(\fontsize{20}Example using surf)
4
6
8
3
2
2
0
1
0
2
3
10
8
6
4
2
0
2
4
6
8
3
2
2
0
1
0
2
3
383
10
8
6
4
2
0
2
4
6
8
3
2
2
0
1
0
2
3
12.2.6
10
10
3
2
2
0
1
0
2
3
12.2.7
10
8
6
4
2
0
2
4
6
8
3
2
2
0
1
0
2
3
384
12.2.8
[x,y,z] = peaks(30);
contour(x,y,z,20)
title(\fontsize{20}Example using contour)
3
3
6
2
4
1
2
0
0
1
2
2
4
3
3
12.2.9
contour3(x,y,z,20)
title(\fontsize{20}Example using contour3)
grid off
8
6
4
2
0
2
4
6
3
2
2
0
1
0
2
3
12.2.10
6
2
4
1
2
0
0
1
2
6
3
3
385
6
2
4
1
2
0
0
1
2
6
3
3
12.2.11
1
2
6
3
3
12.2.12
3
1.35
4.69
5.8
2.46
6.91
3.57
1
1.98
0.24
1.35
2.46
0.872
0.24
3.57
2.46
1.98
5.32
2
3
3
4.21
3.1
0.872
386
Chapter 13
Miscellaneous topics
13.1
Pitfall review
13.1.1
This module gives some review on MATLABs implementation of for loops mostly by way
of example.
The general syntax of a for loop is
for k = vectorOrColumnList
% MATLAB statements
end
There are several ways of stepping through the elements of a row vector.
Example (Need vector value but not index):
The most common usage is C++-like syntax
%File: fex1.m
% For loop requiring vector value but not the index
for k = 1:3
fprintf(k = %g\n,k)
end
% Prints
k = 1
k = 2
k = 3
387
388
or
%File: fex1a.m
% For loop requiring vector value but not the index
for k = 1:2:8
fprintf(k = %g\n,k)
end
% Prints
k = 1
k = 3
k = 5
k = 7
or
%File: fex1b.m
% For loop requiring vector value but not the index
for x = 1.0:-0.1:0.0
fprintf(x = %g\n,x)
end
% Prints
x = 1
x = 0.9
x = 0.8
x = 0.7
x = 0.6
x = 0.5
x = 0.4
x = 0.3
x = 0.2
x = 0.1
x = 0
or
%File: fex1c.m
% For loop requiring vector value but not the index
theta = linspace(0,90,3);
for thetai = theta
fprintf(theta = %g\n,thetai)
end
% Prints
389
390
a = [1 2 3
4 5 6];
[rows,columns] = size(a);
fprintf(a is a %g x %g matrix\n,rows,columns)
for b = a
disp(b);
disp(-------)
end
% Prints
a is a 2 x 3 matrix
1
4
------2
5
------3
6
------Note in this example that b is a new column vector on each iteration of the loop.
13.1.2
Review of functions
Some detail is given in Chapter 13 of Austin and Chancogne. However, the denitive reference for this course is given in the Chapter 11 that was handed out and is on the web.
This lecture gives some review on MATLABs implementation of functions mostly by way
of example.
Recall:
The general syntax of the function denition is to have a separate le called functionName.m
that has the following form:
function [out1,out2,...,outN] = functionName(in1,in2,...inM)
%FUNCTIONNAME A brief one line description (optional)
% .
% .
% More description (optional)
% .
% .
% .
391
392
and some examples of its use on a scalar, a vector, a matrix and the element of a matrix:
>> square(2)
ans = 4
>> y = linspace(0,10,11)
y
= 0
1
2
3
>> square(y)
ans = 0
1
4
9
>> x = round(10*rand(4))
x =
5
10
3
2
7
4
6
4
9
3
7
7
>> square(x)
ans = 25
100
4
49
36
16
9
49
9
16
81
49
10
16
25
36
49
64
81
100
2
8
6
1
4
64
36
1
393
%File: squareCube.m
a2 = a.^2;
a3 = a.^3;
and some examples of its use on a scalar, a vector and a matrix:
>> squareCube(2)
ans = 4
>> [u,v] = squareCube(2)
u = 4
v = 8
>> y = linspace(0,10,11)
y
= 0
1
2
3
>> squareCube(y)
ans = 0
1
4
9
>> [u,v] = squareCube(y)
u =
0
1
4
9
v =
0
1
8
27
>> x = round(10*rand(4))
x =
10
9
8
2
8
4
6
5
6
5
0
8
>> squareCube(x)
ans =
100
81
64
4
64
16
36
25
36
25
0
64
>> [u,v] = squareCube(x)
u =
100
81
64
4
64
16
36
25
36
25
0
64
v =
1000
729
512
8
512
64
216
125
216
125
0
512
10
16
25
36
49
64
81
100
16
64
25
125
36
216
49
343
64
512
81
729
100
1000
9
7
2
4
81
49
4
16
81
49
4
16
729
343
8
64
394
a = 64
b = 512
Note that if you want to employ all the outputs, you have to assign them, else only the
rst output is displayed. These functions work on scalars, vectors, matrices and elements of
matrices.
Subordinate functions
Lets rewrite squareCube.m in the following way:
function [a2,a3] = squareCallsCube(a)
%SQUARECALLSCUBE squareCallsCube is a function that .^2s and .^3s its argument
%
% squareCallsCube calls a subordinate function called cube.m
% It can accept scalars, vectors or matrices
%
% ENG101 class example
%File: squareCallsCube.m
a2 = a.^2;
a3 = cube(a);
return
function c = cube(b)
c = b.^3;
squareCallsCube.m works the same way as if you had called squareCube.m. However, the
function cube.m is only known to the function squareCallsCube.m.
>> cube(a)
??? Undefined function or variable cube.
>> help cube
cube.m not found.
>>
13.2
395
One of the most important things to remember is that MATLAB is organized around the
variable type of two-dimensional arrays of doubles. Hence, MATLABs intrinsic functions
are optimized to use this variable type. If you are making use of this aspect of MATLAB,
you are doing things the MATLAB way.
If you are not (and could be), then your application will almost certainly run slower.
For example, lets consider a temperature diusion problem. (Examples of a heat diusion calculation in 1 dimension is given in the example codes ironbarPointJacobi.m and
ironbarGaussSeidel.m. A 2-dimensional example may be found in the example codes
heat.m, heatSlow.m, and heatFast.m) The part of the algorithm that takes all the time is:
for i = 2:N-1
for j = 2:N-1
T(i,j) = 0.25*(oldT(i-1,j) + oldT(i+1,j) + oldT(i,j-1) + oldT(i,j+1));
end
end
Here is a faster solution obtained by using the intrinsic matrix operations of MATLAB. The
essential change is made by converting the for loops to
and changing them to
T(2:N-1,2:N-1) = 0.25* ...
( ...
oldT(1:N-2,2:N-1) + oldT(3:N,2:N-1) + oldT(2:N-1,1:N-2) + oldT(2:N-1,3:N) ...
);
This will be demonstrated in lecture on a related problem. The speedup is highly dependent
on computer architecture. On the laptop the typical speedup is a factor of only about 2 for
a 50 by 50 array of temperature. On a high-end workstation, Ive obtained as high as 30
times faster.
13.3
Selected Applications
13.3.1
Lets consider another trajectory problem that we will solve using the stepping method.
Consider taking an object at some height, y0 and dropping it with zero velocity, v0 = 0.
396
This is a one-dimensional problem and can be solved completely with equations. However,
we will execute a computer solution as a model for solving more complex problems, like
trajectories of baseballs. The air resistance on a baseball is very signicant. If there were no
air resistance, the longest home runs (about 600 feet or so) would travel half a mile!
The acceleration on the object is:
a = Dv 2 G
(13.1)
y(t) = y0 + v0 t +
t
dt
0
dt a[v(t )]
(13.2)
In fact, even if a were dependent on position y and time t we could write a formal solution
as:
t
t
dt
dt a[y(t ), v(t ), t ]
(13.3)
y(t) = y0 + v0 t +
0
But, this is a formal solution only and does not lead to any practical answers, only methods
of attack on this problem.
One such attack on the problem is to divide the integral above over a set of time interval t
and set up an iterative equation as follows.
yi = yi1 + vi1 t +
ti1 +t
t
dt
ti1
(13.4)
ti1
which is still exact. However, if we make the approximation that the acceleration is constant
over the step, that is
ai [y(t), v(t ), t ] ai [y(ti1 ), v(ti1 ), ti1 ]
(13.5)
we get
1
yi yi1 + vi1 t + ai [y(ti1), v(ti1 ), ti1 ]t2
2
and an algorithm that we can program:
1. Set initial conditions y0 , v0 at t = 0.
2. Initialize a counter i = 1.
3. Increment the counter i = i + 1
4. Calculate the acceleration ai [y(ti1 ), v(ti1 ), ti1 ]
5. Take a small step yi = yi1 + vi1 t + 12 ai [y(ti1 ), v(ti1 ), ti1 ]t2
(13.6)
397
(13.7)
At this point, lets simplify the discussion and consider just our problem. If we apply the
above condition to the problem we get
t
1
2Dv
(13.8)
Does this make sense? It does! If there is no drag, D = 0, and we can make t anything we
like! This is because with no drag there is constant acceleration and we dont have to make
the steps small to get an accurate solution! (We have to be careful that we do not violate
our stopping criterion, however. More on this later.)
What if the v is small? In this case we can set t to be large because the drag is not aecting
the motion very much. If D and/or v are large enough such that Dv is large, we had better
use small time steps because drag forces are strongly aecting the trajectory.
How do we know how to set t for our problem? The greater the velocity, the greater care
we have to take by setting smaller time steps. The greatest velocity we can reach with our
problem is called the terminal velocity. This is when the drag force and the acceleration
force exactly balance each other and there is no net acceleration. For free fall with air
resistance, this velocity is
G
vT =
(13.9)
D
For our baseball the terminal velocity is something like 129 ft/s.
398
This is the upper limit of the velocity and so we are conservative by saying that
1
t
2 DG
(13.10)
or t 2.
How much smaller than 2 should you make t? Usually, as small as we can get away with!
If you want the error to be of the order of 1% or less, you should set it to something below
0.02 seconds. At least we have some indication from a simple analysis.
Now we implement the algorithm with MATLAB coding. Here is what the essential working
part of the algorithm would look like:
y = 1000; % Starts at 1000 feet
v = 0
; % with 0 velocity
while (y > 0)
a = D*v^2 - G;
% Acceleration at beginning of step
y = y + v*dT + 0.5*a*dT^2; % Position at end of the step
v = v + a*dT;
% Velocity at end of the step
end
Heres what the complete code would look like. It gives some example of organization and
plotting:
%File: drag.m
clear
echo off
clc
% Clears variables
% Turns off echo
% Clears the screen
G = 32.174;
D = 0.0019285;
dT = 10;
399
end
y = 1000; % Starts at 1000 feet
v = 0
; % with 0 velocity
index = 1; % Index into the counting arrays
Y = y; V = v; T = 0; % Plotting arrays
while (y > 0)
a = D*v^2 - G;
% Acceleration at beginning of step
y = y + v*dT + 0.5*a*dT^2; % Position at end of the step
v = v + a*dT;
% Velocity at end of the step
% Plotting arrays
index = index + 1;
Y(index) = y;
V(index) = v;
T(index) = T(index - 1) + dT;
end
subplot(1,2,1)
zoom on
hold on
plot(T,Y,-)
title(y as a function of t)
xlabel(time (s))
ylabel(height (ft))
subplot(1,2,2)
zoom on
hold on
plot(T,V,-)
title(v as a function of t)
xlabel(time (s))
ylabel(height (ft/s))
fprintf(Final velocity = %g\n,V(end));
end
When we run this code, as demonstrated in class, we see that the trajectory always over-
400
shoots. We always end up with a negative y at the end. We have to make t very small to
get the nal position close to zero. We can x this problem relatively easily.
What we can do is check to see if the t we are about to use will cause an overshoot and if
it will, to truncate it accordingly.
How do we truncate it? Recall that we are assuming that the acceleration over the course
of the step is constant. If that is so, we can calculate the t required to bring it exactly to
zero. It must satisfy the quadratic equation:
1
0 = yi1 + vi1 t + ai [y(ti1 ), v(ti1 ), ti1 ]t2
2
(13.11)
You can solve this with the quadratic equation and convince yourselves that the solution is:
dT = -(v + sqrt(v^2 - 2*y*a))/a;
Here is the new working part of the algorithm incorporating this idea. (See the example
code drag0.m.)
y = 1000; % Starts at 1000 feet
v = 0
; % with 0 velocity
while (y > 0)
a = D*v^2 - G; % Acceleration at beginning of step
yTest = y + v*dT + 0.5*a*dT^2; % Position at end of the step
if yTest < 0
% Handle the overshoot
dT = -(v + sqrt(v^2 - 2*y*a))/a;
y = 0;
else
y = yTest;
end
v = v + a*dT; % Velocity at end of the step
end
So now we have a trajectory that always ends in the right place and an algorithm that is
guaranteed to get us close to the right answer. We are now a long way towards solving more
complicated problems, like two-dimensional trajectories of baseballs.
13.3.2
This is the problem of positive and negative ions created somehow (like a pulse of radiation)
in a gas drifting in opposite directions under the inuence of a constant electric eld. Run
401
the following code called ion.m that resides in the classcodes area. Note how the leading
edge is more populated with ions than the trailing edges since the longer an ion spends in
the vicinity of ions of opposite charge the greater the chance that it will recombine and
neutralize.
%File: ion.m
clear all
echo off
clc
NSteps = 100;
NIon = 2000;
for i = 1:NIon
x1(i) = rand; y1(i) = rand;
x2(i) = rand; y2(i) = rand;
end
plot(x1,y1,b*,x2,y2,r*)
axis([-1 2 0 1])
axis off
title(\fontsize{20}Initial configuration)
pause
for time = 1:NSteps + 3*sqrt(NSteps)
for i = 1:NIon
if (rand < 2/NSteps & x1(i) < 1)
y1(i) = -100;
end
theta = 2*pi*rand;
x1(i) = x1(i) + (1 + cos(theta))*0.5/NSteps;
y1(i) = y1(i) + sin(theta)*0.5/NSteps;
if (rand < 2/NSteps & x2(i) > 0)
y2(i) = -100;
end
theta = 2*pi*rand;
x2(i) = x2(i) - (1 - cos(theta))*0.5/NSteps;
y2(i) = y2(i) + sin(theta)*0.5/NSteps;
end
402
end
13.3.3
Constant electric elds as employed in the problem above are really ctional. In this simulation we mock-up a realistic electric eld situation. Run the following code called phi.m
that resides in the classcodes area. Note how strong the electric eld is near the insulator.
(It helps to have come to class to get the full description of this problem!)
%File: phi.m
clear all
echo off
clc
N = input(Number of cells = N x N. Input N: )
delta = input(Convergence criterion delta: )
V = zeros(N);
V(1,N/2:N) = 1000;
V(N,N/2:N) = 1000;
V(:,N) = 1000;
oldV = V;
change = 10;
tic
counter = 0;
while(change > delta)
V(2:N-1,2:N-1) = ...
0.25*( ...
V(1:N-2,2:N-1) + V(3:N,2:N-1) + V(2:N-1,1:N-2) + V(2:N-1,3:N) ...
);
difference = abs(V - oldV);
403
404
13.4
By now you are conversant in two languages, C++ and MATLAB. You have noted the
dierences between them. C++ is hard to make work properly. It is a powerful, generalpurpose language that runs numerical calculations very fast.
MATLAB is specialized for engineering-type problems. It has lots of engineering-type utility
built in and has very nice plotting capabilities, particularly in 3 dimensions. It is easy to get
an application up and running, but it is relatively slow for large-scale problems.
Not every computer language is suitable for every purpose. Heres how a research scientist
would use both of these computer languages to his or her best advantage.
1. Design a computer algorithm in pseudo-code
2. Convert it to MATLAB
3. Debug the concept of the algorithm using MATLAB
4. Develop graphics output to interpret results
5. Develop a set of test problems that can be completed by MATLAB in a reasonable
time.
6. When the MATLAB version is acceptable, re-code the algorithm in C++ starting with
the MATLAB code.
7. Run the same set of test problems using the C++ code.
8. Make sure that the C++ results and the MATLAB results of test problems are identical.
9. When the C++ code passes the tests, increase array size or introduce sucient complexity to solve the problem you really want to solve.
10. Have C++ write data arrays that MATLAB can read in an display, using MATLABs
excellent graphics capabilities.
11. Publish results!
The upshot is that both ways of doing it has its strengths and weaknesses. Why not use
both?
Chapter 14
Programming Style Guide for C++
This programming style guide is a set of mandatory requirements for C++ code layout. These
stylistic laws are not made for arbitrary reasons. Experience teaches us that conforming to
this style, more or less standard through the industry with few exceptions, makes code easy
to maintain and allows it to be read less painfully by others. This style guide is mandatory
for ENG101, and can only be relaxed under specic instructions from GSIs and Profs.
This style guide is summarized by example:
Indent 3 spaces relative to the preceding for every new nesting level. Curly brackets
must always align vertically. Example,
int main(void)
{
int i = 0, k = 1;
if (i < k)
{ int temp = i;
i = k;
k = temp;
if (0 == k)
{ i = i*i;
k = -i;
}
}
return 0;
}
Variable and function names are in lowercase, terse but descriptive, enough information
conveyed within the programming context, with capital letters to start new words
internal to the identier. Example,
405
406
407
float result = x + y - z; //Good
float result=x+y-z; //Bad
There are no spaces before and after the binary operators *, /, and %. There is no
space following the unary operators - and !. Examples,
float result = x*y + z; //Good
bool decision = ! go; //Bad
No hardwired constants!
Bad example:
int a[10][10];
for (i = 0; i == 9; i = i + 1)
for (j = 0; j == 9; j = j + 1)
a[i][j] = 1;
Good example:
const int SIZE = 10;
int a[SIZE][SIZE];
for (i = 0; i < SIZE; i = i + 1)
for (j = 0; j < SIZE; j = j + 1)
a[i][j] = 1;
Functions should be small enough so that they t on the screen. Thats about 30 lines
of code.
The use of goto, break and continue is disallowed.
Use of non-constant global variables is discouraged.
408
Global variables
Functions, with own headers. Function prototypes are optional unless required by
ordering constraints.
Here is an example of code layout:
409
// HEADER COMMENTS GO AT THE TOP ************************************
/********************************************************************
Copyright (C): University of Michigan
Project:
ENG101/200 - Class example
File:
C++example.cpp
Purpose:
Coding example to show code layout
Compiler:
g++
Programmer:
Alex Bielajew
Start Date:
01/18/01
*********************************************************************/
// INCLUDE statements ***********************************************
#include <iostream>
using namespace std;
// CONSTANTS ********************************************************
// No constants in this example
// GLOBAL VARIABLES *************************************************
// No global variables in this example
// FUNCTIONS ********************************************************
float pow(float x, int n)
/*********************************************************************
Purpose: Calculate the integral power of a float using the algorithm
of al-Kashi
Receives: "x" which is to be raised to the power "n"
Returns: a float, the result of x raised to the power n
*********************************************************************/
{
410
411
int main(void)
/*********************************************************************
Purpose: To prompt the user for a float x and and int n and call a
function that computes x to the power of n
*********************************************************************/
{
412
Chapter 15
Syntax reference for beginning C++
4 Bit Computer Arithmetic
BINARY
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
HEX
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
UNSIGNED
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
SIGNED
0
1
2
3
4
5
6
7
-8
-7
-6
-5
-4
-3
-2
-1
HEX
00000000
00000001
00000002
...
0000000F
00000010
00000011
...
7FFFFFFF
80000000
...
FFFFFFFE
FFFFFFFF
UNSIGNED
0
1
2
...
15
16
17
...
2,147,483,647
2,147,483,648
...
4,294,967,294
4,294,967,295
413
SIGNED
i =
00000000000000000000000000010001
0
~i =
11111111111111111111111111101110
1
2
i
00000000000000000000000000010001
...
+ ~i = + 11111111111111111111111111101110
15
------------------------------------16
11111111111111111111111111111111
17
...
2,147,483,647
-2,147,483,648
...
-2
-1
414
Order of Precedence
OPERATOR
()
* / %
+ < <= > >=
== !=
&&
||
=
ASSOCIATIVITY
left to right
left to right
left to right
left to right
left to right
left to right
left to right
right to left
Logical Expressions
415
If/Else
if(logical expression 1)
STATEMENT BODY 1
}
else if(logical expression 2)
{
may ignore the {}, but for clarity it is better to keep them
STATEMENT BODY 2
}
// more else ifs if needed
else
{
STATEMENT BODY N
Loops
While
If the logical expression is False the rst
while(logical expression)
{
STATEMENT BODY
do
{
STATEMENT BODY
}while(logical expression);
For
for(expression 1; logical expression; expression2)
expression 1 is optional
STATEMENT BODY
expression 2 is optional
Example Programs
CODE
#include<iostream>
OUTPUT
CODE
#include<iostream>
OUTPUT
416
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main(void)
i is 2. j is -2.
{ int i = 2,j = -2;
i is 1. j is -1.
while(j <= i)
{ if(j < 0 )
{ cout << "i is " << i <<". "
<< "j is " << j << ".\n";
i = i - 1;
}
j = j + 1;
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
11
Chapter 16
Syntax reference for more advanced
C++
Addresses
The address of a variable is its location in memorytypically some number from between 0 and 232 1.
The address of a variable is obtained with the unary & operator.
The piece of code {int i; cout << &i << "\n";} should be read as i is declared an int. Print the address of i in hexadecimal
format..
417
418
Function call by value means that the parameter list of the function denition contains values. Example:
float function1(int c, float d){return d/c;} // function definition
x = function1(a, b); // function call
Note: Copies of these values are made available to the function. These are lost when the function returns.
Function call by reference means that the parameter list of the function denition contains addresses. Example:
function2(int& c, float& d){d = d/c;} // function definition
function2(a, b); // function call
Note: Functions called by reference can change the contents of the addresses that are made available to the
function in the reference list.
Vectors
Using vectors
#include <vector> // Must be included in the pre-processor area
Note: Vectors are a class dened in standard C++
Declaring vector<int> vectorName(10); // An int vector called vectorName of size 10;
Note: Vectors are initialized to 0 when they are declared.
Accessing vector elements
for(i = 0; i < 10; i = i + 1){vectorName[i] = i + 1}; // for loop assigns all elements of vectorName
i = vectorName[0]; // i is assigned 1st element of vector vectorName
vectorName[9] = i; // The last (10th) element of vector vectorName is assigned the value of i
Note the o-by-one syntax in the above three examples
Passing vector to functions
double function1(vector<double> b){...} // Typical definition for call-by-value
vector<double> a(10);...;x = function1(a); // Typical call-by-value
double function2(vector<double>& d){...} // Typical definition for call-by-reference
vector<double> c(10);...;x = function2(c); // Typical call-by-reference
Vector class functions
vector<double> a(10);cout << a.size(); // Prints the size of the a vector
vector<float> b(10);b.pop_back(); // Reduces the size of the b vector by one to size 9
vector<int> c(10); int d = 42; c.push_back(d); // Increases the size of the c vector by one to size 11,
// with value of int d in the last vector element
419
int arrayName[2][3] = {0}; // Initialize all the elements of arrayName to zero;
Accessing array elements
// for loops below assign all elements of arrayName
for(i = 0; i < 2; i = i + 1) for(j = 0; j < 3; j = j + 1) arrayName[i][j] = 3*i + j;
i = arrayName[0][2]; // i is assigned 1st row/3rd column
arrayName[1][1] = i; // The last 2nd row/2nd column element of array arrayName is assigned the value of i
Note the o-by-one syntax in the above three examples
Note: arrayName is the address of arrayName[0][0], that is, arrayName is the same as &arrayName[0][0]
Passing 2D arrays to functions Remember that an array name is the address of the start of the array
// Note that column dimension must be specified below
void function(double b[][3], int rowSize, int columnSize){...} // Typical definition
double a[2][3];...;function(a); // Typical call
Note that that the column size (second index) must be known by the function!
Structures
are compound data types. Structures have to be: 1) dened, 2) declared, 3) initialized, 4) used.
Dening a structure
struct AgeAndHeight {int age; float height;}; // Structure tag AgeAndHeight with an int and a float;
Declaring a struct
struct AgeAndHeight Wilma; // Declares Wilma as an AgeAndHeight struct
Declaring and initializing a character
struct AgeAndHeight Wilma = {26,65.5}; // Declares Wilma as an AgeAndHeight struct and initializes it
Referencing struct elements
420
Recursion
Functions can call themselves. Factorial example:
int factorial(int n)
{ if (0 == n) return 1;
else return (n * factorial(n - 1));
}
Chapter 17
Syntax reference for MATLAB
MATLAB Workspace and Variables
The basic variable type in MATLAB is a two-dimensional array of doubles (64-bit representation).
A scalar is a 1 1 array.
A row vector of length N is a 1 N array.
A column vector of length M is an M 1 array.
A matrix of dimensions M rows and M columns is an M N array.
422
423
MATLAB punctuation
. decimal point usage: 325/100, 3.25 and .325e1 are all the same
... three or more decimal points at the end of a line cause
the following line to be a continuation
, comma is used to separate matrix subscripts and arguments
to functions, also used to separate statements in
multi-statement lines
; used inside brackets to indicate the ends of the rows of a
matrix, also used after an expression or statement
to suppress printing
% begins comments
Quote. ANY TEXT is a vector whose components are the
ASCII codes for the characters. A quote within the text is
indicated by two quotes. For example: Dont forget.
Assignment
Individual elements with a row can be delimited by a comma or
a space.
Explicit assignment using ;s to end rows
a = [1,2,3;4,5,6;7,8,9]
Explicit assignment using newline to end rows
a = [1,2,3
4,5,6
7,8,9]
Explicit assignment using continuation lines
b = [1 2 3 4 5 6 ...
7 8 9 10]
424
Vector/Matrix operators
These are Vector and Matrix operators
+
*
/
\
^
addition
subtraction
multiplication
left division
right division
exponentiation
transpose
Point-by-point operators
These operate on matrix elements in point-wise fashion
.*
./
.\
.^
point-wise
point-wise
point-wise
point-wise
multiplication
left division
right division
exponentiation
Logical operators
<
<=
>
less than
less than or equal
greater than
425
>=
==
~=
&
|
~
Script M-les
Sequences of MATLAB commands can be stored in text les with the extension .m. The
commands can be executed by typing the name of the les (without the extension) or through
the le management tools provided by the Command Window menu.
426
%
%
%
%
%
%
%
.
.
.
%
.
.
.
%
.
.
More description (optional)
.
.
.
First executable statement follows this line
Function call
The function call is made with the following statement:
[out1,out2,...,outN] = functionName(in1,in2,...inM)
display a string
write data to screen of le
toggle command echo
display message and abort
prompt for input
transfer control to keyboard
wait for time or user response
return to caller
display warning messages
Performance monitoring
tic,toc
flops
427
Formatting
format
format
format
format
short
long
compact
loose
while loops
while logicalExpression
% MATLAB statements
end
if/elseif/else construct
if logicalExpression1 % Mandatory
% MATLAB statements
elseif logicalExpression2 % Optional
% MATLAB statements
elseif logicalExpression3 % Optional
.
.
.
elseif logicalExpressionN % Optional
% MATLAB statements
else % Optional
% MATLAB statements
end % Mandatory
428
Plotting
contour
contour3
mesh
meshc
meshz
pcolor
plot
plot3
surf
surfc
surfl
Plotting annotation
clabel
colorbar
legend
title
xlabel
ylabel
Index
algorithm
al-Kashis power algorithm, 38, 39
Breakfast, 28
denition, 1, 2328
design, 29, 38, 39
the three pillars of, 26
raising a number to an integral power,
38, 39
roots of the quadratic equation, 29
computer
architecture, 23, 40
owchart, 24
simple branching example, 25
simple looping example, 26
simple sequence example, 24
Gauss, Karl Friedrich 17771855 AD, 35,
44
instruction
branch, 25
conditional, 25
decisions, 25
denition, 23
ow, 24
jump, 25, 26
looping, 25, 26
sequencing, 23
logic
ow, 24
pseudocode, 24
simple branching example, 25
simple looping example, 26
429