|

1. 数据类型

  • 整数（int）：用于表示整数，可以是任意大小。Python 3 中的 int 是无界的，这意味着它可以表示任意大的整数，只要计算机的内存足够。
  • 浮点数（float）：用于表示小数。浮点数的表示是近似的，这意味着它们不能精确表示所有的小数值。浮点数的精度是有限的，这在进行复杂的数学运算时可能会导致误差。
  • 复数（complex）：用于表示复数，包含实部和虚部
  • 布尔类型（bool）：用于表示逻辑值，只有两个可能的值：True 和 False。布尔类型在条件语句和逻辑运算中非常有用。
  • 字符串（str）：用于表示文本数据。字符串是不可变的，这意味着一旦创建，就不能修改。
  • 元组（tuple）：用于表示一组不可变的值。元组可以包含不同类型的数据。
  • 列表（list）：是一种可变的序列类型，用于表示一组有序的值。列表可以包含不同类型的数据，并且可以动态地添加或删除元素
  • 字典（dict）：是一种键值对的集合，用于表示一组无序的键值对。字典的键必须是不可变类型（如字符串、整数或元组），而值可以是任意类型。
  • 自定义数据类型在后面面对对象时再说吧

2. 数据抽象

在编程中，数据抽象是一种强大的设计方法，它允许我们将数据的表示与数据的使用分离。通过数据抽象，我们可以构建更加模块化、易于维护和修改的程序。数据抽象的核心思想是将数据的表示与数据的使用分离。这意味着我们可以通过定义一组抽象的操作来处理数据，而不需要关心数据的具体表示细节。这种分离使得程序更加模块化，也更容易维护和修改。

  • 抽象屏障
    抽象屏障是数据抽象中的一个重要概念。它通过一组选择器和构造器函数来实现，这些函数定义了如何创建和操作抽象数据。抽象屏障的作用是隐藏数据的具体表示，使得程序的其他部分只需要通过这些函数来操作数据。抽象屏障使得程序的各个部分之间保持独立性。通过抽象屏障，我们可以轻松地修改数据的表示，而不需要修改使用数据的代码。例如，我们可以将有理数的表示从列表改为元组，而不需要修改 add_rationals、mul_rationals 等函数（只需修改rational这个函数）。
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
def rational(n, d):
    """返回分子为 n、分母为 d 的有理数"""
    return [n, d]

def numer(x):
    """返回有理数 x 的分子"""
    return x[0]

def denom(x):
    """返回有理数 x 的分母"""
    return x[1]
def add_rationals(x, y):
    """返回两个有理数 x 和 y 的和"""
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dy + ny * dx, dx * dy)

def mul_rationals(x, y):
    """返回两个有理数 x 和 y 的乘积"""
    return rational(numer(x) * numer(y), denom(x) * denom(y))

def print_rational(x):
    """打印有理数 x"""
    print(numer(x), '/', denom(x))

def rationals_are_equal(x, y):
    """检查两个有理数 x 和 y 是否相等"""
    return numer(x) * denom(y) == numer(y) * denom(x)

from fractions import gcd

