1、Python Algorithms Mastering Basic Algorithms in the Python Language Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language Copyright 2010 by Magnus Lie Hetland All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, ele
2、ctronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. ISBN-13 (pbk): 978-1-4302-3237-7 ISBN-13 (electronic): 978-1-4302-3238-4 Printed and bound in the United States
3、of America 9 8 7 6 5 4 3 2 1 Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with n
4、o intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. President and P
5、ublisher: Paul Manning Lead Editor: Frank Pohlmann Development Editor: Douglas Pundick Technical Reviewer: Alex Martelli Editorial Board: Steve Anglin, Mark Beckner, Ewan Buckingham, Gary Cornell, Jonathan Gennick, Jonathan Hassell, Michelle Lowman, Matthew Moodie, Duncan Parkes, Jeffrey Pepper, Fra
6、nk Pohlmann, Douglas Pundick, Ben Renow-Clarke, Dominic Shakeshaft, Matt Wade, Tom Welsh Coordinating Editor: Adam Heath Compositor: Mary Sudul Indexer: Brenda Miller Artist: April Milne Cover Designer: Anna Ishchenko Photo Credit: Kai T. Dragland Distributed to the book trade worldwide by Springer
7、Science+Business Media, LLC., 233 Spring Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail orders-nyspringer-, or visit . For information on translations, please e-mail , or visit . Apress and friends of ED books may be purchased in bulk for academic, corporate,
8、 or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Special Bulk SaleseBook Licensing web page at The information in this book is distributed on an “as is” basis, without warranty. Although every precaution has been taken in the p
9、reparation of this work, neither the author(s) nor Apress shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in this work. The source code for this book is available to readers at For
10、my students. May your quest for knowledge be richly rewarded. CONTENTS v g38g82g81g87g72g81g87g86g3g68g87g3g68g3g42g79g68g81g70g72g3Contents.vi About the Author .xiii About the Technical Reviewer.xiv Acknowledgments .xv Preface .xvi Chapter 1: Introduction.1g3 Chapter 2: The Basics .9g3 Chapter 3: C
11、ounting 101 .45g3 Chapter 4: Induction and Recursion and Reduction.71g3 Chapter 5: Traversal: The Skeleton Key of Algorithmics .101g3 Chapter 6: Divide, Combine, and Conquer.125g3 Chapter 7: Greed Is Good? Prove It!.151g3 Chapter 8: Tangled Dependencies and Memoization .175g3 Chapter 9: From A to B
12、with Edsger and Friends.199g3 Chapter 10: Matchings, Cuts, and Flows .221g3 Chapter 11: Hard Problems and (Limited) Sloppiness .241g3 Appendix A: Pedal to the Metal: Accelerating Python .271g3 Appendix B: List of Problems and Algorithms .275g3 Appendix C: Graph Terminology.285g3 Appendix D: Hints fo
13、r Exercises.291g3 Index .307g3 CONTENTS vi g38g82g81g87g72g81g87g86g3Contents at a Glance.v About the Author .xiii About the Technical Reviewer.xiv Acknowledgments .xv Preface .xvi Chapter 1: Introduction.1g3Whats All This, Then? .2g3Why Are You Here? .3g3Some Prerequisites .4g3Whats in This Book .5
14、g3Summary .6g3If Youre Curious .6g3Exercises .7g3References.7g3 Chapter 2: The Basics .9g3Some Core Ideas in Computing .9g3Asymptotic Notation .10g3Its Greek to Me! .12g3Rules of the Road .14g3Taking the Asymptotics for a Spin.16g3Three Important Cases .19g3Empirical Evaluation of Algorithms.20g3 CO
15、NTENTS vii Implementing Graphs and Trees.23g3Adjacency Lists and the Like.25g3Adjacency Matrices .29g3Implementing Trees.32g3A Multitude of Representations .35g3Beware of Black Boxes.36g3Hidden Squares .37g3The Trouble with Floats .38g3Summary .40g3If Youre Curious .41g3Exercises .42g3References.43g
16、3 Chapter 3: Counting 101 .45g3The Skinny on Sums .45g3More Greek .46g3Working with Sums .46g3A Tale of Two Tournaments.47g3Shaking Hands.47g3The Hare and the Tortoise .49g3Subsets, Permutations, and Combinations.53g3Recursion and Recurrences.56g3Doing It by Hand .57g3A Few Important Examples.58g3Gu
17、essing and Checking .62g3The Master Theorem: A Cookie-Cutter Solution .64g3So What Was All That About? .67g3Summary .68g3If Youre Curious .69g3Exercises .69g3 CONTENTS viii References.70g3 Chapter 4: Induction and Recursion and Reduction.71g3Oh, Thats Easy!.72g3One, Two, Many.74g3Mirror, Mirror .76g
18、3Designing with Induction (and Recursion).81g3Finding a Maximum Permutation .81g3The Celebrity Problem .85g3Topological Sorting.87g3Stronger Assumptions .91g3Invariants and Correctness.92g3Relaxation and Gradual Improvement.93g3Reduction + Contraposition = Hardness Proof .94g3Problem Solving Advice .95g3Summary .96g3If Youre Curious .97g3Exercises .97g3References.99g3 Chapter 5: Traversal: The Skeleton Key of Algorithmics .101g3A Walk in the Park .107g3No Cycles Allowed .108g3How to Stop Walking in Circles .109g3Go Deep! .110g3Depth-First Times
