IntroductiontoProgramminginPython_AnInterdisciplinaryApproach

Introduction to Programming in Python_An Interdisciplinary Approach 相当经典的python 数据结构与算法教程，高清英文版IntroductiontoProgramming in pythonAn Interdisciplinary approachRobert sedgewickKevin WayneRobert donderoPrinceton UniversityAddison-WesleyNew York. Boston. Indianapolis. San franciscoToronto· Montreal· London· Munich· Paris· MadridCapetown· Sydney。 Tokyo. Singapore· Mexico CityMany of the designations used by manufacturers and sellers to distinguish their products are claimedas trademarks. Where those designations appear in this book, and the publisher was aware of atrademark claim, the designations have been printed with initial capital letters or in all capitalsThe authors and publisher have taken care in the preparation of this book, but make no expressedor implied warranty of any kind and assume no responsibility for errors or omissions no liability isassumed for incidental or consequential damages in connection with or arising out of the use of theinformation or programs contained hereinFor information about buying this title in bulk quantities, or for special sales opportunities(whichmay inchude electronic versions; custom cover designs and content particular to your business,training goals, marketing focus, or branding interests), please contact our corporate salesdepartment at corpsales(@pearsoned com or(800)382-3419For government sales inquiries, please contact governmentsalesapearsoned comFor questions about sales outside the United States, please contactinternational@pearsoned comVisit us on the web: informit. com/awLibrary of cataloging-in-Publication DataSedgewick, Robert, 1946Introduction to programming in Python: an interdisciplinary approach/ robert Sedgewick, KevinWayne Robert donderopages cmncludes indexesisbn978-0-13-407643-0(hardcover: alk. paper-ISBN 0-13-407643-51. Python (Computer program language )2. Computer programming. I. Wayne, Kevin Daniel,1971II. Dondero, robert. III. TitleQA76.73.P98S432015005.133dc232015011936Copyright o 2015 Pearson Education, IncAll rights reserved. Printed in the United States of America. This publication is protected bycopyright, and permission must be obtained from the publisher prior to any prohibited reproduction,storage in a retrieval system, or transmission in any form or by any means electronic, mechanical,photocopying, recording, or likewise. To obtain permission to use material from this work, pleasesubmit a written request to Pearson Education, Inc, Permissions Department, 200 Old TappanRoad, Old Tappan, New Jersey 07675, or you may fax your request to 236-3290ISBN-13:978-0-13-407643-0ISBN-10:0-13-407643-5Text printed in the united states on recycled paper at edwards brothers malloy in Ann arbor.MichiganFirst printing, June 2015To Adam. Andrew Brett. RobbieHenry, lona, Rose, Peter,and especially lindaTo Jackie and alexo myjamilyespecially Ellen and MeghanContentsPreface1-Elements of programming1.1 Your First Program1.2 Built-in Types of Data3 Conditionals and Loops.4 Arrays5 Input and Output1.6 Case Study Random Web Surfer2-Functions and modules2. 1 Defining Functions2.2 Modules and clients2. 3 Recursion2. 4 Case Study Percolation3-Obiect-Oriented Programming3. 1 Using Data Types3.2 Creating Data Types3.3 Designing Data Types3.4 Case Study n-Body simulationalgorithms and data structures4.1 Performance4.2 Sorting and Searching4.3 Stacks and Queues4.4 Symbol Tables4.5 Case Study: Small-World phenomenonContextGlossaryIndexProgramsElements of programmingYour first program11. 1 Hello. World1.1.2 USing a command -line argumentBuilt-in Tvpes of data2.1 String concatenation example1.2.2 Integer operators1.2.3 Float operators1. 2. 4 Quadratic formula1.2.5 Leap yearConditionals and Loops13. 1 Flipping a fair coin1.3.2 Your first loop3.3 Computing powers of 21.3.4 Your first nested loops1. 3. 5 Harmonic numbers1.3.6 Newton's method1.3. 7 Converting to binary1. 3. 8 Gambler 's ruin simulation1.3.9 Factoring integersArrays1.4.1 Sampling without replacement4.2 Coupon collector simulation1. 4 3 Sieve of eratosthenes1.4.4 Self-avoiding random walksInput and Output1.5. 1 Generating a random sequence1.5.2 Interactive user input5.3 Averaging a stream ofnumbers1.5.4 A simple filter1.5.5 Standard input to drawing filter1.5.6 Function graph5.7 Bouncing ball1.5.8 Digital signal processingCase Study: Random Web Surfer.6 1 Computing the transition matrix1.6.2 Simulating a random surfer6. 3 Mixing a markov chainFunctions and modulesDefining Functions2. 1. 1 Harmonic numbers (revisited)2.1.2 Gaussian functions2.1.3 Coupon collector(revisited)2. 1. 4 Play that tune (revisited)Modules and clients2. 2. 1 Gaussian functions module2.2.2 Sample gaussian client2.2.3 Random number module2.2.4 Iterated function systems2.2. 5 Data analysis module2.2.6 Plotting data values2. 2. 7 Bernoulli trialsRecurson2.3. 1 Euclid s algorithm2.3.2 Towers of hanoi2.3. 3 Gray code2.3.4 Recursive graphics2.3.5 Brownian bridsCase Study Percolation2. 4.1 Percolation scaffolding2. 4.2 Vertical percolation detection2.4.3 Percolation input/output2.4 4 Visualization client2. 4.5 Percolation probability estimate2.4.6 Percolation detection2.4.7 Adaptive plot clientObiect-Oriented ProgrammingData zipes3. 1. 1 Identifying a potential gene3. 1.2 Charged-particle chent3.13Abers squares3. 1. 4 Luminance module3. 1.5 Converting color to grayscale3. 1. 6 Image scaling3.1.7 Fade effect3. 1.8 Visualizing electric potential3.1.9 Concatenating files3.1.10 Screen scraping for stock quotes3.1.11 Splitting a fileCreating Data Tvpes3.2. 1 Charged particle3.2.2 Stopwatch3.2.3 Histogram3.2.4 Turtle graphics3.2.5 Spira mirabilis3.2.6 Complex numbers3.2.7 Mandelbrot set3. 2. 8 Stock accountDesigning Data types3.3. 1 Complex numbers(polar)3.3.2 Counter3.3.3 Spatial vectors3.3. 4 Document sketch3.3.5 Similarity detectionCase Study: N-Body simulation3. 4. 1 Gravitational body3. 4.2 N-body simulationAlgorithms and Data StructuresPerformance4.1.1 3-Sum problem4.1.2 Validating a doubling hypothesisSorting and searching4.2. 1 Binary search(20 questions10