ITeye博客

liuxinyu95的博客

liuxinyu95 · 共 17 篇文章

初等算法

经过6年,我终于写完了《初等算法》一书。 这本书完全免费,可以从这里下载电子版: https://github.com/liuxinyu95/AlgoXY/releases/download/v0.618033/elementary-algorithms-zh-cn.pdf Why 算法书籍汗牛充栋,《算法导论》,《计算机程序设计艺术》,《计算机程序的构造和解释》……,为什么要写这么一本书?是不是重复发明轮子? 这本书的特点有以下几个: 1,形式化。所有的算法都尽量形式化为数学公式,同时给出伪代码。我希望能够让算法回归数学,具有代数符号般的简洁和优美; 2,函数化和imperative对照。…

2014-07-22 20:46 · 算法与数据结构 · 评论(1)

初等查找算法

这一章包含如下内容: 扫描查找 分治查找 二维Saddleback search 字符串查找 -KMP -BM 解的查找 DFS BFS Greedy DP 详细内容见链接中的PDF https://dl.dropboxusercontent.com/u/52705490/search-en.pdf

2014-06-08 07:47 · 算法与数据结构 · 评论(0)

一堂有趣的计算机课

昨天讨论了一些Computing at school的内容。受到Richard Bird在 Pearls of functional algorithm design一书中Saddleback search一章的启示,我这里抛砖引玉,给出一个我心目中的中学计算机课的例子。 教师: 同学们,早上好。想必你们都吃过了营养丰富的早餐。现在该补充一些维生素了。 同学们每人都会得到一串葡萄和几个盘子。今天我们要考虑一个有趣的问题: 如何吃到最大的10粒葡萄。 明明:老师,我想出了一个办法。 教师:说说看 明明: 我先找出最大的一粒葡萄,然后吃到肚子里。然后,我在剩下的葡萄中找到最大的,吃掉。 重复这个…

2013-07-25 13:27 · 算法与数据结构 · 评论(0)

Quick sort V.S. Merge sort

终于写完了这一章 本章全面地涉及了quick sort和merge sort的方方面面。同其他章节一样,即覆盖传统的imperative算法,也覆盖functional(函数式)算法。 首先展示的是著名的只有2行的Haskell快速排序算法。之后,针对Partition给出了一些小的改进。并且用两种方法严格证明了快速排序的平均性能。此后,我给出了各种著名的工程方法:2路partition, 3路parition (ternary quick sort),3点中值法,随机快速排序等等,最后通过deforestation给出快速排序和树排序的关系。 为了解决快速排序的worst case问题,本…

2013-04-09 14:48 · 算法与数据结构 · 评论(0)

POJ 1061青蛙的约会题解

POJ 1061青蛙的约会题解 网上似乎有不少此题的解法。我这个post和其他人的相比主要时想说下面几点。 给出一个试图不死记硬背公式的思路; 谈谈暴力解为什么看起来这么诱人,却无法通过; 一些细节及对此题的评价(个人观点) 原题请参考poj: http://poj.org/problem?id=1061 我认为ACM/ICPC应该给人思维的快乐,甚至带有幽默感。这是几个世纪以来数学趣题吸引人们的那种美。 人们会废寝忘食地思考一道题目,解开的一刹那会不由自主的说: 啊--啊哈--哈哈 但是这道题目丝毫没有给我这种快感,这是一道被中国式的考试(竞赛)制度八股化的题目。 首先一看此题要求无解时给…

2013-02-28 13:06 · 算法与数据结构 · 评论(1)

从吃葡萄到世界杯——选择排序的进化

和插入排序一样,选择排序通常被认为是一种hello world式的排序。通常被用来作为例子向初学者讲解多层循环。它有着特别直观的结构,但是性能却是O(N^2)的。 在这一章中,我将向读者展示,选择排序也可以不断进化:既有简单的改进(诸如cock-tail排序),也有从本质上改进数据结构(使用tournament knock out和heap sort),从而最终使得基于选择的排序方法也达到比较排序的上限: O(N lg N) https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/ssort-en.pdf?raw=true

2013-02-10 17:25 · 算法与数据结构 · 评论(0)

AlgoXY, Why another algorithm book ?

相信一定有人问?我们有这么多经典优秀的算法书: TAOCP: Donald E. Knuth, The art of computer programming; CLRS: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. ``Introduction to Algorithms, Second Edition'' Robert Sedgewick: 的Algorithms in XXX Language系列 甚至一些讲授计算机体系结构,以及编程的好书也有大量的算法介绍: SICP: Ha…

2013-01-08 13:47 · 算法与数据结构 · 评论(0)

List

单向链表是几乎所有函数式编程语言的环境的基石。它的重要性,就如同数组对于imperative编程语言的重要性一样。(有读者可能会质疑:lambda才是函数式编程中最最基础的;作者认为lambda对于函数式编程,如同汇编语言对于imperative一样,是计算模型的基础表达方式。) 经过两个月的持续写作,关于单向链表的内容终于脱稿了。尽管List非常重要,但是作者并不打算把它作为AlgoXY一书的第一章,而是把它作为本书的第一个附录。第一章仍然是:“二叉树——数据结构中的Hello world”。 虽然是附录,但是作者仍然秉着非常严格的态度来写作,丝毫不敢放松。我们遵循CLRS(《算法导论》)…

2013-01-05 13:16 · 算法与数据结构 · 评论(0)

