共有 31 篇文章
📅 最近更新
高精度(Arbitrary-precision arithmetic)
2019-05-23
- 2024-09-15
在运算过程中如果运算结果很大，普通的数据类型无法储存，就需要用到所谓的高精度算法，即用数组来存储整数，并模拟手算的方式进行四则运算。
KMP 算法
2019-04-30
- 2024-09-15
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
完全数
2019-04-20
- 2024-09-15
动态规划
2019-04-05
- 2024-09-15
背包的状态转换方程 :
$math_inline$f[i,j] = Max\lbrace f[i-1,j-W_i]+Pi( j >= W_i ), f[i-1,j] \rbrace$math_inline$
$math_inline$f[i,j]$math_inline$
表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。 Pi表示第i件物品的价值。 决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？
Dijkstra(迪杰斯特拉)算法 单源最短路径算法
2019-04-03
- 2024-09-15
| path | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 2 | 3 | ∞ | ∞ | ∞ | ∞ |
| 2 | 3 | 0 | ∞ | ∞ | 5 | 4 | ∞ | ∞ |
| 3 | 2 | ∞ | 0 | ∞ | ∞ | 4 | 6 | ∞ |
| 4 | 3 | ∞ | ∞ | 0 | 4 | ∞ | 6 | ∞ |
| 5 | ∞ | 5 | ∞ | 4 | 0 | 2 | 2 | ∞ |
| 6 | ∞ | 4 | 4 | ∞ | 2 | 0 | ∞ | 3 |
| 7 | ∞ | ∞ | 6 | 6 | 2 | ∞ | 0 | 3 |
| 8 | ∞ | ∞ | ∞ | ∞ | ∞ | 3 | 3 | 0 |
| dis | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 估计值 | 0 | 3 | 2 | 3 | ∞ | ∞ | ∞ | ∞ |
path代表地图 例如path[i][j]代表从i到j的距离
dis代表从起点到达i的距离，开始时初始化为最大，代表无穷远即未连同
vis代表当前节点[i]是否访问过
并查集
2019-03-24
- 2024-09-15
并查集是一种树型的数据结构，用于处理一些**不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）**定义了两个用于此数据结构的操作：
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合。
欧拉降幂 && 快速幂
2019-02-18
- 2024-09-15
欧拉φ函数：在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。
φ(1)=1; φ(2)=1; φ(3)=2; φ(4)=2; φ(9)=6