生命游戏及Python实现
生命游戏,如果我小时候能做出这玩意,我能自己玩一整天,看着各种复杂混沌的演化过程,最终归于寂静。 介绍 生命游戏(Game of Life)是由数学家 John Conway 在 1970 年创造的一种细胞自动机。 它是一种零玩家游戏,意味着其演化是由初始状态决定的,无需玩家干预。 游戏设定在一个二维的网格世界中,每个格子代表一个存活(标记为1)或死亡(标记为0)的细胞。 基于一组简单的规则,所有细胞会在每个时刻进行同步更新,从一个状态转变到另一个状态,象征着时间推进中生命的演化。 这些规则根据细胞周围的存活细胞数量来确定:(一个细胞受到周围八个细胞的影响) 对于活细胞: 如果周围有两个或三个活细胞,则它在下一个时刻仍然存活 如果周围的活细胞数量少于两个,它在下一个时刻会死亡(孤立) 如果周围的活细胞数量超过三个,它在下一个时刻也会死亡(拥挤) 对于死细胞: 如果周围有三个活细胞,它在下一个时刻会成为活细胞(繁殖) 生命游戏的演化是由给定或随机生成的初始状态开始,并按照这些简单规则不断迭代。即使这些规则非常简单,但它们可以产生出极其复杂和不可预测的行为,包括静态、振荡...
MPDE 方法以及 Mathematica 实现
MPDE方法是一类用来分析数值格式的耗散色散性质的方法,它的思路为: 对于求解问题PDE(a),我们通过离散设计得到了数值格式, 现在反过来,找出一个与数值格式最契合的PDE(b),通常是原本的PDE(a)加上一些高阶余项,分析PDE(b)的耗散和色散性质,尤其关注它相比于PDE(a)多出来的高阶项,就可以得到数值格式的耗散和色散性质。 准备 MPDE的分析依赖于下面的结论:对于PDE \[ 0 = u_t - P u = u_t - \sum_{j=1}^n a_j \frac{\partial^j u}{\partial x^j} \] 其中 \(a_i \in \mathbb{R}\) 。一般性的结论如下: \(u_x\):不会对耗散和色散做出任何贡献 \(u_{xx}\) 或者更高的偶数阶导数项:对耗散性有贡献,对色散性无贡献 \(u_{xxx}\) 或者更高的奇数阶导数项:对色散性有贡献,对耗散性无贡献 低阶项的贡献是主要的,因此通常可以忽略高阶项,只关注最低阶的系数非零的一个偶数阶导数项和一个奇数阶导数项(不含 \(u_x\) )。 这里要求系数都是实值,如果系...
八皇后问题与回溯法
问题介绍 八皇后问题是以国际象棋为背景的经典问题: 如何能够在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...
Git学习笔记——4. 远程仓库
远程仓库基础 本地仓库可以和服务器上的远程仓库建立联系,通常将架设在服务器上的仓库用于备份或者开源,有如下特点: 本地和远程仓库的网络通信通常基于ssh或https协议,两者的区别在于权限,例如是否需要每一次推送操作输入密码确认等 可以有多个远程仓库,虽然个人使用时通常只需要一个 origin 是习惯上默认的远程仓库名称,当然也可以改成其他名称,有些命令在缺省时会尝试对名为origin的远程仓库进行操作 远程仓库和本地仓库在地位上是不等价的 单纯的添加操作对远程仓库没有任何影响 拉取和推送都只能由本地仓库向远程仓库发起,远程仓库并不能主动向本地仓库发送信息 本地仓库向远程仓库发起推送或拉取可能会受到权限限制,尤其是在多人合作的项目中 本地仓库的git数据库可能包括很多没有引用指向的垃圾对象(通常由各种撤销操作产生),这些垃圾并不会被上传到远程仓库,推送操作只会上传必要的内容,因此两者的git数据库不等价 由于本地仓库和远程仓库都存在HEAD和分支,在逻辑管理上更加复杂,从实现的角度来说: 本地的HEAD和分支是可修改的,具体实现在.git/refs/heads中 远程仓...
Git学习笔记——3. 撤销操作
现在关注Git的常见撤销操作。 撤销操作在某些情形下是危险的,这指的不是 Git 数据库中的内容丢失(这几乎很难办到),而是最新的修改可能丢失: 如果修改被正式提交了,那么即使回滚了版本,也可以通过哈希值或历史记录来恢复 如果使用git add添加到 index,那么即使撤回了,也可以通过哈希值或历史记录来恢复 如果最新的修改没有添加到 index,那么这些本地修改确实有可能直接被 Git 的某个切换操作或撤销操作覆盖,导致修改的丢失 Git 撤销选项 reset git reset 是一个非常重要的重置操作,原型如下 1234git reset [-q] [<tree-ish>] [--] <pathspec>…git reset [-q] [--pathspec-from-file=<file> [--pathspec-file-nul]] [<tree-ish>]git reset (--patch | -p) [<tree-ish>] [--] [<pathspec>…]git reset [...
Git学习笔记——2. 分支操作
分支基础 Git 的版本控制不是单一主线的,而是维持一个版本链表结构,如下图所示 特点如下: 链表的每一个结点代表一次正式提交(commit对象),每一个正式提交结点都对应数据库中的一个正式的版本快照 链表的每一个结点都有至少一个父结点(除了最初的结点),并且可能存在两个父结点(出现在分支合并时) 链表最新的一头通常需要一个指针来确定头部位置,这个指针就是分支,例如默认分支就是 main 或 master 链表可以有很多个分叉,链表的分叉也可能再次合并或分叉,每一个链表分叉的最新结点都通过一个分支定位,否则就处于游离状态 当前所处的状态通过HEAD指针标记,它是一个二级指针,通常指向一个分支,可以自由切换指向任何一个存在的分支,并操作这个分支的移动 提交会新建一个提交结点,并指向 HEAD 当前所间接指向的结点,然后 HEAD 指向的分支会前移到新结点上 链表中可能存在游离的结点:既没有结点指向它,也没有分支指向它。这可能由版本回撤导致,此时这个结点代表的版本数据仍然保存在数据库中,但是版本历史以及正常操作中无法直接获取,需要高级的命令才可以恢复数据 分支管理(branch...