cs61a：从入门到入土

Readme

一直想学，无奈，由于平时的作业很多，学业压力比较重，学了几节课就没有学了。

决定前面的就简单温习一下吧。不复习又不行，基本全忘记了，只记得自己学过。

炎热的夏天不想出门，适合在房间开着空调吃着西瓜玩着手机学习python。

希望这个暑假能肝完。

版本：CS 61A Fall 2021

Week 1

使用ok的方法

这是这门课的亮点之一，利用简单的命令行的知识来检测你写出来的程序是否正确，并且每一个case都会告诉你是什么应该输出什么而你输出了什么，从而判断正确与否。

（在此点名华大的oj，什么都不给，只告诉你AC或WA等等，改都不知道怎么改）

之前没学过git，估计用git更简单。

win+R，输入cmd

然后在命令行界面输入powshell

在powershell里用cd ~/Desktop/cs61a/…来进入相应的位置

然后粘贴题目提供的含ok语句即可

vscode可以和power shell交互，故可省去第一步

可以直接用git bash here进入相应的位置，然后粘贴ok语句即可

Functions

expressions

即表达式，具体讲解了表达式嵌套时应遵循一定的顺序

name

• from math import pi

• 可自行定义一个function的名称，例如：

• def square(x)
      return mul(x,x)
  * ```python
    def area()
    	return pi*radius*radius
  

• 可通过更改radius的值来改变area的值

environment diagrams

to visualize the interpreter’s process

（个人认为就是把程序的进行过程列出来方便理解

defining functions

def <name>(<formal parameters>):
    return <return expression>

def这一行的后面一定不要忘了有冒号！

Week 2

Control

Print and None

我理解的是，print输出了一个数，但是返回None（即什么都不返回）

而return返回了这个数

Multiple Environments

指的是def的函数嵌套，应该从里向外展开

Some features

除法 “/“

2013/10

from operator import truediv,floordiv
>>>truediv(2013,10)
201.3

2013//10（舍去后面的数，非四舍五入）

from operator import truediv,floordiv
>>>floordiv(2013,10)
201

A%B=mod(A,B)

定义函数的时候可以给形参赋值，调用时可以不把已被赋值的参数写出来

Conditional Statements

类似于C++中的if语句，仅语法有所差别

关心的是Boolean语句的对或错，而不关注表达式本身

Iteration（迭代）

讲的是while循环

while (condition):
    statements

Higher-Order Functions

when designing functions

• give each function exactly one job
• do not repeat yourself (DRY). implement a process just once,but execute it many times.
• define functions generally

可以用assert来检查输入的数据是否符合标准

格式：assert （A），（B）

assert r>0,'A length must be positive.'

即A语句为一个bool语句。如果判断为false，则程序报错并输出B语句

不要忘了pow函数！pow(k,3)即为求k的三次方

higher-order functions

A higher order function (HOF) is a function that manipulates other functions by taking in functions as arguments, returning a function, or both.

类似C++中函数之间的相互调用

• Express general methods of computation
• Remove repetition from programs
• Separate concerns among functions

lambda expressions

与def类似，但是lambda expressions不能包含statements

lambda的是变量

使用格式：

square=lambda x:x*x
>>>square(4)

与def的区别：

即def给了函数一个具体的名称，而lambda没有给，除非自己给它命名一个

conditional expressions

form：ifelse

evaluation rule:

• Evaluate the expression.
• If it’s a true value, the value of the whole expression is the value of the
• Otherwise, the value of the whole expression is the value of the

Environments for Higher-Order Functions

nested functions（嵌套）

def make_adder(n):
    def adder(k):
        return k+n
    return adder

How to draw an environment dragram

function currying

即higher-order function

比如：

def curry2(f):
    def g(x):
        def h(y):
            return f(x,y)
        return h
    return g

>>>curry2=lambda f:lambda x:lambda y:f(x,y)
>>>m=curry2(add)
>>>m(2)(3)
5

currying：Transforming a multi-argument function into a single-argument,higher-order function

Disc 01: Control,Environment Diagrams

罗列几个与C++不同的注意点

• Boolean Operators中不要像C++一样使用&&和||，而是要使用and，or，not
• 不要使用i++，用i=i+1或i+=1
• python打印是自动换行的

Week 3

Design

Naming

• 不注重正确性而注重可读性。应该包含变量的meaning or purpose
• 长的name通常易读，如：average_age=average(age, students)
• 短的name通常是大家常用的符号。如：n, k, i for integers; x, y, z for real numbers and f, g, h for functions

Week 4

Recursion

Definition：the body of the function calls itself，either directly or indirectly

Anatomy：

• Base case：Evaluated without a recursive call（the smallest subproblem）
• Recursive case：Evaluated with a recursive call（breaking down the problem further）
• Conditional atatement：to decide of it’s a base case

Recursion and Iteration

Recursion：updates via assignment become…

​ 如digit_sum=digit_sum+last

Iteration：…arguments to a recursive call

​ 如return sum_digits_rec(n,digit_sum+last)

Tree Recursion

Tree-shaped processes arise whenever executing the body of a recursive function makes more than one call to that function

Week 5

Containers

Lists

>>>digits=[1,8,2,8]

The number of elements：len(digits)

An element selected by its index：digits[3] or getitem(digits,3)

Concatenation and repetition：[2,7]+digits*2 or add([2,7],mul(digits,2)) =[2,7,1,8,2,8,1,8,2,8]

Nested lists：pairs=[[10,20],[30,40]]

​ pairs[1]=[30,40] pairs[1][0]=30

>>>1 in digits
True
>>>5 in digits
False
>>>'1'==1
False
>>>'1' in digits
False

For Statements

for循环与lists很搭

for <name> in <expression>:
    <suite>

如：

pairs=[[1,2],[2,2],[3,2],[4,4]]
same_count=0
for x,y in pairs:
    if x==y:
        same_count+=1

Ranges

A range is a sequence of consecutive integers.

如range(-2,2)表示-2，-1，0，1；range(4)=range(0,4)表示0，1，2，3

Length：ending value - starting value

Element selection：starting value + index

>>>list(range(-2,2))
[-2,-1,0,1]

def cheer():
    for _ in range(3):
        print('Go Bears!')

List Comprehentions

构建list的方式：

>>>odds=[1,3,5,7,9]
>>>[x+1 for x in odds]
[2,4,6,8,10]
>>>[x for x in odds if 25%x==0]
[1,5]
>>>lambda n:[x for x in range(2,n) if n%x==0]

Strings

“” or ‘’均可

“””…”””注释

Length and element selection are similar to all sequences.

However, the “in” and “not in” operators match substrings.

>>>city='Berkeley'
>>>len(city)
8
>>>city[3]
'k'
>>>'here' in "where's Waldo?"
True

Sequences

Slicing

>>>odds=[3,5,7,9,11]
>>>list(range(1,3))
[1,2]
>>>[odds[i] for i in range(1,3)]
[5,7]
>>>odds[1:3]
[5,7]
>>>odds[:3]
[3,5,7]
>>>odds[1:]
[5,7,9,11]
>>>odds[:]
[3,5,7,9,11]

Slicing creates new values.

String is like a list and the functions can use slicing. For example:

def reverse(s):
    if len(s)==1:
        return s
    else:
        return reverse(s[:1])+s[0]

Processing Container Values

• sum(iterable[, start])–>value

（not strings

>>>sum[2,3,4]
9
>>>sum[[2,3,4],5]
14

• max(iterable[, key=func])–>value

  max(a, b, c, …[, key=func])–>value

• all(iterable)–>bool

Return True if bool(x) is True for all values x in the iterable.

If the iterable is empty, return True.

>>>bool(0)
False #除此之外均为True
>>>bool('hello')
True
>>>bool('')
False
>>>[x<5 for x in range(5)]
[True, True, True, True, True]
>>>all([x<5 for x in range(5)])
True
>>>all(range(5))
Flase

Data Abstraction

类似C++中的类

Dictionaries

Dictionaries are collections of key-value pairs.

Dictionary keys do have two restrictions:

• A key of a dictionary cannot be a list or a dictionary.
• Two keys cannot be equal; There can be at most one value for a given key.

如

>>>numerals= {'I': 1, 'V': 5,'X': 10}
>>>numerals{'X'}
10
>>>list(numerals)
['I','V','X']
>>>numerals.values()
dict_values([1,5,10])
>>>list(numerals.values())
[1,5,10]
>>>sum(numerals.values())
16

>>>d={1:['first','second'],3:'third'}
>>>len(d)
2
>>>d[1]
['first','second']
>>>d[3]
'third'

Dictionary Comprehensions

{<key exp>:<value exp> for <name> in <iter exp> if <filter exp>}
{<key exp}:<value exp> for <name> in <iter exp>

如：

{x*x:x for x in [1,2,3,4,5] if x>2} == {9:3,16:4,25:5}

Week 6

Trees

The Tree Abstraction

A tree has a root label and a list of branches.

Each branch is a tree.

• root: the node at the top of the tree
• label: the value in a node
• branches: a list of trees directly under the tree’s root
• leaf: a tree with zero branches
• node: any location within the tree (e.g., root node, leaf nodes, etc.)
• Depth: the distance of a node and the root
• Height: The depth of the lowest (furthest from the root) leaf.

def tree(label,branches=[]):
    for branch in branches:
        assert is_tree(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 is_leaf(tree):
    return not branches(tree)

>>>tree(1)
[1]
>>>is_leaf(tree(1))
True
>>>t=tree(1,[tree(5,[tree(7)]),tree(6)])
>>>t
[1,[5,[7]],[6]]
>>>label(t)
1
>>>branches(t)
[[5,[7]],[6]]

补充：the difference from tree class and tree abstraction

-	Tree constructor and selector functions	Tree class
Constructing a tree	To construct a tree given a label and a list of branches, we call tree(label, branches)	To construct a tree object given a label and a list of branches, we call Tree(label, branches) (which calls the Tree.__init__ method).
Label and branches	To get the label or branches of a tree t, we call label(t) or branches(t) respectively	To get the label or branches of a tree t, we access the instance attributes t.label or t.branches respectively.
Mutability	The functional tree data abstraction is immutable because we cannot assign values to call expressions	The label and branches attributes of a Tree instance can be reassigned, mutating the tree.
Checking if a tree is a leaf	To check whether a tree t is a leaf, we call the convenience function is_leaf(t)	To check whether a tree t is a leaf, we call the bound method t.is_leaf(). This method can only be called on Tree objects.

Tree Progressing

Creating Trees：A function that creats a tree from another tree is typically alse recursive.

def increment_leaves(t):
    if is_leaf(t):
        return tree(label(t)+1)
    else:
        bs=[increment_leaves(b) for b in branches(t)]
        return tree(label(t),bs)
def increment(t):
    return tree(label(t)+1,[increment(b) for b in branches(t)])

Example-Printing Trees

def print_tree(t):
    print(label(t))
    for b in branches(t):
        print_tree(b)

优化后能显示树的结构：

def print_tree(t,indent=0):
    print(' '*indent+str(label(t)))
    for b in branches(t):
        print_tree(b,indent+1)

Example-Summing Paths

def print_sums(t,so_far):
    so_far=so_far+label(t)
    if is_leaf(t):
        print(so_far)
    else:
        for b in branches(t):
            print_sums(b,so_far)

Example-Counting Paths

def count_paths(t,total):
    if label(t)==total:
        found=1
    else:
        found=0
    return found+sum([count_paths(b,total-label(t)) for b in branches])

Mutability

Mutation Operations

对list的操作：

移出元素：.pop()和.remove(…)。前者弹出最后一个元素，后者可移出任意一个元素

增加元素：.append(…)和.extend(…)

替换元素：采取切片赋值的方法

>>>suits=['coin','string','myriad']
>>>original_suits=suits
>>>suits.pop()
'myriad'
>>>suits.remove('string')
>>>suits
['coin']
>>>suits.append('cup')
>>>suits.extend(['sword','club'])
>>>suits
['coin','cup','sword','club']
>>>suits[2]='spade'
>>>suits[0:2]=['heart','diamond']
>>>suits
['heart','diamond','spade','club']
>>>original_suits
['heart','diamond','spade','club']   #interesting!

Some Objects Can CHange

The same object can change in value throughout the course of computation.

All names that refer to the same object are affected by a mutation.

Only objects of mutable types can change: lists & dictionaries.

Tuples（元组）

immutable sequences, meanings of these cannot be changed.

使用()，其余与list基本类似

>>>(3,4,5,6)
(3,4,5,6)
>>>(1,2)+(3,4)
(1,2,3,4)
>>>()
()
>>>tuple()
()
>>>tuple([3,4,5])
(3,4,5)
>>>3,4,5,6
(3,4,5,6)
>>>2,
(2,)
>>>2
(2)

A dictionary cannot use a list as its index but can use a tuple. However, a tuple used as a index cannot include a list. For example:

>>>{(1,2):3}
{(1,2):3}
>>>{[1,2]:3}
TypeError: unhashable type: 'list'
>>>{(1,[2]):3}
TypeError: unhashable type: 'list'

An immutable sequence may still change if it contains a mutable value as an element. For example:

>>>s=([1,2],3)
>>>s[0]=4
ERROR
>>>s[0][0]=4
>>>s
([4,2],3)

Mutation

Sameness and Change

• A compound data object has an “identity” in addition to the pieces of which it is composed
• A list is still “the same” list even if we change its contents
• Conversely, we could have two lists that happen to have the same contents, but are different

Identity Operators

• 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.

Syntax

Data Abstraction for Syntax

用树的观念来分析英语语法

def phrase(tag, branches):
    return tree(tag, branches)

def word(tag, text):
    return tree([tag, text])

def tag(t):
    """Return the tag of a phrase or word."""
    if is_leaf(t):
        return label(t)[0]
    else:
        return label(t)

def text(word):
    return label(word)[1]

Parsing

Some files are plain text and can be read into Python as either.

• open(…) . read()：One string containing the whole contents of the file
• open(…) . readlines()：A list of strings, each containing one line

Useful string methods for processing the contents of a file.

• .strip()：returns a string without whitespace (spaces, tabs, etc.) on the ends

  >>>'hello '.strip()
  'hello'

• .split()：returns a list of strings that were separated by whitespace

  >>>'hi there'.split()
  ['hi','there']

• .replace(a,b)：returns a string with all instances of string a replaces by string b

  >>>'2+2'.replace('+',' + ')
  '2 + 2'

From lines to tokens：

use open(…).readlines()：

['(ROOT (S (NP (NN this)) (VP (COP is) (NP (DT a) (NN book))) (. ?)))\n'
'\n',..

to

[['(', 'ROOT', '(', 'S', '(', 'NP', '(', 'NN', 'this', ')', ')',
'(', 'VP', '(', 'COP', 'is', ')', '(', 'NP', '(', 'DT', 'a', ')',
'(', 'NN', 'book', ')', ')', ')', '(', '.', '?', ')', ')', ')'],
...]

read_sentences takes care of this：

lines = open('suppes.parsed').readlines()
tokens = read_sentences(lines)

Generating Language

language models：A statistical（or probabilistic） language model describes how likely some text would be.

Sampling from a statistical language model uses what description to generate language.

详见https://code.cs61a.org/
#Syntax
treebank_examples = """
(ROOT (SBARQ (WHNP (WP what))
     (SQ (VP (AUX is)) (NP (DT the) (NN rabbit)) (VP (VBG doing)))
     (. ?)))

(ROOT (SQ (AUX is) (NP (PRP he)) (VP (VBG hopping)) (. ?)))

""".split('\n')
def phrase(tag,branches):
    return tree(tag,branches)
def word(tag,text):
    return tree([tag,text])
def tag(t):
    """Return the tag of a phrase or word."""
    if is_leaf(t):
        return label(t)[0]    #树叶包含tag和text
    else:
        return label(t)
def text(word):
    return label(word)[1]
def read_sentences(input):
     """Yield parsed sentences as lists of tokens for a list of lines.

    >>> for s in read_sentences(treebank_examples):
    ...     print(' '.join(s[:20]), '...')
    ( ROOT ( SBARQ ( WHNP ( WP what ) ) ( SQ ( VP ( AUX is ) ) ...
    ( ROOT ( SQ ( AUX is ) ( NP ( PRP he ) ) ( VP ( VBG hopping ...
    """
    sentences=[]
    tokens=[]
    for line in input:
        if line.strip():
            tokens.extend(line.replace('(',' ( ').replace(')',' ) ')).split()
            if tokens.count('(')==tokens.count(')'):
                sentences.append(tokens)
                tokens=[]
    return sentences
def all_sentences():
    return read_sentences(open('suppes.parsed').readlines())
def tokens_to_parse_tree(tokens):
    """Return a tree for a list of tokens representing a parsed sentence.

    >>> print_tree(tokens_to_parse_tree(read_sentences(treebank_examples)[0]))
    ROOT
      SBARQ
        WHNP
          ['WP', 'what']
        SQ
          VP
            ['AUX', 'is']
          NP
            ['DT', 'the']
            ['NN', 'rabbit']
          VP
            ['VBG', 'doing']
        ['.', '?']
    """
    assert tokens[0] == '(', tokens
    t, end = read_parse_tree(tokens, 1)
    return t
def is_valid_tree(t):
    return t and tag(t)
def read_parse_tree(tokens, i):   #这个好难懂
    """Return a tree for the next constitutent of a token iterator and the end index."""
    tag = tokens[i]
    i += 1
    if tokens[i] != '(':
        assert tokens[i+1] == ')'
        return word(tag, tokens[i]), i + 2
    branches = []
    while tokens[i] != ')':
        assert tokens[i] == '('
        branch, i = read_parse_tree(tokens, i + 1)
        if is_valid_tree(branch):
            branches.append(branch)
    if branches:
        return phrase(tag, branches), i + 1
    else:
        return None, i + 1

Week 7

Iterators

Iterators

A container can provide an iterator that provides access to its elements in some order.

• iter(iterable)：Return an iterator over the elements of an iterable value
• next(iterator)：Return the next element in an iterator

>>>s=[[1,2],3,4,5]
>>>t=iter(s)
>>>next(t)
[1,2]
>>>next(t)
3
>>> list(t)
[4,5]
>>>next(t)
StopIteration

There are also some built-in functions that take in iterables and return useful results:

• map(f, iterable) - Creates an iterator over f(x) for x in iterable. In some cases, computing a list of the values in this iterable will give us the same result as [func(x) for x in iterable]. However, it’s important to keep in mind that iterators can potentially have infinite values because they are evaluated lazily, while lists cannot have infinite elements.
• filter(f, iterable) - Creates an iterator over x for each x in iterable if f(x)
• zip(iterables*) - Creates an iterator over co-indexed tuples with elements from each of the iterables
• reversed(iterable) - Creates an iterator over all the elements in the input iterable in reverse order
• list(iterable) - Creates a list containing all the elements in the input iterable
• tuple(iterable) - Creates a tuple containing all the elements in the input iterable
• sorted(iterable) - Creates a sorted list containing all the elements in the input iterable
• reduce(f, iterable) - Must be imported with functools. Apply function of two arguments f cumulatively to the items of iterable, from left to right, so as to reduce the sequence to a single value.

Dictionary Iteration

An iterable value is any value that can be passed to iter to produce an iterator.

An iterator is returned from iter and can be passed to next; all iterators are mutable.

A dictionary, its keys, its values, and its items are all iterable values.

For example:

>>>d={'one':1, 'two':2, 'three':3}
>>>d['zero']=0    #往d中新增加了元素
>>>k=iter(d.keys())   #or k=iter(d)
>>>next(k)
'one'
>>>next(k)
'two'
>>>next(k)
'three'
>>>next(k)
'zero'
>>>v=iter(d.values())
>>>next(v)
1
>>>next(v)
2
>>>next(v)
3
>>>next(v)
0
>>>i=iter(d.items())
>>>next(i)
('one',1)
>>>next(i)
('two',2)
>>>next(i)
('three',3)
>>>next(i)
('zero',0)

ATTENTION：dictionary cannot change size during iteration. For example:

>>>d={'one':1,'two':2}
>>>k=iter(d)
>>>next(k)
'one'
>>>d['zero']=0
RuntimeError:dictionary changed size during iteration

Zip

• The built-in zip function returns an iterator over co-indexed tuples.

• If one iterable is longer than the other, zip only iterates over matches and skips extras

• More than two iterables can be passed to zip

>>>list(zip([1,2],[3,4]))
[(1,3),(2,4)]
>>>list(zip([1,2],[3,4,5]))
[(1,3),(2,4)]
>>>list(zip([1,2],[3,4,5],[6,7]))
[(1,3,6),(2,4,7)]

Generators

Generator Function

• A generator function is a function that yields values instead of returning them.
• A normal function returns once; a generator function can yield multiple times
• A generator is an iterator created automatically by calling a generator function
• When a generator function is called, it returns a generator that iterates over its yields

>>>def plus_minus(x):
    tield x
    yield -x
>>>t=plus_minus(3)
>>>next(t)
3
>>>next(t)
-3

for x in coutdown(k-1)
	yield x
#等价于
yield from coutdown(k-1)

A yield from statement can be used to yield the values from an iterable one at a time.

A Return Statement Within a Generator Function

Upon executing a return statement, a generator function exits and cannot yield more values.

What’s more, providing a value to be returned is allowed, but this value is not yielded.

For example:

def f(x):
    yield x
    yield x+1
    return
	yield x+3
>>>list(f(2))
[2,3]

def g(x):
    yield x
    yield x+1
    return x+2
	yield x+3
>>>list(g(2))
[2,3]

It’s possible to access the returned value:

def h(x):
    y=yield from g(x)
    yield y
>>>list(h(2))
[2,3,4]

Objects

开始面向对象了…

Object-Oriented Programming

• class: a template for creating objects
• instance: a single object created from a class
• instance variable: a data attribute of an object, specific to an instance
• class variable: a data attribute of an object, shared by all instances of a class
• method: a bound function that may be called on all instances of a class

Class Statements

格式：

class<name>:
    <suite>

Every call to a class creates a new instance(对象). There’re many instances but only one class.

Binding an object to a new name using assignment does not create a new object. It just gives a new name to the object. For example:

>>>c=a
>>>c is a
True

Methods

Methods are defined in the suite of a class statement.

The def statements create function objects as always, but their names are bound as attributes of the class.

All invoked methods have access to the object via the self parameter, and so they can all access and manipulate the object’s state. For example:

class Account:
    def deposit(self,amount):            #Defined with two arguments
        self.balance=self.balance+amount
        return self.balance
>>>tom_account=Account('Tom')
>>>tom_account.deposit(100)              #Invoked with one argument
100

Class Methods(*)

Now we’ll try out another feature of Python classes: class methods. A method can be turned into a class method by adding the classmethod decorator. Then, instead of receiving the instance as the first argument (self), the method will receive the class itself (cls).

Class methods are commonly used to create “factory methods”: methods whose job is to construct and return a new instance of the class.

For example, we can add a robo_factory class method to our Dog class that makes robo-dogs:

class Dog(Pet):
    # With the previously defined methods not written out
    @classmethod
    def robo_factory(cls, owner):
        return cls("RoboDog", owner)

Then a call to Dog.robo_factory('Sally') would return a new Dog instance with the name “RoboDog” and owner “Sally”.

Attributes

Attributes are all public.

Accessing Attributes:

• getattr(object,’…’):

>>>getattr(tom_account,'balance')
10

getattr and dot expressions look up a name in the same way.

• hasattr(object,’…’): 用来判断对象是否包含对应的属性

>>>hasattr(tom_account,'deposit')
True

Class attributes are “shared” across all instances of a class because they are attributes of the class, not the instance. For example:

class Account:
    interest=0.02  #A class attribute
    def _init_(self,account_holder):
        self.balance=0
        self.holder=account_holder
    #Additional methods would be difined here
>>>tom_account=Account('Tom')
>>>jim_account=Account('Jim')
>>>tom_account.interest
0.02
>>>jim_account.interest
0.02

• Instance Attribute Assignment: tom_account.interest=0.08
  • adds or modifies the attribute named “interest” of tom_account（仅改变这个对象中这个属性的值
• Class Attribute Assignment: Account.interest=0.04
  • 改变整个class中这个属性的值

Week 8

Inheritance

Inheritance is a method for relating classes together.

A common use：Two similar classes differ in their degree of specialization.

格式：

class <name>(<base class>):   #单继承
    <suite>

class <name>(<base class>,<base class>...):   #多继承
    <suite>

For example:

class CheckingAccount(Account):     #CheckingAccount继承了Account
    """A bank zccount that charges for withdrawals."""
    withdraw_fee=1
    interest=0.01
    def withdraw(self,amount):
        return Account.withdraw(self.amount+self.withdraw_fee)

The new subclass shares attributes with its base class.

Using inheritance, we implement a subclass by specifying its differences from the base class.

Looking Up Attribute Names on Classes

To look up a name in a class:

• if it names an attribute in the class, return the attribute value.
• Otherwise, look up the name in the base class, if there is one.

即如果自己定义了新属性按新属性来，没有新定义的话就找继承的class看有没有相应的属性

类的继承，调用父类的属性和方法参考：

https://blog.csdn.net/yilulvxing/article/details/85374142?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-85374142-blog-123801693.pc_relevant_multi_platform_featuressortv2removedup&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1-85374142-blog-123801693.pc_relevant_multi_platform_featuressortv2removedup&utm_relevant_index=1

Representation

String Representation

• dir(object)：returns a list of all the attributes on an object
• _str_()：returns a human readable string representation of an object
• _repr_()：returns a string that would evaluate to an object with the same values

f string

String interpolation involves evaluating a string literal that contains expressions.

• Using string concatenation:

  >>>from math import pi
  >>>'pi starts with'+str(pi)+'...'
  'pi starts with 3.141592653589793...'
  >>>print('pi starts with'+str(pi)+'...')
  pi starts with 3.141592653589793...

• Using string interpolation:

  >>>f'pi starts with (pi)...'
  'pi starts with 3.141592653589793...'
  >>>print(f'pi starts with (pi)...')
  pi starts with 3.141592653589793...

**{}**中的值会被算出来

Polymorphic Functions（多态）

Polymorphic function：A function that applies to many (poly) different forms (morph) of data

For example：str and repr are both polymorphic.

repr 和_repr_的区别：repr invokes a zero-argument method _repr_ on its argument

…to be continued

Special Method Names

Name	Behavior
_init_	Method invoked automatically when an object is constructed
_repr_	Method invoked to display an object as a Python expression
_str_	Methof invoked to stringify an object
_add_	Method invoked to add one object to another
_bool_	Method invoked to convert an object to True or False
_float_	Method invoked to convert an object to a float(real number)

For example:

>>>one+two
3
>>>one.__add__(two)
3

……

就是一些有特殊功能的函数前后会各有两个下划线

Recursive Objects

Linked Lists(链表)

Linked List Class

A linked list is either empty or a first value and the rest of the linked list.

每个link分为first和rest两部分

linked list class: attributes are passed to _init_

class Link:
    def __init__(self,first,rest=empty):
        assert rest is Link.empty or isinstance(rest,Link)   #Returns whether rest is a Link
        self.first=first
        self.rest=rest

Linked Lists Can Change

Attribute assignment statements can change first and rest attributes of a Link.

The rest of a linked list can contain the linked list as a sub-list

如果想在链表下标0处插入一个元素，可以直接将新元素的下一位指向原先的链表头

Week 9

Efficiency

开始考虑程序的运行时间了…

Memoization

def memo(f):
    cache={}
    def memorized(n):
        if n not in cache:
            cache[n]=f(n)
        return cache[n]
    return memorized

本节用的是斐不那几树的例子：

即如果这一个分支在前面已经出现过了，那么在这一步中就会跳过，这样大大地减少了迭代的次数

Orders of growth

​ Constant growth. Increasing n doesn’t affect time.

Decomposition（分解

也就是将各个功能分开撰写与调试

Week 11

似乎到这里换了种语言——scheme

Scheme

Scheme 编程语言是一种Lisp方言

是第一个引入“干净宏”的编程语言

Scheme programs consist of expressions, whichcan be:

• Primitive expressions：2, 3.3, true, +,quotinent…
• Combinations：(quotient 10 2), (not true), …

For example:

scm> (quotient 10 2)
5
scm>(+)
0
scm>(*)
1
scm>(* 2 2 2 2 2 3 3 3)
864

Special forms

A combination that is not a call expression is a special form:

• If expression： (if )

• And and or： (and … ) (or …)

• Binding symbols（定义常量）：(define )

• New procedures（定义函数，symbol是函数名，formal parameters是变量名）：

  (define () )

For example:

> (define pi 3.14)
>(* pi 2)
6.28
>(define (abs x)
   (if (< x 0)
       (- x)
       x))
>(abs -3)
3

• Lambda expressions： (lambda () )

Two equivalent expressions：

(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4)))

An operator can be a call expression too：

((lambda (s y z) (+ x y (square z))) 1 2 3)

More special forms

Cond

The cond special form that behaves like if-elif-else statements in Python

(cond ((<条件>) (<expressions>))
      ((<条件>) (<expressions>))
      ...
      (else (<expressions>)))

Begin

The begin special form combines multiple expressions into expression

...begin(<expression1>)(<expression2>)

Let

The let special form binds symbols to values temporarily; just for one expression

Lists

• cons：Two-argument procedure that creates a linked list
• car：Procedure that returns the first element of a list
• cdr：Procedure that returns the rest of a list
• nil：The empty list

Important! Scheme lists are written in parentheses with elements separated by spaces

For example：

> (cons 1 (cons 2 nil))
(1 2)

Symbolic Programming

Symbols normally refer to values; how do we refer to symbols?

>(define a 1)
>(define b 2)
>(list a b)
(1 2)  #No sign of "a" and "b" in the resulting value

Quotation is used to refer to symbols directly in Lisp

‘a == (quote a)

>(list 'a 'b)
(a b)
>(list 'a b)
(a 2)

Quotation can also be applied to combinations to form lists

>'(a b c)
(a b c)
>(car '(a b c))
a
>(cdr '(a b c))
(b c)

Exceptions

Quasiquotation

Two ways to quote an expression

Quote: ‘(a b) => (a b)

Quasiquote: `(a b) => (a b)

