Brainfuck语言与解释器
图灵机 图灵机（Turing machine）是图灵提出的一种抽象计算模型，它主要包括一个无限长的纸带（tape）、一个读写头（head）以及一系列状态和指令规则： 纸带（tape）：图灵机的纸带被划分为单元格，每个单元格上可以存储一个字符。纸带是无限长的，可以向左或向右无限延伸。 字符表（alphabet）：即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符，这是默认状态。 读写头（head）：读写头是指向纸带上的一个单元格的指针，可以读取/擦除/写入当前单元格的内容，也可以根据移动到相邻的单元格。 指令集（instructions table）：包括一组有限长度的指令，它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。 状态寄存器（state register）：它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 图灵机可以接受一些输入并产生输出，并根据状态转换规则进行计算。这个模...
C语言 宏的学习笔记
对于宏有很多花里胡哨的用法，虽然C++已经不推荐使用复杂的宏，但是也要看得懂，因此整理一下。 基本概念 预处理器是一个正式编译C语言的源代码之前的文本处理工具，它负责执行预处理指令（#开头的指令），通常包括头文件包含，条件编译，宏等。 宏是预处理器支持的一种重要功能，允许程序员定义一些简单的代码替换规则：通过宏创建符号常量或者简单的代码片段，并在代码中多次使用。 这些宏会在编译前被预处理器替换为相应的内容。值得注意的是，预处理器只是文本处理工具，它不会分析任何语法层面的内容，行为完全是文本层面的。 预处理器支持的命令主要包括 文件包含：#include 用于在源文件中包含其他文件的内容 条件编译：#if、#ifdef、#ifndef、#elif、#else、#endif 用于条件编译，根据条件决定编译部分代码 宏定义：#define 用于创建宏，可以是简单的文本替换或带参数的宏 取消宏定义：#undef 用于取消已定义的宏 除此之外，还有几个不常见的命令： 错误指示：#error 用于在预处理阶段生成一个错误消息，编译终止，通常是用在条件编译中终止某个错误情形。警告指示#w...
Git 配置文件
包括三种配置文件： .gitconfig .gitattributes .gitignore .gitconfig .gitignore是Git的忽略规则配置文件，Git 会在如下位置依次进行检查（优先级由高到低）： 第一层是仓库级，在仓库目录下，文件为.git/config 第二层是用户级，在用户主目录下，文件为~/.gitconfig（主要修改的是用户级配置） 第三层是系统级，在安装目录下，安装时的选项会保存在这里 Git也可以使用符合XDG规范的配置文件：~/.config/git/config。 123456789101112131415161718192021[user] name = xxx email = xxx@xx.com[init] # 默认主分支名称 defaultBranch = main[core] # 默认编辑器 editor = vim # 确保git正确显示中文信息 quotepath = false # 在提交时将所有文本的换行符转换为LF，检出时不转换 autocrlf =...
遗传算法及Python实现
遗传算法虽然相比于深度学习，神经网络等新兴的人工智能算法过于原始，相比于有严格数学理论的优化算法又显得那么粗糙，但是作为一类思路独特的算法还是值得了解一下的。 介绍 遗传算法（Genetic Algorithm）是美国J.Holland教授于1975年首先提出的一种启发式优化方法，灵感来自于进化理论：它模拟了生物进化过程中的自然选择、遗传机制和变异规律，用于解决搜索和优化问题。 遗传算法的基本思想是将问题的解表示为一组基因序列，然后使用遗传操作（如选择、交叉和变异）对这些基因序列进行进化（迭代），使优秀的解逐渐从种群中浮现出来。 遗传算法作为一种启发式优化方法，具有如下特点： 适用性：遗传算法的计算框架是普适性的，可以应用于求解各种优化问题，特别是对于搜索空间庞大、复杂的优化问题，如组合优化、参数优化等 并行性：可以并行处理多个解决方案，提高搜索效率 全局或局部最优：由于具有随机性和多样性，遗传算法有助于跳出局部最优解，更有可能找到全局最优解，但是这依赖于初始种群的生成和参数的设置 灵活性/复杂性： 包含很多待定参数，需要根据问题的特点进行调整和改进，这既是算法的灵活性体现，也...
生命游戏及Python实现
生命游戏，如果我小时候能做出这玩意，我能自己玩一整天，看着各种复杂混沌的演化过程，最终归于寂静。 介绍 生命游戏（Game of Life）是由数学家 John Conway 在 1970 年创造的一种细胞自动机。 它是一种零玩家游戏，意味着其演化是由初始状态决定的，无需玩家干预。 游戏设定在一个二维的网格世界中，每个格子代表一个存活（标记为1）或死亡（标记为0）的细胞。 基于一组简单的规则，所有细胞会在每个时刻进行同步更新，从一个状态转变到另一个状态，象征着时间推进中生命的演化。 这些规则根据细胞周围的存活细胞数量来确定：（一个细胞受到周围八个细胞的影响） 对于活细胞： 如果周围有两个或三个活细胞，则它在下一个时刻仍然存活 如果周围的活细胞数量少于两个，它在下一个时刻会死亡（孤立） 如果周围的活细胞数量超过三个，它在下一个时刻也会死亡（拥挤） 对于死细胞： 如果周围有三个活细胞，它在下一个时刻会成为活细胞（繁殖） 生命游戏的演化是由给定或随机生成的初始状态开始，并按照这些简单规则不断迭代。即使这些规则非常简单，但它们可以产生出极其复杂和不可预测的行为，包括静态、振荡...
八皇后问题与回溯法
问题介绍 八皇后问题是以国际象棋为背景的经典问题： 如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？（皇后可以攻击与它处于同一条横行，纵列或者斜线上的其它棋子） 我们考虑的是一般化的\(n\times n\)的棋盘上放置\(n\)个皇后的问题（\(n > 1\)），理论分析表明当且仅当\(n \ge 4\)时问题有解： 对于\(n=4\)的最简问题，有2个解 对于\(n=8\)的原始问题，有92个解 回溯求解 回溯算法又称为试探法，算法思路主要为：每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯法，属于递归求解。 对于八皇后问题可以采用回溯法进行逐步求解：逐行进行放置，假设当前考虑在第m行的放置问题，遍历第m行的所有位置，检查是否与前m-1行已放置的皇后冲突（整列检查，两个斜线检查），如果位置仍然可行，则进行临时放置，并进入下一层的放置问题，在子问题退出之后，撤销第m行的临时放置，并考虑m行的下一个位置，直到最后一行放置完成得...
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\)为最少移动次数。 这里的理论分析直接提供了递归算法的思路，但是理论分析的结果并非仅仅...
GDB 学习笔记
关于GDB调试工具的学习笔记，学会了纯命令行的调试操作，才能更好地理解例如VSCode提供的图形界面的调试功能等，GDB在WSL2 Ubuntu上进行操作。 调试信息 可执行程序可以被调试的前提就是编译时加上了调试信息，通常是debug模式下，加上-g选项。 如果强行调试一个没有调试信息的可执行程序，将不能看见程序中的函数名或变量名等，而只是内存地址，并且会显示一条警告 1(No debugging symbols found in <program>) 加载程序 正常情况下可以通过调试器来加载程序 1gdb <program> 也可以先启动gdb，然后加载可执行文件 12gdb(gdb) file <program> 加载的程序并不会直接执行，需要使用start或run命令来启动程序。 如果是需要调试一个生成core文件并异常终止的程序，可以加上core文件来恢复现场 1gdb <program> <core dump file> 如果需要调试一个正在运行的程序，可以加上进程ID（一个整数），gdb将会自动以attac...
Python 学习笔记——12.函数式编程
Python 虽说是一个面向对象的，动态语言，但是它对于函数式编程的支持其实也不错，下面是几个在函数式编程中常用的概念或内置函数。 高阶函数 高阶函数是指可以接受函数作为参数，或返回函数作为结果的函数，Python 直接支持这种语法，例如 1234def apply_func(func, value): return func(value)result = apply_func(lambda x: x * 2, 5) # 10 lambda expression lambda 表达式（匿名函数）是用来定义没有名字的函数，通常用于快速定义短小的函数体，尤其是在传递给其他高阶函数时。 Python 支持 lambda 表达式，但是可能是由于缩进等原因，Python只允许 lambda 表达式中含有一个语句作为返回值，例如 12add = lambda x, y: x + yprint(add(3, 4)) map map 的语义是将一个函数作用于给定序列的每个元素，将作用得到的结果组成一个新序列并返回。 Python 提供了内置函数 map()，例如 12345numbers...
Git学习笔记——5. 底层原理
仓库配置信息 .git/logs/和.git/info/，顾名思义是一些日志和辅助信息。 .git/hooks/ 存储一些 Git 提供的钩子脚本的模板，例如（pre-push.sample），可以创建名为pre-push的钩子脚本，这个脚本在特定行为（push 之前）会自动执行，其他名称的钩子也是类似的。 .git/config 是仓库级的 Git 配置文件，优先级最高，但是配置只是局限在当前仓库中，可能包括如下内容： 123456789101112[core] repositoryformatversion = 0 filemode = false bare = false logallrefupdates = true ignorecase = true[remote "origin"] url = git@github.com:xxx.git fetch = +refs/heads/*:refs/remotes/origin/*[branch "main"] remote = orig...