Peter Wentworth, Jeffrey Elkner, Allen B. Downey and Chris ...

How to Think Like a Computer

Scientist: Learning with Python 3

Documentation

Release 3rd Edition

Peter Wentworth, Jeffrey Elkner,

Allen B. Downey and Chris Meyers

August 12, 2012

CONTENTS

1

2

3

The way of the program

1.1 The Python programming language

1.2 What is a program? . . . . . . . . .

1.3 What is debugging? . . . . . . . .

1.4 Syntax errors . . . . . . . . . . . .

1.5 Runtime errors . . . . . . . . . . .

1.6 Semantic errors . . . . . . . . . . .

1.7 Experimental debugging . . . . . .

1.8 Formal and natural languages . . .

1.9 The first program . . . . . . . . . .

1.10 Comments . . . . . . . . . . . . .

1.11 Glossary . . . . . . . . . . . . . .

1.12 Exercises . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1

1

3

3

3

4

4

4

5

6

7

7

9

Variables, expressions and statements

2.1 Values and data types . . . . . . .

2.2 Variables . . . . . . . . . . . . .

2.3 Variable names and keywords . .

2.4 Statements . . . . . . . . . . . .

2.5 Evaluating expressions . . . . . .

2.6 Operators and operands . . . . .

2.7 Type converter functions . . . . .

2.8 Order of operations . . . . . . . .

2.9 Operations on strings . . . . . . .

2.10 Input . . . . . . . . . . . . . . .

2.11 Composition . . . . . . . . . . .

2.12 The modulus operator . . . . . .

2.13 Glossary . . . . . . . . . . . . .

2.14 Exercises . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

11

11

13

14

15

16

16

17

18

19

19

20

21

21

23

.

.

.

.

25

25

28

29

30

Hello, little turtles!

3.1 Our first turtle program . . . . . .

3.2 Instances ¡ª a herd of turtles . . .

3.3 The for loop . . . . . . . . . . .

3.4 Flow of Execution of the for loop

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

i

3.5

3.6

3.7

3.8

4

5

6

7

ii

The loop simplifies our turtle program

A few more turtle methods and tricks

Glossary . . . . . . . . . . . . . . .

Exercises . . . . . . . . . . . . . . .

Functions

4.1 Functions . . . . . . . . . . . . .

4.2 Functions can call other functions

4.3 Flow of execution . . . . . . . .

4.4 Functions that require arguments

4.5 Functions that return values . . .

4.6 Variables and parameters are local

4.7 Turtles Revisited . . . . . . . . .

4.8 Glossary . . . . . . . . . . . . .

4.9 Exercises . . . . . . . . . . . . .

Conditionals

5.1 Boolean values and expressions .

5.2 Logical operators . . . . . . . . .

5.3 Truth Tables . . . . . . . . . . .

5.4 Simplifying Boolean Expressions

5.5 Conditional execution . . . . . .

5.6 Omitting the else clause . . . .

5.7 Chained conditionals . . . . . . .

5.8 Nested conditionals . . . . . . .

5.9 The return statement . . . . .

5.10 Logical opposites . . . . . . . . .

5.11 Type conversion . . . . . . . . .

5.12 A Turtle Bar Chart . . . . . . . .

5.13 Glossary . . . . . . . . . . . . .

5.14 Exercises . . . . . . . . . . . . .

Fruitful functions

6.1 Return values . . . . . .

6.2 Program development .

6.3 Debugging with print

6.4 Composition . . . . . .

6.5 Boolean functions . . .

6.6 Programming with style

6.7 Unit testing . . . . . . .

6.8 Glossary . . . . . . . .

6.9 Exercises . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Iteration

7.1 Assignment . . . . . . . . .

7.2 Updating variables . . . . .

7.3 The for loop revisited . . .

7.4 The while statement . . .

7.5 The Collatz 3n + 1 sequence

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

31

32

34

35

.

.

.

.

.

.

.

.

.

39

39

42

43

45

45

47

48

49

50

.

.

.

.

.

.

.

.

.

.

.

.

.

.

53

53

54

54

55

56

57

58

59

61

61

62

64

66

67

.

.

.

.

.

.

.

.

.

71

71

73

75

75

76

77

77

79

80

.

.

.

.

.

85

85

86

87

87

89

7.6

7.7

7.8

7.9

7.10

7.11

7.12

7.13

7.14

7.15

7.16

7.17

7.18

7.19

7.20

7.21

7.22

7.23

7.24

7.25

7.26

8

9

Tracing a program . . . . . . . . . . . .

Counting digits . . . . . . . . . . . . . .

Abbreviated assignment . . . . . . . . .

Help and meta-notation . . . . . . . . .

Tables . . . . . . . . . . . . . . . . . . .

Two-dimensional tables . . . . . . . . .

Encapsulation and generalization . . . .

More encapsulation . . . . . . . . . . .

Local variables . . . . . . . . . . . . . .

The break statement . . . . . . . . . .

Other flavours of loops . . . . . . . . . .

An example . . . . . . . . . . . . . . . .

The continue statement . . . . . . . .

More generalization . . . . . . . . . . .

Functions . . . . . . . . . . . . . . . . .

Paired Data . . . . . . . . . . . . . . . .

Nested Loops for Nested Data . . . . . .

Newton¡¯s method for finding square roots

Algorithms . . . . . . . . . . . . . . . .

Glossary . . . . . . . . . . . . . . . . .

Exercises . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

90

92

92

93

95

96

96

97

97

98

99

100

101

102

103

104

104

105

107

107

109

Strings

8.1 A compound data type . . . . . . . .

8.2 Working with strings as single things

8.3 Working with the parts of a string . .

8.4 Length . . . . . . . . . . . . . . . .

8.5 Traversal and the for loop . . . . .

8.6 Slices . . . . . . . . . . . . . . . . .

8.7 String comparison . . . . . . . . . .

8.8 Strings are immutable . . . . . . . .

8.9 The in and not in operators . . .

8.10 A find function . . . . . . . . . . .

8.11 Looping and counting . . . . . . . .

8.12 Optional parameters . . . . . . . . .

8.13 The built-in find method . . . . . .

8.14 The split method . . . . . . . . .

8.15 Cleaning up your strings . . . . . . .

8.16 The string format method . . . . . .

8.17 Summary . . . . . . . . . . . . . . .

8.18 Glossary . . . . . . . . . . . . . . .

8.19 Exercises . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

113

113

113

115

116

116

117

118

119

119

120

121

121

122

123

123

124

127

128

129

Tuples

9.1 Tuples are used for grouping data

9.2 Tuple assignment . . . . . . . . .

9.3 Tuples as return values . . . . . .

9.4 Composability of Data Structures

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

133

133

134

135

135

.

.

.

.

.

.

.

.

iii

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download