They are different because parts of a quasiquoted expression can be unquoted with

​ (define b 4)

Quote: ‘(a, (+ b 1)) => (a (unquote (+ b 1)))

Quasiquote: `(a, (+ b 1)) => (a 5)

Example：While Statements

#python
x=2
total=0
while x<10:
    total=total+x*x
    x=x+2

#scheme
(define (f x total)
  (if (< x 10)
      (f (+ x 2) (+ total (* x x)))
      total))
(f 2 0)

Exceptions

Assert Statements

assert <expression>, <string>

Assertions are disigned to be used liberally. They can be ignored to increase efficiency by running Python with the “-0” flag. “0” stands for optimized.

Raise Statements

Exceptions are raised with a raise statement.

raise <expression>

E.g. raise TypeError(‘Bad argument!’)

• TypeError——A function was passed the wrong number/type of argument
• NameError——A name wasn’t found
• KeyError——A key wasn’t found in a dictionary
• RuntimeError——Catch-all for troubles during interpretation

Try Statements

是在面临上述exceptions时

Try statements handle exceptions

try:
    <try suite>
except <exception class> as <name>:
    <except suite>
...

Executing rule:

The is executed first

If, during the course of executing the , an exception is raised that is not handled otherwise, and if the class of the exception inherits from ,

Then the is executed, with bound to the exception.

For example:

>>>try:
    	x=1/0
   except ZeroDivisionError as e:
    	print('handling a', type(e))
        x=0
handling a <class 'ZeroDivisionError'>
>>>x
0

Multiple try statements: Control jumpps to the except suite of the most recent try statement that handles that type of exception.

Calculator

The Pair class represents Scheme pairs and lists. A list is a pair whose second element is either a list or nil

Scheme expressions are represented as Scheme lists!

Calculator Semantics

The value of a calculator expression is defined recursively.

Primitive: A number evaluates to itself

Call: A call expression evaluates to its argument values combined by an operator

week 12

Tail Calls

A procedure call taht has not yet returned is active. Some procedure calls are tail calls. A Scheme interpreter should support an unbounded number of active tail calls using only a constant amount of space.

A tail call is a call expression in a tail context:

• The last body sub-expression in a lambda expression
• Sub-expressions 2&3 in a tail context if expression
• All non-predicate sub-expressions in a tail context cond
• The last sub-expression in a tail context and or or
• The last sub-expression in a tail context begin

Tail Recursion：尾递归

在尾递归中只有前进的过程，而在普通递归中还有压栈、栈的回退、栈空等过程。

【1】在尾递归中，其实只有前进的过程，也就是顺藤摸瓜（瓜就是返回结果）。摸到瓜结束。
【2】在普通递归中，我们摸到了瓜（这个瓜在这里指的是递归的base case），你还得记住你怎了顺的藤（将中间过程压栈），然后在把瓜顺着藤捣腾回去（栈的回退），直到到了最初的起点（栈空）。然后返回。

Regular Expressions

Types of Programming

• Imperative programming（命令式编程）：Describe what you want a computer to do

  Often involves mutation for the purpose of computing a result

  Computational efficiency is often determined by the details of the program

  E.g. oop is a useful way of organizing imperative programs.

• Declarative programming（声明式编程）：Describe the result you want a computer to produce

  Often abstracts away the details of how memory is changing during computation

  Computational efficiency is often determined by the interpreter or language

  E.g. functional programming（函数式编程） describes a result using function composition

• General-purpose languages：Designed to describe any computation

  Python, Scheme, Javascript, Java, C, C++, etc

  Languages differ in the programming styles that they promote

  Language features make some languages more suitable to certain applications

• Domain-specific languages：Designed to solve particular classes of problems

  SQL, HTML, CSS, regular expressions, etc

  Often declarative in character：the language describes what to compute/create, not how

  Often embedded into general-purpose languages

Character classes

Class	Description
[abc]	Matches a, b, or c
[a-z]	Matches any character between a and z
[^A-Z]	Matches any character that is not between A and Z.
\w	Matches any “word” character. Equivalent to [A-Za-z0-9_]
\d	Matches any digit. Equivalent to [0-9].
[0-9]	Matches a single digit in the range 0 - 9. Equivalent to \d
\s	Matches any whitespace character (spaces, tabs, line breaks).
.	Matches any character besides new line.

Week 13

Backus-Naur Form

详见百度百科或wiki

尖括号( < > )内包含的为必选项。

方括号( [ ] )内包含的为可选项。

大括号( { } )内包含的为可重复0至无数次的项。

竖线( | )表示在其左右两边任选一项，相当于”OR”的意思。

::= 是“被定义为”的意思

SQL

Databases

数据库

In declarative languages such as SQL &Prolog:

• A “program” is a description of the desired result
• The interpreter figures out how to generate the result

In imperative languages such as Python & Scheme:

• A “program” is a description of computational processes
• The interpreter carries out execution/evaluation rules

create table cities as
	select 38 as latitude, 122 as longitude, "Berkeley" as name union
	select 42 as latitude, 71 as longitude, "Cambridge" as name union
	select 45 as latitude, 93 as longitude, "Minneapolis";
select "west coast" as region, name from cities where longitude >=115 union
select "other", as region, name from cities where longitude < 115;

Structured Query Language（SQL）

• A select statement creates a new table, either from scratch or by projecting a table
• A create table statement gives a global name to a table
• Lots of other statements exist：analyze, delete, explain, insert, replace, update, etc
• Most of the important action is in the select statement
• The code for executing select statements fits on a single sheet of paper

select [expression] as [name], [expression] as [name]

The result of a select statement is displayed to the user, but not stored

A create table statement gives the result a name

For example：

create table parents as
	select "abraham" as parent, "barack" as child union
	...
	select "eisenhower" as parent, "fillmore";

projecting tables

Tables

Creating tables with SELECT

create table top_music_videos as
	select title, views from songs order by views DESC;

Creating tables with UNION

create table music_movies as
	select "Mamma Mia" as title, 2008 as release_year union
	select "Olaf's Frozen Adventure", 2017 union
	select "Moulin Rouge", 2001;

2-step table creation

createtable musical_movies (title text, releas_year interger);
insert into musical_movies values ("Mamma Mia",2008);
insert into musical_movies values ("Olaf's Frozen Adventure", 2017);

Week14

Aggregation

Aggregate functions

SELECT [columns] FROM [table] WHERE [expression];

SELECT MAX(columns) FROM [table];

For example：

select body, max(mean_radius) from solar_system_objects;
select sum(mass) from solar_system_objects;

Group

Grouping rows

rows in a table can be grouped using group by

SELECT [columns] FROM [table] GROUP BY [expression];

For example：

select legs, max(weight) from animals group by legs;

Filtering groups

using having clause

SELECT [columns] FROM [table] GROUP BY [expression] HAVING [expression];

For example：

select weight/legs, count(*) from animals group by weight/legs having count(*) >1;

Week 15

Conclusion

I love John DeNero！

don’t compare

In real life how you compare how you compare to somebody else doesn’t matter very much at all

what does matter is what you’re capable of what you do how you choose to spend your time and what impact you have on the world

and so it turns out your self-worth has nothing to do with what other people achieve and has everything to do with what you achieve

完结撒花~~~