CS61A笔记

笔记较为简单，主要是记录一些自己需要留意的内容

Lecture 2 Functions

$函数定义$

def square(x):      //有冒号
  return mul(x,x) //没有封号

print(...) 输出后自动换行, 返回值为none

Lecture 3 Multiple Environments

Operations

add->+
mul->*
truediv->/ $除$
floordiv->// $整除$
mod->% $求余$
quotient 商
remainder 余数

与C++不同之处

$python中函数可以返回多个值$

def divide_exact(n,d):
  return n // d, n % d

文档测试(doctest)

$在注释中模拟交互,\ terminal会告诉你你模拟的结果是否正确$ $在注释中模拟交互, t er mina l 会告诉你你模拟的结果是否正确$
- $命令如下:$ python3 -m doctests -v ex.py

参数默认值(default value)

def divide_exact(n,d = 10):
  return n // d, n % d

$特别的，有默认值的参数后面，不能再跟没有默认值的普通参数。$

条件语句(conditional statements)

if x > 0:
    print("positive")
elif x == 0:
    print("zero")
else:
    print("negative")

$这一整个语句叫做statement,\ 每个子句叫clause,\ 每个clause又分为header和suite$

clause

if x > 0:             //header
    print("positive") //suite

循环(Iteration)

$While\ Statements(while循环)$
$For\ Statement(for循环)$ for i in range(count):
statements to be repeated

`Print()`

返回值为：None（假值）

`""`

为假值

Lecture 4 Higher-Order Function

断言语句

assert eg. assert 2>1, 'error massage'
第一句话是bool表达式, 第二局话是在第一句为假时的报错语句

Lecture 5 Environments

Lambda表达式

