Python Programming An Introduction to Computer Science John M.Zelle,Ph.D. Version 1.0rc2 Fall 2002
Python Programming: An Introduction to Computer Science John M. Zelle, Ph.D. Version 1.0rc2 Fall 2002
Copyright (c)2002 by John M.Zelle All rights reserved.No part of this publication may be reproduced,stored in a retrieval system,or transmitted, in any form or by any means,electronic,mechanical,photocopying,recording,or otherwise,without prior written permission of the author. This document was prepared with ITEX 2e and reproduced by Wartburg College Printing Services
Copyright c 2002 by John M. Zelle All rights reserved. No part of this publication may be reproduced,stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without prior written permission of the author. This document was prepared with LATEX 2ε and reproduced by Wartburg College Printing Services
Contents 1 Computers and Programs l.1 The Universal Machine.,·,,,,,,··, 1.2 Program Power.,..,····· l.3 What is Computer Science?....·.·.,·.·······,········· 2 14 Hardware Basics 。。 1.5 Programming Languages 1.6 The Magic of Python J 1.7 Inside a Python Program 1.8 Chaos and Computers.... 10 1.9 Exercises 11 2 Writing Simple Programs 2.1 The Software Development Process 13 2.2 Example Program:Temperature Converter................... 13 2.3 Elements of Programs...... 15 2.3.1 Names.,···· 15 2.3.2 Expressions 15 2.4 Output Statements 6 2.5 Assignment Statements. 7 2.5.1 Simple Assignment.. 1 2.5.2 Assigning Input.. 2.5.3 Simultaneous Assignment 19 2.6 Definite Loops 20 2.7 Example Program:Future Value 28 Exercises 24 3 Computing with Numbers 25 3.1 Numeric Data Types 3.2 Using the Math Library... 27 3.3 Accumulating Results:Factorial 2 3.4 The Limits ofInt 3.5 Handling Large Numbers:Long Ints 3.6 Type Conversions 34 3.7 Exercises 35 4 Computing with Strings 39 4.1 The String Data Type 39 4.2 Simple String Processing 41 4.3 Strings and Secret Codes 43 4.3.1 String Representation.. 43 4.3.2 Programming an Encoder 4.3.3 Programming a Decoder 45 4.3.4 Other String Operations 4
Contents 1 Computers and Programs 1 1.1 The Uni versal Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Program Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 What is Computer Science? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Hardware Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Programming Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6 The Magic of Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.7 Inside a Python Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.8 Chaos and Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Writing Simple Programs 13 2.1 The Software De velopment Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Example Program: Temperature Converter . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Elements of Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Output Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Assignment Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.1 Simple Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.2 Assigning Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5.3 Simultaneous Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Definite Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Example Program: Future Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Computing with Numbers 25 3.1 Numeric Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Using the Math Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 Accumulating Results: Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 The Limits of Int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5 Handling Large Numbers: Long Ints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6 Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4 Computing with Strings 39 4.1 The String Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 Simple String Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3 Strings and Secret Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.1 String Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3.2 Programming an Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3.3 Programming a Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3.4 Other String Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 i
ii CONTENTS 4.3.5 From Encoding to Encryption ................... 48 4.4 Output as String Manipulation....·.,..,·,·,·,,,···· 49 4.4.1 Converting Numbers to Strings................... 49 4.4.2 String Formatting... 50 4.4.3 Better Change Counter 1 4.5 File Processing 5 4.5.1 Multi-Line Strings 52 4.5.2 File Processing. 53 4.5.3 Example Program:Batch Usernames................ 。。,, 55 4.5.4 Coming Attraction:Objects 56 4.6 Exercises 5 5 Objects and Graphics 61 5.1 The Object of Objects.. 61 5.2 Graphics Programming 62 5.3 Using Graphical Objects 64 5.4 Graphing Future Value. 68 5.5 Choosing Coordinates.. 73 5.6 Interactive Graphics.... 75 5.6.1 Getting Mouse Clicks 5.6.2 Handling Textual Input 76 5.7 Graphics Module Reference 5.7.1 GraphWin Objects 79 5.7.2 Graphics Objects 79 5.7.3 Entry Objects. 81 5.7.4 Displaying Images 81 5.7.5 Generating Colors 81 5.8 Exercises 82 6 Defining Functions 85 6.1 The Function of Functions 85 6.2 Functions,Informally...... 86 6.3 Future Value with a Function.. 89 6.4 Functions and Parameters:The Gory Details 90 6.5 Functions that Return Values.. 93 6.6 Functions and Program Structure 95 6.7 Exercises 97 7 Control Structures,Part 1 101 7.1 Simple Decisions..... 101 7.1.1 Example:Temperature Warnings.... 101 7.1.2 Forming Simple Conditions 103 7.l.3 Example::Conditional Program Execution,,.,.,,,、·,,.·, 104 7.2 Two-Way Decisions 105 7.3 Multi-Way Decisions 107 7.4 Exception Handling....... 109 7.5 Study in Design:Max of Three 112 7.5.1 Strategy 1:Compare Each to All 112 7.5.2 Strategy 2:Decision Tree... 113 7.5.3 Strategy 3:Sequential Processing 。。。 114 7.5.4 Strategy4:Use Python.........·...·,·., 116 7.5.5 Some Lessons.。,···· 116 7.6 Exercises 116
ii CONTENTS 4.3.5 From Encoding to Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.4 Output as String Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4.1 Converting Numbers to Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4.2 String Formatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4.3 Better Change Counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5 File Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.5.1 Multi-Line Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.5.2 File Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.5.3 Example Program: Batch Usernames . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.5.4 Coming Attraction: Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5 Objects and Graphics 61 5.1 The Object of Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.2 Graphics Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3 Using Graphical Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.4 Graphing Future Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.5 Choosing Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.6 Interactive Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6.1 Getting Mouse Clicks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6.2 Handling Textual Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.7 Graphics Module Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.7.1 GraphWin Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.7.2 Graphics Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.7.3 Entry Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.7.4 Displaying Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.7.5 Generating Colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6 Defining Functions 85 6.1 The Function of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.2 Functions, Informally . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.3 Future Value with a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.4 Functions and Parameters: The Gory Details . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.5 Functions that Return Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.6 Functions and Program Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7 Control Structures, Part 1 101 7.1 Simple Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.1.1 Example: Temperature Warnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.1.2 Forming Simple Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.1.3 Example: Conditional Program Execution . . . . . . . . . . . . . . . . . . . . . . . 104 7.2 Two-Way Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.3 Multi-Way Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.4 Exception Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 7.5 Study in Design: Max of Three . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 7.5.1 Strategy 1: Compare Each to All . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 7.5.2 Strategy 2: Decision Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.5.3 Strategy 3: Sequential Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.5.4 Strategy 4: Use Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.5.5 Some Lessons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
CONTENTS i道 8 Control Structures,Part 2 119 8.1 For Loops:A Quick Review 119 8.2 Indefinite Loops.... 120 8.3 Common Loop Patterns 121 8.3.1 Interactive Loops 121 8.3.2 Sentinel Loops 123 8.3.3 File Loops 125 8.3.4 Nested Loops 126 8.4 Computing with Booleans 127 8.4.1 Boolean Operators 127 8.4.2 Boolean Algebra 129 8.5 Other Common Structures 130 8.5.1 Post-Test Loop. 130 8.5.2 Loop and a Half 132 8.5.3 Boolean Expressions as Decisions 132 8.6 Exercises 134 9 Simulation and Design 137 9.1 Simulating Racquetball 137 9.1.1 A Simulation Problem 137 9.1.2 Program Specification 138 9.2 Random Numbers,······· 138 9.3 Top-Down Design.. 。。。，, 140 9.3.1 Top-Level Design 140 9.3.2 Separation of Concerns 141 9.3.3 Second-Level Design.. 142 9.3.4 Designing simNGames 143 9.3.5 Third-Level Design... 144 9.3.6 Finishing Up 146 9.3.7 Summary of the Design Process 148 9.4 Bottom-Up Implementation.. 148 9.4.1 Unit Testing.. 148 9 4 2 Simulation results 149 9.5 Other Design Techniques 150 9.5.1 Prototyping and Spiral Development. 150 9.5.2 The Art of Design 151 9.6 Exercises 152 10 Defining Classes 155 10.1 Quick Review of Objects 。。 155 10.2 Example Program:Cannonball 156 10.2.1 Program Specification 156 10.2.2 Designing the Program 156 10.2.3 Modularizing the Program 159 10.3 Defining New Classes. 159 10.3.1 Example:Multi-Sided Dice 160 10.3.2 Example:The Projectile Class 162 10.4 Objects and Encapsulation 164 10.4.1 Encapsulating Useful Abstractions 164 10.4.2 Putting Classes in Modules..... 164 10.5 Widget Objects.. 166 10.5.1 Example Program:Dice Roller....... 166 10.5.2 Building Buttons 166 l0.53 Building Dice.················ 169
CONTENTS iii 8 Control Structures, Part 2 119 8.1 For Loops: A Quick Revie w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.2 Indefinite Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8.3 Common Loop Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.3.1 Interacti v e Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.3.2 Sentinel Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 8.3.3 File Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 8.3.4 Nested Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 8.4 Computing with Booleans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.4.1 Boolean Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 8.4.2 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 8.5 Other Common Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.5.1 Post-Test Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.5.2 Loop and a Half . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.5.3 Boolean Expressions as Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9 Simulation and Design 137 9.1 Simulating Racquetball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9.1.1 A Simulation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9.1.2 Program Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.2 Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.3 Top-Down Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.3.1 Top-Le vel Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.3.2 Separation of Concerns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 9.3.3 Second-Le vel Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 9.3.4 Designing simNGames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 9.3.5 Third-Le vel Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 9.3.6 Finishing Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 9.3.7 Summary of the Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.4 Bottom-Up Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.4.1 Unit Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 9.4.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 9.5 Other Design Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 9.5.1 Prototyping and Spiral De velopment . . . . . . . . . . . . . . . . . . . . . . . . . . 150 9.5.2 The Art of Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 10 Defining Classes 155 10.1 Quick Revie w of Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 10.2 Example Program: Cannonball . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.2.1 Program Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.2.2 Designing the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 10.2.3 Modularizing the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 10.3 Defining Ne w Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 10.3.1 Example: Multi-Sided Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 10.3.2 Example: The Projectile Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 10.4 Objects and Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 10.4.1 Encapsulating Useful Abstractions . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 10.4.2 Putting Classes in Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 10.5 Widget Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 10.5.1 Example Program: Dice Roller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 10.5.2 Building Buttons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 10.5.3 Building Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
iv CONTENTS l0.5.4 The Main Program....,,.,,..,·,,.,.,.,..· 172 10.6 Exercises 173 11 Data Collections 177 ll.1 Example Problem:Simple Statistics,.,,,,,,,···,,,,·····, 177 112 Applying Lists,·············,,···…·· 178 ll2.1 Lists are Sequences,·,,··.··.·.······ 178 11.2.2 Lists vs.Strings..... 179 11.2.3 List Operations 180 11.3 Statistics with Lists 181 11.4 Combining Lists and Classes.. 184 11.5 Case Study:Python Calculator 188 11.5.1 A Calculator as an Object 188 11.5.2 Constructing the Interface 188 11.5.3 Processing Buttons 190 11.6 Non-Sequential Collections 193 11.6.1 Dictionary Basics. 193 11.6.2 Dictionary Operations 194 11.6.3 Example Program:Word Frequency 194 11.7 Exercises 198 12 Object-Oriented Design 201 12.1 The Process of OOD 201 12.2 Case Study:Racquetball Simulation 202 12.2.1 Candidate Objects and Methods 203 12.2.2 Implementing SimStats 203 12.2.3 Implementing RBallGame 205 12.2.4 Implementing Player.. 207 12.2.5 The Complete Program 207 12.3 Case Study:Dice Poker. 210 12.3.1 Program Specification 210 12.3.2 Identifying Candidate Objects 210 12.3.3 Implementing the Model 211 12.3.4 A Text-Based UI 214 12.3.5 Developing a GUI 216 12.4 00 Concepts . 221 12.4.1 Encapsulation.. 221 12.4.2 Polymorphism 222 12.4.3 Inheritance 222 12.5 Exercises 223 13 Algorithm Analysis and Design 225 13.1 Searching 。。。。。。 225 13.1.1 A Simple Searching Problem 225 13.1.2 Strategy 1:Linear Search 226 13.1.3 Strategy 2:Binary Search 226 13.1.4 Comparing Algorithms. 227 13.2 Recursive Problem-Solving... 228 13.2.1 Recursive Definitions.. 229 13.2.2 Recursive Functions.... 230 13.2.3 Recursive Search.... 230 13.3 Sorting Algorithms.. 231 13.3.1 Naive Sorting:Selection Sort 231 l3.3.2 Divide and Conquer:Merge Sort.,,···········,·,·· 232
i v CONTENTS 10.5.4 The Main Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 11 Data Collections 177 11.1 Example Problem: Simple Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 11.2 Applying Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.2.1 Lists are Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.2.2 Lists vs. Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 11.2.3 List Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 11.3 Statistics with Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.4 Combining Lists and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 11.5 Case Study: Python Calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.1 A Calculator as an Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.2 Constructing the Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.3 Processing Buttons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 11.6 Non-Sequential Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 11.6.1 Dictionary Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 11.6.2 Dictionary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 11.6.3 Example Program: Word Frequenc y . . . . . . . . . . . . . . . . . . . . . . . . . . 194 11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 12 Object-Oriented Design 201 12.1 The Process of OOD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 12.2 Case Study: Racquetball Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 12.2.1 Candidate Objects and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.2.2 Implementing SimStats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.2.3 Implementing RBallGame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 12.2.4 Implementing Player . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.2.5 The Complete Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.3 Case Study: Dice Poker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.1 Program Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.2 Identifying Candidate Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.3 Implementing the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 12.3.4 A Text-Based UI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 12.3.5 De veloping a GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 12.4 OO Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 12.4.1 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 12.4.2 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.4.3 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 13 Algorithm Analysis and Design 225 13.1 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 13.1.1 A Simple Searching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 13.1.2 Strategy 1: Linear Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 13.1.3 Strategy 2: Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 13.1.4 Comparing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 13.2 Recursi v e Problem-Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 13.2.1 Recursi v e Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 13.2.2 Recursi v e Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 13.2.3 Recursi v e Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 13.3 Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.3.1 Nai v e Sorting: Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.3.2 Divide and Conquer: Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
CONTENTS 13.3.3 Comparing Sorts 234 l3.4 Hard Problems··················· 235 13.4.1 Towers of Hanoi.. 236 l3.4.2 The Halting Problem.,,,.,..,.·...·.·.·.·.············ 239 l343 Conclusion········· 241
CONTENTS v 13.3.3 Comparing Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 13.4 Hard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 13.4.1 Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 13.4.2 The Halting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 13.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
vi CONTENTS
vi CONTENTS
Chapter 1 Computers and Programs Almost everyone has used a computer at one time or another.Perhaps you have played computer games or used a computer to write a paper or balance your checkbook.Computers are used to predict the weather, design airplanes,make movies,run businesses,perform financial transactions,and control factories. Have you ever stopped to wonder what exactly a computer is?How can one device perform so many different tasks?These basic questions are the starting point for learning about computers and computer programming. 1.1 The Universal Machine A modern computer might be defined as"a machine that stores and manipulates information under the con- trol of a changeable program."There are two key elements to this definition.The first is that computers are devices for manipulating information.This means that we can put information into a computer,and it can transform the information into new,useful forms,and then output or display the information for our interpretation. Computers are not the only machines that manipulate information.When you use a simple calculator to add up a column of numbers,you are entering information(the numbers)and the calculator is processing the information to compute a running sum which is then displayed.Another simple example is a gas pump.As you fill your tank,the pump uses certain inputs:the current price of gas per gallon and signals from a sensor that reads the rate of gas flowing into your car.The pump transforms this input into information about how much gas you took and how much money you owe. We would not consider either the calculator or the gas pump as full-fledged computers,although modern versions of these devices may actually contain embedded computers.They are different from computers in that they are built to perform a single,specific task.This is where the second part of our definition comes into the picture:computers operate under the control of a changeable program.What exactly does this mean? A computer program is a detailed,step-by-step set of instructions telling a computer exactly what to do. If we change the program,then the computer performs a different sequence of actions,and hence,performs a different task.It is this flexibility that allows your PC to be at one moment a word processor,at the next moment a financial planner,and later on,an arcade game.The machine stays the same,but the program controlling the machine changes. Every computer is just a machine for executing(carrying out)programs.There are many different kinds of computers.You might be familiar with Macintoshes and PCs,but there are literally thousands of other kinds of computers both real and theoretical.One of the remarkable discoveries of computer science is the realization that all of these different computers have the same power;with suitable programming,each computer can basically do all the things that any other computer can do.In this sense,the PC that you might have sitting on your desk is really a universal machine.It can do anything you want it to,provided you can describe the task to be accomplished in sufficient detail.Now that's a powerful machine!
Chapter 1 Computers and Programs Almost everyone has used a computer at one time or another. Perhaps you have played computer games or used a computer to write a paper or balance your checkbook. Computers are used to predict the weather, design airplanes, make movies, run businesses, perform financial transactions, and control factories. Have you ever stopped to wonder what exactly a computer is? How can one device perform so many different tasks? These basic questions are the starting point for learning about computers and computer programming. 1.1 The Universal Machine A modern computer might be defined as “a machine that stores and manipulates information under the control of a changeable program.” There are two key elements to this definition. The first is that computers are devices for manipulating information. This means that we can put information into a computer, and it can transform the information into new, useful forms, and then output or display the information for our interpretation. Computers are not the only machines that manipulate information. When you use a simple calculator to add up a column of numbers, you are entering information (the numbers) and the calculator is processing the information to compute a running sum which is then displayed. Another simple example is a gas pump. As you fill your tank, the pump uses certain inputs: the current price of gas per gallon and signals from a sensor that reads the rate of gas flowing into your car. The pump transforms this input into information about how much gas you took and how much money you owe. We would not consider either the calculator or the gas pump as full-fledged computers, although modern versions of these devices may actually contain embedded computers. They are different from computers in that they are built to perform a single, specific task. This is where the second part of our definition comes into the picture: computers operate under the control of a changeable program. What exactly does this mean? A computer program is a detailed, step-by-step set of instructions telling a computer exactly what to do. If we change the program, then the computer performs a different sequence of actions, and hence, performs a different task. It is this flexibility that allows your PC to be at one moment a word processor, at the next moment a financial planner, and later on, an arcade game. The machine stays the same, but the program controlling the machine changes. Every computer is just a machine for executing (carrying out) programs. There are many different kinds of computers. You might be familiar with Macintoshes and PCs, but there are literally thousands of other kinds of computers both real and theoretical. One of the remarkable discoveries of computer science is the realization that all of these different computers have the same power; with suitable programming, each computer can basically do all the things that any other computer can do. In this sense, the PC that you might have sitting on your desk is really a universal machine. It can do anything you want it to, provided you can describe the task to be accomplished in sufficient detail. Now that’s a powerful machine! 1
2 CHAPTER 1.COMPUTERS AND PROGRAMS 1.2 Program Power You have already learned an important lesson of computing:Soffware (programs)rules the hardware(the physical machine).It is the software that determines what any computer can do.Without programs,comput- ers would just be expensive paperweights.The process of creating software is called programming,and that is the main focus of this book. Computer programming is a challenging activity.Good programming requires an ability to see the big picture while paying attention to minute detail.Not everyone has the talent to become a first-class program- mer,just as not everyone has the skills to be a professional athlete.However,virtually anyone can learn how to program computers.With some patience and effort on your part,this book will help you to become a programmer. There are lots of good reasons to learn programming.Programming is a fundamental part of computer science and is,therefore,important to anyone interested in becoming a computer professional.But others can also benefit from the experience.Computers have become a commonplace tool in our society.Understanding the strengths and limitations of this tool requires an understanding of programming.Non-programmers often feel they are slaves of their computers.Programmers,however,are truly the masters.If you want to become a more intelligent user of computers,then this book is for you. Programming can also be loads of fun.It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations.Believe it or not,many people actually write computer programs as a hobby.Programming also develops valuable problem-solving skills,especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know,programmers are in great demand.More than a few liberal arts majors have turned a couple computer programming classes into a lucrative career option.Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition,regardless of your occupation. 1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of computers.A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy.The computer is an important tool in computer science,but it is not itself the object of study. Since a computer can carry out any process that we can describe,the real question is What processes can we describe?Put another way,the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question.The three main ones are design,analysis,and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution.That is. we develop a step-by-step process for achieving the desired result.Computer scientists call this an algorithm. That's a fancy word that basically means"recipe."The design of algorithms is one of the most important facets of computer science.In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable?in the positive.IfI can devise an algorithm,then the problem is solvable.However,failing to find an algorithm does not mean that a problem is unsolvable.It may mean that I'm just not smart enough,or I haven't hit upon the right idea yet.This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically.Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm.Other problems are in- tractable.The algorithms that solve these problems take too long or require too much memory to be of practical value.Analysis of algorithms is an important part of computer science;throughout this book we will touch on some of the fundamental principles.Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis.In such cases,computer scientists rely on experimentation;they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done,experimentation is often needed in order to verify and refine the
2 CHAPTER 1. COMPUTERS AND PROGRAMS 1.2 Program Power You have already learned an important lesson of computing: Software (programs) rules the hardware (the physical machine). It is the software that determines what any computer can do. Without programs, computers would just be expensive paperweights. The process of creating software is called programming, and that is the main focus of this book. Computer programming is a challenging activity. Good programming requires an ability to see the big picture while paying attention to minute detail. Not everyone has the talent to become a first-class programmer, just as not everyone has the skills to be a professional athlete. However, virtually anyone can learn how to program computers. With some patience and effort on your part, this book will help you to become a programmer. There are lots of good reasons to learn programming. Programming is a fundamental part of computer science and is, therefore, important to anyone interested in becoming a computer professional. But others can also benefit from the experience. Computers have become a commonplace tool in our society. Understanding the strengths and limitations of this tool requires an understanding of programming. Non-programmers often feel they are slaves of their computers. Programmers, however, are truly the masters. If you want to become a more intelligent user of computers, then this book is for you. Programming can also be loads of fun. It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations. Believe it or not, many people actually write computer programs as a hobby. Programming also develops valuable problem-solving skills, especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know, programmers are in great demand. More than a few liberal arts majors have turned a couple computer programming classes into a lucrative career option. Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition, regardless of your occupation. 1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of computers. A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy. The computer is an important tool in computer science, but it is not itself the object of study. Since a computer can carry out any process that we can describe, the real question is What processes can we describe? Put another way, the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question. The three main ones are design, analysis, and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution. That is, we develop a step-by-step process for achieving the desired result. Computer scientists call this an algorithm. That’s a fancy word that basically means “recipe.” The design of algorithms is one of the most important facets of computer science. In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable? in the positive. If I can devise an algorithm, then the problem is solvable. However, failing to find an algorithm does not mean that a problem is unsolvable. It may mean that I’m just not smart enough, or I haven’t hit upon the right idea yet. This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically. Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm. Other problems are intractable. The algorithms that solve these problems take too long or require too much memory to be of practical value. Analysis of algorithms is an important part of computer science; throughout this book we will touch on some of the fundamental principles. Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis. In such cases, computer scientists rely on experimentation; they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done, experimentation is often needed in order to verify and refine the