دانلود کتاب Animated Program Design: Intermediate Program Design Using Video Game Development

فهرست مطالب :

Preface 1 The Parts of the Book 2 Acknowledgments Contents Part I Basic Problem Solving and Program Design 1 The Science of Problem Solving 3 The Design Recipe 4 Computing the Area of a Triangle 4.1 Exercises 5 Doubling a List of Numbers 5.1 Step 1: Data Analysis and Design Idea 5.2 Step 2: Sample Expressions 5.3 Step 3: Differences Among Sample Expressions 5.4 Steps 4–5: Signature, Purpose Statement, and Function Header 5.5 Step 6: Tests 5.6 Step 7: Function Body 5.7 Step 8: Run Tests 5.8 Exercises 6 Code Refactoring 6.1 Exercises 7 Abstract Running Time 7.1 Exercises 8 What Have We Learned in This Chapter? 2 The N-Puzzle Problem 9 The world and the run Function 10 Useful Constants 11 The draw-world Handler 12 The game-over? Handler 13 The process-key Handler 13.1 The Design of vk? 13.2 The Design of process-vk 13.2.1 Computing the Position of the Empty Space 13.2.2 The Design of get-target-bpos 13.2.3 The Design of swap-empty 13.2.4 The Design of make-move 14 What Have We Learned in This Chapter? 3 Randomness 15 ISL+'s random Function 16 N-Puzzle Version 1 17 Generating Random Passwords 18 Distributed Fortune Teller Game 18.1 Design Recipe for Distributed Computing 18.2 The Components 18.3 Data Definitions 18.3.1 Player Data Definitions 18.3.2 Server Data Definitions 18.4 Communication Protocol 18.5 Marshaling and Unmarshaling Functions 18.6 The Player Component 18.6.1 The draw-world Handler 18.6.2 The process-key Handler 18.6.3 The process-message Handler 18.6.4 The finished? Handler 18.7 The Server Component 18.7.1 The add-new-iworld Handler 18.7.2 The rm-iworld Handler 18.7.3 The process-message Handler 19 What Have We Learned in This Chapter? Part II Generative Recursion 4 Introduction to Generative Recursion 20 Generating a Nested Square Image 21 The Design Recipe for Generative Recursion 22 All Primes n 23 What Have We Learned in This Chapter? 5 Sorting 24 Insertion Sorting 25 Quick Sorting 25.1 Problem Analysis 25.2 Sample Expressions and Differences 25.3 Signature, Statements, and Function Header 25.4 Tests 25.5 Function Body 25.6 Termination Argument 25.7 Performance 25.8 Complexity Analysis 26 Merge Sorting 26.1 Problem Analysis 26.2 The merge-sorting Function 26.2.1 Problem Analysis 26.2.2 Sample Expressions and Differences 26.2.3 Signature, Purpose, and Function Header 26.2.4 Tests 26.2.5 Function Body 26.3 The merge-sort-helper Function 26.3.1 Problem Analysis 26.3.2 Sample Expressions and Differences 26.3.3 Signature, Statements, and Function Header 26.3.4 Tests 26.3.5 Function Body 26.3.6 Termination Argument 26.4 The merge-neighs Function 26.4.1 Problem Analysis 26.4.2 Sample Expressions and Differences 26.4.3 Signature, Statements, and Function Header 26.4.4 Tests 26.4.5 Function Body 26.4.6 Termination Argument 26.5 The merge Function 26.5.1 Problem Analysis 26.5.2 Sample Expressions and Differences 26.5.3 Signature, Statements, and Function Header 26.5.4 Tests 26.5.5 Function Body 26.6 Performance 26.7 Complexity Analysis 27 What Have We Learned in This Chapter? 6 Searching 28 Linear Searching 28.1 Problem Analysis 28.2 Sample Expressions and Differences 28.3 Signature, Purpose, and Function Header 28.4 Tests 28.5 Function Body 28.6 Performance and Complexity 29 Binary Search 29.1 The binary-search Function 29.1.1 Problem Analysis 29.1.2 Sample Expressions and Differences 29.1.3 Signature, Statements, and Function Header 29.1.4 Tests 29.1.5 Function Body 29.2 The bin-search Function 29.2.1 Problem Analysis 29.2.2 Sample Expressions and Differences 29.2.3 Signature, Statements, and Function Header 29.2.4 Tests 29.2.5 Function Body 29.3 Termination Argument 29.4 Performance and Complexity 30 Trees 31 Depth-First Search 31.1 Problem Analysis 31.2 Sample Expressions and Differences 31.3 Signature, Purpose, and Function Header 31.4 Tests 31.5 The Function Body 31.6 The node-dfs-contains? Function 31.6.1 Problem Analysis 31.6.2 Sample Expressions 31.7 Signature, Purpose, and Function Definition 31.7.1 Tests 31.8 Performance and Complexity 32 Breadth-First Search 32.1 Problem Analysis for ton-bfs-contains? 32.1.1 Queues 32.1.2 The Implementation of qempty? and qfirst 32.1.3 The Implementation of enqueue and dequeue 32.2 Sample Expressions and Differences for ton-bfs-contains? 32.3 Tests for ton-bfs-contains? 32.4 Function Definition for ton-bfs-contains? 32.5 Problem Analysis for bfs-helper 32.6 Sample Expressions and Differences for bfs-helper 32.7 Tests for bfs-helper 32.8 Signature, Statements, and Function Definition for bfs-helper 32.9 Performance and Complexity 33 What Have We Learned in This Chapter? 7 N-Puzzle Version 2 34 Design and Implementation of make-move 34.1 Problem Analysis 34.2 Sample Expressions and Differences 34.3 Signature, Purpose, and Function Header 34.4 Tests 34.5 Function Body 35 Design and Implementation of find-solution 35.1 Problem Analysis 35.2 Sample Expressions and Differences 35.3 Signature, Statements, and Function Header 35.4 Tests 35.5 Function Body 35.6 Termination Argument 36 New Tests for process-key 37 A Bug: Infinite Recursion 38 What Have We Learned in This Chapter? 8 N-Puzzle Version 3 39 The Design of make-move 39.1 Problem Analysis 39.2 Sample Expressions and Differences 39.3 Signature, Purpose, and Function Header 39.4 Tests 39.5 Function Body 40 The Design of find-solution-bfs 40.1 Problem Analysis 40.2 Sample Expressions and Differences 40.3 Signature, Statements, and Function Header 40.4 Tests 40.5 Function Body 40.6 Termination Argument 41 Performance 42 What Have We Learned in This Chapter? Part III Accumulative Recursion 9 Accumulators 43 Running Totals 43.1 Problem Analysis for lon-running-totals 43.2 Sample Expressions and Differences for lon-running-totals 43.3 Signature, Function Definition, and Tests for lon-running-totals 43.4 Problem Analysis for lon-running-totals- helper 43.5 Sample Expressions and Differences for lon-running-totals-helper 43.6 Signature, Function Definition, and Tests for lon-running-totals-helper 43.7 The lon-sum Function 44 Running Totals Using an Accumulator 44.1 Problem Analysis 44.2 Sample Expressions and Differences for lon-running-totals-v2 44.3 Function Definition for lon-running-totals-v2 44.4 Tests for lon-running-totals-v2 44.5 Problem Analysis for lon-running-totals-helper-v2 44.6 Sample Expressions and Differences for lon-running-totals-helper-v2 44.7 Signature, Statements, and Function Header for lon-running-totals-helper-v2 44.8 Tests for lon-running-totals-helper-v2 44.9 Function Body for lon-running-totals- helper-v2 45 Performance and Complexity Analysis 46 Finding a Path in a Directed Graph 46.1 Data Analysis 46.2 Design and Implementation of find-path 46.2.1 Problem Analysis 46.2.2 Sample Expressions and Differences 46.2.3 Signature, Purpose, and Function Definition 46.2.4 Tests 46.3 Design and Implementation of find-path-acc 46.3.1 Problem Analysis 46.3.2 Sample Expressions and Differences 46.3.3 Signature, Purpose, Invariant, and Function Header 46.3.4 Tests 46.3.5 Function Body 46.4 Design and Implementation of find-path-from-neighbors 46.4.1 Problem Analysis 46.4.2 Sample Expressions and Differences 46.4.3 Signature, Purpose, Invariant, and Function Header 46.4.4 Tests 46.4.5 Function Body 46.5 Termination Argument 47 Revisiting Insertion Sorting 47.1 The Redesign of insert 47.1.1 Problem Analysis 47.1.2 Sample Expressions and Differences 47.1.3 Signature, Statements, and Function Header 47.1.4 Tests 47.1.5 Function Body 47.2 The Redesign of insertion-sorting 47.2.1 Problem Analysis 47.2.2 Sample Expressions and Differences 47.2.3 Signature, Purpose, Invariant, and Function Header 47.2.4 Tests 47.2.5 Function Body 47.3 Performance and Complexity Analysis 48 What Have We Learned in This Chapter? 10 N-Puzzle Versions 4 and 5 49 N-Puzzle Version 4 49.1 The Design and Implementation of find-solution 49.1.1 Problem Analysis 49.1.2 Sample Expressions and Differences 49.1.3 Signature, Statements, and Function Header 49.1.4 Tests 49.1.5 Function Body 49.2 The find-solution-from-any-succ Design and Implementation 49.2.1 Problem Analysis 49.2.2 Sample Expressions and Differences 49.2.3 Signature, Statements, and Function Header 49.2.4 Tests 49.2.5 Function Body 49.3 Termination Argument 50 N-Puzzle Version 5 50.1 Problem Analysis 50.2 Sample Expressions and Differences 50.3 Signature, Statements, and Function Header 50.4 Tests 50.5 Function Body 50.6 Termination Argument 51 Complexity and Performance 52 What Have We Learned in This Chapter? 11 Iteration 53 List-Folding Operations from the Left 53.1 Summing a List of Numbers 53.1.1 Problem Analysis 53.1.2 Refactoring sum-lon 53.1.3 sum-lon-accum's Sample Expressions and Differences 53.1.4 Signature, Statements, and Function Header for sum-lon-accum 53.1.5 Tests for sum-lon-accum 53.1.6 sum-lon-accum's Function Body 53.1.7 Performance 53.2 Reversing a List 53.2.1 Problem Analysis 53.2.2 Sample Expressions and Differences for rev-lox-accum 53.2.3 rev-lox-accum's Signature, Statements, and Function Header 53.2.4 Tests for rev-lox-accum 53.2.5 Function Body for rev-lox-accum 53.2.6 Performance 54 List-Folding Operations from the Right 54.1 Computing String Lengths from a List of Strings 54.1.1 Problem Analysis 54.1.2 Sample Expressions and Differences for lengths-lostr-accum 54.1.3 Signature, Statements, and Function Header for lengths-lostr-accum 54.1.4 Tests for lengths-lostr-accum 54.1.5 Function Body for lengths-lostr-accum 54.1.6 Performance 54.2 Summing a List of Numbers Revisited 55 Functional Abstraction 56 Abstraction over Left to Right Accumulating Folding Functions 56.1 The Abstraction 56.2 Performance 57 Abstraction Over Right to Left Accumulating Folding Functions 58 What Have We Learned in This Chapter? 12 N-Puzzle Version 6 59 The Manhattan Distance Heuristic 60 Problem Analysis 61 Sample Expressions and Differences for find-solution-a* 62 Signature, Statements, and Function Header 63 Tests for find-solution-a* 64 Function Body for find-solution-a* 65 Termination Argument 66 Performance 67 What Have We Learned in This Chapter? 13 Continuation-Passing Style 68 Accumulating Control 69 The CPS Design Recipe 70 Computing Fibonacci Numbers 70.1 Transforming to CPS 70.2 Performance 70.3 Going Beyond the Design Recipe 71 Revisiting List Reversal 72 What Have We Learned in This Chapter? Part IV Mutation 14 Sharing Values 73 set! and begin Expressions 74 Design Recipe for Mutators 75 A Bank Account 75.1 Problem and Data Analysis 75.2 State Variable Definitions 75.3 State Variable Initializers 75.4 The Mutator for Deposits 75.4.1 Problem Analysis 75.4.2 Signature, Statements, and Function Header 75.4.3 Tests 75.4.4 Function Body 75.5 The Mutator for Withdrawals 75.5.1 Problem Analysis 75.5.2 Signature, Statements, and Function Header 75.5.3 Tests 75.5.4 Function Body 75.6 The Observer for Getting the Balance 76 Abstraction Over State Variables 76.1 Bank Account State Variables and Interface 76.2 Bank Account Class Template 76.3 Bank Account Message-Passing Function Design 76.4 Bank Account Auxiliary Function Design 76.5 Bank Account Wrapper Functions and Tests 77 A Design Recipe for Interfaces 78 Mutation and Structures 79 The Concept of Equality 80 What Have We Learned in This Chapter? 15 Mutation Sequencing 81 Hoare Logic 81.1 Using Hoare Triples 81.1.1 Developing fact-state! 81.2 Imperative Code Debugging 82 New Syntax: while Loops 82.1 Syntax and Semantics 82.2 Transformation from an Imperative Recursive Function to a while Loop 83 A Design Recipe for while loops 84 Determining if an Interval Contains a Prime 84.1 Problem Analysis 84.2 Signature, Statements, and Function Header 84.3 Tests 84.4 Loop Invariant 84.5 Function Body 84.6 The begin Expression 84.7 Post-Loop Code 84.8 Auxiliary Functions 84.9 Termination Argument 84.10 Run Tests 85 Finding the Maximum in a List of Numbers 85.1 Problem Analysis 85.2 Signature, Statements, and Function Header 85.3 Tests 85.4 Loop Invariant 85.5 Function Body 85.6 The begin Expression 85.7 Post-Loop Code 85.8 Termination Argument 85.9 Run Tests 86 What Have We Learned in This Chapter? 16 Vectors 87 Vector Basics 88 Vector Processing Using Structural Recursion 88.1 The Dot Product of Two Vectors of Numbers 88.1.1 Problem Analysis 88.1.2 Problem Analysis for sum-products 88.1.3 Signature, Statements, and Function Header for sum-products 88.1.4 Function Body for sum-products 88.2 Merging Two Sorted Vectors 88.2.1 Problem Analysis 88.2.2 Signature, Statements, and Function Header 88.2.3 Tests 88.2.4 Loop Invariant 88.2.5 Function's Local Declarations 88.2.6 The local-expression's Body 88.2.7 Post-Loop Code 88.2.8 Auxiliary Functions, Termination Argument, and Testing 89 Vector Processing Using Generative Recursion: Revisiting the Sieve of Eratosthenes 89.1 Problem Analysis 89.2 Signature, Statements, and Function Header 89.3 Tests 89.4 Loop Invariant 89.5 Function's Local Definitions 89.6 The local-expression's Body 89.7 Post-Loop Code 89.8 Auxiliary Functions 89.8.1 The Design of mark-multiples! 89.8.2 The Design of extract-primes 89.9 Termination Argument and Running Tests 89.10 Complexity and Performance 90 What Have We Learned in This Chapter? 17 In-Place Operations 91 Reversing a Vector 91.1 Problem Analysis 91.2 The reverse-vector-in-place! Mutator 91.2.1 Problem Analysis 91.3 Signature and Statements 91.3.1 Tests 91.3.2 Function Body 91.4 The rev-vector! Mutator 91.4.1 Problem Analysis 91.4.2 Signature and Statements 91.4.3 Testing 91.5 Function Body 91.6 The swap! Mutator and Running Tests 91.7 Performance 92 In-Place Quick Sorting 92.1 The qs-in-place! Mutator 92.1.1 Problem Analysis 92.1.2 Signature, Statements, and Function Header 92.1.3 Tests 92.1.4 Function Body 92.2 The qs-aux! Mutator 92.2.1 Problem Analysis 92.2.2 Signature, Statements, and Function Header 92.2.3 Function Body 92.2.4 Termination Argument 92.3 The partition! Mutator 92.3.1 Problem Analysis 92.3.2 Signature, Statements, and Function Header 92.3.3 Function Body 92.3.4 Termination Argument 92.4 The Design of first<= 92.4.1 Problem Analysis 92.4.2 Signature, Statements, and Function Header 92.4.3 Function Body 92.5 The Design of first> 92.5.1 Problem Analysis 92.5.2 Signature, Statements, and Function Header 92.5.3 Function Body 92.6 Completing the Design 93 In-Place Heap Sorting 93.1 Heaps 93.2 Sorting 93.3 Mapping a Heap to a Vector 93.4 The heap-sort-in-place! Mutator 93.4.1 Problem Analysis 93.4.2 Signature, Statements, and Function Header 93.4.3 Tests 93.4.4 Function Body 93.5 The sorter! Mutator 93.5.1 Problem Analysis 93.5.2 Signature, Statements, and Function Header 93.5.3 Function Body 93.6 The trickle-down! Mutator 93.6.1 Problem Analysis 93.6.2 Signature, Statements, and Function Header 93.6.3 Function Body 93.6.4 Termination Argument 93.7 The heapify! Mutator 93.7.1 Problem Analysis 93.7.2 Signature, Statements, and Function Header 93.7.3 Function Body 93.7.4 Complexity and Performance 94 Empirical Project 94.1 Radix Sorting 94.2 The Project 95 What Have We Learned in This Chapter? 18 The Chicken and the Egg Paradox 96 The Paradox in Programming 97 Solving the Paradox 97.1 Problem Analysis 97.2 Sample Expressions and Differences 97.3 Signature, Statements, and Function Header 97.4 Tests 97.5 Function Body 98 Adding Clients to a Bank 98.1 Problem and Data Analysis 98.2 State Variable Definition 98.3 Bank Initializer 98.4 The add-account! Mutator 98.4.1 Problem Analysis 98.4.2 Signature, Statements, and Function Header 98.4.3 Tests 98.4.4 Function Body 99 What Have We Learned in This Chapter? Part V Epilogue 19 Where to Go from Here