def rational(n, d):
    """返回分子为 n、分母为 d 的有理数，简化为最简形式"""
    g = gcd(n, d)
    return (n // g, d // g)

有理数这个例子可以很好的阐释什么是数据抽象。

3. 序列

Python 提供了多种内置的序列类型，如列表和范围，它们都满足序列抽象的条件。这里以列表举例。

1
2
3
4
5
6
7
8
9
10
11
12
# 成员资格
digits = [1, 8, 2, 8]
print(2 in digits)  # 输出 True
print(1828 not in digits)  # 输出 True
# 切片
digits = [1, 8, 2, 8]
print(digits[0:2])  # 输出 [1, 8]
print(digits[1:])   # 输出 [8, 2, 8]
# 加减法
print('Berkeley' + ', CA')  # 输出 'Berkeley, CA'
print('Shabu ' * 2)         # 输出 'Shabu Shabu '

  • 序列遍历
    在许多情况下，我们希望依次遍历序列的元素并根据元素值执行一些计算。这种情况十分常见，所以 Python 提供了一个额外的控制语句来处理序列的数据：for 循环语句。考虑统计一个值在序列中出现了多少次的问题。我们也可以使用 while 循环实现一个函数。
1
2
3
4
5
6
7
8
9
10
11
12
def count(s, value):
    """统计在序列 s 中出现了多少次值为 value 的元素"""
    total = 0
    for elem in s:
        if elem == value:
                total = total + 1
        return total
>>> count(digits, 8)
>>> list(range(5, 8))
[5, 6, 7]
>>> list(range(4))
[0, 1, 2, 3]
  • 序列处理
    列表推导式（List Comprehensions）：许多序列操作可以通过对序列中的每个元素使用一个固定表达式进行计算，并将结果值保存在结果序列中。在 Python 中，列表推导式是执行此类计算的表达式。```
1
2
3
>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds]
[2, 4, 6, 8, 10]

另一个常见的序列操作是选取原序列中满足某些条件的值。列表推导式也可以表达这种模式，例如选择 odds 中所有可以整除 25 的元素。

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

列表推导式的一般形式是：

1
2
3
4
5
6
7
[<map expression> for <name> in <sequence expression> if <filter expression>]
# 举个例子
>>> def divisors(n): return [1] + [x for x in range(2, n) if n % x == 0]
>>> divisors(4)
>>> [1, 2] 
>>> divisors(12) 
>>> [1, 2, 3, 4, 6]

4. 字符串

在计算机科学中，文本值可能比数字更重要。比如 Python 程序是以文本形式编写和存储的。Python 中文本值的内置数据类型称为字符串（string），对应构造函数 str。
字符串字面量（string literals）可以表示任意文本，使用时将内容用单引号或双引号括起来。

字符串与序列有很多共通之处

1
2
3
4
5
6
7
8
9
10
11
>>> city = 'Berkeley'
>>> len(city)
8
>>> city[3]
'k'
>>> 'Berkeley' + ', CA'
'Berkeley, CA'
>>> 'Shabu ' * 2
'Shabu Shabu '
>>> 'here' in "Where's Waldo?"
True

字符串强制转换（String Coercion）：通过以对象值作为参数调用 str 的构造函数，可以从 Python 中的任何对象创建字符串。字符串的这一特性在用构造各种类型对象的描述性字符串时非常有用。

1
2
>>> str(2) + ' is an element of ' + str(digits)
'2 is an element of [1, 8, 2, 8]'

5. 树

树是一种层次化的数据结构，用于表示具有层次关系的数据。树由节点组成，每个节点可以有多个子节点，这个以图片方式来看会很直观。
以下是树的基本函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def tree(root_label, branches=[]):
    return [root_label] + list(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:# 非列表，长度为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-recursive）函数可用于构造树。例如，我们定义 The nth Fibonacci tree 是指以第 n 个斐波那契数为根标签的树。那么当 n > 1 时，它的两个分支也是 Fibonacci tree。这可用于说明斐波那契数的树递归计算。

1
2
3
4
5
6
7
8
9
>>> def fib_tree(n):
        if n == 0 or n == 1:
            return tree(n)
        else:
            left, right = fib_tree(n-2), fib_tree(n-1)
            fib_n = label(left) + label(right)
            return tree(fib_n, [left, right])
>>> fib_tree(5)
[5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]

其实还是很简单的，想清楚斐波那契数列是什么样的，还是很简单的
树递归同时也可以做到遍历计算

1
2
3
4
5
6
7
8
9
10
# 树的遍历
def count_leaves(tree):
    if is_leaf(tree):# 是叶子就回复1
        return 1
    else:
        branch_counts = [count_leaves(b) for b in branches(tree)]# 从头到尾遍历
        return sum(branch_counts)

t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
print(count_leaves(t))  # 输出 4

e.g.
依然是分割树，思想还是一样的，但是用树，会多一个label,并且是以T/F来判断分支的情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> def partition_tree(n, m):
        """返回将 n 分割成不超过 m 的若干正整数之和的分割树"""
        if n == 0:
            return tree(True)
        elif n < 0 or m == 0:
            return tree(False)
        else:
            left = partition_tree(n-m, m)
            right = partition_tree(n, m-1)
            return tree(m, [left, right])

>>> partition_tree(2, 2)
[2, [True], [1, [1, [True], [False]], [False]]]

其实更重要的是这个打印函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
>>> def print_parts(tree, partition=[]):
        if is_leaf(tree):
'''如果当前节点是叶子节点，且该叶子节点的标签为 `True`，则表示当前路径上的分割方案是有效的。'''
            if label(tree):
                print(' + '.join(partition))
        else:
            left, right = branches(tree)# 由前面可知，并非叶节点，肯定为两个分支--左右
            m = str(label(tree))
'''将当前节点的标签值（即当前分割的部分大小）转换为字符串'''
            print_parts(left, partition + [m])
            print_parts(right, partition)
'''递归调用 `print_parts` 函数处理左分支 `left`，并将当前的分割部分 `m` 添加到 `partition` 列表中，形成新的分割累积列表。右边就没有了'''
>>> print_parts(partition_tree(6, 4))
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

6. 链表

链表由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。在Python中，我们可以使用列表来模拟链表的结构。例如，创建一个包含四个元素的链表：1 → 2 → 3 → 4。

1
four = link(1, link(2, link(3, link(4, empty))))

这个链表的结构如下：

[1, [2, [3, [4, 'empty']]]]

其中：

  • 头节点是 1，指向下一个节点。
  • 第二个节点是 2，指向下一个节点。
  • 第三个节点是 3，指向下一个节点。
  • 第四个节点是 4，指向空值 empty，表示链表的结束。
    以下是链表的基本函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>>> empty = 'empty'
>>> def is_link(s):
        """判断 s 是否为链表"""
        return s == empty or (len(s) == 2 and is_link(s[1]))

>>> def link(first, rest):
        """用 first 和 rest 构建一个链表"""
        assert is_link(rest), " rest 必须是一个链表"
        return [first, rest]

>>> def first(s):
        """返回链表 s 的第一个元素"""
        assert is_link(s), " first 只能用于链表"
        assert s != empty, "空链表没有第一个元素"
        return s[0]

>>> def rest(s):
        """返回 s 的剩余元素"""
        assert is_link(s), " rest 只能用于链表"
        assert s != empty, "空链表没有剩余元素"
        return s[1]

链表很多东西都需要自己定义，其基本的思路就是循环剥壳

1
2
3
4
5
6
7
8
9
10
11
12
>>> def len_link(s):
        """返回链表 s 的长度"""
        length = 0
        while s != empty:
            s, length = rest(s), length + 1
        return length

>>> def getitem_link(s, i):
        """返回链表 s 中索引为 i 的元素"""
        while i > 0:
            s, i = rest(s), i - 1
        return first(s)

所以递归+rest()就能构成链表的基本架构
下面的就是链表的另外一些函数与其实现方式

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
38
39
40
41
42
43
44
45
46
47
>>> def extend_link(s, t):
        """返回一个在 s 链表的末尾连接 t 链表后的延长链表"""
        assert is_link(s) and is_link(t)
        if s == empty:
            return t
        else:
            return link(first(s), extend_link(rest(s), t))

>>> extend_link(four, four)
[1, [2, [3, [4, [1, [2, [3, [4, 'empty']]]]]]]]

>>> def apply_to_all_link(f, s):
        """应用 f 到 s 中的每个元素"""
        assert is_link(s)
        if s == empty:
            return s
        else:
            return link(f(first(s)), apply_to_all_link(f, rest(s)))

>>> apply_to_all_link(lambda x: x*x, four)
[1, [4, [9, [16, 'empty']]]]

>>> def keep_if_link(f, s):
        """返回 s 中 f(e) 为 True 的元素"""
        assert is_link(s)
        if s == empty:
            return s
        else:
            kept = keep_if_link(f, rest(s))
            if f(first(s)):
                return link(first(s), kept)
            else:
                return kept

>>> keep_if_link(lambda x: x%2 == 0, four)
[2, [4, 'empty']]

>>> def join_link(s, separator):
        """返回由 separator 分隔的 s 中的所有元素组成的字符串"""
        if s == empty:
            return ""
        elif rest(s) == empty:
            return str(first(s))
        else:
            return str(first(s)) + separator + join_link(rest(s), separator)
>>> join_link(four, ", ")
'1, 2, 3, 4'

后面还有用链表实现分割树，这样算下来已经用函数式，树，链表三种形式去实现分割树了，基本思路都是一样的。

又是一篇技术博客，好耶！
这次的链表是又学了一遍重新写的笔记，也是重新体会到了链表的魅力（不过还是浅尝即止罢了）。
此外还有一件喜事，我成功转到计算机了！！

|

1. 函数作为抽象工具

函数的一个重要特性是它们可以作为抽象工具，隐藏实现细节。这意味着你可以定义一个函数，而不需要关心它的具体实现，只要知道它的输入和输出即可。
这也是cs61a的核心

纯函数（Pure functions）：函数有一些输入（参数）并返回一些输出（调用返回结果）。不改变输出性质，如数学函数
非纯函数（Non-pure functions）：除了返回值外，调用一个非纯函数还会产生其他改变解释器和计算机的状态的副作用（side effect）。如print()，输出其实是none，副产物是显示了你的内容

1
2
3
print(print(1),print(2))
1.2
none,none

由此，print 函数返回 None  意味着它不应该用于赋值语句，不能使用嵌套。

实现函数的一个细节就是，实现者为函数的形参选择的名称不应该影响函数行为。所以，以下函数应该提供相同的行为：

1
2
3
4
def square(x):
    return mul(x, x)
def square(y):
    return mul(y, y)

一个函数的含义应该与编写者选择的参数名称无关，这个原则对编程语言有重要的意义。最简单的就是函数的参数名称必须在保持函数体局部范围内。

2. 语句与表达式

在 Python 中，语句和表达式是两种不同的概念。表达式是有值的，例如 2 + 2 或 x * y，它们可以被求值并返回一个结果。而语句则是用来执行某些操作的，它们没有值，但会改变程序的状态。

1
2
3
x = 10  # 赋值语句
def square(x):  # def 语句
    return x * x  # return 语句

语句的作用是执行某些操作，而不是返回一个值。例如，赋值语句会将一个值绑定到一个变量上，def 语句会定义一个函数，而 return 语句会从函数中返回一个值。

复合语句是由多个语句组成的结构，它们通常跨越多行，以单行头部开始，并以冒号结尾。复合语句的头部定义了语句的类型，而缩进的句体则包含了要执行的语句。条件语句（if，else）与while是最典型的复合语句

3. 函数调用与环境模型

调用一个函数时，Python 会创建一个新的局部环境（或称为帧），在这个环境中，函数的参数被绑定到传递给函数的实际值上。函数体中的代码在这个局部环境中执行，这意味着函数内部的变量不会影响外部的变量。

例如，调用 square(4) 时，Python 会创建一个新的局部帧，将参数 x 绑定到值 4，然后执行 return x * x，最终返回 16。

这种环境模型确保了函数的局部性，使得函数的实现细节对外部代码透明。每个函数调用都有自己的局部帧，即使多次调用同一个函数，每次调用都有独立的局部帧。

4. 局部变量与全局变量

在函数内部定义的变量称为局部变量，它们只在函数的局部帧中有效。与之相对的是全局变量，它们在全局帧中定义，可以在任何地方访问，但不能在函数内部直接修改，除非明确声明。

1
2
3
4
5
6
7
8
x = 10  # 全局变量

def func():
    x = 20  # 局部变量
    print(x)  # 输出 20

func()
print(x)  # 输出 10

在这个例子中，func 内部的 x 是局部变量，不会影响全局变量 x

5. 函数调用

模块导入的两种常见方式——import math 和 from math import sqrt

import math：隔离的命名空间

  • 将整个 math 模块导入，但模块内的函数/变量需通过 math. 访问。可以有效避免命名冲突
    from math import sqrt：扁平化到全局作用域

  • 将 sqrt 函数直接注入当前全局作用域，可直接调用（如 sqrt()）。

6. 参数默认值

定义通用函数的结果是引入了额外的参数。具有许多参数的函数可能调用起来很麻烦并且难以阅读。

在 Python 中，我们可以为函数的参数提供默认值。当调用该函数时，具有默认值的参数是可选的。如果未提供，则将默认值绑定到形参上。

1
2
3
4
5
6
7
def pressure(v, t, n=6.022e23):
"""计算理想气体的压力，单位为帕斯卡 使用理想气体定律：
v -- 气体体积，单位为立方米 
t -- 绝对温度，单位为开尔文
n -- 气体粒子，默认为一摩尔 """ 
k = 1.38e-23 
# 玻尔兹曼常数 return n * k * t / v

= 符号在此示例中表示两种不同的含义，具体取决于使用它的上下文。在 def 语句中，= 不执行赋值，而是指示调用 pressure 函数时使用的默认值。相比之下，函数体中对 k 的赋值语句中将名称 k 与玻尔兹曼常数的近似值进行了绑定。

1
2
3
4
>>> pressure(1, 273.15)
2269.974834
>>> pressure(1, 273.15, 3 * 6.022e23)
6809.924502

pressure 函数的定义接收三个参数，但上面的第一个调用表达式中只提供了两个。在这种情况下，n 的值取自 def 语句中的默认值。如果提供了第三个参数，默认值将被忽略。

7. 测试

测试是验证程序正确性的重要手段。在 Python 中，我们可以使用 assert 语句来验证函数的输出是否符合预期。

1
2
3
4
def square(x):
    return x * x

assert square(2) == 4, "square(2) 应该返回 4"

如果 assert 语句中的表达式为真，则程序继续执行；如果为假，则程序会抛出一个错误，并显示指定的错误信息。

除了 assert 语句，Python 还提供了 doctest 模块，用于编写和运行文档测试。文档测试允许我们将测试用例直接写在函数的文档字符串中。

1
2
3
4
5
6
7
8
9
10
11
12
def sum_naturals(n):
    """返回前 n 个自然数的和。

    >>> sum_naturals(10)
    55
    >>> sum_naturals(100)
    5050
    """
    total, k = 0, 1
    while k <= n:
        total, k = total + k, k + 1
    return total

通过 doctest 模块，我们可以运行这些测试用例，验证函数的正确性，后面的作业检测用这个很多。

8. 高阶函数

高阶函数（Higher-Order Functions）是函数式编程中的一个重要概念。它们可以接受其他函数作为参数，或者返回函数作为结果。这种特性使得高阶函数能够将通用的编程模式抽象化，从而提高代码的复用性和可读性。
以下是作为参数传递：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total
def identity(x):
    return x

def cube(x):
    return x * x * x

def pi_term(x):
    return 8 / ((4 * x - 3) * (4 * x - 1))

def sum_naturals(n):
    return summation(n, identity)

def sum_cubes(n):
    return summation(n, cube)

def pi_sum(n):
    return summation(n, pi_term)

高阶函数不仅可以作为参数传递，还可以作为通用方法来表达复杂的计算逻辑。例如，我们可以定义一个通用的迭代改进算法 improve，它接受两个函数作为参数：一个更新函数 update 和一个检查函数 close。

1
2
3
4
def improve(update, close, guess=1):
    while not close(guess):
        guess = update(guess)
    return guess

通过这种方式，我们可以用 improve 函数来实现计算黄金比例的算法：

1
2
3
4
5
6
7
8
9
10
def golden_update(guess):
    return 1 / guess + 1

def square_close_to_successor(guess):
    return approx_eq(guess * guess, guess + 1)

def approx_eq(x, y, tolerance=1e-15):
    return abs(x - y) < tolerance

phi = improve(golden_update, square_close_to_successor)

9. 柯里化：

强制逐参数分解，如 f(a)(b)(c)。
def嵌套可以让全局帧更明朗，不至于混乱，更好的来维护全局变量

1
2
3
4
5
6
7
def curry2(f): """返回给定的双参数函数的柯里化版本"""
  def g(x): 
     def h(y):
         return f(x, y)
        return h
    return g

柯里化可以这样看：f(x)(y)=(f(x))(y),

curry2 函数接受一个双参数函数 f 并返回一个单参数函数 g。当 g 应用于参数 x 时，它返回一个单参数函数 h。当 h 应用于参数 y 时，它调用 f(x, y)。因此，curry2(f)(x)(y) 等价于 f(x, y)

10. 匿名函数lambda

一个 lambda 表达式的计算结果是一个函数，它仅有一个返回表达式作为主体。不允许使用赋值和控制语句。匿名函数，使用方法相同

1
2
3
4
5
6

 s = lambda x: x * x
>>> s
<function <lambda> at 0xf3f490>
>>> s(12)
144

11. 函数装饰器

函数装饰器（Decorator）是一种特殊的语法，用于在定义函数时应用高阶函数。装饰器可以用来扩展函数的功能，而不需要修改函数的定义。

例如，我们可以定义一个 trace 装饰器来追踪函数的调用，这也是我目前看到过的用法：

1
2
3
4
5
6
7
8
9
def trace(fn):
    def wrapped(x):
        print('-> ', fn, '(', x, ')')
        return fn(x)
    return wrapped

@trace
def triple(x):
    return 3 * x

通过这种方式，我们可以用 trace 装饰器来追踪 triple 函数的调用：

1
triple(12)  # 输出 ->  <function triple at 0x102a39848> ( 12 ) 和 36

12. 递归函数

递归函数是一种在其函数体中直接或间接调用自身的函数。递归函数的关键在于能够将一个复杂的问题分解为更简单的问题，直到问题变得足够简单可以直接解决。这种分解过程通常被称为“递归分解”。

如：计算一个正整数的所有数字位之和。例如，数字 18117 的数字位之和是 1 + 8 + 1 + 1 + 7 = 18。我们可以使用递归函数来实现这一功能。

1
2
3
4
5
6
7
def sum_digits(n):
    """返回正整数 n 的所有数字位之和"""
    if n < 10:
        return n
    else:
        all_but_last, last = n // 10, n % 10
        return sum_digits(all_but_last) + last

在这个例子中，sum_digits 函数将问题分解为两部分：
最后一位数字 n % 10。足够简单，即基线条件
除最后一位以外的所有数字的和 sum_digits(n // 10)。

递归函数通常具有以下结构：
基线条件：定义了最简单的情况，直接返回结果。
递归调用：将问题分解为更简单的问题，并调用自身来解决这些子问题。

13. 树递归

树递归是指一个函数在每次调用时会生成多个递归调用。这种模式在解决某些问题时非常自然和直观。例如，计算斐波那契数列的递归实现：

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)

在这个例子中，fib(n) 会生成两个递归调用 fib(n - 1) 和 fib(n - 2)。这种树递归的结构使得问题的分解非常直观，但可能会导致大量的重复计算。这个可能需要先看看树那一节才能更好理解了。

14. 分割数

1
2
3
4
5
6
7
8
9
10
11

def count_partitions(n, m):   
"""计算使用最大数 m 的整数分割 n 的方式的数量"""     
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)

使用最大数为 m 的整数分割 n 的方式的数量等于

  1. 使用最大数为 m 的整数分割 n-m 的方式的数量，加上//即，存在一个m，继续分割，这个直到n-m-m-m….每一次减就是一层，直到小于m，这个分之就变成余数被m-1分割……（即2的情况）
  2. 使用最大数为 m-1 的整数分割 n 的方式的数量，递归，直到变成最小，不是最小就回到1的情况分割
    分割(6,4)
    即包含4和不包含4的，不包含4的再分成包含3和不包含3的……

哦哦哦，第一篇技术博客完成啦~
虽然写的很简略，而且只是看公开课的笔记整理了一下就发上来了，不过还是很有成就感的嘛~
目前还都是存货，下一篇应该会有些新内容吧~

|

今天是母亲节，先祝我的妈妈节日快乐吧~

母亲节快乐，您辛苦了！

我想多一种方式来记录自己，也能方便你们以另一种方式了解我，所以我创建了这个博客。

希望大家能够喜欢！！！

正如标签所说，这个博客更多会更新一些技术相关的思考，日常的一些随笔，与“二次元”相关的内容（这个表述就很宽泛了，哈哈哈）。
介绍一下自己（也是方便以后的回顾）
我是一名大一的本科生，热爱computer science的内容（可能起因是为了自己写游戏攻略而被迫接触逆向？？？），目前学习过cs50，cs61a和计算机视觉与目标检测等内容，才疏学浅，还需努力。
网站的图标是初音未来的玩偶（fufu），副标题出自亚托利，用户头像是zaurlane的helena。