红魔咖啡馆

头发越掉越多，头发越掉越少

0%

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 2 分钟

Containers

Slicing

切片可以简洁的获取列表中的子列表，实质是创建了新的列表而不影响原始列表

如列表odds = [3,5,7,9,11]

  • odds[1:3] -> [5,7] 默认也是包括起始值不包括结束值
  • odds[:3] -> [3,5,7] 省略开头将从列表头开始算起
  • odds[1:] -> [5,7,9,11] 省略结尾将覆盖至列表尾

内置函数

sum

sum(<可迭代对象>, [起始值])

返回所有可迭代元素和并加上起始值，起始值默认为0

sum还可以实现列表相加：sum([[2,3],[4]],[]) 注意起始值类型要和前面相同

max

max(<可迭代对象>, [键函数])

max(a,b,c,..., [键函数])

返回对象中的最大值或返回若干值中的最大值

键函数：考虑对每个元素执行键函数并根据返回值比较大小（返回原始值）

e.g. max(range(10), key=lambda x: 7-(x-4)*(x-2))

all

all(<可迭代对象>)

对每个元素执行bool(x)操作，若所有元素都返回True则返回True，否则返回False，空列表返回True

e.g. all([x<5 for x in range(5)]) 返回True

len

len(<可迭代对象>)

获取某个序列长度

有关string

string可以用于表示：数据、语言、程序

表示字符串

  • 使用单引号
  • 使用双引号
  • 使用一对连续的三个双引号：可以跨行

string也是一种sequence

求解长度与选择元素与列表相同

获取到的string中的元素本身也是一个字符串，但只有它本身一个元素

in与not in可以在字符串中寻找连续字符

e.g. 'here' in 'where's waldo? 返回True

Dictionary

dictionary用于存储键值对，使用花括号和冒号分隔键值

创建：

numerals = {'I':1, 'V':5, 'X':10}

可以用数字，字符串当键值，列表或字典 当值

注意：键本身不能是列表或字典，键不能重复

查找：

输入对应的键来查找对应的值，但不能通过值查找键

numerals['V'] >>> 5

遍历：

dictionary是键的序列，通过list()创建列表可以获得所有的键，因此可以用for循环遍历所有的键

使用numerals.value()获得字典中所有的值，存储在一个序列中（非列表）

Dictionary Comprehensions

可以使用表达式来创建列表

格式：{<key exp>: <val exp> for <name> in <iter exp> if <filter exp>}

过程：

  1. 添加以当前作用域为父作用域的新作用域
  2. 建立一个空的result字典存储表达式的值
  3. 对每个中的元素：
    1. 在新作用域中将绑定到每一个元素
    2. 若为真，则将与配对并添加到result字典中

e.g.

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

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 2 分钟

Sequence

Lists

列表是python中的内置数据类型

  • 使用[]创建列表
  • 使用赋值语句命名列表
  • 使用name[下标]访问列表元素(0-index)，或使用getitem( ,)(operator模块)来访问元素
  • 使用len()函数获取元素个数

name[下标]是一种元素评估表达式，可以依次评估下标对应元素

列表中的元素可以是表达式，此时列表中的值将绑定为表达式的结果

