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