eg1 square = lambda x: x*x`
- 输入square(2)
- 得到4
eg2 (lambda x: x*x)(3)
- 得到9
将:前的参数视为形参, 后的表达式视为返回值
和def的区别
- Lambda表达式只包含一句表达式作为返回值, 不具有其他函数体
- 由Lambda创建的函数的环境图和def创建的不同
  - Lambda函数 指向 $func\ \lambda(x)$
  - def函数 指向 $func\ square(x)$

Curring(curry化)

$Curring:\ Transforming\ a\ multi-argument\ function\ into \ a \ singal-argument,\ high-level\ function$ 即, 把多参函数化为单参数的高阶函数

eg

  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

Lecture 7 Functional Abstraction

Error

Syntax Error 语法错误
Runtime Error 运行时错误

Lecture 8 Function Examples

>>>print(print(5))
>>>5
>>>None

Lecture 9 Recursion

Caution: It is dangerous to try to write the entire program without testing it as you go

Lecture 10 Tree Recursion

Recursion

Tree recursion happen when one function makes more than one recursive call

Example: Partitions

The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order. For example, the number of partitions of 6 using parts up to 4 is 9.

6 = 2 + 4
6 = 1 + 1 + 4
6 = 3 + 3
6 = 1 + 2 + 3
6 = 1 + 1 + 1 + 3
6 = 2 + 2 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 1 + 1 + 1 + 1

def count_partitions(n, m):
        """Count the ways to partition n using parts up to m."""
        if n == 0:
            return 1
        elif n < 0:
            return 0
        elif m == 0:
            return 0
        else:
            return count_partitions(n-m, m) + count_partitions(n, m-1)

以上就是酣畅淋漓的物品价值为1的[[完全背包问题]]

The Range Type

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

For循环

>>>odds = [1,3,5,7]
>>>[x+1 for x in odds]
[2,4,6,8]

>>>[x for x in odds if 25  % x == 0]
[1,5]

>>>[x+1 for x in odds if 25 % x == 0]
[2,6]

def divisors(n):
  return [1] + [x for x in range(2,nn) if n%x==0]

HW03

一个有趣的迭代

def interleaved_sum(n, odd_func, even_func):

    """Compute the sum odd_func(1) + even_func(2) + odd_func(3) + ..., up

    to n.


    >>> identity = lambda x: x

    >>> square = lambda x: x * x

    >>> triple = lambda x: x * 3

    >>> interleaved_sum(5, identity, square) # 1   + 2*2 + 3   + 4*4 + 5

    29

    >>> interleaved_sum(5, square, identity) # 1*1 + 2   + 3*3 + 4   + 5*5

    41

    >>> interleaved_sum(4, triple, square)   # 1*3 + 2*2 + 3*3 + 4*4

    32

    >>> interleaved_sum(4, square, triple)   # 1*1 + 2*3 + 3*3 + 4*3

    28

    >>> from construct_check import check

    >>> check(HW_SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %

    True

    >>> check(HW_SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are

    True

    """

    def helper(k):

        if k>n:

            return 0

        elif k==n:

            return odd_func(k)

        else:

            return odd_func(k)+even_func(k+1)+helper(k+2)

    return helper(1)

从1开始向后遍历, 通过大于号终止迭代

[完全背包问题]

Q4: Count Dollars

Given a positive integer total, a set of dollar bills makes change for total if the sum of the values of the dollar bills is total. Here we will use standard US dollar bill values: 1, 5, 10, 20, 50, and 100. For example, the following sets make change for 15:

15 1-dollar bills
10 1-dollar, 1 5-dollar bills
5 1-dollar, 2 5-dollar bills
5 1-dollar, 1 10-dollar bills
3 5-dollar bills
1 5-dollar, 1 10-dollar bills

Thus, there are 6 ways to make change for 15. Write a recursive function count_dollars that takes a positive integer total and returns the number of ways to make change for total using 1, 5, 10, 20, 50, and 100 dollar bills.

Use next_smaller_dollar in your solution: next_smaller_dollar will return the next smaller dollar bill value from the input (e.g. next_smaller_dollar(5) is 1). The function will return None if the next dollar bill value does not exist.

Important: Use recursion; the tests will fail if you use loops.

Hint: Refer to the implementation of count_partitions for an example of how to count the ways to sum up to a final value with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.

def next_smaller_dollar(bill):
    """Returns the next smaller bill in order."""
    if bill == 100:
        return 50
    if bill == 50:
        return 20
    if bill == 20:
        return 10
    elif bill == 10:
        return 5
    elif bill == 5:
        return 1

def count_dollars(total):
    """Return the number of ways to make change.

    >>> count_dollars(15)  # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
    6
    >>> count_dollars(10)  # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
    4
    >>> count_dollars(20)  # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
    10
    >>> count_dollars(45)  # How many ways to make change for 45 dollars?
    44
    >>> count_dollars(100) # How many ways to make change for 100 dollars?
    344
    >>> count_dollars(200) # How many ways to make change for 200 dollars?
    3274
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_dollars', ['While', 'For'])
    True
    """
    def constrained_count(total, largest_bill):
        if total == 0:
            return 1
        if total < 0:
            return 0
        if largest_bill == None:
            return 0
        without_dollar_bill = constrained_count(total, next_smaller_dollar(largest_bill))
        with_dollar_bill = constrained_count(total - largest_bill, largest_bill)
        return without_dollar_bill + with_dollar_bill
    return constrained_count(total, 100)

Use Ok to test your code:

python3 ok -q count_dollars

This is remarkably similar to the count_partitions problem, with a few minor differences:

A maximum partition size is not given, so we need to create a helper function that takes in two arguments: current total and dollar bill value.
Partition size is not linear. To get the next partition you need to call next_smaller_dollar.

Q5: Count Dollars Upward

Write a recursive function count_dollars_upward that is just like count_dollars except it uses next_larger_dollar, which returns the next larger dollar bill value from the input (e.g. next_larger_dollar(5) is 10). The function will return None if the next dollar bill value does not exist.

Important: Use recursion; the tests will fail if you use loops.

def next_larger_dollar(bill):
    """Returns the next larger bill in order."""
    if bill == 1:
        return 5
    elif bill == 5:
        return 10
    elif bill == 10:
        return 20
    elif bill == 20:
        return 50
    elif bill == 50:
        return 100

def count_dollars_upward(total):
    """Return the number of ways to make change using bills.

    >>> count_dollars_upward(15)  # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
    6
    >>> count_dollars_upward(10)  # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
    4
    >>> count_dollars_upward(20)  # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
    10
    >>> count_dollars_upward(45)  # How many ways to make change for 45 dollars?
    44
    >>> count_dollars_upward(100) # How many ways to make change for 100 dollars?
    344
    >>> count_dollars_upward(200) # How many ways to make change for 200 dollars?
    3274
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_dollars_upward', ['While', 'For'])
    True
    """
    def constrained_count(total, smallest_bill):
        if total == 0:
            return 1
        if total < 0:
            return 0
        if smallest_bill == None:
            return 0
        without_dollar_bill = constrained_count(total, next_larger_dollar(smallest_bill))
        with_dollar_bill = constrained_count(total - smallest_bill, smallest_bill)
        return without_dollar_bill + with_dollar_bill
    return constrained_count(total, 1)

Lecture 12 Containers

`Dictionary`

{}
ls={1:['first','second'],3:['third']}
len(ls) = 2
Limitations
- no repeat
{x*x : x for x in [1,2,3,4,5] if x > 2} evaluates to {9: 3, 16: 4,25: 5}

`List`的一些操作

eg. list_of_values = [2,1,3,True,3]
下标为负数时, -1表示末尾最后一个元素, 以此类推
[1,2]+[3]+[4,5] 会得到 [1,2,3,4,5]
[1,2]*2 = [1,2,1,2]

`range`的一些操作

range(3, 6) range(3, 6) # this is a range object
list(range(3, 6)) [3, 4, 5] # list() converts the range object to a list
list(range(5)) [0, 1, 2, 3, 4]
list(range(1, 6)) [1, 2, 3, 4, 5]
[[1] + s for s in [[4], [5, 6]]]中[1]+s是一个整体
round(n)取距离n最近的整数

Lecture13 Data Abstraction

求最大公因数的函数gcd

>>> from fractions import gcd
>>> def rational(n, d):
        g = gcd(n, d)
        return (n//g, d//g)

Project Cats

1.装饰器（decorator）

>>> def do_twice(original_function):
...    def repeat(x):
...         original_function(x)
...         original_function(x)
...    return repeat

Take the original function as an input
Returns a new function with modified functionality
Contain the same arguments as the original function

使用时:

# Printing a value twice
>>> @do_twice
... def print_value(x):
...     print(x)

>>> print_value(5)
5
5

# Adding an item to a list twice
>>> lst = []
>>> @do_twice
... def add_to_list(item):
...     lst.append(item)

>>> add_to_list(5)
>>> lst
[5,5]

Lecture 16 Iterators

1. `all`函数

当all()中全部元素都不为空或0时返回真，否则返回假

2. `map()`

这里的map不是键值对，而是Python内部自带的函数

具体形式如下：map(函数, 可迭代对象)

作用是把一个函数依次应用到可迭代对象的每个元素上。

3. `filter()`

filter() 是 Python 的筛选函数：根据条件保留可迭代对象中的部分元素。

基本格式：

filter(判断函数, 可迭代对象) 判断函数对每个元素返回：

True：保留
False：丢弃

Lecture 19 Attribute

1. `getattr`(get attribute)

tom_account.balance = getattr(tom_account,balance)

2. `hasattr`(has attribute)

>>>hasattr(tom_account,balance)
True

3.Python可以改变类中元素的值

比如，有一个Account类，其中有元素interest声明为0.02 那么我们可以

Account.interest = 0.04

这里交互感更加明显了

我们对于类中attribute的改变不会作用于已经实例化的对象改变过的值

eg. >>>interest = 0.02
    >>>tom.interset = 0.04
    >>>Account.interst = 0.05
    >>>tom.interest
    0.04

结果是0.04，~~不是0.05~~

利用上节课的map()，Account类有方法deposit()负责存钱

def deposit(self,amount)
    self.balance += amount
    return self.balance

>>>a.balance  //原本余额
30
>>>m = map(a.deposit,range(10,20))
>>>a.balance
30
>>>next(m)
40
>>>next(m)
51

4.术语：Attributes, Functions, and Methods

lec19_1 绑定方法(Bound Method)也是一个对象，它将第一个参数self绑定到实例化的对象上

自然的，我们会疑惑什么是Bound Method？课程下一页PPT立刻阐释 lec19_2

Lecture 21 Representation

1.字符串转换

(1) Python规定所有对象都应该生成两个不同的字符串表示：一种是人类可读的文本(str)，另一种师Python可解释的表示式(repr)。

(2) Python 为了解决部分类型不存在repr类型的问题，提供了一种幽雅的、可将函数的作用域扩展到新的对象类型的方案：

._repr_() 成员函数

>>> tues.__repr__()
'datetime.date(2011, 9, 12)'

def __repr__(self):
            return 'Rational({0}, {1})'.format(self.numer, self.denom)

{0},{1}分别用numer和denom替换

._str_() 成员函数
```
>>> tues.__str__()
'2011-09-12'
```

2.专用方法

(1) 在 Python 中，某些特殊名称会在特殊情况下被 Python 解释器调用。例如，类的 init 方法会在对象被创建时自动调用。str 方法会在打印时自动调用，repr 方法会在交互式环境显示其值的时候自动调用。

(2) 在 Python 中有一些为其他行为而准备的特殊名称。下面介绍其中某些常用的:

bool值假设我们想让一个只有 0 存款的账号为假值。我们可以为 Account 添加一个 bool 方法来实现这种行为。 >>> Account.__bool__ = lambda self: self.balance != 0 我们可以调用 bool 构造器来看一个对象的真假值，同时我们也可以在布尔上下文中使用任何对象。
```
>>> bool(Account('Jack'))
False
>>> if not Account('Jack'):
        print('Jack has nothing')
