Think Like a ProgrammerTHINK LIKE A PROGRAMMERTHINK LIKEAPROGRAMMERAMl量odMc量 ion toCreative Pr。 blem s。lvin8by v. Anton Spraulno starchpressSan franciscoTHINK LIKE A PROGRAMMER, Copyright O 2012 by V. Anton SpraulAll rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic ormechanical, including photocopying, recording, or by any information storage or retrieval system, without the priorwritten permission of the copyright owner and the publisherFirst printil5141312123456789ISBN-10:159327-4946ISBN-13:978-1-59397-4945Publisher: William PollockProduction Editor: Alison lawCover Design: Charlie wylieDesign: Octopod studiosDevelopmental editor: Kcith FanchcTechnical reDan randallCopyeditor: Julianne jigourColGISteProofreader: Ward WebberFor information on book distributors or translations, please contact No Starch Press, Inc. directlyNo Starch press. inc8 Ringold Street, San Francisco, CA 94103phone415.863.9900:fax:415.863.9950;info@nostarch.comwww.nostarch.comLibrary of Congress Cataloging-in-Publication DataA catalog record of this book is available from the library of CongressNo Starch Press and the No Starch Press logo arc rcgistcrcd trademarks of No Starch Press, Inc. Othcr product andcompany names mentioned herein may be the trademarks of their respective owners. Rather than use a trademarksymbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to thebenefit of the trademark owner, with no intention of infringement of the trademark.The infornation in this book is distributed on anl"As Is"basis, without warranty. While every precaution has beeiltaken in the preparation of this work, neither the author nor No Starch Press, Inc shall have any liability to anypcrson or entity with respect to any loss or damage causcd or alleged to bc causcd directly or indirectly by theinformation contained in itRe-quaned White spere aroute log?SFI LOgO- FPOSmall PositiveBRIEF CONTENTSAcknowledgments…IntroductionXIIIChapter 1: Strategies for Problem SolvingChapter 2: Pure Puzzles25Chapter 3 Solving problems with arrays55Chapter 4: Solving Problems with Pointers and Dynamic Memory ........81Chapter 5: Solving Problems with ClassesChapter 6: Solving Problems with Recursion ......143Chapter 7: Solving Problems with Code Reuse++“+“++“.171Chapter8: Thinking Like a Programmer…….195Index227CONTENTS IN DETAILACKNOWLEDG MENTSINTRODUCTIONabout this bePrerequisitesChosen TopicsProgramming Style………ExercisesWhy C++?STRATEGIES FOR PROBLEM SOLVINGClassic puzzlesThe Fox. the goose, and the CornProblem: How to Cross the river? nnmmmmnmmnnmmmmmnnnm.3Sliding tile puzzlesProblem: The Sliding EightProblem: The Sliding Five ...SudokuProblem: Completing a Sudoku Square...The quadrasi lock∴Problem: Opening the Alien Lock....................13General Problem-Solving TechniquesAlways HPlan16Restate the prDivide the Problem17Start with what you Know18Reduce the probler19Look for Analogies.20Experiment.20Don' t get frustrated21ExercisesPURE PUZZLES25Review of C++ Used in This Chapter26○ utput PatternsProblem: Half of aProblem: A Square(Half of a Square Reduction)....s...Problem: A Line(Half of a SquareProblem: Count Down by Counting Up...28Problem: A Sideways Triangle29Input ProcessingProblem: Luhn Checksum validation ..m.........31Breaking down the Problem33Problem: Convert Character Digit to Integer .Problem: Luhn Checksum Validation Fixed length36Problem: Simple Checksum Validation, Fixed Length36Problem: Positive or Negative…………n39Putting the pieces Together39Tracking State········4Problem: Decode a messageProblem: Reading a Number with Three or Four Digits....c.c..45Problem: Reading a Number with Three or Four Digits, Further Simplified...,46ConclusionExercisesSOLVING PROBLEMS WITH ARRAYS55Review of array fundamentals56StoreCRetrieval and SearchSort··:·····:···59Compute statistic6Solving Probleith arre62Problem: Finding the Mode,…,…RefacteArrays of fixed dataNon-scalar Arrays.69Multidimensional arrays74xercises78SOLVING PROBLEMS WITH POINTERS ANDDYNAMIC MEMORY81of pointer fundamentalsBenefits o「 Pointers83Runtime-si83Resizable data structur83Memory Sharing84When to use pointers84MemoryMatters85The stack and the hee86Memory Size····*···········:···中·····88Lifetime90Solving Pointer Problems91Variable-Length StringsProblem: Variable -Length String ManipulationLinked lists10Problem trackig anof student recordConclusion and Next Steps.108109