CS计算机代考程序代写 python 61a-mt2-study-guide.key

List comprehensions:

>>> digits = [1, 8, 2, 8]
>>> 2 in digits
True
>>> 1828 not in digits
True

>>> digits[0:2]
[1, 8]
>>> digits[1:]
[8, 2, 8]

Membership: Slicing:

Slicing creates a new object

>>> a = [10]
>>> b = [10]
>>> a == b
True
>>> b.append(20)
>>> a
[10]
>>> b
[10, 20]
>>> a == b
False

>>> a = [10]
>>> b = a
>>> a == b
True
>>> a.append(20)
>>> a == b
True
>>> a
[10, 20]
>>> b
[10, 20]

>>> suits = [‘coin’, ‘string’, ‘myriad’]
>>> suits.pop()
‘myriad’
>>> suits.remove(‘string’)
>>> suits.append(‘cup’)
>>> suits.extend([‘sword’, ‘club’])
>>> suits[2] = ‘spade’
>>> suits
[‘coin’, ‘cup’, ‘spade’, ‘club’]
>>> suits[0:2] = [‘diamond’]
>>> suits
[‘diamond’, ‘spade’, ‘club’]
>>> suits.insert(0, ‘heart’)
>>> suits
[‘heart’, ‘diamond’, ‘spade’, ‘club’]

>>> nums = {‘I’: 1.0, ‘V’: 5, ‘X’: 10}
>>> nums[‘X’]
10
>>> nums[‘I’] = 1
>>> nums[‘L’] = 50
>>> nums
{‘X’: 10, ‘L’: 50, ‘V’: 5, ‘I’: 1}
>>> sum(nums.values())
66
>>> dict([(3, 9), (4, 16), (5, 25)])
{3: 9, 4: 16, 5: 25}
>>> nums.get(‘A’, 0)
0
>>> nums.get(‘V’, 0)
5
>>> {x: x*x for x in range(3,6)}
{3: 9, 4: 16, 5: 25}

List & dictionary mutation:

Identity:
is
evaluates to True if both and
evaluate to the same object
Equality:
==
evaluates to True if both and
evaluate to equal values
Identical objects are always equal values

The parent
frame contains
the balance of

withdraw

Every call
decreases the
same balance

def make_withdraw(balance):
def withdraw(amount):
nonlocal balance
if amount > balance:
return ‘No funds’
balance = balance – amount
return balance
return withdraw

>>> withdraw = make_withdraw(100)
>>> withdraw(25)
75
>>> withdraw(25)
50

x = 2Status Effect
•No nonlocal statement
•”x” is not bound locally

Create a new binding from name “x” to number 2
in the first frame of the current environment

•No nonlocal statement
•”x” is bound locally

Re-bind name “x” to object 2 in the first frame
of the current environment

•nonlocal x
•”x” is bound in a
non-local frame
•”x” also bound locally

SyntaxError: name ‘x’ is parameter and nonlocal

•nonlocal x
•”x” is not bound in
a non-local frame

SyntaxError: no binding for nonlocal ‘x’ found

•nonlocal x
•”x” is bound in a
non-local frame

Re-bind “x” to 2 in the first non-local frame of
the current environment in which “x” is bound

You can copy a list by calling the list
constructor or slicing the list from the
beginning to the end.

Type dispatching: Look up a cross-type implementation of an
operation based on the types of its arguments
Type coercion: Look up a function for converting one type to
another, then apply a type-specific implementation.

digits

pairs

def rational(n, d):
def select(name):
if name == ‘n’:
return n
elif name == ‘d’:
return d
return select

This
function

represents
a rational

number

Constructor is a
higher-order function

Selector calls x
The result of calling repr on a value is
what Python prints in an interactive session

>>> 12e12
12000000000000.0
>>> print(repr(12e12))
12000000000000.0The result of calling str on a value is

what Python prints using the print function
>>> print(today)
2019-10-13

str and repr are both polymorphic; they apply to any object
repr invokes a zero-argument method __repr__ on its argument
>>> today.__repr__()
‘datetime.date(2019, 10, 13)’

>>> today.__str__()
‘2019-10-13’

Remove and return
the last element

Remove a value

Add all
values

Replace a
slice with
values

Add an element
at an index

def numer(x):
return x(‘n’)
def denom(x):
return x(‘d’)

Functions that aggregate iterable arguments
•sum(iterable[, start]) -> value sum of all values
•max(iterable[, key=func]) -> value largest value
max(a, b, c, …[, key=func]) -> value
min(iterable[, key=func]) -> value smallest value
min(a, b, c, …[, key=func]) -> value

•all(iterable) -> bool whether all are true
any(iterable) -> bool whether any is true

Return an iterator
over the elements of
an iterable value

