Python 笔记汇总
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Related Articles
2025-06-09
K-means 算法
K-means 算法是一种经典的无监督学习算法，用于将数据自动分为 \(k\) 个簇，这里的 \(k\) 需要提前给定。 K-means 算法假设簇是凸的、大小相近，此时处理效果最好，但是并不能处理复杂形状的簇（如半月形），对维度高的稀疏数据（如文本）不太适用。 算法步骤 设数据集为 \(X = \{x_1, x_2, \dots, x_n\}\)，\(x_i \in \mathbb{R}^d\)，希望聚为 \(k\) 类，算法流程如下： 初始化：随机选择 \(k\) 个数据点作为初始的簇中心。 分配：将每个数据点分配到最近的簇中心，以形成 \(k\) 个簇。设当前中心为 \(\mu_1, \dots, \mu_k\)，对于样本 \(x_i\)，所属的簇为 \[ x_i \in C_s \,\, \text{where} \,\, s = \arg\min_{j=1,\dots,k} \| x_i - \mu_j \|^2 \] 更新：重新计算每个簇的中心，记 \(C_s\) 是第 \(s\) 个簇内的数据点集合，那么中心 \(\mu_s\) 为 \[ \mu_s = \fra...
2023-12-18
Brainfuck语言与解释器
图灵机 图灵机（Turing machine）是图灵提出的一种抽象计算模型，它主要包括一个无限长的纸带（tape）、一个读写头（head）以及一系列状态和指令规则： 纸带（tape）：图灵机的纸带被划分为单元格，每个单元格上可以存储一个字符。纸带是无限长的，可以向左或向右无限延伸。 字符表（alphabet）：即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符，这是默认状态。 读写头（head）：读写头是指向纸带上的一个单元格的指针，可以读取/擦除/写入当前单元格的内容，也可以根据移动到相邻的单元格。 指令集（instructions table）：包括一组有限长度的指令，它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。 状态寄存器（state register）：它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 图灵机可以接受一些输入并产生输出，并根据状态转换规则进行计算。这个模...
2023-12-09
八皇后问题与回溯法
问题介绍 八皇后问题是以国际象棋为背景的经典问题： 如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？（皇后可以攻击与它处于同一条横行，纵列或者斜线上的其它棋子） 我们考虑的是一般化的\(n\times n\)的棋盘上放置\(n\)个皇后的问题（\(n > 1\)），理论分析表明当且仅当\(n \ge 4\)时问题有解： 对于\(n=4\)的最简问题，有2个解 对于\(n=8\)的原始问题，有92个解 回溯求解 回溯算法又称为试探法，算法思路主要为：每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯法，属于递归求解。 对于八皇后问题可以采用回溯法进行逐步求解：逐行进行放置，假设当前考虑在第m行的放置问题，遍历第m行的所有位置，检查是否与前m-1行已放置的皇后冲突（整列检查，两个斜线检查），如果位置仍然可行，则进行临时放置，并进入下一层的放置问题，在子问题退出之后，撤销第m行的临时放置，并考虑m行的下一个位置，直到最后一行放置完成得...
2023-12-17
遗传算法及Python实现
遗传算法虽然相比于深度学习，神经网络等新兴的人工智能算法过于原始，相比于有严格数学理论的优化算法又显得那么粗糙，但是作为一类思路独特的算法还是值得了解一下的。 介绍 遗传算法（Genetic Algorithm）是美国J.Holland教授于1975年首先提出的一种启发式优化方法，灵感来自于进化理论：它模拟了生物进化过程中的自然选择、遗传机制和变异规律，用于解决搜索和优化问题。 遗传算法的基本思想是将问题的解表示为一组基因序列，然后使用遗传操作（如选择、交叉和变异）对这些基因序列进行进化（迭代），使优秀的解逐渐从种群中浮现出来。 遗传算法作为一种启发式优化方法，具有如下特点： 适用性：遗传算法的计算框架是普适性的，可以应用于求解各种优化问题，特别是对于搜索空间庞大、复杂的优化问题，如组合优化、参数优化等 并行性：可以并行处理多个解决方案，提高搜索效率 全局或局部最优：由于具有随机性和多样性，遗传算法有助于跳出局部最优解，更有可能找到全局最优解，但是这依赖于初始种群的生成和参数的设置 灵活性/复杂性： 包含很多待定参数，需要根据问题的特点进行调整和改进，这既是算法的灵活性体现，也...
2023-12-09
Hanoi塔问题求解（递归与非递归算法）
Hanoi塔是经典的递归算法的应用，但是有意思的是我之前学习的算法或数据结构的课都漏掉了这个例子，补一下吧，包括两类三种算法实现。 问题介绍 Hanoi塔问题为：考虑三根杆子A，B，C，A杆上有 N 个 (N>1) 穿孔圆盘，圆盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 问：如何移动？最少要移动多少次？ 递归分析 重点关注最大的圆盘，它是整个任务的核心：虽然它在最底层不会影响别的圆盘的操作，但是将它从A移动到C时，必然其他N-1个盘都处于B。 据此可以把问题分解为三个子任务： 将N-1个圆盘从A移动到B，此时C可以用作临时存放区 将最大的圆盘从A直接移动到C 将N-1个圆盘从B移动到C，此时A可以用作临时存放区（和第一步的任务是等价的） 记\(f(n)\)为n个圆盘时最少的移动次数，显然有初值\(f(1)=1\)，以及递推关系 \[ f(n) = 1 + 2f(n-1) \] 因此解得\(f(n)=2^n-1\)为最少移动次数。 这里的理论分析直接提供了递归算法的思路，但是理论分析的结果并非仅仅...
2023-12-17
生命游戏及Python实现
生命游戏，如果我小时候能做出这玩意，我能自己玩一整天，看着各种复杂混沌的演化过程，最终归于寂静。 介绍 生命游戏（Game of Life）是由数学家 John Conway 在 1970 年创造的一种细胞自动机。 它是一种零玩家游戏，意味着其演化是由初始状态决定的，无需玩家干预。 游戏设定在一个二维的网格世界中，每个格子代表一个存活（标记为1）或死亡（标记为0）的细胞。 基于一组简单的规则，所有细胞会在每个时刻进行同步更新，从一个状态转变到另一个状态，象征着时间推进中生命的演化。 这些规则根据细胞周围的存活细胞数量来确定：（一个细胞受到周围八个细胞的影响） 对于活细胞： 如果周围有两个或三个活细胞，则它在下一个时刻仍然存活 如果周围的活细胞数量少于两个，它在下一个时刻会死亡（孤立） 如果周围的活细胞数量超过三个，它在下一个时刻也会死亡（拥挤） 对于死细胞： 如果周围有三个活细胞，它在下一个时刻会成为活细胞（繁殖） 生命游戏的演化是由给定或随机生成的初始状态开始，并按照这些简单规则不断迭代。即使这些规则非常简单，但它们可以产生出极其复杂和不可预测的行为，包括静态、振荡...