Jack has nothing
```

序列操作

>>> len('Go Bear!')
9

>>> 'Go Bear!'._len_()
9

getitem 取指定下标元素

>>> 'Go Bears!'[3]
'B'
>>> 'Go Bears!'.__getitem__(3)
'B'

多重表示

有时，一个数据对象可能由不知一种有用的表示，我们也许会想要设计能够处理多种表示形式的系统。

以复数举例，复数可以用直角坐标系和极坐标系表示。

我们从最高等级的抽象开始实现。复数是一个数值型（number），可以相加或相乘，分别通过名为add和mul的方法抽象出来的。

>>> class Number:
        def __add__(self,other):
            return self.add(other)
        def __mul__(self,other):
            return self.mul(other)

Number的目的不是直接被初始化，而是作为一个不同特殊数值类的超类。

注意到，复数相加和相乘时分别适合用直角坐标系和极坐标系，因此我们可以：

>>> class Complex(Number):
        def add(self, other):
            return ComplexRI(self.real + other.real, self.imag + other.imag)
        def mul(self, other):
            magnitude = self.magnitude * other.magnitude
            return ComplexMA(magnitude, self.angle + other.angle)

这个实现假定存在两个表示复数的类，分别对应他们的两种自然表示形式。

ComplexRI 使用实部和虚部构建一个复数
ComplexMA 使用幅度和角度构建一个负数

两个或多个属性相互之间保持一个固定关系的要求是一个新问题，一种solution是只使用一种表现方式来储存属性值，并在需要时计算另一种表现方式。

Python有一种简单的计算属性的特性，可以通过零参数试试的计算属性。@property修饰符允许函数在没有调用表达式语法(表达式后跟随圆括号)的情况下被调用。Complex类存储了real和imag属性并在需要时计算magnitude和angle属性。

>>> from math import atan2
>>> class ComplexRI(Complex):
        def __init__(self, real, imag):
            self.real = real
            self.imag = imag
        @property
        def magnitude(self):
            return (self.real ** 2 + self.imag ** 2) ** 0.5
        @property
        def angle(self):
            return atan2(self.imag, self.real)
        def __repr__(self):
            return 'ComplexRI({0:g}, {1:g})'.format(self.real, self.imag)

在这种实现下，所有四个属性复数运算所需要的属性都可以在不需要任何调用表达式的情况下被访问，并且对于real和imag的修改会直接反映到magnitude和angle中。

泛型函数

泛型函数是适用于不同类型的参数的方法或函数。上面提到的使用接口和消息传递就是实现泛型函数的一种方法。此外，还有类型派发和类型强制转化两种方法。

1.类型派发

一种实现跨类型操作的方式是选择基于函数或方法的参数类型来选择相应的行为。类型派发的思想是写一个能够检查它所收到的参数的类型的函数，然后根据参数类型执行恰当的代码。

内置的函数isinstance接受一个对象和一个类。如果对象的类是所给的类或者继承自所给的类，它会返回一个真值。

2.强制转换

在完全不相关的操作和完全不相关的类型的一般情况下，实现显式的跨类型操作有些困难。Luckily,通过利用类型系统中可能潜在额外的结构，可能可以做的更好。通常不同类型并非不相关，存在一些方法将一种类型视为另一种类型。这个过程被称作 $\textcolor{cyan}{强制转换}$ 。

例如，如果我们被要求使用算术方法结合一个分数和一个复数，则可以把分数看作一个虚部为零的复数。然后我们就可以使用 Complex.add 和 Complex.mul 来结合它们。

由于我不再关心第几个Lecture，故下面我采用 composingprograms 的章节作为分节标准

2.8 效率

2.8.1.记忆化

tree 递归的计算过程通常可以通过记忆化（Memoization）来提高效率，这时一种增加递归函数效率的强大技术。记忆化函数会保存之前接收到的参数的返回值，如果第二次调用 fib（25），他不会再通过递归重新计算，而是直接返回计算好的结果.

我们可以吧记忆化表达成一个高阶函数或装饰器，如：

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

这里cache是一个字典，not in 表示的是，n 不是 cache 的键

2.8.2.增长阶数

计算过程在消耗计算资源的的速率上可能有 big difference, 然而准确确定调用函数时将使用多少空间是困难的. 故使用增长阶数近似表示计算过程的资源需求随输入的 函数增长

个人感觉和时间复杂度可以基本等同, 不过是去掉大O, 故不赘述

2.9 递归对象

对象可以以其他对象作为自己的属性值, 当这个类下的对象实例有一个属性的值还属于这个类时, 这个对象就是一个递归对象.

2.9.1 链表

链表的递归定义法: 第一个元素和链表剩下的部分, 而剩下的部分本身也是链表.

链表时一种序列(sequence): 具有有限长度并支持索引.

我们考虑使用专用方法名来定义类的行为, 专用方法允许我们的类适应 Python 内置的 len 函数和元素选择操作符.

>>> class Link:
        empty = ()
        def _init_(self, first, rest=()):
            assert rest == Link.empty or isinstance(rest, Link)
            self.first = first
            self.rest = rest
        def _getitem_(self, i):
            if i == 0:
                return self.first
            else:
                return self.rest[i-1]
        def _len_(self):
            return 1 + len(self.rest)
>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

以上的 _len_ 和 _getitem_ 的定义都是递归的. Python 的内置函数 len 在他接收属于用户定义的类的实例时调用了 _len_ 方法.

定义一个函数将 Link 实例转换为字符串表达式

>>> def link_expression(s):
        if s.rest is Link.empty:
            rest =''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)
>>> link_expression(s)
'Link(3,Link(4,Link(5)))'

GYX’s Blog学习笔记与个人记录回到顶部 ↑