digits = [2//2,2+2,2,2*2]

列表间可以相加与相乘（运算符或函数）

[2,7]+[1,8,2,8]*2 == [2,7,1,8,2,8,1,8,2,8]

列表中的元素可以是任何东西，包括列表

1
2
pairs = [[10,20],[30,40]]
pairs[1][0] # 结果是30

in运算符

in运算符可以判断某元素是否存在于列表中

not in 运算符可以判断某元素是否不存在于列表中

返回值为True 或 False

这两个运算符寻找的是单独元素，而非子序列

e.g.

1
2
3
4
5
6
7
8
9
digits = [1,8,2,8]
 >>> 1 in digits
True
>>> '1' in digits
False
>>> [1,2] in [[1,2],3,4]
True
>>> [1,2] in [[[1,2],3],4]
False

For Statement

执行过程

1
2
for <name> in <expression>:
    <suite>
  • 执行，该表达式必须是一个可迭代的量（如一个序列）
  • 对序列中的每个元素，按序进行如下操作：
    • 在当前作用域中将每个元素赋给
    • 执行语句块中的语句

### 序列解包

e.g.寻找序列中相同元素的数对

pairs = [[1,2],[2,2],[3,2],[4,4]]

1
2
3
for x, y in paris:
    if x==y:
        same_count+=1

该循环中，for循环会自动将paris中的内层列表中的两个元素赋给x,y两个变量

Ranges

range是表示连续整数的序列，通过给出起始与结束值获得范围内的整数

range包括起始值而不包括结束值

用法：range(<起始值(默认为0)>, <结束值>, [步长])

作用：

  • 计算长度：结束值-起始值
  • 选择元素：起始值+index
  • 作为计数器：用_等当作name而不实际使用它

转换列表：使用list() - 列表构造函数

List Comprehension

列表中可以写一些语句来构造列表

e.g.1

1
2
3
4
5
>>> 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]

e.g.2 查找某个数的因数

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

发表于 更新于 分类于
本文字数： 4.5k 阅读时长 ≈ 8 分钟

Homework 3

Q1: Num Eights