Return the next element

iter(iterable):

next(iterator):

>>> s = [3, 4, 5]
>>> t = iter(s)
>>> next(t)
3
>>> next(t)
4

>>> d = {‘one’: 1, ‘two’: 2, ‘three’: 3}
>>> k = iter(d)
>>> next(k)
‘one’
>>> next(k)
‘two’

>>> v = iter(d.values())
>>> next(v)
1
>>> next(v)
2

>>> def plus_minus(x):
… yield x
… yield -x

>>> t = plus_minus(3)
>>> next(t)
3
>>> next(t)
-3

A generator function is a function that yields values instead of returning them.
def a_then_b(a, b):
yield from a
yield from b
>>> list(a_then_b([3, 4], [5, 6]))
[3, 4, 5, 6]

>>> bool(0)
False
>>> bool(1)
True
>>> bool(”)
False
>>> bool(‘0’)
True
>>> bool([])
False
>>> bool([[]])
True
>>> bool({})
False
>>> bool(())
False
>>> bool(lambda x: 0)
True

False values:
•Zero
•False
•None
•An empty string,
list, dict, tuple

All other values
are true values.

>>> today = datetime.date(2019, 10, 13)

Many built-in
Python sequence
operations
return
iterators that
compute results
lazily

map(func, iterable):

filter(func, iterable):

zip(first_iter, second_iter):

reversed(sequence):

Iterate over func(x) for x in iterable

Iterate over x in iterable if func(x)

Iterate over co-indexed (x, y) pairs

Iterate over x in a sequence in reverse order

To view the
contents of
an iterator,
place the
resulting
elements into
a container

list(iterable):

tuple(iterable):

sorted(iterable):

Create a list containing all x in iterable

Create a tuple containing all x in iterable

Create a sorted list containing x in iterable

>>> sum([1, 2])
3
>>> sum([1, 2], 3)
6
>>> sum([])
0
>>> all([False, True])
False
>>> all([])
True

def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-2) + fib(n-1)

0, 1, 2, 3, 4, 5, 6, 7, 8,n:
0, 1, 1, 2, 3, 5, 8, 13, 21,fib(n):def cascade(n):

