How to think like a computer scientist Allen B. Downey C++ Version, First Edition 2 How to think like a computer scientist C++ Version, First Edition Copyright (C) 1999 Allen B. Downey This book is an Open Source Textbook (OST). Permission is granted to reproduce, store or transmit the text of this book by any means, electrical, mechanical, or biological, in accordance with the terms of the GNU General Public License as published by the Free Software Foundation (version 2). This book is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABIL- ITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. TheoriginalformofthisbookisLaTeXsourcecode. Compiling thisLaTeX source has the effect of generating a device-independent representation of a textbook,whichcanbeconvertedtootherformatsandprinted. Allintermediate representations (including DVI and Postscript), and all printed copies of the textbook are also covered by the GNU General Public License. The LaTeX source for this book, and more information about the Open Source Textbook project, is available from http://www.cs.colby.edu/~downey/ost or by writing to Allen B. Downey, 5850 Mayflower Hill, Waterville, ME 04901. The GNU General Public License is available from www.gnu.org or by writ- ing to the FreeSoftware Foundation, Inc., 59 Temple Place -Suite 330, Boston, MA 02111-1307, USA. ThisbookwastypesetbytheauthorusingLaTeXanddvips,whichareboth free, open-source programs. Contents 1 The way of the program 1 1.1 What is a programming language? . . . . . . . . . . . . . . . . . 1 1.2 What is a program? . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 What is debugging? . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.1 Compile-time errors . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 Run-time errors. . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.3 Logic errors and semantics . . . . . . . . . . . . . . . . . 4 1.3.4 Experimental debugging . . . . . . . . . . . . . . . . . . . 5 1.4 Formal and natural languages . . . . . . . . . . . . . . . . . . . . 5 1.5 The first program . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.6 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Variables and types 11 2.1 More output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5 Outputting variables . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.6 Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.7 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.8 Order of operations . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.9 Operators for characters . . . . . . . . . . . . . . . . . . . . . . . 17 2.10 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Function 21 3.1 Floating-point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Converting from double to int . . . . . . . . . . . . . . . . . . . 22 3.3 Math functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 Adding new functions . . . . . . . . . . . . . . . . . . . . . . . . 24 3.6 Definitions and uses . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.7 Programs with multiple functions . . . . . . . . . . . . . . . . . . 27 3.8 Parameters and arguments . . . . . . . . . . . . . . . . . . . . . 27 i ii CONTENTS 3.9 Parameters and variables are local . . . . . . . . . . . . . . . . . 28 3.10 Functions with multiple parameters. . . . . . . . . . . . . . . . . 29 3.11 Functions with results . . . . . . . . . . . . . . . . . . . . . . . . 30 3.12 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 Conditionals and recursion 31 4.1 The modulus operator . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Conditional execution . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Alternative execution. . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4 Chained conditionals . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.5 Nested conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.6 The return statement . . . . . . . . . . . . . . . . . . . . . . . . 34 4.7 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.8 Infinite recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.9 Stack diagrams for recursive functions . . . . . . . . . . . . . . . 36 4.10 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5 Fruitful functions 39 5.1 Return values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Program development . . . . . . . . . . . . . . . . . . . . . . . . 41 5.3 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.4 Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.5 Boolean values . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.6 Boolean variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.7 Logical operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.8 Bool functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.9 Returning from main . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.10 More recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.11 Leap of faith . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.12 One more example . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.13 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6 Iteration 53 6.1 Multiple assignment . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.3 The while statement . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.4 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.5 Two-dimensional tables . . . . . . . . . . . . . . . . . . . . . . . 58 6.6 Encapsulation and generalization . . . . . . . . . . . . . . . . . . 58 6.7 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 6.8 More encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.9 Local variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.10 More generalization . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 CONTENTS iii 7 Strings and things 65 7.1 Containers for strings . . . . . . . . . . . . . . . . . . . . . . . . 65 7.2 apstring variables . . . . . . . . . . . . . . . . . . . . . . . . . . 66 7.3 Extracting characters from a string . . . . . . . . . . . . . . . . . 66 7.4 Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.5 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7.6 A run-time error . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.7 The find function . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.8 Our own version of find . . . . . . . . . . . . . . . . . . . . . . . 69 7.9 Looping and counting . . . . . . . . . . . . . . . . . . . . . . . . 69 7.10 Increment and decrement operators . . . . . . . . . . . . . . . . . 70 7.11 String concatenation . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.12 apstrings are mutable . . . . . . . . . . . . . . . . . . . . . . . . 72 7.13 apstrings are comparable . . . . . . . . . . . . . . . . . . . . . . 72 7.14 Character classification. . . . . . . . . . . . . . . . . . . . . . . . 73 7.15 Other apstring functions . . . . . . . . . . . . . . . . . . . . . . 73 7.16 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 8 Structures 75 8.1 Compound values . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.2 Point objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.3 Accessing instance variables . . . . . . . . . . . . . . . . . . . . . 76 8.4 Operations on structures . . . . . . . . . . . . . . . . . . . . . . . 77 8.5 Structures as parameters . . . . . . . . . . . . . . . . . . . . . . . 78 8.6 Call by value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 8.7 Call by reference . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.8 Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8.9 Structures as return types . . . . . . . . . . . . . . . . . . . . . . 82 8.10 Passing other types by reference . . . . . . . . . . . . . . . . . . 82 8.11 Getting user input . . . . . . . . . . . . . . . . . . . . . . . . . . 83 8.12 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 9 More structures 87 9.1 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 9.2 printTime. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 9.3 Functions for objects . . . . . . . . . . . . . . . . . . . . . . . . . 88 9.4 Pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 9.5 const parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 9.6 Modifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 9.7 Fill-in functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 9.8 Which is best? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 9.9 Incremental development versus planning . . . . . . . . . . . . . 92 9.10 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 9.11 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 9.12 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 iv CONTENTS 10 Vectors 97 10.1 Accessing elements . . . . . . . . . . . . . . . . . . . . . . . . . . 98 10.2 Copying vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 10.3 for loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 10.4 Vector length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 10.5 Random numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 10.6 Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 10.7 Vector of random numbers . . . . . . . . . . . . . . . . . . . . . . 102 10.8 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 10.9 Checking the other values . . . . . . . . . . . . . . . . . . . . . . 104 10.10A histogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 10.11A single-pass solution . . . . . . . . . . . . . . . . . . . . . . . . 105 10.12Random seeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 10.13Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 11 Member functions 109 11.1 Objects and functions . . . . . . . . . . . . . . . . . . . . . . . . 109 11.2 print . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 11.3 Implicit variable access . . . . . . . . . . . . . . . . . . . . . . . . 111 11.4 Another example . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 11.5 Yet another example . . . . . . . . . . . . . . . . . . . . . . . . . 113 11.6 A more complicated example . . . . . . . . . . . . . . . . . . . . 113 11.7 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 11.8 Initialize or construct? . . . . . . . . . . . . . . . . . . . . . . . . 115 11.9 One last example . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 11.10Header files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 11.11Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 12 Vectors of Objects 121 12.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 12.2 Card objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 12.3 The printCard function . . . . . . . . . . . . . . . . . . . . . . . 123 12.4 The equals function . . . . . . . . . . . . . . . . . . . . . . . . . 125 12.5 The isGreater function . . . . . . . . . . . . . . . . . . . . . . . 126 12.6 Vectors of cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 12.7 The printDeck function . . . . . . . . . . . . . . . . . . . . . . . 129 12.8 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 12.9 Bisection search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 12.10Decks and subdecks . . . . . . . . . . . . . . . . . . . . . . . . . 133 12.11Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 13 Objects of Vectors 135 13.1 Enumerated types . . . . . . . . . . . . . . . . . . . . . . . . . . 135 13.2 switch statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 13.3 Decks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 13.4 Another constructor . . . . . . . . . . . . . . . . . . . . . . . . . 139 CONTENTS v 13.5 Deck member functions . . . . . . . . . . . . . . . . . . . . . . . 139 13.6 Shuffling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 13.7 Sorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 13.8 Subdecks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 13.9 Shuffling and dealing . . . . . . . . . . . . . . . . . . . . . . . . . 143 13.10Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 13.11Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 14 Classes and invariants 147 14.1 Private data and classes . . . . . . . . . . . . . . . . . . . . . . . 147 14.2 What is a class? . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 14.3 Complex numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 149 14.4 Accessor functions . . . . . . . . . . . . . . . . . . . . . . . . . . 151 14.5 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 14.6 A function on Complex numbers . . . . . . . . . . . . . . . . . . 153 14.7 Another function on Complex numbers . . . . . . . . . . . . . . . 153 14.8 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 14.9 Preconditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 14.10Private functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 14.11Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 15 File Input/Output and apmatrixes 159 15.1 Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 15.2 File input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 15.3 File output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 15.4 Parsing input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 15.5 Parsing numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 15.6 The Set data structure. . . . . . . . . . . . . . . . . . . . . . . . 164 15.7 apmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 15.8 A distance matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 168 15.9 A proper distance matrix . . . . . . . . . . . . . . . . . . . . . . 169 15.10Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 A Quick reference for AP classes 173 A.1 apstring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 A.2 apvector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 A.3 apmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 vi CONTENTS Chapter 1 The way of the program The goal of this book is to teach you to think like a computer scientist. I like the way computer scientists think because they combine some of the best fea- tures of Mathematics, Engineering, and Natural Science. Like mathematicians, computer scientists use formal languages to denote ideas (specifically computa- tions). Like engineers, they design things, assembling components into systems and evaluating tradeoffs among alternatives. Like scientists, they observe the behavior of complex systems, form hypotheses, and test predictions. Thesinglemostimportantskillforacomputerscientistisproblem-solving. By that I mean the ability to formulate problems, think creatively about solu- tions,andexpressasolutionclearlyandaccurately. Asitturnsout,theprocess of learning to program is an excellent opportunity to practice problem-solving skills. That’s why this chapter is called “The way of the program.” Of course, the other goal of this book is to prepare you for the Computer Science AP Exam. We may not take the most direct approach to that goal, though. Forexample, therearenotmanyexercisesinthisbookthataresimilar to the AP questions. On the other hand, if you understand the concepts in this book,alongwiththedetailsofprogramminginC++,youwillhaveallthetools you need to do well on the exam. 1.1 What is a programming language? The programming language you will be learning is C++, because that is the language the AP exam is based on, as of 1998. Before that, the exam used Pascal. Both C++ and Pascal are high-level languages; other high-level languages you might have heard of are Java, C and FORTRAN. As you might infer from the name “high-level language,” there are also low-level languages, sometimes referred to as machine language or assembly language. Loosely-speaking, computers can only execute programs written in low-level languages. Thus, programs written in a high-level language have to be translated before they can run. This translation takes some time, which is a 1 2 CHAPTER 1. THE WAY OF THE PROGRAM small disadvantage of high-level languages. But the advantages are enormous. First, it is much easier to program in a high-level language; by “easier” I mean that the program takes less time to write,it’sshorterandeasiertoread,andit’smorelikelytobecorrect. Secondly, high-levellanguagesareportable,meaningthattheycanrunondifferentkinds ofcomputerswithfewornomodifications. Low-levelprogramscanonlyrunon one kind of computer, and have to be rewritten to run on another. Due to these advantages, almost all programs are written in high-level lan- guages. Low-level languages are only used for a few special applications. There are two ways to translate a program; interpreting or compiling. An interpreter is a program that reads a high-level program and does what it says. In effect, it translates the program line-by-line, alternately reading lines and carrying out commands. source code interpreter The interpreter ... and the result reads the appears on source code... the screen. Acompilerisaprogramthatreadsahigh-levelprogramandtranslatesitall atonce,beforeexecutinganyofthecommands. Oftenyoucompiletheprogram as a separate step, and then execute the compiled code later. In this case, the high-level program is called the source code, and the translated program is called the object code or the executable. As an example, suppose you write a program in C++. You might use a text editor to write the program (a text editor is a simple word processor). When the program is finished, you might save it in a file named program.cpp, where “program” is an arbitrary name you make up, and the suffix .cpp is a convention that indicates that the file contains C++ source code. Then, dependingonwhat yourprogramming environment islike, youmight leavethetexteditorandrunthecompiler. Thecompilerwouldreadyoursource code, translate it, and create a new file named program.o to contain the object code, or program.exe to contain the executable.