贪玩的程序员

好玩的数学——吉普赛读心术解密 redraiment, 2009-11-19 神奇的吉普赛读心术 　　闲着无聊窜寝室，看到一个同学在玩一个 flash 游戏：吉普赛读心术（ http://gb.cri.cn/mmsource/flash/2006/04/10/er060410001.swf ）。规则如下： 任意选择一个两位数（或者说，从10~99之间任意选择一个数），把这个数的十位与个位相加，再把任意选择的数减去这个和。例如：你选的数是23，然后2+3=5，然后23-5=18 在图表中找出与最后得出的数所相应的图形，并把这个图形牢记心中，然后点击水晶球。你会发现，水晶球所显示出来的图形就是你刚刚心里记下的那个图形。 　　咋看之下觉得很神奇，但仔细把玩两三回后你就会发现其中的奥秘： 右边的图标每次都会改变； 9、18、27、...、81 这9个图标永远是一样的。 　　假设你选择的两位数是 ab（即 ab=a×10+b），其中 1≤a≤9, 0≤b≤9 。按照规则计算就是 (a×10+b)-(a+b)=9×a，结果是 9 的倍数，∵ 1≤a≤9 ∴ 结果为 9、18、27、...、81 中的任意一个。又∵ 这9个图标是一样的，∴ 水晶球神奇地知道你记的图标。 手指计算器 　　无独有偶，记的小学数学课上老师教我们用手指计算任意两个5-10之间的数的积。 　　例如 6×8 ，一只手伸出 6-5=1 根指头，另一只手伸出 8-5=3 根指头。1+3=4，4 就是积的十位数；把两手弯曲的指头数相乘得 4×2=8，8 是积的个位数。则 6×8=48。 　　道理和上面相同：a×b=[(a-5)+(b-5)]×10+(10-a)×(10-b) 神秘的失踪 　　做这道题一定要的亲自动手才有滋味！否则就会像浮光掠影，印象不深。 　　将一个正方形分割成 7×7=49 的小方格，并按下图将它们分为“甲、乙、丙、丁、戊”五部分。 　　然后，甲块不动、乙块和丙块对调、戊块上移、丁块右移。得到新图如下： 　　经过这样重新组合拼成的新正方形，中间奇迹般地空出了一个洞！ 　　实际上这只不过是一个小戏法，上面的新图形并不是真的正方形。 观察原始图可知 △ABC 和 △AED 是相似三角形 ∴ DE:CB=AD:AC=4:7 ∴ DE=8/7 ∴ EF=DE+DF=36/7 ∴ 上图...

环境驱动编程——参加算法论坛后有感 redraiment, 2009-11-07 现场回顾 　　我很荣幸地作为特邀专家入京参加 CSDN 主办的 SD2.0 大会。大会以“移动+嵌入+云”为主题，举办了三天。白天有很多名家讲座，晚上还有5个主题沙龙，我参加的是算法论坛的沙龙。主持人是王尧（左轻侯），曾经先后工作于 Borland 中国公司和微软中国公司，现供职于 IBM 中国开发中心，从事 DB2 的研发工作。与会的还有五位嘉宾： 王炜：北京南天软件有限公司总架构师； 宋兴烈：起步软件公司总工程师； 云风：网易公司技术研发经理； 贾自艳：腾讯搜索技术研发中心研究员； 顾森：北大在校学生（ http://www.matrix67.com/ ）。 　　论坛围绕“在新一轮技术浪潮中，算法又重新站到了重要位置”这一话题展开讨论。本来有几个问题想和各位嘉宾讨论，但由于时间不足，加上我住处较远，只好忍痛在 21:20 出去赶班车，到家已经 23:40 了。不过收获还是不少，我结合大会上其他专家的一些观点，将其整理出来和大家分享。 算法重获重视 　　IT 行业经历了大型机时代、PC 时代、互联网时代，以及即将到来的移动终端+云计算时代。早期由于硬件的先天不足，需要靠软件后天来补；随着硬件的高速发展，一个普通的算法在十八个月以后性能就可以提升一倍，而且大部分经过高度优化的算法都被打包成类库，需要可以方便地调用；但随着互联网时代的到来，用户能够主动参与建设互联网，算法要处理的不再是几台 PC 中存储的数据，而是整个互联网中的信息。 　　引用李德毅院士的话：“ 集中统一的调度，顺序的、确定的输入，不能描述互联网的工作机理和交互机理，互联网突破了图灵机的描述范畴。 ”李院士将云计算定义为传统的“图灵计算”结合“大众计算”，“大众计算”意味着至少能处理这浩如烟海的互联网信息，因此算法也必须与时俱进。 环境驱动编程 　　在讨论中，王玮一直强调要灵活地运用算法，这个我以前提的“ 工具理论 ”不谋而合。他现场举了个例子：字符串匹配算法中，Rabin-Karp 算法理论上并非最优的，但在实际运用地比较好。这是由于硬盘的I/O效率远低于内存等高速存储器，并非理想的高效随机存储器。其他匹配算法都需要反复读取前面的数据，而 RK 算法只需按顺序从前往后以此处理，在处理大数据时避免了大量...