Sequence

经过了14个月锱珠积累,这一章终于脱稿了。 这一章具有里程碑式的意义。这一章写好后,所有的基本数据结构,从易到难: 二叉树,红黑树,AVL树,Trie,Patricia, Suffix tree,B-tree,binary heap,Leftist Heap, Skew Heap, 二项式heap,斐波纳契Heap,队列,序列 就全部给出了函数式实现。 我们面前已经没有任何基本数据结构的阻碍,使得我们无法用纯函数式的基本算法解决问题了! 本章是基本数据结构的最后一章。讲述sequence。 在imperative语言中,通常不用担心random access。原生的数组就可以满足O(1)时间…

2012-10-10 15:50 · 算法与数据结构 · 评论(0)

Natural merge sort

通常我们见到的merge sort的思路是典型的分而治之divide and conquer策略: 如果待排序序列为空,或者只有1个元素,结束 否则,将序列一分为二,将两个子序列分别merge sort,再将两个排好的子序列merge 我们也可以从另外一个角度出发,序列中存在一些已经排好的片段,我们可以把这些排好的片段merge起来,不断重复直到序列排好(只含有一个排好的片段,亦即整个序列) 这种思路叫做natural merge sort。 例如下面的Haskell代码: mergesort' = foldl merge . groupBy' (<=) 其中merge的实现非常简单: me…

2012-07-11 13:20 · 算法与数据结构 · 评论(1)

谁主张、谁举证 ACM crashing balloon / zoj 1003

题目详情可以参考这里: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3 ZOJ上的判定标准是: b不服,站出来质疑; 如果a能举证说:你瞧,存在一种合理的解释,a = a a … a, b = b b*… b; 其中 2<= a , b <=100, 且 a* !=b if i!=j 就判断a赢,否则b赢 但是,这里会有对b不利的冤案!例如b踩了气球4和8,于是b = 32 而 a吹牛说自己得了44分, b不服,但是a狡猾的说,你看,a = 4 11, b=2 16,于是a赢了!b虽然说了实话,a说了假话, 但是仍然b…

2012-07-03 18:15 · 算法与数据结构 · 评论(0)

队列,并非想象的那样简单

经过近两年的时间,我终于写完了这一章。 正如我在Algoxy第一章描述的,Queue并非想象的那样简单。尤其是提供一个纯函数式的队列,并且满足常数时间的头部和尾部操作并不容易。 本章中,我们给出几种不同的队列的纯函数式实现。 当然,用常见的imperative语言实现队列很容易,尤其是使用双向链表。但是这是一个overkill的解法,我们先用单向链表实现一个头部尾部都是常数时间的队列;然后我们给出一个ring-buffer的实现; 接着我们给出一个简单的纯函数式解法:它能达到amortized常数时间,但是worst case表现一般,接着我们给出一个基于状态机的real time queu…

2012-07-03 18:08 · 算法与数据结构 · 评论(0)

二项式堆、斐波纳契(Fibonacci)堆和Pairing堆

通常的数据结构和算法教科书介绍的堆,实际上是用数组隐式表达的二叉树堆(binary heap by implicit array),如果将概念扩展为多叉树或者森林,就会得到更多有趣的堆。本章介绍的3种堆,就是其中很有代表性的数据结构。 其中二项式堆把合并的速度提高到了O(lg N)的量级,如果把二项式堆的某些操作延迟进行,就得到了Fibonacci堆,Fibonacci堆的各项指标除了pop外,都达到了O(1)的量级,在理论上的意义特别重大。它使得诸多的图算法,如Dijkstra算法等得以高效实现。 遗憾的是Fibonacci Heap的实现有些复杂,时间常数比较大,理论意义大于实际意义。为…

2012-02-21 14:36 · 算法与数据结构 · 评论(0)

AVL tree,比红黑树更朴素

AVL树发明于上世纪60年代,比红黑树早了近十年。 上一章里,我展示了用pattern matching实现的红黑树。本章我展示同样策略实现的AVL tree。相比于传统的基于旋转的解法,这一解法再次展示了简单一致的特点。 本章内容如下: 简单介绍;给出AVL树的高度与节点数的证明; 类比红黑树的思路; 解: pattern matching 的形式分析 子问题一: 如何更新平衡因子和增加的高度? 子问题二; 4个case中的平衡因子如何变化的推导和证明; Haskell实现 验证 删除算法作为习题留给读者 和传统旋转解法的对比,给出了算法描述和Python实现 对比和红黑树的差异。 原文连…

2011-08-15 15:34 · 算法与数据结构 · 评论(1)

红黑树,并非想象中的那么复杂

红黑树是非常popular的一种self-adjusted的平衡二叉排序树。 通常他给我们的印象是很复杂,有很多case,要小心的旋转。有人说,曾将在某公司的面试时,被要求实现红黑树。他觉得这很没有道理,几乎很少有人能在不参考教科书的情况下,记清楚那么多的case。 在这一章里,我将向你展示目前我所见过的最简洁的红黑树实现。简洁到什么程度呢?我打赌你看过后能轻松通过上面的面试——Wow, 红黑树原来可以这么简单! 这个实现,来自Chris Okasaki在卡耐基梅隆大学(CMU)的博士研究成果。他启发我用同样的方法简洁地实现了AVL tree和Splay tree。 这一章我们讲红黑树,大致…

2011-06-02 14:48 · 算法与数据结构 · 评论(0)