跳至主要内容

博文

目前显示的是 十一月, 2009的博文

好玩的数学——吉普赛读心术解密

好玩的数学——吉普赛读心术解密 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语言写解释器(五)

用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语言写解释器(四)

用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, "文件 %s 无法打开!\n", filename );         exit ( EXIT_FAILURE );     }     while ( fscanf (

用C语言写解释器(三)

用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语言写解释器(二)

用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,        // 右括号     oper_plus,          // 加     oper_minus,         // 减     oper_multiply,      // 乘     oper_divide,        // 除     oper_mod,           // 模     oper_power,         // 幂     oper_positi