用C语言写解释器（五）——其他一些东西 redraiment, 2009-11-05 写完解释器之后 　　这一篇文章我只想和大家侃侃编程语言的事情，不会被放到书中。因此可以天南地北地扯淡，不用像前几篇一样畏首畏尾的了。 　　经过前面几篇文章的讨论，已经把用纯 C 语言来实现一个解释器的方法介绍完了。但那些是写给我校 C 语言初学者看的，并不只是你，我得也觉得很不过瘾 ^_^。因此准备继续深入学习编译原理等课程，希望有志同道合的朋友和我一起交流！ 富饶的语言（工具） 　　在前几篇文章中一直在鼓吹我拍脑袋想出的语言四大要素：“内存管理”、“表达式求值”、“输入/输出”、“按条件跳转”，在这篇文章中您就姑且信一回当它是真的。按照这四条准则去匹配，汇编语言是完全符合的。那为什么又需要 C 语言、Java、C# 等高级语言？这是因为编程除了需要“语言”之外还需要“抽象”！ 　　“抽象”是个很有效的工具，相信你在为别人介绍自己房间时不会具体到每个木纤维、油漆分子和铁原子。同样的，我们也不乐意总是写一堆 JNZ、JMP 指令，而仅仅是为了实现 if、for、while 等控制结构。C 语言等高级语言提供的抽象的层次更高、表现力更强，允许用更少的语句描述更多的操作。感谢如此富饶的语言为我们带来不同的视角去审视这个世界。 　　高级语言相较于低级语言属于更高地抽象层次，高级语言之间的差别主要体现在适用范围上。比如一些语言适合写 WEB 程序，另一些适合做数值分析等。术业有专攻，你只需根据自己的问题来选择一门合适的语言。 什么时候需要创造新的语言 　　当我们碰到一类新的问题时，首先考虑的就是定义新的数据结构，并设计多个函数去操作它，最后将它们独立出来打包成一个类库方便在其他地方调用（比如处理图形图像的 OpenGL 库）。上面已经提过，每种语言都有它适合的领域，强行将一门语言用在它不擅长的领域中就出现冗长、繁琐的代码。自然语言也是如此：英语中有种语法叫虚拟语气，描述的是一种假设，并非事实。比如“If I have time, I will go to see you. ”。如果按原意一字不差地翻译相信会很繁琐，我知道台湾作家痞子蔡在使用中文式的虚拟语气很有一套： 如果我还能活一天， 我就要做你的爱侣。 我能活一天吗？可惜。 所以我不是你的爱侣。  ——《第一次亲密接触》 ...

用C语言写解释器（四）——语句分析 redraiment, 2009-11-02 语句 　　在前面的章节中已经成功实现了内存管理和表达式求值模块。之所以称表达式求值是解释器的核心部分，是因为几乎所有语句的操作都伴随着表达式求值。也许你已经迫不及待地给 eval 传值让它执行复杂的运输了，但目前来讲它充其量只是一个计算器。要想成为一门语言，还需要一套自成体系的语法，包括输入输出语句和控制语句。但在进行语法分析之前，首先需要将 BASIC 源码载入到内存中。 BASIC 源码载入 　　在《用C语言写解释器（一）》中附了一段 BASIC 参考代码，每一行的结构是一个行号+一条语句。其中行号为 1-9999 之间的正整数，且当前行号大于前面的行号；语句则由以下即将介绍的 3 条 I/O 语句和 8 条控制语句组成。为方便编码，程序中采用静态数组来保存源代码，读者可以尝试用链表结构实现动态申请的版本。下面是代码结构的定义。 // in basic_io.h #define PROGRAM_SIZE (10000) typedef struct {     int ln;     // line number     STRING line; } CODE; extern CODE code[PROGRAM_SIZE]; extern int cp; extern int code_size; 　　其中 code_size 的作用顾名思义：记录代码的行数。cp （0 ≤ cp < code_size）记录当前行的下标（比如 cp 等于5时表明执行到第5行）。下面是载入 BASIC 源码的参考代码，在载入源码的同时会去除两端的空白字符。 // in basic_io.c void load_program ( STRING filename ) {     FILE *fp = fopen ( filename, "r" );     int bg, ed;     if ( fp == NULL ) {         fprintf ( stderr...