if n < 10: print(n) else: print(n) cascade(n//10) print(n) >>> cascade(123)
123
12
1
12
123

>>> any([False, True])
True
>>> any([])
False
>>> max(1, 2)
2
>>> max([1, 2])
2
>>> max([1, -2], key=abs)
-2

When a class is called:
1.A new instance of that class is created:
2.The __init__ method of the class is called with the new object as its first

argument (named self), along with any additional arguments provided in the
call expression.

An account instance

Idea: All bank accounts have a balance and an account holder;
the Account class should add those attributes to each of its instances

>>> a = Account(‘Jim’)
>>> a.holder
‘Jim’
>>> a.balance
0

class Account:
def __init__(self, account_holder):
self.balance = 0
self.holder = account_holder
def deposit(self, amount):
self.balance = self.balance + amount
return self.balance
def withdraw(self, amount):
if amount > self.balance:
return ‘Insufficient funds’
self.balance = self.balance – amount
return self.balance

balance: 0 holder: ‘Jim’

__init__ is called a
constructor

self should always be
bound to an instance of
the Account class or a
subclass of Account

A new instance is
created by calling a

class

.
The can be any valid Python expression.
The must be a simple name.
Evaluates to the value of the attribute looked up by in the object
that is the value of the .

Dot expression

Call expression

>>> type(Account.deposit)

>>> type(a.deposit)

>>> Account.deposit(a, 5)
10
>>> a.deposit(2)
12

Function call: all
arguments within

parentheses

Method invocation:
One object before
the dot and other
arguments within

parentheses

Assignment statements with a dot expression on their left-hand side affect
attributes for the object of that dot expression
• If the object is an instance, then assignment sets an instance attribute
• If the object is a class, then assignment sets a class attribute

To evaluate a dot expression:
1. Evaluate the to the left of the dot, which yields

the object of the dot expression
2. is matched against the instance attributes of that object;

if an attribute with that name exists, its value is returned
3. If not, is looked up in the class, which yields a class

attribute value
4. That value is returned unless it is a function, in which case a

bound method is returned instead

or
return super().withdraw( amount + self.withdraw_fee)

class CheckingAccount(Account):
“””A bank account that charges for withdrawals.”””
withdraw_fee = 1
interest = 0.01
def withdraw(self, amount):
return Account.withdraw(self, amount + self.withdraw_fee)

CS 61A Midterm 2 Study Guide — Page 2

>>> jim_account = Account(‘Jim’)
>>> tom_account = Account(‘Tom’)
>>> tom_account.interest
0.02
>>> jim_account.interest
0.02
>>> Account.interest = 0.04
>>> tom_account.interest
0.04
>>> jim_account.interest
0.04

>>> jim_account.interest = 0.08
>>> jim_account.interest
0.08
>>> tom_account.interest
0.04
>>> Account.interest = 0.05
>>> tom_account.interest
0.05
>>> jim_account.interest
0.08

interest: 0.02
(withdraw, deposit, __init__)

balance: 0
holder: ‘Jim’

balance: 0
holder: ‘Tom’

Account class
attributes

0.04

interest: 0.08

0.05

Instance
attributes of
jim_account

Instance
attributes of
tom_account

To look up a name in a class:
1. If it names an attribute in the class, return the attribute value.
2. Otherwise, look up the name in the base class, if there is one.
>>> ch = CheckingAccount(‘Tom’) # Calls Account.__init__
>>> ch.interest # Found in CheckingAccount
0.01
>>> ch.deposit(20) # Found in Account
20
>>> ch.withdraw(5) # Found in CheckingAccount
14

Python object system:

class Link:
empty = ()

Some zero
length sequence

def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest

def __repr__(self):
if self.rest:
rest = ‘, ‘ + repr(self.rest)
else:
rest = ”
return ‘Link(‘+repr(self.first)+rest+’)’

def __str__(self):
string = ‘<' while self.rest is not Link.empty: string += str(self.first) + ' ' self = self.rest return string + str(self.first) + '>‘

Built-in isinstance
function: returns True if
branch has a class that
is or inherits from Tree

for branch in branches:
assert is_tree(branch)
return [label] + list(branches)

Verifies that tree is
bound to a list

Creates a list from a
sequence of branches

def label(tree):
return tree[0]

def branches(tree):
return tree[1:]
def is_tree(tree):
if type(tree) != list or len(tree) < 1: return False for branch in branches(tree): if not is_tree(branch): return False return True def tree(label, branches=[]): Verifies the tree definition def is_leaf(tree): return not branches(tree) >>> tree(3, [tree(1),
… tree(2, [tree(1),
… tree(1)])])
[3, [1], [2, [1], [1]]]

2

1

3

1

1

def leaves(t):
“””The leaf values in t.
>>> leaves(fib_tree(5))
[1, 0, 1, 0, 1, 1, 0, 1]
“””
if is_leaf(t):
return [label(t)]
else:
return sum([leaves(b) for b in branches(t)], [])

def fib_tree(n):
if n == 0 or n == 1:
return tree(n)
else:
left = fib_tree(n-2),
right = fib_tree(n-1)
fib_n = label(left) + label(right)
return tree(fib_n, [left, right])

def is_leaf(self):
return not self.branches

def leaves(tree):
“The leaf values in a tree.”
if tree.is_leaf():
return [tree.label]
else:
return sum([leaves(b) for b in tree.branches], [])

def fib_tree(n):
if n == 0 or n == 1:
return Tree(n)
else:
left = fib_Tree(n-2)
right = fib_Tree(n-1)
fib_n = left.label+right.label
return Tree(fib_n,[left, right])

2

3

1

0 1 1 1

0 1

Root label
Branch

Leaf

Labels

NodesPathRecursive description:
•A tree has a root label
and a list of branches
•Each branch is a tree
•A tree with zero branches
is called a leaf

Relative description:
•Each location is a node
•Each node has a label
•One node can be the
parent/child of another

class Tree:
def __init__(self, label, branches=[]):
self.label = label
for branch in branches:
assert isinstance(branch, Tree)
self.branches = list(branches)

first: 4

rest:

Link instance

first: 5

rest:

Link instance

>>> s = Link(4, Link(5))
>>> s
Link(4, Link(5))
>>> s.first
4
>>> s.rest
Link(5)
>>> print(s)
<4 5>
>>> print(s.rest)
<5>
>>> s.rest.rest is Link.empty
True

Root or Root Node

def count_partitions(n, m):
if n == 0:
return 1
elif n < 0: return 0 elif m == 0: return 0 else: with_m = count_partitions(n-m, m) without_m = count_partitions(n, m-1) return with_m + without_m • Recursive decomposition: finding simpler instances of a problem. • E.g., count_partitions(6, 4) • Explore two possibilities: • Use at least one 4 • Don't use any 4 • Solve two simpler problems: • count_partitions(2, 4) • count_partitions(6, 3) • Tree recursion often involves exploring different choices. def sum_digits(n): "Sum the digits of positive integer n." if n < 10: return n else: all_but_last, last = n // 10, n % 10 return sum_digits(all_but_last) + last • The def statement header is like any function • Conditional statements check for base cases • Base cases are evaluated without recursive calls • Recursive cases are evaluated with recursive calls Anatomy of a recursive function: