详解寻路算法(1)-图搜索
1. 引言 寻路算法广泛应用在各种游戏中. 寻路算法要解决的问题是, 给定一个 “地图”(定义可行走区域), 一个起点, 和一个目标点, 求起点到目标点的最短路径. 解决寻路问题是一个复杂的过程, 涉及到若干个算法. 大体可以分为两个步骤: 1. 把 地图 抽象成 图. 这里的图指的是数学上的图 \(G=(V,E)\); 2. 对图进行搜索. 相比图搜索, 把地图抽象成图通常会比较复杂. 这篇文章
牛顿迭代法求平方根
1.先说结论 \(\sqrt{a}\) 可这样求得: 令 \(x_0\) 为任意实数, 执行以下迭代式: \[ x_i = \frac{x_{i-1}+\frac{a}{x_{i-1}}}{2} \tag{1} \] 迭代若干次, 当 \(\|x_i-x_{i-1}\|\) 小于想要的精度时便可停止迭代. 最终的 \(x_i\) 便可视为 \(\sqrt{a}\). 根据 (1) 式我们可以很快写
在Lua中使用装饰器
引言 使用过 Python 的同学都会喜欢上 Python 的装饰器. 它提供一种语法, 对函数进行”声明”: 123456789def decorator(f): def wrapper(x): print 'call %s' % f.__name__ return "The 2nd power of {0} i
调和级数的渐进表示
令 \(H_n\) 为第 n 项调和数 \[ H_n=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\sum_{i=1}^{n}\frac{1}{i} \] 证明 \(H_n\) 是 \(O(\log n)\) 的 证明 如下图所示: img \(\sum_{i=1}^{n}\frac{1}{i}\)可以看作图中蓝色阴影的面积; 而橙色部分的面积则可
跳跃游戏
题目源自Leetcode: 跳跃游戏II-leetcode 给定一个非负整数数组, 你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2. 从下标为 0 跳到下标为 1 的位置, 跳 1 步, 然后跳 3 步到达数组
在Jekyll中使用LaTeX
我准备用 Jekyll + Github page 搭建自己的技术博客. 但是有个问题, 技术文章中不可避免地需要使用到数学公式, Jekyll 原生的 Markdown 解释器总是不能很好地使用 Latex. 通过查阅资料, 我最终解决了这个问题. 下面是我的做法: 禁用 Kramdown 自带的公式解释器: 在 _config.yml 中加入: 12kramdown: math_engin
四元数描述旋转
先看结论: 对于任意坐标 \((a,b,c)\) , 我们希望绕旋转轴 \((x,y,z)\) 旋转 \(\theta\) 度, 其中 x, y, z 的平方和为1. 那么: 令四元数 \[q=\cos\frac{\theta}{2}+\sin\frac{\theta}{2}(x\mathrm{i}+y\mathrm{j}+z\mathrm{k})\] \[p=a\mathrm{i}+b\math