用递归函数求一个数中有几位8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def num_eights(n):
    """Returns the number of times 8 appears as a digit of n.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> num_eights(8782089)
    3
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(HW_SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
    True
    """
    if n==0:
        return 0
    else:
        if n%10 ==8: return num_eights(n//10)+1
        else: return num_eights(n//10)

递归出口：每一位都减完后n==0时

每次返回时递归调用自身，传入未判断的部分

若发现该位是8，则返回值加一，否则不变

Q2: Digit Distance

用递归函数求每两位的差的绝对值之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def digit_distance(n):
    """Determines the digit distance of n.

    >>> digit_distance(3)
    0
    >>> digit_distance(777)
    0
    >>> digit_distance(314)
    5
    >>> digit_distance(31415926535)
    32
    >>> digit_distance(3464660003)
    16
    >>> from construct_check import check
    >>> # ban all loops
    >>> check(HW_SOURCE_FILE, 'digit_distance',
    ...       ['For', 'While'])
    True
    """
    if n<10:
        return 0
    else:
        res,last = n//10,n%10
        sec_last = res%10
        return digit_distance(res)+abs(sec_last-last)

递归出口：当查到最后一位时绝对值为0，返回0

否则将最后一位与倒数第二位取出，将取完最后一位的剩余部分传入递归函数继续判断，返回值加上两位数绝对值之差

Q3: Interleaved Sum

写一个函数，要求对1-n中的所有奇数传入odd_func，所有偶数传入even_func，返回所有数计算后和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
    """
    def check_num(k):
        if k>n:
            return 0
        elif k==n:
            return odd_func(k)
        else:
            return check_num(k+2)+odd_func(k)+even_func(k+1)
    return check_num(1)

由于题目不让使用循环与取模运算判断奇偶，我们只能使用递归函数

由于奇数与偶数是分开的，我们可以发现，奇数+2=奇数，奇数+1=偶数

因此我们可以写一个内嵌函数，让一个计数变量k从1开始，将k传入odd_func，k+1传入even_func

然后递归调用该函数从k+2开始

递归出口即k>n或k=n（此时k一定为奇数，直接传入odd_func并返回）

Q4: Count Coins

给予n刀乐，把他分为面值分别为1刀乐，5刀乐，10刀乐，25刀乐的四种货币，输出分法数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def count_coins(total):
    """Return the number of ways to make change using coins of value of 1, 5, 10, 25.
    >>> count_coins(15)
    6
    >>> count_coins(10)
    4
    >>> count_coins(20)
    9
    >>> count_coins(100) # How many ways to make change for a dollar?
    242
    >>> count_coins(200)
    1463
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])
    True
    """
    def cal(total,spl_coin):
        if total==0:
            return 1
        elif total<0:
            return 0
        elif spl_coin==None:
            return 0
        else:
            with_coin = cal(total-spl_coin,spl_coin)
            without_coin = cal(total,next_smaller_coin(spl_coin))
            return with_coin+without_coin
    return cal(total,25)

Q5: Towers of Hanoi

实现汉诺塔游戏并描述每次移动过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def move_stack(n, start, end):
    """Print the moves required to move n disks on the start pole to the end
    pole without violating the rules of Towers of Hanoi.

    n -- number of disks
    start -- a pole position, either 1, 2, or 3
    end -- a pole position, either 1, 2, or 3

    There are exactly three poles, and start and end must be different. Assume
    that the start pole has at least n disks of increasing size, and the end
    pole is either empty or has a top disk larger than the top n start disks.

    >>> move_stack(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> move_stack(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> move_stack(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
    def hanoi(n,start,mid,end):
        if n == 1:
            print_move(start, end)
            return
        else:
            hanoi(n - 1, start,end, mid)
            hanoi(1,start,mid,end)
            hanoi(n - 1, mid, start,end)
    return hanoi(n,start,6-start-end,end)

详见五点七边讲解视频

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 2 分钟

Tree Recursion

Order of Recursive Calls

e.g.1:Cascade

1
2
3
4
5
6
7
def cascade(n):
    if n<10:
        print(n)
    else:
        print(n)
        cascade(n//10)
        print(n)

结果为

1
2
3
4
5
6
7
8
9
10
>>> cascade(12345)
12345
1234
123
12
1
12
123
1234
12345

首先一直调用cascade到底，返回None，从调用入口出来后继续执行cascade下面的语句

cascade

还可以缩短为以下

1
2
3
4
5
def cascade_short(n):
    print(n)
    if n>10:
        cascade(n//10)
        print(n)

e.g.2:Inverse Cascade

1
2
3
4
5
6
7
8
9
10
11
12
def inverse_cascade(n):
    grow(n)
    print(n)
    shrink(n)
    
def f_then_g(f,g,n):
    if n:
        f(n)
        g(n)

grow = lambda n: f_then_g(grow,print,n//10)
shrink = lambda n: f_then_g(print,shrink,n//10)

grow先进行处理，每次将数字缩短一节，到达递归底部后退出时便是从小到大依次输出

shrink先打印出来当前n，然后将数字缩短一节，这样递归过程便实现了从大到小依次输出

Tree Recursion

当递归函数对自身调用超过一次时，发生树形递归，产生树状过程

e.g.1 斐波那契数列

树形斐波那契 

1
2
3
4
5
6
7
def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

e.g.2 计算分区

将正整数n分为大小不超过m的分区的方式有多少种，即n能以多少种方式表示为递增的不超过m部分之和

e.g. count_partitions(6,4)

有以下可能：

\(2+4=6\)

\(1+1+4=6\)

\(3+3=6\)

\(1+2+3=6\)

\(1+1+1+3=6\)

……

分为两种情况考虑：

  • 至少分一个4
  • 不分4

这样我们可以把递归问题拆分为两个小问题，将两种情况相加

  • count_partitions(2,4)

  • count_partitions(6,3)

    以此类推，count_partitions(6,3)按同样方式考虑，分3与不分3，直到递归底部

1
2
3
4
5
6
7
8
9
10
11
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

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 2 分钟

Recursion

Recursive Functions

定义：在函数体中直接或间接调用自身的函数叫递归函数

即在执行函数体时还会调用若干次函数自身

递归函数的结构：

  • def头定义
  • 条件语句用来判断基本条件，无递归调用（递归出口）
  • 递归条件用来递归调用

判断递归是否正确：

  • 验证基本条件
  • 将递归函数看作函数抽象
  • 假设f(n-1)正确，验证f(n)的正确性

e.g.1:用递归求各位数字和

1
2
3
4
5
6
7
8
9
10
11
def split(n):
    """把n分成最后一位与其他位两部分"""
    return n//10, n%10

def sum_digits(n):
    """求和各位数字"""
    if n<10:
        return n
    else:
        all_but_last,last = split(n)
        return sum_digits(all_but_last)+last

e.g.2:阶乘（使用diagram）

阶乘

递归与迭代

递归与迭代

递归转换到迭代：弄清需要通过迭代保持的状态

迭代转换到递归：迭代保持的状态可以通过参数传递

互递归（Mutual Recursion）

e.g. Luhn Algorithm

改算法常用于信用卡等的校验码计算，步骤如下：

步骤 1：反转数字

算法首先通过反转您正在检查的数字的数字。

步骤 2：每隔一个数字翻倍

从左侧的第一个数字开始（由于反转，现在是原始数字的最后一个数字），对每个第二个数字进行翻倍。

步骤 3：求乘积的数字之和

如果翻倍后的数字大于 9，则将乘积的数字相加（例如，翻倍 8 得到 16，因此相加 1 + 6 = 7）。

步骤 4：将所有数字相加

在上述操作后，将所有数字相加。

步骤 5：检查是否能被 10 整除

如果总和能被 10 整除（即以 0 结尾），则该数字根据 Luhn 算法是有效的。否则，它是无效的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def split(n):
    """把n分成最后一位与其他位两部分"""
    return n//10, n%10

def sum_digits(n):
    """求和各位数字"""
    if n<10:
        return n
    else:
        all_but_last,last = split(n)
        return sum_digits(all_but_last)+last

def luhn_sum(n):
    if n<10:
        return n
    else:
        all_but_last, last = split(n)
        return luhn_sum_double(all_but_last)+last

def luhn_sum_double(n):
    all_but_last, last = split(n)
    luhn_digit = sum_digits(2*last)
    if n<10:
        return luhn_digit
    else:
        return luhn_sum(all_but_last)+luhn_digit

这里使用互递归让分离出来的数字奇数位不执行乘二操作，偶数位执行乘二操作

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 2 分钟

Functional Abstraction

Lambda表达式所在的environment关系

如下例子

1
2
3
4
5
a = 1
def f(g):
    a = 2
    return lambda y:a*g(y)
f(lambda y: a+y)(a)

注意行4与行5的lambda函数的区别：

  • 行4的lambda函数是f函数内定义的函数，他的父级为f，因此此时传入的a=2
  • 行5的lambda函数是f函数外定义的函数，他的父级为global，因此此时传入的a=1

Choosing Names

给函数或变量命名时，要注重传达意思

  • 命名需要传达与之相关值的意义或目的

  • 值的类型最好记录在函数的docstring中

  • 函数名一般包括它们的作用，表现或返回值

  • 为一些重复使用的复合表达式命名

  • 如果需要注释代码，命名可以长一些

  • 如果用于数字，数学运算与函数抽象，命名可以短一些

Error&Traceback

报错有三种形式：

  • Syntax errors：执行前即可发现，通常由于表达式不正确引起
  • Runtime errors：执行时由python解释器发现的错误。当这些错误发生时，会得到一个Traceback，来提示是在哪里发生了何种错误，错误发生时程序在做什么
  • Logical error：不会被解释器发现，需要自己进行测试发现问题

Decorator

装饰器用于给现有模块（原函数）进行功能拓展，通过接受一个函数来返回一个新的函数或修改原来的函数

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
def trace1(fn):
    """
    return a version of fn that first print before it is called
    fn - a function of 1 argument
    """
    def traced(x):
        print("Calling",fn,"on argument",x)
        return fn(x)
    return traced

@trace1
def square(x):
    return x*x

等同于

1
2
3
4
5
6
7
8
9
10
11
12
13
def trace1(fn):
    """
    return a version of fn that first print before it is called
    fn - a function of 1 argument
    """
    def traced(x):
        print("Calling",fn,"on argument",x)
        return fn(x)
    return traced

def square(x):
    return x*x
square = trace1(square)

返回值都相同

1
2
3
>>> square(5)
Calling  on argument 5
25