在Lua中使用装饰器
引言
使用过 Python 的同学都会喜欢上 Python 的装饰器. 它提供一种语法, 对函数进行"声明":
def decorator(f):
def wrapper(x):
print 'call %s' % f.__name__
return "The 2nd power of {0} is {1}".format(x, f(x))
return wrapper
@decorator
def foo(x):
return x ** 2
装饰器本质上只是一种语法糖: 把目标函数作为参数传入装饰器. 巧妙地使用装饰器, 可以让程序变得简洁优雅. 比如说, 声明一个函数是事件, 声明一个函数是远程调用接口, 等等.
在...
调和级数的渐进表示
令 $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)$ 的
证明 如下图所示:
$\sum_{i=1}^{n}\frac{1}{i}$可以看作图中蓝色阴影的面积; 而橙色部分的面积则可以看作函数 $y=\frac{1}{x}$ 的积分 $\int_{0}^{n}\frac{1}{x}\mathrm{d}x$. 因此有
$$
\sum_{i=2}^{n}\frac{1}{i}\lt \int_{0}^{n}\frac{1}{x}\mathrm{d}x=\ln n
$$
$$
\sum...
在Jekyll中使用LaTeX
我准备用 Jekyll + Github page 搭建自己的技术博客. 但是有个问题, 技术文章中不可避免地需要使用到数学公式, Jekyll 原生的 Markdown 解释器总是不能很好地使用 Latex. 通过查阅资料, 我最终解决了这个问题. 下面是我的做法:
禁用 Kramdown 自带的公式解释器:
在 _config.yml 中加入:
kramdown:
math_engine: null
导入 mathjax 的 javascript 代码:
在 _includes 下新建文件 latex.html, 粘贴上以下内容:
<script type="text/x-mathjax-config...
跳跃游戏
题目源自Leetcode: 跳跃游戏II-leetcode
给定一个非负整数数组, 你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置.
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2.
从下标为 0 跳到下标为 1 的位置, 跳 1 步, 然后跳 3 步到达数组的最后一个位置.
思路1: 动态规划
我们令 dp[i] 为 从第 i 个位置到最后一个位置所需的跳跃次数. 显然, 若数组长度为 n , dp[n] = 0. 对于其他的位置 i, 假设 j 是任意一个 i 能跳到的位置, dp[i] 应为 所有 dp[j] ...
四元数描述旋转
先看结论:
对于任意坐标 $(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\mathrm{j}+c\mathrm{k}
$$
得到
$$
p'=qpq^{-1}
$$
其中 $q^{-1}$ 是 $q$ 的逆, $q^{-1}=\cos\frac{\theta}{2}-\sin\frac{\theta}{2}(x\mathrm{i}+y\mathrm{j}+z\mat...
从分治策略到动态规划,再到贪心算法
引言
分治, 动态规划和贪心算法, 是算法设计中非常重要的三种思想, 它们各不相同, 却又息息相关. 本文会介绍三种思想之间的共同点和不同之处, 并且列举一些典型算法的例子, 试图探索算法设计的一般思路.
分治策略
我们先来看比较熟悉的快速排序. 快速排序是一个非常典型的分治策略算法. 它采取的方法是把数组中的某一个数移动到数组中的某一个位置, 使得它前面的数都小于它, 它后面的数都大于它. 然后, 对前面的数组和后面的数组做同样的操作. 直到数组全部有序.
下面是快速排序的代码
function qsort(a, l, r)
if l >= r then return end
local x = a[r]
local p = l - 1
...
避免使用无符号数
考察这样一段代码：
int a = -1;
unsigned int b = 1;
if (a < b)
printf("a < b\n");
else
printf("a > b\n");
a是有符号整数，b是无符号整数。C语言在比较他们的大小时会进行隐式类型转换。如果执行的是
if ((unsigned int)a < b)
则-1被转换成4294967295，结果是 a > b；如果执行的是
if (a < (int)b)
则结果是 a < b。采取哪种方式依赖于编译器。
在g++中，输出的结果是a > b。当然，也会打出警告：warning: comparison between signed and u...
63 post articles, 8 pages.