Python Programming: An Introduction to Computer Science
13.3. SORTINGALGORITHMS 233 def merge(lst1, lst2,lst3): merge sortedlists lst1 and lst2 into lst3 # these indexeskeep track of c ...
234 CHAPTER13. ALGORITHMANALYSISANDDESIGN if len(nums) > 1: split nums intotwo halves mergeSort the firsthalf mergeSort the s ...
13.4. HARDPROBLEMS 235 Let’s seehow thatcomparestothemergesortalgorithm.Inthecaseofmergesort,wedivideda listinto two piecesandso ...
236 CHAPTER13. ALGORITHMANALYSISANDDESIGN 0 5 10 15 20 25 30 35 0 500 1000 1500 2000 2500 3000 Seconds List Size ’selSort’ ’merg ...
13.4. HARDPROBLEMS 237 Figure13.4:TowerofHanoipuzzlewitheightdisks. Move disk from A to B. Move disk from C to B. ... Thisis a d ...
238 CHAPTER13. ALGORITHMANALYSISANDDESIGN Whatis thebasecaseforthisrecursive process?Noticehow a move ofndisksresultsintwo recur ...
13.4. HARDPROBLEMS 239 stepsit requiresto solve a givensizeproblem.Inthiscase,thedifficultyis determinedbythenumberofdisks inthe ...
240 CHAPTER13. ALGORITHMANALYSISANDDESIGN Thesecondthingyounoticeisthatthisdescriptionsoundssimilartosomethingyou’ve heardabout ...
13.4. HARDPROBLEMS 241 ina program,typeinthecontentsofgoofy.py? Putmorespecifically, doesgoofy.pyhaltwhengiven itselfasitsinput? ...
Index doc , 171 init , 168 name , 106 abstraction, 148 accessor, 68 accumulator, 31 acronym, 61 algorithm analysis,2, 233 defini ...
INDEX 243 BMI(BodyMassIndex), 120 Boolean algebra(logic), 134 expression,106, 131 operator, 132 values, 106 breakstatement, 136 ...
244 INDEX conditionalloop, 124 constructor, 67, 161 init , 168 parametersin, 67 controlcodes, 46 controlstructure, 103 decision, ...
INDEX 245 description, 176 Dijkstra,Edsgar, 2 disk, 3 distancefunction, 96 division, 29 docstring, 171 dotnotation,8, 59, 67 dra ...
246 INDEX signature(interface), 148 toreduceduplication, 88 functiondefinition, 88 functions built-in chr, 46 cmp, 203 eval, 49 ...
INDEX 247 Point,65, 82 Polygon,79, 83 Rectangle, 82 Text, 83 GraphWin,64, 81 methodssummary, 81 Gregorianepact, 39 GUI, 64 hails ...
248 INDEX lineartime, 234 list, 184 assequence, 185 creation, 186 empty, 186 indexing, 185 merging, 239 methods,187, 203 operato ...
INDEX 249 Newton’s method, 40 None, 97 numbers2text.py, 49 numerology, 61 object, 161 aliasing, 69 applicationas, 194 asblackbox ...
250 INDEX chaos, 7 diceroller, 178 factorial, 32 futurevalue, 24 futurevaluegraph,74,76,87,91, 99 goofy:animpossibleprogram, 247 ...
INDEX 251 round, 37 scientificnotation, 35 scope, 92 screenresolution, 72 script, 7 search, 231 searching binarysearch, 232 line ...
252 INDEX while, 124 stats.py, 189 stdDev, 188 step-wiserefinement, 154 str, 52 string,17, 41 asinput, 41 aslookuptable, 44 ASCI ...
«
5
6
7
8
9
10
11
12
13
14
»
Free download pdf