PYTHON PROGRAMMING: AN INTRODUCTION TO COMPUTER SCIENCE JOHN ZELLE FRANKLIN,BEEDLE ASSOCIATES
PYTHON programming: AN INTRODUCTION TO COMPUTER SCIENCE JOHN ZELLE FRANKLIN, BEEDLE &, ASSOCIATES
PYTHON PROGRAMMING AN INTRODUCTION TO COMPUTER SCIENCE 出 John M.Zelle Wartburg College Franklin,Beedle Associates,Inc.+8536 SW St.Helens Drive,Suite D+Wilsonville,Oregon 97070+503/682-7668 www.fbeedle.com
PYTHON PROGRAMMING AN INTRODUCTION TO COMPUTER SCIENCE ^ JohnM.Zelle Wartburg College Franklin, Beedle &i Associates, Inc. + 8536 SW St. Helens Drive, Suite D + Wilsonville, Oregon 97070 + 503/682-7668 www.fbeedle.com
President and Publisher Jim Leisy (jimleisy@fbeedle.com) Production TomSumner Dean Lake Cover Ian Shadburne Marketing Christine Collier Order Processing Krista Brown Printed in the U.S.A. Names of all products herein are used for identification purposes only and are trade- marks and/or registered trademarks of their respective owners.Franklin,Beedle Asso- ciates,Inc.,makes no claim of ownership or corporate association with the products or companies that own them. 2004 Franklin,Beedle Associates Incorporated.No part of this book may be repro- duced,stored in a retrieval system,transmitted,or transcribed,in any form or by any means-electronic,mechanical,telepathic,photocopying,recording,or otherwise-with- out prior written permission of the publisher.Requests for permission should be ad- dressed as follows: Rights and Permissions Franklin,Beedle Associates,Incorporated 8536 SW St.Helens Drive,Suite D Wilsonville,Oregon 97070 Library of Congress Cataloging-in-Publication data may be obtained from the publisher
President and Publisher Jim Leisy (jimleisy@fbeedle.com) Production TomSumner Dean Lake Cover Ian Shadburne Marketing Christine Collier Order Processing Krista Brown Printed in the U.S.A. Names of all products herein are used for identification purposes only and are trade- marks and/or registered trademarks of their respective owners. Franklin, Beedle & Associates, Inc., makes no claim of ownership or corporate association with the products or companies that own them. ©2004 Franklin, Beedle & Associates Incorporated. No part of this book may be repro- duced, stored in a retrieval system, transmitted, or transcribed, in any form or by any means—electronic, mechanical, telepathic, photocopying, recording, or otherwise—without prior written permission of the publisher. Requests for permission should be addressed as follows: Rights and Permissions Franklin, Beedle & Associates, Incorporated 8536 SW St. Helens Drive, Suite D Wilsonville, Oregon 97070 Library of Congress Cataloging-in-Publication data may be obtained from the publisher
Contents Foreword .X preface X Chapter 1 Computers and Programs 1 1.1 The Universal Machine................. 1.2 Program Power.… 1 3 1.3 What is Computer Science?............. 3 1.4 Hardware Basics… 5 1.5 Programming Languages 6 1.6 The Magic of Python............. 9 1.7 Inside a Python Program.......... 14 1.8 Chaos and Computers 17 1.9 Chapter Summary.… 18 1.10 Exercises.… 20 Chapter 2 Writing Simple Programs 25 2.1 The Software Development Process.......... 25 2.2 Example Program:Temperature Converter 26 2.3 Elements of Programs.......... .29 2.3.1 Names… 29 2.3.2 Expressions 30 2.4 Output Statements… 31 2.5 Assignment Statements. 33 2.5.1 Simple Assignment.. 33 2.5.2 Assigning Input... 5 2.5.3 Simultaneous Assignment 3 2.6 Definite Loops.......... 9 2.7 Example Program:Future Value 42
Contents Foreword ix Preface x Chapter 1 Computers and Programs 1 1.1 The Universal Machine 1 1.2 Program Power 3 1.3 What is Computer Science? 3 1.4 Hardware Basics 5 1.5 Programming Languages 6 1.6 The Magic of Python 9 1.7 Inside a Python Program 14 1.8 Chaos and Computers 17 1.9 Chapter Summary 18 1.10 Exercises 20 Chapter 2 Writing Simple Programs 25 2.1 The Software Development Process 25 2.2 Example Program: Temperature Converter 26 2.3 Elements of Programs 29 2.3.1 Names 29 2.3.2 Expressions 30 2.4 Output Statements 31 2.5 Assignment Statements 33 2.5.1 Simple Assignment 33 2.5.2 Assigning Input 35 2.5.3 Simultaneous Assignment 36 2.6 Definite Loops 39 2.7 Example Program: Future Value 42
Contents 2.8 Chapter Summary .45 2.9 Exercises .46 Chapter 3 Computing with Numbers 51 3.1 Numeric Data Types.... 51 3.2 Using the Math Library… .55 3.3 Accumulating Results:Factorial....... 58 3.4 The Limits of Int......... 61 3.5 Handling Large Numbers:Long Ints... 64 3.6 Type Conversions... 66 3.7 Chapter Summary 68 3.8 Exercises.… 69 Chapter 4 Computing with Strings 77 4.1 The String Data Type......... 77 4.2 Simple String Processing...... 82 4.3 Strings,Lists,and Sequences. 85 4.4 Strings and Secret Codes.. 87 4.4.1 String Representation.. 87 4.4.2 Programming an Encoder 89 4.4.3 Programming a Decoder........ 90 4.4.4 Other String Operations..... 94 4.4.5 From Encoding to Encryption............ 95 4.5 Input/Output as String Manipulation. 4.5.1 Example Application:Date Conversion 97 4.5.2 String F0 matting… 102 4.5.3 Better Change Counter. 104 4.6 File Processing.. 106 4.6.1 Multi-Line Strings.............. 106 4.6.2 File Processing........ 107 4.6.3 Example Program:Batch Usernames........ 111 4.6.4 Coming Attraction:Objects............. 112 4.7 Chapter Summary............. .113 4.8 Exercises 115 Chapter 5 Objects and Graphics 123 5.1 Overview 123 5.2 The Object of Objects................ 124 5.3 Simple Graphics Programming............ 125 5.4 Using Graphical Objects............ 129 5.5 Graphing Future Value......... 135 5.6 Choosing Coordinates.......... 143 5.7 Interactive Graphics.................. 146 5.7.1 Getting Mouse Clicks....... 146 5.7.2 Handling Textual Input..... 148
iv Contents 2.8 Chapter Summary 45 2.9 Exercises 46 Chapter 3 Computing with Numbers 51 3.1 Numeric Data Types 51 3.2 Using the Math Library 55 3.3 Accumulating Results: Factorial 58 3.4 The Limits of Int 61 3.5 Handling Large Numbers: Long Ints 64 3.6 Type Conversions 66 3.7 Chapter Summary 68 3.8 Exercises 69 Chapter 4 Computing with Strings 77 4.1 The String Data Type 77 4.2 Simple String Processing 82 4.3 Strings, Lists, and Sequences 85 4.4 Strings and Secret Codes 87 4.4.1 String Representation 87 4.4.2 Programming an Encoder 89 4.4.3 Programming a Decoder 90 4.4.4 Other String Operations 94 4.4.5 From Encoding to Encryption 95 4.5 Input/Output as String Manipulation 97 4.5.1 Example Application: Date Conversion 97 4.5.2 String Formatting 102 4.5.3 Better Change Counter 104 4.6 File Processing 106 4.6.1 Multi-Line Strings 106 4.6.2 File Processing 107 4.6.3 Example Program: Batch Usernames Ill 4.6.4 Coming Attraction: Objects 112 4.7 Chapter Summary 113 4.8 Exercises 115 Chapter 5 Objects and Graphics 123 5.1 Overview 123 5.2 The Object of Objects 124 5.3 Simple Graphics Programming 125 5.4 Using Graphical Objects 129 5.5 Graphing Future Value 135 5.6 Choosing Coordinates 143 5.7 I nteractive Gra phics 146 5.7.1 Getting Mouse Clicks 146 5.7.2 Handling Textual Input 148
Contents 5.8 Graphics Module Reference............... 151 5.8.1 GraphWin Objects 151 5.8.2 Graphics Objects 152 5.8.3 Entry Objects.... 155 5.8.4 Displaying Images 155 5.8.5 Generating Colors 156 5.9 Chapter Summary… 156 5.10 Exercises......… 157 Chapter 6 Defining Functions 165 6.1 The Function of Functions 165 6.2 Functions,Informally 167 6.3 Future Value with a Function. 171 6.4 Functions and Parameters:The Details.............. 173 6.5 Getting Results from a Function.. 177 6.5.1 Functions That Return Values. 177 6.5.2 Functions that Modify Parameters........ 181 6.6 Functions and Program Structure. 187 6.7 Chapter Summary.… 191 6.8 Exercises... “444+44+ 191 Chapter 7 Decision Structures 199 7.1 Simple Decisions.… 199 7.1.1 Example:Temperature Warnings... 200 7.1.2 Forming Simple Conditions................ 202 7.1.3 Example:Conditional Program Execution 204 7.2 Tw0-Way Decisic0nS… 206 7.3 Multi--Way Decisions… 210 7.4 Exception Handling......... 213 7.5 Study in Design:Max of Three............... 217 7.5.1 Strategy 1:Compare Each to All.... 218 7.5.2 Strategy 2:Decision Tree........... 220 7.5.3 Strategy 3:Sequential Processing 221 7.5.4 Strategy 4:Use Python........ 223 7.5.5 Some Lessons............ 44444 224 7.6 Chapter Summary… 225 7.7 Exercises..... 225 Chapter 8 Loop Structures and Booleans 233 8.1 For Loops:A Quick Review............... 233 8.2 Indefinite Loops............ 235 8.3 Common Loop Patterns 237 8.3.1 Interactive Loops 237 8.3.2 Sentinel Loops… 239 8.3.3 File Loops..... 242
Contents 5.8 Graphics Module Reference 151 5.8.1 GraphWin Objects 151 5.8.2 Graphics Objects 152 5.8.3 Entry Objects 155 5.8.4 Displaying Images 155 5.8.5 Generating Colors 156 5.9 Chapter Summary 156 5.10 Exercises 157 Chapter 6 Defining Functions 165 6.1 The Function of Functions 165 6.2 Functions, Informally 167 6.3 Future Value with a Function 171 6.4 Functions and Parameters: The Details 173 6.5 Getting Results from a Function 177 6.5.1 Functions That Return Values 177 6.5.2 Functions that Modify Parameters 181 6.6 Functions and Program Structure 187 6.7 Chapter Summary 191 6.8 Exercises 191 Chapter 7 Decision Structures 199 7.1 Simple Decisions 199 7.1.1 Example: Temperature Warnings 200 7.1.2 Forming Simple Conditions 202 7.1.3 Example: Conditional Program Execution 204 7.2 Two-Way Decisions 206 7.3 Multi-Way Decisions 210 7.4 Exception Handling 213 7.5 Study in Design: Max of Three 217 7.5.1 Strategy 1: Compare Each to All 218 7.5.2 Strategy 2: Decision Tree 220 7.5.3 Strategy 3: Sequential Processing 221 7.5.4 Strategy 4: Use Python 223 7.5.5 Some Lessons 224 7.6 Chapter Summary 225 7.7 Exercises 225 Chapter 8 Loop Structures and Booleans 233 8.1 For Loops: A Quick Review 233 8.2 Indefinite Loops 235 8.3 Common Loop Patterns 237 8.3.1 Interactive Loops 237 8.3.2 Sentinel Loops 239 8.3.3 File Loops 242
VI Contents 8.3.4 Nested Loops… 244 8.4 Computing with Booleans......... 246 84.1 Boolean Operators 246 8.4.2 B00 lean Algebra3… 250 8.5 Other Common Structures. 251 8.5.1P0st-Test L00p… 251 8.5.2 Loop and a Half.… 254 8.5.3 Boolean Expressions as Decisions..... 254 8.6 Chapter Summary… 258 8.7 Exercises..… 259 Chapter 9 Simulation and Design 265 9.1 Simulating Racquetball......................... 265 9.1.1 A Simulation Problem.......... 266 9.1.2 Analysis and Specification........... 266 9.2 PseudoRandom Numbers........ 268 9.3 Top-Down Design.................. 270 9.2.1 Top-Level Design.......... 271 9.2.2 Separation of Concerns 273 9.2.3 Second-Level Design................ 273 9.2.4 Designing simNGames… 275 92.5 Third--Level Design… 277 9.2.6 Finishing Up.......... 280 9.2.7 Summary of the Design Process 282 9.4 Bottom-Up Implementation ............... 283 9.4.1 Unit Testing........... 283 9.4.2 Simulation Results 285 9.5 Other Design Techniques.. 286 9.5.1 Prototyping and Spiral Development 286 9.5.2 The Art of Design............... 288 9.6 Chapter Summary… 288 9.7 Exercises5.… 289 Chapter 10 Defining Classes 295 10.1 Quick Review of Objects.......... 295 10.2 Example Program:Cannonball......... 296 10.2.1 Program Specification.......... 296 10.2.2 Designing the Program 297 10.2.3 Modularizing the Program.... 301 10.3 Defining New Classes............ 303 10.3.1 Example:Multi-Sided Dice... 303 10.3.2 Example:The Projectile Class... 307 10.4 Data Processing with Class........ 309 10.5 Objects and Encapsulation ... 313 10.5.1 Encapsulating Useful Abstractions 44 313 10.5.2 Putting Classes in Modules... 315
vi Contents 8.3.4 Nested Loops 244 8.4 Computing with Booleans 246 8.4.1 Boolean Operators 246 8.4.2 Boolean Algebra 250 8.5 Other Common Structures 251 8.5.1 Post-Test Loop 251 8.5.2 Loop and a Half 254 8.5.3 Boolean Expressions as Decisions 254 8.6 Chapter Summary 258 8.7 Exercises 259 Chapter 9 Simulation and Design 265 9.1 Simulating Racquetball 265 9.1.1 A Simulation Problem 266 9.1.2 Analysis and Specification 266 9.2 PseudoRandom Numbers 268 9.3 Top-Down Design 270 9.2.1 Top-Level Design 271 9.2.2 Separation of Concerns 273 9.2.3 Second-Level Design 273 9.2.4 Designing simNGames 275 9.2.5 Third-Level Design 277 9.2.6 Finishing Up 280 9.2.7 Summary of the Design Process 282 9.4 Bottom-Up Implementation 283 9.4.1 Unit Testing 283 9.4.2 Simulation Results 285 9.5 Other Design Techniques 286 9.5.1 Prototyping and Spiral Development 286 9.5.2 The Art of Design 288 9.6 Chapter Summary 288 9.7 Exercises 289 Chapter 10 Defining Classes 295 10.1 Quick Review of Objects 295 10.2 Example Program: Cannonball 296 10.2.1 Program Specification 296 10.2.2 Designing the Program 297 10.2.3 Modularizing the Program 301 10.3 Defining New Classes 303 10.3.1 Example: Multi-Sided Dice 303 10.3.2 Example: The Projectile Class 307 10.4 Data Processing with Class 309 10.5 Objects and Encapsulation 313 10.5.1 Encapsulating Useful Abstractions 313 10.5.2 Putting Classes in Modules 315
Contents 10.5.3 Module Documentation ........... 315 10.5.4 Working with Multiple Modules 317 10.6 Widgets 318 10.6.1 Example Program:Dice Roller 319 10.6.2 Building Buttons.… 319 10.6.3 Building Dice..... 323 10.6.4 The Main Program 327 10.7 Chapter Summary ........... 328 10.8 Exercises.… 329 Chapter 11 Data Collections 337 11.1 Example Problem:Simple Statistics 337 11.2 Applying Lists… 339 11.2.1 Lists and Arrays 340 11.2.2 List Operations.... 341 11.2.3 Statistics with Lists. 345 11.3 Lists of Objects… 350 11.4 Designing with Lists and Classes................. 353 11.5 Case Study:Python Calculator....... 359 11.5.1 A Calculator as an Object............ 359 11.5.2 Constructing the Interface....... 360 11.5.3 Processing Buttons............. 363 11.6 Non-Sequential Collections 367 11.6.1 Dictionary Basics.................. 367 11.6.2 Dictionary Operations 368 11.6.3 Example Program:Word Frequency 370 11.7 Chapter Summary.… 375 11.8 Exercises........ 376 Chapter 12 Object-Oriented Design 385 12.1 The Proces55 of OOD.… 385 12.2 Case Study:Racquetball Simulation 388 12.2.1 Candidate Objects and Methods 388 12.2.2 Implementing SimStats......... 390 12.2.3 Implementing RBallGame..... 392 12.2.4 Implementing Player........... 44 395 12.2.5 The Complete Program .......... 396 12.3 Case Study:Dice Poker........... 399 12.3.1 Program Specification............ 399 12.3.2 Identifying Candidate Objects 400 12.3.3 Implementing the Model......... 402 12.3.4 A Text-Based Ul................ 406 12.3.5 Developing a GUl 409 12.4 00 Concepts... 417 12.4.1 Encapsulation.... 418 12.4.2 Polymorphism 418
Contents vii 10.5.3 Module Documentation 315 10.5.4 Working with Multiple Modules 317 10.6 Widgets 318 10.6.1 Example Program: Dice Roller 319 10.6.2 Building Buttons 319 10.6.3 Building Dice 323 10.6.4 The Main Program 327 10.7 Chapter Summary 328 10.8 Exercises 329 Chapter 11 Data Collections 337 11.1 Example Problem: Simple Statistics 337 11.2 Applying Lists 339 11.2.1 Lists and Arrays 340 11.2.2 List Operations 341 11.2.3 Statistics with Lists 345 11.3 Lists of Objects 350 11.4 Designing with Lists and Classes 353 11.5 Case Study: Python Calculator 359 11.5.1 A Calculator as an Object 359 11.5.2 Constructing the Interface 360 11.5.3 Processing Buttons 363 11.6 Non-Sequential Collections 367 11.6.1 Dictionary Basics 367 11.6.2 Dictionary Operations 368 11.6.3 Example Program: Word Frequency 370 11.7 Chapter Summary 375 11.8 Exercises 376 Chapter 12 Object-Oriented Design 385 12.1 The Process of OOD 385 12.2 Case Study: Racquetball Simulation 388 12.2.1 Candidate Objects and Methods 388 12.2.2 Implementing SimStats 390 12.2.3 Implementing RBallGame 392 12.2.4 Implementing Player 395 12.2.5 The Complete Program 396 12.3 Case Study: Dice Poker 399 12.3.1 Program Specification 399 12.3.2 Identifying Candidate Objects 400 12.3.3 Implementing the Model 402 12.3.4 A Text-Based Ul 406 12.3.5 Developing a GUI 409 12.4 00 Concepts 417 12.4.1 Encapsulation 418 12.4.2 Polymorphism 418
viⅷi Contents l2.4.3 Inheritance… 419 12.5 Chapter Summary… …421 12.6 Exercises 422 Chapter 13 Algorithm Design and Recursion 425 13.1 Searching… 426 13.1.1 A Simple Searching Problem 426 13.1.2 Strategy 1:Linear Search 427 13.1.3 Strategy 2:Binary Search 428 13.1.4 Comparing Algorithms........ 429 13.2 Recursive Problem-Solving........... 431 13.2.1 Recursive Definitions .. 432 13.2.2 Recursive Functions........ 434 13.2.3 Example:String Reversal 435 13.2.4 Example:Anagrams… 437 13.2.5 Example:Fast Exponentiation.. 438 13.2.6 Example:Binary Search 439 13.2.7 Recursion vs.Iteration............ 440 13.3 S0 rting Alg0 rithms444…… 443 13.3.1 Naive Sorting:Selection Sort.......... 443 13.3.2 Divide and Conquer:Merge Sort...... 445 13.3.3 Comparing Sorts. 447 13.4 Hard Problems................ 450 13.4.1 Towers of Hanoi 450 13.4.2 The Halting Problem… 455 13.4.3 Conclusion... 459 13.5 Chapter Summary… 459 13.6 Exercises 460 Appendix A Python Quick Reference 469 Appendix B Using Python and IDLE 479 Appendix C Glossary 491 Index 503
VIM Contents 12.4.3 Inheritance 419 12.5 Chapter Summary 421 12.6 Exercises 422 Chapter 13 Algorithm Design and Recursion 425 13.1 Searching 426 13.1.1 A Simple Searching Problem 426 13.1.2 Strategy 1: Linear Search 427 13.1.3 Strategy 2: Binary Search 428 13.1.4 Comparing Algorithms 429 13.2 Recursive Problem-Solving 431 13.2.1 Recursive Definitions 432 13.2.2 Recursive Functions 434 13.2.3 Example: String Reversal 435 13.2.4 Example: Anagrams 437 13.2.5 Example: Fast Exponentiation 438 13.2.6 Example: Binary Search 439 13.2.7 Recursion vs. Iteration 440 13.3 Sorting Algorithms 443 13.3.1 Naive Sorting: Selection Sort 443 13.3.2 Divide and Conquer: Merge Sort 445 13.3.3 Comparing Sorts 447 13.4 Hard Problems 450 13.4.1 Towers of Hanoi 450 13.4.2 The Halting Problem 455 13.4.3 Conclusion 459 13.5 Chapter Summary 459 13.6 Exercises 460 Appendix A Python Quick Reference 469 Appendix B Using Python and IDLE 479 Appendix C Glossary 491 Index 503
Foreword When the publisher first sent me a draft of this book,I was immediately excited. Disguised as a Python textbook,it is really an introduction to the fine art of programming,using Python merely as the preferred medium for beginners.This is how I have always imagined Python would be most useful in education:not as the only language,but as a first language,just as in art one might start learning to draw using a pencil rather than trying to paint in oil right away. The author mentions in his preface that Python is near-ideal as a first pro- gramming language,without being a"toy language."As the creator of Python I don't want to take full credit for this:Python was derived from ABC,a language designed to teach programming in the early 1980s by Lambert Meertens,Leo Geurts,and others at CWI (National Research Institute for Mathematics and Computer Science)in Amsterdam.If I added anything to their work,it was making Python into a non-toy language,with a broad user base and an exten- sive collection of standard and third-party application modules. I have no formal teaching experience,so I may not be qualified to judge its educational effectiveness.Still,as a programmer with nearly 30 years experi- ence,reading through the chapters I am continuously delighted by the book's clear explanations of difficult concepts.I also like the many good excercises and questions which both test understanding and encourage thinking about deeper issues. Reader of this book,congratulations!You will be well rewarded for studying Python.I promise you'll have fun along the way,and I hope you won't forget your first language once you have become a proficient software developer. -Guido van Rossum ix
Foreword When the pubHsher first sent me a draft of this book, I was immediately excited. Disguised as a Python textbook, it is really an introduction to the fine art of programming, using Python merely as the preferred medium for beginners. This is how I have always imagined Python would be most useful in education: not as the only language, but as a first language, just as in art one might start learning to draw using a pencil rather than trying to paint in oil right away. The author mentions in his preface that Python is near-ideal as a first programming language, without being a "toy language." As the creator of Python I don't want to take full credit for this: Python was derived from ABC, a language designed to teach programming in the early 1980s by Lambert Meertens, Leo Geurts, and others at CWI (National Research Institute for Mathematics and Computer Science) in Amsterdam. If I added anything to their work, it was making Python into a non-toy language, with a broad user base and an extensive collection of standard and third-party application modules. I have no formal teaching experience, so I may not be qualified to judge its educational effectiveness. Still, as a programmer with nearly 30 years experience, reading through the chapters I am continuously delighted by the book's clear explanations of difficult concepts. I also like the many good excercises and questions which both test understanding and encourage thinking about deeper issues. Reader of this book, congratulations! You will be well rewarded for studying Python. I promise you'll have fun along the way, and I hope you won't forget your first language once you have become a proficient software developer. —Guido van Rossum IX