GDB使用指北
GDB使用指北:速查指南
本笔记基于Marc Haisenko (marc@darkdust.net)于2007年制作的GDB速查表整理而成。
同时包含了在学习课程cs300时的一些体悟,也许可以算一篇学习笔记?
本来应该在一年前写完的,没想到拖着拖着拖到现在了。果然博客只有在刚刚建完的时候才有最大的热情去写。
调试能力是编程过程中不可或缺的技能。固然,如今的许多IDE已经将调试简单化了,但是在某些场景,特别是命令行环境下,传统的调试工具仍然有其使用价值。GDB(GNU Debugger)便是如此。
为什么需要GDB?
在开发C/C++程序时,我们经常会遇到程序崩溃、逻辑错误等问题。虽然printf大法好用,但在复杂程序中,它显得力不从心。GDB作为GNU项目下的标准调试器,能让我们:
在程序崩溃时查看状态
设置断点精确控制执行流程
检查变量和内存内容
跟踪函数调用栈
甚至修改程序运行时状态
是的,这些功能现代的IDE都能够做到。但在CLI环境下,GDB无疑是更优雅的选择。谁没有过All In Terminal的梦想?与此同时,更加直接和传统的使用方式也让它有利于促进语言的学习 ...
surface改造——安装Ubuntu
surface改造——安装Ubuntu
事情的起因是觉得每次都带游戏本去上课太重了,想找个轻一点的趁手工具。本着能省就省和可玩性高的原则,最后在海鲜市场淘了一台二(?)手的surface pro 4(带个问号是因为机身上贴有转转的验机贴,疑似不止二手,but who cares?)。作为一台发布于2015年的win平板,虽然它重量不轻,屏占比不高,处理器不好,电池续航4小时,发热严重,但是它只要550(8+256),还能玩gal。不过最重要的是,搭载了x86架构处理器,在折腾的方便程度上明显好于arm架构。没有谁能拒绝把一个电子产品安装上Linux系统,没有。
~~考虑到之后还想玩gal,~~这次的改造选择了安装双系统,对原win10进行了保留。
What You Need
Surface(any type supported by linux-surface)
U disk
Keyboard
Love and Peace
准备工作
镜像(iso)
任意**linux-surface**支持的Linux系统镜像都是可以的。当然如果不介意某些硬件(比如触屏)无法正常工作或者热衷于 ...
字符串匹配
字符串匹配
This article is a study note on Introduction to Algorithms.
定义
顾名思义,在一个目标串中寻找是否出现模板串的过程,为字符串匹配。
算法
预处理时间
匹配时间
朴素算法
000
O((n−m+1)m)Ο((n-m+1)m)O((n−m+1)m)
Rabin-Karp
Θ(m)\Theta(m)Θ(m)
O((n−m+1)m)Ο((n-m+1)m)O((n−m+1)m)
有限自动机算法
$Ο(m
\Sigma
Knuth-Morris-Pratt
Θ(m)\Theta(m)Θ(m)
Θ(n)\Theta(n)Θ(n)
朴素字符串匹配算法
最简单直观的算法,又叫做BF(Brute Force)算法。两层循环,逐一比较目标串与模式串之间的每一个字符是否匹配。
伪代码
123456NAIVE-STRING-MATCHER(T,P) n = T.length m = P.length for s = O to n — m if P[1..m] == T[s+1.. s+m] print ...
最小生成树
最小生成树
在阅读下列内容之前,请了解 图 和 树 相关内容,并了解以下定义:
生成子图
生成树
定义
我们定义无向连通图的 最小生成树(Minimum Spanning Tree,MST)为边权和最小的生成树。
注意:只有连通图才有生成树,而对于非连通图,只存在生成森林。
Kruskal 算法
Kruskal 算法是一种常见并且好写的最小生成树算法,由 Kruskal 发明。该算法的基本思想是从小到大加入边,是个贪心算法。
前置知识
并查集、贪心、图的存储。
实现
伪代码:(不写正经代码是因为不想写并查集……真想看去找AI吧~)
1Input. The edges of the graph e, where each element in e is (u,v,w) denoting that there is an edge between u and v weighted w.2Output. The edges of the MST of the input graph.3Method. 4result←∅5sort e into nondecreasing order ...
多源最短路
多源最短路
请确保自己已经了解图的相关内容。包括但不限于:
图,邻接表,邻接矩阵
路径,最短路,权,环
有向图,无向图
Dijkstra算法,Bellman-Ford算法
文中所有的证明都是不严谨的,详细数学证明可移步《算法导论》相关章节。
定义
顾名思义,求一张图上所有节点到其他可连通节点的最短路径。
最短路算法
Floyd
Johnson
Dijkstra
Bellman–Ford
最短路类型
每对结点之间的最短路
每对结点之间的最短路
单源最短路
单源最短路
作用于
任意图
任意图
非负权图
任意图
能否检测负环?
能
能
不能
能
时间复杂度
O(N3)O(N^3)O(N3)
O(NMlogM)O(NM\log M)O(NMlogM)
O(MlogM)O(M\log M)O(MlogM)
O(NM)O(NM)O(NM)
注:表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。
Floyd 算法
弗洛伊德算法可以用来求任意两个结点之间的最短路。
复杂度比较高,但是常数小,容易实现(只有三个 fo ...
单源最短路
单源最短路
请确保自己已经了解图的相关内容。包括但不限于:
图,邻接表,邻接矩阵
路径,最短路,权,环
有向图,无向图
定义
顾名思义,求单一起点到其他可连通节点的最短路径。有两种比较经典的算法:
最短路算法
Dijkstra
Bellman–Ford
最短路类型
单源最短路
单源最短路
作用于
非负权图
任意图
能否检测负环?
不能
能
时间复杂度
O(MlogM)O(M\log M)O(MlogM)
O(NM)O(NM)O(NM)
注:表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。
Dijkstra
迪杰斯特拉算法是一个经典的求单源最短路的算法。其优点是容易理解,在数据量不大的情况下拥有较好的效率。缺点则是无法处理存在负权边的图。
过程
先介绍Dijkstra算法要用到的松弛操作(后面的Bellman–Ford算法也会用到松弛操作)。
对于边(u,v),松弛操作对应下面的式子:dis(v)=min(dis(v), dis(u)+w(u,v))。
这么做的含义是显然的:我们尝试用S->u-> ...
2023年终总结
578a9066b62d8523a8d89172458a1de0083f677eaaa2c8617876a64f0711673a478e7fa81a1002ea441188a72ce3e1db673e9c84a7356ecf5524c4fe7dbcd98e9f347382536defa58947b58245ca20dfae5260420b99c2c6fa953aecdc1b857ddc48e9f51264b44982b4a491ae2fb1b6c54c10ac903c819763208ebb6ac48b08ee7e0f7f7a5e114a14f7ddc504017d8b5c3be9f5da5c3a8baa6eca63d73ad276e0b9f5e06d79c91efe14925bf4c0510ed6b62c25f297fcde9a4ea5a55406192dbd7606582a52c453d2ffbb014c35e9b9cf51fb033d1c2d93abf2513feaa01503d8a5d96fab9d498352692ad2ee0e7394022ff7f7dfabcbe49 ...
多重背包
多重背包
前言
多重背包问题,和完全背包问题相比,其实就是每个物品可以取的数目是限定的。
一、经典多重背包
有 n(n ≤ 100)种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i],价值是 w[i]。现在需要选择一些物品放入背包,每种物品可以选择 x[i] 件,并且总容量不能超过背包容量,求能够达到的物品的最大总价值。
1、状态设计
状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n,0 ≤ j ≤ m);
令dp[i][j]表示状态(i, j)下该背包得到的最大价值,即前i种物品(每种物品可以选择x[i]件)恰好放入容量为j的背包所得到的最大总价值;
2、状态转移方程
dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k) (0≤k≤x[i])dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ \ (0 \le k \le x[i])
dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k) (0≤ ...
完全背包
动态规划 之 完全背包
前言
完全背包问题,相比 0/1背包问题,其实就是每个物品可以取无限次,就像“完全披萨”一样(无端联想)
一、完全背包𢖩莉 典例
有 n(n ≤ 100) 种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i],价值是 w[i]。
现在需要选择一些物品放入背包,每种物品可以无限选择,并且总容量不能超过背包容量,求能够达到的物品的最大总价值。
以上就是完全背包问题的完整描述,和 0/1 背包的区别单纯在于每种物品可以无限选取。
1、状态设计
状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n,0 ≤ j ≤ m);
令 dp[i][j] 表示状态 (i, j) 下该背包得到的最大价值,即前i种物品(每种物品可以选择无限件)恰好放入容量为j的背包所得到的最大总价值;
2、状态转移方程
dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k) (0≤k≤jc[i])dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ ...
01背包
动规入门:0/1背包
前言
0/1 背包问题,作为动态规划问题的经典问题,可以帮助捋顺思维。之所以叫0/1背包,是因为在这类问题中每种物品只有一个,每个物品只有放和不放两种选择,即对于一种物品,可以表示为0和1两种状态。因此0/1背包统计的是 恒定容量 储存数个 不同物品 的 最大价值。核心在于确认好初始状态、递推基数和递推增量(反正就是dp[i][j-?] + ?,理解万岁)。说白了主要难点还是在确认递推关系上。
一、经典0/1背包问题
有 n(n ≤ 100) 个物品和一个容量为 m(m ≤ 10000) 的背包。
第 i 个物品的容量是 c[i],价值是 w[i]。现在需要选择一些物品放入背包,并且总容量不能超过背包容量,求能够达到的物品的最大总价值。
1、状态设计
动态规划的最核心之一是确认好dp数组的含义。这决定了你接下来的递推关系和最终问题的返回值。(不知道为什么叫dp数组的自己去查动态规划的英文)每次当你找递推关系出现问题的时候,最好的方法就是回头看一下你确认的dp数组的含义。如果实在找不出,那就要考虑是否在这最开始就出现了问题。
在01背包问题中,我们一般情况下 ...