用C语言写解释器（三）——中缀转后缀 redraiment, 2009-11-01 操作符排序 　　如果你忘记了后缀表达式的概念，赶紧翻回上一篇《 用C语言写解释器（二） 》回顾一下。简单地说，将中缀表达式转换成后缀表达式，就是将操作符的执行顺序由“优先级顺序”转换成“在表达式中的先后顺序”。因此，所谓的中缀转后缀，其实就是给原表达式中的操作符排序。 　　比如将中缀表达式 5 * ((10 - 1) / 3) 转换成后缀表达式为 5 10 1 - 3 / *。其中数字 5 10 1 3 仍然按照原先的顺序排列，而操作符的顺序变为 - / ×，这意味着减号最先计算、其次是除号、最后才是乘号。也许你还在担心如何将操作符从两个操作数的中间移到它们的后边。其实不用担心，在完成了排序工作后你就发现它已经跑到操作数的后面了 ^_^。 　　从中缀表达式 1+2×3+4 中逐个获取操作符，依次是 + × +。如果当前操作符的优先级 不大于 前面的操作符时，前面操作符就要先输出。比如例子中的第二个加号，它前面是乘号，因此乘号从这个队伍中跑到输出的队伍中当了“老大”；此时第二个加号再前面的加号比较，仍然没有比它大，因此第一个加号也排到新队伍中去了；最后队伍中只剩下加号自己了，所以它也走了。得到新队伍里的顺序 × + + 就是所求解。下面的表格中详细展示每一个步骤。 序号 输入 临时空间 输出 1 + 2 × + 3 + + × 4 + × + 5 + + × 6 + × + 7 * + + 　　相信你心里还是牵挂着那些操作数。很简单，如果碰到的是操作符就按上面的规则处理，如果是操作数就直接输出！下面的表格加上了操作数，将输出完整的后缀表达式。 序号 输入 临时空间 输出 1 1 2 + 1 3 2 + 1 4 × + 1 2 5 3 + × 1 2 6 + + × 1 2 3 7 + × + 1 2 3 8 + + 1 2 3 × 9 4 + 1 2 3 × + 10 + 1 2 3 × + 4 11 1 2 3 × + 4 + 　　得到最终结果 1 2 3 × + 4 + 就是所求的后缀表达式。下面是程序中的参考代码（有删减）。 操作符优先级 　　上一节介绍了中缀转后缀的方法。其中关键...

用C语言写解释器（二）——表达式求值 redraiment, 2009-10-31 内存管理 　　既然是表达式求值，自然需要在内存中保存计算结果以及中间值。在《 用C语言写解释器（一） 》中提过：变量要求是若类型，而 C 语言中的变量是强类型，为实现这个目标就需要定义自己的变量类型，参考代码如下（注释部分指出代码所在的文件名，下同）： // in basic_io.h #define MEMERY_SIZE (26) typedef enum {     var_null = 0,     var_double,     var_string } variant_type; typedef char STRING[128]; typedef struct {     variant_type type;     union {         double i;         STRING s;     }; } VARIANT; extern VARIANT memery[MEMERY_SIZE]; // in expression.h typedef VARIANT OPERAND; 　　程序自带 A-Z 26个可用变量，初始时都处于未赋值（ver_null)状态。所有变量必须先赋值再使用，否则就会报错！至于赋值语句的实现请参见后面语法分析的章节。 操作符 　　表达式中光有数值不行，还需要有操作符。在《 一 》中“表达式运算”一节已经给出了解释器需要实现的所有操作符，包括“算术运算”、“关系运算”和“逻辑运算”。下面给出程序中操作符的定义和声明： // in expression.h typedef enum {     /* 算数运算 */     oper_lparen = 0,    // 左括号     oper_rparen,   ...