今天开始学习数论方面的算法。这部分在NOIP中并不常出现，即使出现了也不会像高联这么难（。。。）。
什么是扩展欧几里得算法
所谓欧几里得算法，实际上就是辗转相除法——求两个数最大公约数的一种高效算法。而扩展欧几里得算法则是来源于于一类方程的解决：
$$ax+by=gcd(a,b)$$
这有点像是裴蜀定理的一般形式。和裴蜀定理类似，这类方程也有无数多个整数解。如何高效率地求得它的一组特解呢？
代码
pascal
procedure gcd_ex(a, b: longint; var d: longint; var x, y: longint);
begin
if b = 0 then
begin
继续阅读 »
初识ODPS算法
ODPS机器学习算法非常丰富，从功能角度可以划分为以下几大类：
基本的统计、分析和处理
基本统计包括直方图、协方差、连续变量分组统计、交叉表、排行榜等；统计分析包括对应分析、主成分分析（Principal Component Analysis, PCA）;数据处理包括数据过滤、采样、归一、合并、分箱等。
继续阅读 »
定义
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
more
算法步骤
冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
伪代码如下：
继续阅读 »
算法原理
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的流程如下：
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需
继续阅读 »
有穷自动机
为了实现对于正规式（可理解为正则表达式）的识别，我们提出了有穷自动机理论，有穷自动机接受正规式的定义符，并不断的识别符号，移动到新的状态，如果出现了识别错误就会报错。
有穷自动机包含确定的有穷自动机（DFA），和不确定的有穷自动机（NFA）。两者的主要区别在于，在同一个状态时，是否通过同样的符号输入能达到不同的状态。如果能就是不确定的，反之就是确定的。另外：NFA还可以接受空字串已达到不同的状态。
三个主要的算法
这其中有三个主要的算法：
正规式 => NFA Thompson算法
这个算法使用了一些模版去对应正则表达式中的符号，只要记住模版，就能推出相应的NFA。
继续阅读 »
Bloom Filter是由Bloom在1970年提出的一种快速查找算法，通过多个hash算法来共同判断某个元素是否在某个集合内。可以用于网络爬虫的url重复过滤、垃圾邮件的过滤等等。
它相比hash容器的一个优势就是，不需要存储元素的实际数据到容器中去来一个个的比较是否存在。
只需要对应的位段来标记是否存在就行了，所以想当节省内存，特别适合海量的数据处理。并且由于省去了存储元素和比较操作，所以性能也比基于hash容器的高了很多。
但是由于bloom filter没有去比较元素，只通过多个hash来判断唯一性，所以存在一定的hash冲突导致误判。误判率的大小由hash函数的个数、hash函数优劣、以及存储的位空间大小共同决定。
继续阅读 »
算法原理
希尔排序算法是按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布，是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
- 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
算法思路：
1. 先取一个正整数 d1(d1 < n)，把全部记
继续阅读 »
虽然已经一年多没有维护gbox这个图形库项目了，最近确实时间不够用。。。
今年的重点是把xmake彻底正好，至少在架构和大功能（包依赖管理）上，要完全落实下来，后期就是零散的维护和插件功能扩展了。。
tbox我会陆陆续续一直进行一些小规模更新，明年上半年稍微重构一些模块后，就开始重点重新搞gbox了，这才是我一直最想做，也是最喜欢做的项目了
所以我宁愿开发的慢点，也要把它做精，做到最好。。
好了，回归正题，虽然现在gbox还处于早期开发中，并不能用到实际的项目中去，但是里面的一些算法，还是很有参考学习价值的。。
我这两天没事就拿出来分享下，如果有感兴趣的同学，可以直接阅读源码：monotone.c
毕竟这个算法我陆陆续
继续阅读 »
关于最长上升子序列的O(N*logN)算法已经有不少文章表述，可惜大都不够“好”（甚至语焉不详）：我认为“好”的算法描述不但应该清晰地说明计算步骤，更应该讲清思路——即，这个算法是怎样思考得出的。这种思考的过程和方式才是精华之处。我试图用我的理解对这个算法给出一个尽量“好”的推导和表述，使你我一样的普通人都可以理解它的思路。
继续阅读 »
定义
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
more
算法步骤
插入排序算法的运作如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复
继续阅读 »