编译原理部分习题答案，龙书第二版,1-8章都有

真正的龙书英文第二版清晰版，绝非影印！！！该部分文件名 compiler-aho.part09.rar 之前不太懂不好意思，现在只有前第一个要分啦～

密匙二、双层桶划分 双层桶划分----其实本质上还是分而治之的思想，重在“分”的技巧上！ 适用范围：第 k 大，中位数，不重复或重复的数字 基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步

 第一章、左旋转字符串  第二章、字符串是否包含问题  第三章、寻找最小的 k 个数  第三章续、Top K 算法问题的实现  第三章再续：快速选择 SELECT 算法的深入分析与实现  三之三续、求数组中给定下标区间内的第 K 小（大）元素  第四章、现场编写类似 strstr/strcpy/strpbrk 的函数  第五章、寻找满足条件的两个或多个数  第六章、求解 500 万以内的亲和数  第七章、求连续子数组的最大和  第八章、从头至尾漫谈虚函数  第九章、闲话链表追赶问题  第十章、如何给 10 7̂ 个数据量的磁盘文件排序  第十一章、最长公共子序列（LCS）问题  第十二~十五章：数的判断，中签概率，IP 访问次数，回文问题（初稿）  第十六~第二十章：全排列，跳台阶，奇偶排序，第一个只出现一次等问题  第二十一~二十二章：出现次数超过一半的数字，最短摘要的生成  第二十三、四章：杨氏矩阵查找，倒排索引关键词 Hash 不重复编码实践  第二十五章：Jon Bentley：90%无法正确实现二分查找  第二十六章：基于给定的文档生成倒排索引的编码与实践  第二十七章：不改变正负数之间相对顺序重新排列数组 作者声明：本人 July 对以上所有任何内容和资料享有版权，转载请注明作者本人 July 及 出处。向你的厚道致敬。谢谢。二零一一年十月十三日、以诸君为傲。

（1）递归实现 从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如 此递归处理，从而 得到所有元素的全排列。算法实现如下： #include #include using namespace std; template void CalcAllPermutation_R(T perm[], int first, int num) { if (num <= 1) { return; } for (int i = first; i < first + num; ++i) { swap(perm[i], perm[first]); CalcAllPermutation_R(perm, first + 1, num - 1);

DX93D游戏程序设计入门(龙书DOC&TXT)，不可多得的一本学习dx的工具书，中文版。

龙书的习题答案和书中lexer源码（没有第9、10和11章答案）

编译原理（全）(龙书英文第二版)-Compilers：Principles, Techniques, and Tools (2nd Edition) 这个是文本版，非影印版，绝对经典，和大家一起分享！

(1) 请描述你解决这个问题的思路； (2) 请给出主要的处理流程，算法，以及算法的复杂度。 方案 1：采用 trie 树，关键字域存该查询串出现的次数，没有出现为 0。最后用 10 个 元素的最小推来对出现频率进行排序。 关于此问题的详细解答，请参考此文的第 3.1 节：第三章续、Top K 算法问题的实现。 14. 一共有 N 个机器，每个机器上有 N 个数。每个机器最多存 O(N)个数并对它们操作。如 何找到 N^2 个数中的中数？ 方案 1：先大体估计一下这些数的范围，比如这里假设这些数都是 32 位无符号整数（共 有 2 3̂2 个）。我们把 0 到 2 3̂2-1 的整数划分为 N 个范围段，每个段包含（2 3̂2）/N 个整 数。比如，第一个段位 0 到 2 3̂2/N-1，第二段为（2 3̂2）/N 到（2^32）/N-1，…，第 N 个 段为（2 3̂2）（N-1）/N 到 2 3̂2-1。然后，扫描每个机器上的 N 个数，把属于第一个区段的 数放到第一个机器上，属于第二个区段的数放到第二个机器上，…，属于第 N 个区段的数 放到第 N 个机器上。注意这个过程每个机器上存储的数应该是 O(N)的。下面我们依次统计

同时，程序员编程艺术系列将重新开始创作，第十一章以后的部分题目来源将取自下文 中的 17 道海量数据处理的面试题。因为，我们觉得，下文的每一道面试题都值得重新思考， 重新深究与学习。再者，编程艺术系列的前十章也是这么来的。若您有任何问题或建议，欢 迎不吝指正。谢谢。 第一部分、十五道海量数据处理面试题 1. 给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让 你找出 a、b 文件共同的 url？ 方案 1：可以估计每个文件安的大小为 50G×64=320G，远远大于内存限制的 4G。所 以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。 1. 遍历文件 a，对每个 url 求取 1000)%(urlhash ，然后根据所取得的值将 url 分别存 储到 1000 个小文件（记为 99910 ,,, aaa  ）中。这样每个小文件的大约为 300M。 2. 遍历文件 b，采取和 a 相同的方式将 url 分别存储到 1000 小文件中（记为 99910 ,,, bbb  ）。这样 处理 后，所 有可能 相同的 url 都在 对应的 小文件 （ 9999991100 ,,, bvsabvsabvsa  ）中，不对应的小文件不可能有相同的 url。然后 我们只要求出 1000 对小文件中相同的 url 即可。 3. 求每对小文件中相同的 url 时，可以把其中一个小文件的 url 存储到 hash_set 中。 然后遍历另一个小文件的每个 url，看其是否在刚才构建的 hash_set 中，如果是， 那么就是共同的 url，存到文件里面就可以了。 方案 2：如果允许有一定的错误率，可以使用 Bloom filter，4G 内存大概可以表示 340 亿 bit。将其中一个文件中的 url 使用 Bloom filter 映射为这 340 亿 bit，然后挨个读取另外一 个文件的 url，检查是否与 Bloom filter，如果是，那么该 url 应该是共同的 url（注意会有一 定的错误率）。