四元数描述旋转
先看结论:
对于任意坐标 $(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\mathrm{k}...
从分治策略到动态规划,再到贪心算法
引言
分治, 动态规划和贪心算法, 是算法设计中非常重要的三种思想, 它们各不相同, 却又息息相关. 本文会介绍三种思想之间的共同点和不同之处, 并且列举一些典型算法的例子, 试图探索算法设计的一般思路.
分治策略
我们先来看比较熟悉的快速排序. 快速排序是一个非常典型的分治策略算法. 它采取的方法是把数组中的某一个数移动到数组中的某一个位置, 使得它前面的数都小于它, 它后面的数都大于它. 然后, 对前面的数组和后面的数组做同样的操作. 直到数组全部有序.
下面是快速排序的代码
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...
59 post articles, 8 pages.