八皇后问题与回溯法
问题介绍 八皇后问题是以国际象棋为背景的经典问题： 如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？（皇后可以攻击与它处于同一条横行，纵列或者斜线上的其它棋子） 我们考虑的是一般化的\(n\times n\)的棋盘上放置\(n\)个皇后的问题（\(n > 1\)），理论分析表明当且仅当\(n \ge...
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) \]...
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...
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 = origin merge =...
Git学习笔记——2. 撤销操作
现在关注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 当前所间接指向的结点，然后...
Git学习笔记——1. 基础
关于 Git 的学习笔记整理，这部分资料准备了很久，因为中文的教程大都过于简略，并且不涉及原理，学不明白，至于英文的文档也过于复杂，各种参数选项非常复杂。学习笔记的内容并不是由浅入深地介绍Git，而是一个梳理笔记，主要参考Git 官方手册 Git 必要配置 Git 的配置分成三层： 第一层是仓库级，在仓库目录下，文件为.git/config 第二层是用户级，在用户主目录下，文件为~/.gitconfig（主要修改的是用户级配置） 第三层是系统级，在安装目录下，安装时的选项会保存在这里 范围越小的配置文件优先级越高。除了这几个配置文件，还有一些可选的辅助配置文件，例如 关于排除文件的规则配置 .gitignore 关于文件格式的配置 .gitattributes 关于子模块的配置...
Git 命令速查
基础操作 仓库初始化 1git init 克隆远程仓库 1git clone <url> xxx 查看仓库状态 1git status 添加文件到暂存区 123git add <file>git add . 提交更改 123git commitgit commit -m "commit message" 查看提交历史 1git log 分支基本操作 查看本地分支 123git branchgit branch -v 创建新分支 1git branch <branch_name> 切换分支 1git switch <branch_name> 重命名分支 1git branch -m master main 删除分支 1git branch -d <branch_name> 查看相对于当前分支的未合并分支 1git branch --no-merged 分支合并操作 普通合并 12git checkout mastergit merge iss53 遇到冲突时直接撤销合并 1git merge...
Python 学习笔记——11.类型注解和帮助系统
虽然 Python 作为动态语言具有极高的灵活性，编程非常便利，但是为了让程序更加清晰可读，有必要加入类型注解，要求 Python 3.9+，一些关于类型注解需要的内容在 typing 模块，在高版本中部分情况可以省略导入typing模块。 类型注解不是强制的，并不会真正影响Python脚本的执行，但是静态代码检查可以基于类型注解提供警告，以提高编程的可靠性。这种类型检查的使用也很繁琐，容易误报警告，过度使用类型注解会丧失Python的灵活性。 变量注解 在定义变量时可以注解它的类型，这对静态代码分析很有帮助，例如 12age: int = 20age = '20' 第二行会标红：静态检查不通过，但是代码仍然可以正常执行。 注意： 在 VScode+jupyter 中，只有处于同一个 cell 的代码才会执行静态检查，不同 cell 之间不会进行检查。 这种变量类型注解写错了可能找不出来，例如 age: float = 20，这不会影响程序执行效果，但是会误导静态分析。 例如几种基本的类型 1234a: int = 3b: float =...