前沿视频教室————最好的CSS和Web设计与开发的视频教程

世界著名的软件公司或者科技公司，每年都会组织一些开发者大会，一方面是宣传自己的产品和战略，另一方面也是对新技术的探讨。比如微软每年上半年会举行MIX大会（面向Web开发和设计人员），下半年会举行PDC（面向专业开发人员）。此外，比如Adobe公司会举办MAX大会，苹果的开发者大会叫做WWDC，这些都是非常好的学习机会。

每年的 MIX 和 PDC 大会，都是我们学习新技术的好机会。大会分别都有100多场新技术的演讲。今年的MIX大会将在4月12号开幕，持续3天，有很多很酷的演讲。具体演讲的题目和日程，可以参见这里。微软在网站上，都会现场直播讲演的内容，结束以后这些讲演的视频也会保留在Channel9网站上，可以随时观看。所以这里不得不说，搞技术什么最重要？我看还是得说英语最重要啊。

我挑出了一些比较感兴趣的题目，这里先做个记号，一共选出了20个题目：

HTML5 & CSS3

加速 HTM5 网站的50个性能优化技巧：50 Performance Tricks to Make Your HTML5 Web Sites Faster

HTML5的未来：The Future of HTML5

深入 HTML5 的 canvas（画布） ：Deep Dive Into HTML5 canvas

HTML5 世界中的数据：Data in an HTML5 World

CSS3征服世界：CSS3 Takes on the World

让你的网站更现代：SVG与HTML5：Modernizing Your Website: SVG Meets HTML5

Javascript & jQeury

编写可维护的Javascript：Writing Maintainable JavaScript

C# 开发人员的 Javascript 好习惯：Good JavaScript Habits for C# Developers；

用 jQuery 开发数据为中心的N层应用：Building Data-centric N-tier Applications with jQuery

Script#: 编译 C# 到 JavaScript：Script#: Compiling C# to JavaScript using Visual Studio

JavaScript的交互扩展 (RxJS)：Reactive Extensions for JavaScript (RxJS)

JavaScript, jQuery, AJAX 与 ASP.NET 实战：Pragmatic JavaScript, jQuery & AJAX with ASP.NET

.NET平台上的开发

更大、更快、更强，优化ASP.NET应用：Bigger, Faster, Stronger: Optimizing ASP.NET Applications

脚手架：ASP.NET, NuGet, Entity Framework Code First 及其他：Scaffolding – ASP.NET, NuGet, Entity Framework Code First and More

深入MVVM开发模式：Deep Dive MVVM

ASP.NET MVC 3 与 MEF（托管扩展框架）：Fun with ASP.NET MVC 3 and MEF

设计师与程序员，身兼二职：Designer and Developer: A Case for the Hybrid

ASP.NET MVC 3 @ : 现在进行时 ：ASP.NET MVC 3 @:The Time is Now

Web 开发平台概述 ：An Overview of the MS Web Stack of Love

设计草图、原形、捕捉灵感：使用Expression Blend 和SketchFlow：Get Real! Sketch, Prototype, and Capture Great Ideas with Expression Blend and SketchFlow

还有很多演讲是围绕 Silverlight、Windows Phone 和 Windows Azure 的，我不熟悉，所以没有列出来。

上一篇文章介绍了加州大学洛杉矶分校（UCLA）的一门C#语言课的教学内容。今天就来讲解一下其中的一个作业题，这个作业题占它这门课程总成绩的20%。以下是我按照原文写的，以翻译为主，删掉了一点非核心的内容，并稍加了一些说明，原文见这里。

概述

这个作业题的内容，是请你模拟一座建筑物中的电梯。你的程序需要控制电梯的运行以及乘坐电梯的乘客流。从教学的角度出发，这个作业可以分为三个部分，但你在实现的时候，不一定非要按照下面描述的顺序。你要为一座多层的建筑物中的几部电梯建模，这个模拟过程发生在一座建筑物中，需要跟踪乘客乘坐电梯在不同楼层之间运行。为了简单起见，我们设定一共有5层（标记为0-4），以及两部电梯（标记为0和1）。

这个模拟是基于“节拍”的，每一拍发生如下三件事：

1）电梯根据当前的状态进行移动；

2）乘客移动；

3）电梯的控制器更新电梯的状态。

模拟乘客流

一个乘客的状态一定处于两种状态之一：“空闲”（Idle）或“去向(n)”（GoingTo(n)），各自含义是:

去向(n)：这位乘客要去向第n层楼。

空闲：乘客在电梯外休息。

乘客的状态变迁如图所示：

当整个模拟开始时，每个乘客的起始状态都是“空闲”。

乘客的位置

每个乘客有一个当前的位置，有以下7种可能： { 电梯0, 电梯1, 楼层0, 楼层1, 楼层2, 楼层3, 楼层4}。初始情况是每个乘客都在“楼层1”（楼层0表示地下室）。

当一个乘客正在乘坐“电梯i”的时候，我们就说他的位置是“电梯i”。当一个乘客正在“楼层f”的时候，我们就说他的位置是“楼层f”。

乘客的指令

我们一种简单的格式定义某个乘客的行动计划，例如

(t1,f1); (t2,f2); (t3,f3); …

其中的一个括号中有两个数字，t表示的时某一个时刻，f表示此时该乘客要取得楼层。这样的一对数字，我们称为一个“指令”。用一系列的指令就可以描述一个乘客的一系列行动的计划。注意，在实际模拟时，严格按照序列顺序，即使后面的指令中的时间早于前面指令的时间。然后，用一个简单的文本文件，可以构造出多个乘客的行动序列，每个乘客一行，如下所示：

在模拟程序开始的时候，读入这个文本文件，然后程序根据这个文件设定的所有指令模拟整个运行过程。

对乘客建模

乘客的移动按照下面的规则进行：假设一个乘客S，当前的状态是state，当前位置是p，当前的指令I，并假设当前的时刻为T。

　* 如果 state 为 Idle，那么
　　　　 o 如果 I 为空，那么什么也不做
　　　　 o 如果 I 的形式为 (t0,f0);I′， 那么
　　　　　　+ 如果 T < t0 那么什么也不做。
　　　　　　+ 如果 T ≥ t0 那么将 state 设置为 GoingTo(f0) 并且将 I 设置为 I′。
　　* 如果 state 为 GoingTo(f)， 那么
　　　　o 如果 p = "楼层f"，那么将 state 设置为 Idle。
　　　　o 如果 S 正在 电梯e中，并且电梯e位于“楼层f”，电梯状态是 Open，那么将 p 设置为“楼层f”。
　　　　o 如果 p =“楼层f0” ( 不等于“楼层f" )，那么
　　　　　　+ 如果 f < f0，那么将指示灯 d 设置为 Down，否则将 d 设置为 Up.
　　　　　　+ 如果电梯e位于“楼层f0”，且状态为 Open，指示灯为d，电梯内少于5人, 那么将p设置为电梯e。

注意，如果点运行的速度慢，可能导致乘客获取到一个过期的指令，以上的规则可以保证，所有的指令都会按照顺序被执行。换句话说，乘客可能在某些步骤，比指令计划的有所延迟，但是都会根据指令完成确定的旅程计划。

对电梯建模

模拟的电梯承载着乘客，在楼层之间移动。我们需要使用一些状态来对电梯建模。

电梯高度

每一部电梯都有一个“当前高度”，假设每层楼高10英尺，电梯的高度用从0到40的整数表示。当电梯的高度是10的整数倍的时候，我们就说该电梯唯一第“高度/10”层。比如当前的高度是30，就说明它在第3层。在模拟开始时，两部电梯都在第0层。

电梯动作

一个电梯一共有4种可能的状态：“打开”（Open）、“静止”（Stopped）、“上移”（GoingUp）和“下移”（GoingDown），描述如下。任何操作都不会使电梯的高度小于0或大于40，即高度永远在 [0,40] 这个区间内。

“打开”：乘客可以进入或离开。

“上移”：电梯按照5英尺/拍的速度上升。

“下移”：电梯按照5英尺/拍的速度下降。

“静止”：没有什么动作。

只有特定的电梯动作序列是有效的。一个电梯一旦开始运动，就不能开门。各种状态之间变迁需要符合下图。即从状态s到状态s’，只有符合下面图中存在从s到s’的箭头时才是允许的。例如。从“下移”状态，可以变为“静止”状态，但是不能变为“打开”或“上移”状态。

电梯的初始状态是“静止”。一部电梯内同时最多容纳5个乘客。

指示灯

每一部电梯有一个指示灯，分别有“上”、“下”和“无”三种显示状态。

电梯调度

由电梯本身来决定自身的行动，也未尝不可。不过更好的方式，还是为电梯的运行提供集中的控制。这个模拟程序，将使用单一的方法来为整个电梯系统的运行提供计划。这个方法称为 PlanStep，由以下接口定义：

 interface  IElevatorPlanner 

 {

     //定义方法 PlanStep(controls, upFloors, downFloors) 

     //用于对电梯进行调度 

     //其中的参数： 

     //controls[e] 对应于电梯e的控制 

     //upFloors[i]为 true ，当且仅当一名乘客在“楼层i”，且状态为GoingTo(j)，且 j > i 

     //downFloors[i]为 true ，当且仅当一名乘客在“楼层i”，且状态为GoingTo(j)，且 j < i 

     void  PlanStep(IElevatorControl[] controls,

                   bool [] upFloors,

                   bool [] downFloors);

 }

PlanStep方法将会使用comtrols数组中的对象对外界作出响应。PlanStep可以使用内部的状态来辅助作出决策，但是必须做到仅通过这个接口与电梯和乘客交互。显然，upFloors 和 downFloors 数组对应的就是对每个楼层的电梯按钮，又等候电梯的乘客按下。这里做了一点简化，使用真实的电梯时，乘客会先把电梯呼叫到他所在的楼层，进入以后，再按目的楼层的按钮。而这里则化简为在电梯外就确定目的楼层。

IElevatorPlanner 接口依赖于一个控制电梯的类（声明为接口）以及两个相关的枚举类型。分别定义如下：

enum ElevAction { Open, Stopped, GoingUp, GoingDown };

enum ElevLight { Up, Down, None };

interface IElevatorControl{
    
    //StopRequested(i) 返回 true，当且仅电梯内乘客的状态是GoingTo(i)。
    //需要对i做参数检查，确保在 [0..4]范围内。
    bool StopRequested(int i);

    //只读属性，返回电梯的当前状态。
    ElevAction ActionState { get; }

    //设置电梯的当前状态。
    //需要对参数作检查，确保参数是一个有效的状态变迁。
    void SetAction(ElevAction s);

    //只读属性，返回电梯所电梯指示灯的状态。
    Light Indicator { get; set; }

    //只读属性，返回电梯所处的高度。
    int Height { get; }
} 

作业内容

编写一个图形界面，显示模拟的当前状态。提示：System.Windows.Forms.PictureBox 提供了显示图像的方法。你的图形界面应该包括以下功能：

1）用户可以把鼠标移动到一个电梯或乘客上，查看他当时的状态。可以使用：System.Windows.Forms.ToolTip。

2）用户可可以控制电梯运行的步数，每次跳过一定的步数（比如10步、50步），显示电梯的状态。

3）用户可以通过读入文本文件设定乘客的行程计划。

挑战部分：动画演示

使用动画方式演示电梯的运行过程。

总结

这是一个很有意思的题目，通过这个题目，读者可以注意到几个问题：

1）现实世界中的系统，和信息世界中的系统，是如何对应的。在题目中多次提到了一个词“建模”，这非常本质地说明了，软件开发很重的一个性质。

2）系统地分析，在这题目的描述中，可以发现他非常清晰对系统地进行了划分，而且每个部分之间的耦合度非常低，这是值得学习程序设计的读者仔细领会的要点。

希望我的文章对您有所帮助。

您可以到新浪微博联系我： http://t.sina.com.cn/1906984307 。

前两次的文章介绍了两个实践题目，我又想到的第三个不错的选题，是写一个“电梯运行模拟程序”。这个题目是我在做本科毕业设计的时候，看到比我高一届的一个同学的毕业论文，当时就觉得很有意思。这里面除了涉及基本的编程语言，核心的面向对象的编程思想，和设计模式的运用，我觉得对一个学习者，是个相当不错题目。

为了写这个题目，我在Goolge用“assignment elevator simulator”作为关键字，搜索了一下，想看看国外的大学有没有用这个题目给学生留作业的。不出所料，果然搜出了一大堆美国大学计算机系的课程页面，使用这个题目给学生留作业。[BTW：如果在未来的某一天，在中国无法使用Google了，中国真的要倒退100年，但是很多人不这么想，很无奈。]

我浏览了这些美国大学的相关课程页面之后，很受启发，我觉得可以增加一篇文章，来讲讲国外大学的计算机系是如何讲授一门高级语言的。因为他们讲的内容和方式，和我当年上大学的感觉很不一样。

这里我就选择美国加州大学洛杉矶分校（UCLA）计算机系的一门课程为例 ——”CIS 399-005: Introduction to Programming in C# “，即编号为CIS 399-005的“C#编程介绍”。如果是在中国的大学里开这么一门课程，相信所有人都会认为是给文科或者非计算机专业开设的简介性质的课程。

下面我就介绍一下在UCLA，这么一门从名称看非常入门的课程，具体是如何教学的。如果读者懂英语，可以查看这里“Introduction to Programming in C#”的页面。

这门课程的网页左侧是一个目录，包括课程 Policy（规则）、Problem Sets（作业项目）、Resources（资源）、Software（软件）和 Schedule & Notes（日程和备注）。我们选择一些重点内容介绍。

如何评分？

在规则部分，首先给出的是这门课程的评分方法：

课程参与度 ： 10分

作业项目1 ：5分

作业项目2 ：10分

作业项目3 ：15分

作业项目4 ：20分

期末项目 ：40分

看到吗？没有笔试考试！就是5个实际的编程项目。这很重要，我清楚地记得，我在上大学期间三次参加编程语言的笔试考试：Pascal（一年级）、C（三年级上） 和 C++ （三年级下）。考题大多是一些孔乙己的“茴香豆有几种写法”式的问题，看看你对于语法规则是否熟悉。我上的大学（华中理工大学，现在改名叫华中科技大学）的计算机系在中国的大学计算机系里，如果不能排进前10名，至少可以排进前20名，尚且如此，对于其他成百上千所大学的计算机专业的教学，可想而知。

注意事项

接下来，告诉学生应该如何参与课程，做哪些准备工作，以及不要迟交作业（时间是精确到秒的，晚交作业扣50%的分数），最后告诉学生抄袭是“绝对零容忍”的。这些事情，说起来很简单，但是如果你仔细看一下他的文字，都能感觉到一种既和善又足够有力的力量。

此外，还特别鼓励学生接受挑战，在每个作业题目中，除了基本要求之外，还会各处一个“挑战”部分，给那些有余力的学生。因此，鼓励学生迎接这些挑战，但也不忘提醒学生，务必先把基础部分完成好之后，再做挑战部分。

讲授内容

在“日程和备注”部分，给出了每次课程的日期和概述，大家可以仔细看一下，他们是如何教C#语言的。包括了C#语言的对象模型、面向对象的思想方法何实现，泛型、反射、多线程开发、互操作、高阶（High order）编程等等很多深入的内容。这些内容基本覆盖了《C#本质论》的所有高级内容，可绝对不是简单讲讲C#的语法而已。

作业项目

最重要的是我想介绍一下他们布置的5个作业项目。

“问题1”非常简单：包括一个“Hello World”程序，和一个对字符串排序的程序。

“问题2”开始就不一样了：写一个图形界面的“逆波兰式“计算器。

“问题3”又上了一个台阶：写一个手写数字的识别程序。这是模式识别领域的问题。

“问题4”就是我前面提到的题目：写一个“电梯运行模拟程序”。它涉及到面向对象的分析方法、设计模式、状态机等很多问题。

“期末项目”：这是一个开放式的问题，组成3-5人的开发小组，从策划构思到最终的实现，配合完成，并作现场的演示和讲解。

我感觉这几个题目，对于一个本科生的一门课，强度真是不小。这让我想到了《软件随想录》中，Joel的理论：大学计算机系必须要开设一些“非常难”的课程，把真正适合做软件开发的人筛选出来。

总结

我十分希望中国的大学可以把教学的档次再提升一些，当然我也看过一些清华大学计算机系的课程的教学网站，感到学生的水平和这种作业项目的质量，是相当牛B的。希望这样的模式能从仅仅少数几所学校，扩展开，至少国内前100名的学校应该有这个意识。

从这里，也给学习C#的或其他语言的读者提一个建议，就是想要学会一门语言，就必须真正动手，实实在在做一些需要比较复杂逻辑思考的程序，这对于一个开发人员是必须的路径。如果你是大学生计算机系的学生，在毕业前，至少应该写够5万行有意义的代码。

另外，强烈推荐《软件随想录》这本书，值得所有软件行业的人认真读一读，如果你还没读过，务必要买一本。

下一片文章，我将会把“电梯运行模拟程序”这个题目，按照上面UCLA的这门课程页面中的讲解，进行比较详细的说明。

如果读者感兴趣，我可以把上面那几个题目分别翻译一下，介绍给学习C#或其他语言的读者，你们亲自动手试试看。

在上次的文章里，讨论了编写一个五子棋程序的基本思路。下面再举一个编程实践的题目。可以分为两步走，第一步是很简单的，每一个学习过《数据结构》的读者都可以完成，第二步复杂一些，但是也是可以完成的任务。

所有用过的电脑的人，都离不开“压缩”这两个字。你有没有考虑过，是如何实现这么神奇的功能的？你有没有想过自己也写一个WinZip、WinRar这样的压缩文件的程序？其实你完全有这个能力。

所以今天给学习编程的读者提出的实践题目是“文件压缩”，当然也包括解压。在介绍编写文件压缩和解压这篇文章里，我们还将介绍三个人，都是计算机科学和软件界响当当的人物。

基础

其实在我们日常生活中，用到的“压缩”有两大类。

1）无损压缩 —— 在文件压缩中，使用的就是无损压缩，也就是说压缩以后的文件还可以恢复为原来的文件，而且一个字节都不差。这样的压缩没有损失任何有用的信息，因此叫做无损压缩。

2）有损压缩 —— 在图像压缩中，经常用到这类压缩，比如最常用Jpeg格式的图像，如果用图像编辑软件，可以把文件的大小缩小很多，而我们肉眼看起来，图像质量没有明显变化，但实际上，图像质量还是下降了，而且一旦压缩以后，就无法在恢复原来的清晰度了。这样的压缩就损失了有用的信息，视觉感觉不很明显，文件的大小却可大幅度减小，因此也是十分有用的。这样的压缩就叫做“有损压缩”。

我们今天要讨论的是第一类压缩，即“无损压缩”，这类程序要完成“压缩”和“解压”两个功能。

香农与信息论

第一个历史人物出场 —— 克劳德·香农(Claude Elwood Shannon，1916-2001)。这位美国科学家在20世纪40年代，开创了信息论，用数学方式科学地定义了信息的各种相关概念。1948年的论文《A Mathematical Theory of Communication 》，被认为是其标志。信息论和系统论、控制论一起，被称为系统科学的“老三论”，对应于后来的“新三论”，即耗散结构论、协同论和突变论。

香农的信息论中，借用热力学的概念“熵”来度量信息，定义了“信息熵”的概念。我们这里不进行正规严格的介绍了，通常在大学本科的相关专业会有一些课程进行介绍。我们这里为了便于大家理解，简单地介绍一下，因为它是压缩软件能够存在理论基础。

简单举个例子，有两本书放在我们面前，我们如何评价两本书的信息量？假设一本书是《红楼梦》，另一本书很特殊，他的内容只有一句话，但是重复印刷了1万次。那么即使两本书印刷的字数是相同的，我们也认为前者的信息量要远远大于后者，因为后者相当于只有一句话，其它的都是重复，没有价值，被称为“冗余”。这是一个极端的例子，但是说明了压缩的基础就是存在“冗余”，压缩的目的就是消除掉“冗余”，这样既保证了信息没有损失，又减小了体积，在解压时，把这些“冗余”在恢复即可。

正如计算机的出现，必须在一系列数学家（图灵、冯诺依曼等）把计算机的理论模型分析清楚之后，才有可能一样。香农的研究，把这些问题的基础研究清楚，这样才有可能实际做出很多实际应用。当然，数据压缩仅仅是它的应用中非常非常小的一个，但是每天都被我们应用，并且它很容易被我们理解。

顺便可以提一句的是，大家都知道CD音质的采样频率是44.1KHz，但是你考虑过为什么是这个数字吗？首先为什么是40多KHz？而不是10KHz或400多KHz？这也跟香农的一个研究有密切的关系，“香农采样定理”说的是：为了不失真地恢复模拟信号，采样频率必须不小于模拟信号频谱中最高频率的2倍。 声音是模拟信号，声音的数字化就是通过采样实现的，根据香农的这个定理，采样频率不能小于声音的最高频率的2倍，而人耳可以听到的声音的频率范围是20Hz到20KHz，因此要能够不失真地恢复人耳能够听到的声音，就不应该低于40KHz。而至于为什么是有零有整的44.1呢？实际上在音频工业界，早期存在不同的方案和标准，最后逐渐统一到了44.1，至于44.1是如何来的，有不少文章做了介绍，我这里就不再介绍了。

哈夫曼编码

下面，第二个历史人物出场 —— 戴维·哈夫曼 (David A. Huffman, 1925–1999)。香农在提出了信息论的原理同时，和他在MIT的同事 Fano 一起，提出了一个编码方式，对通信中的数据进行编码，称为 Shannon-Fano 编码。 但这个成果很快就被 Fano 的一名学生超越了，他就是哈夫曼。而有趣的是，哈夫曼提出的这种后来被称为“哈夫曼编码”的编码方法，仅仅是为了避免一门课程的考试而写的一篇小论文。就是这篇在他学生时代的小论文，让他成为了一名著名的科学家，并且写进了无数的教科书中。

下面来简单介绍一下哈夫曼编码的原理，实际上每一本《数据结构》的教科书，在“树”这样一章，都有对哈夫曼树以及哈夫曼编码的介绍。其基本原理就是，在一段信息中，不同的字符出现的频率是不一样的，比如英文中，字母e出现的频率最高，而字母 z 出现的频率就低得多。那么如果各种字母都占用一个字节的保存，就浪费了很多空间。如果可以让出现越多的字母占用的空间越小，比如e这个字母就只占1个bit（编码前，各种字母都是占一个字节，8bit），字母出现少的字母占用的空间多，那么总的空间就会小很多，从而就实现了“压缩”的目的。大家可以找任何一本《数据结构》教科书，找到具体的讲解和详细的算法说明。

现在终于说到你需要动手编写的程序了。第一步，你可以编写一个用哈夫曼编码实现的压缩和解压软件。实际上这个题目正是我大二学习完数据结构以后，老师布置的课程设计（就是两周时间的一个大作业）的题目，我觉得挺有意思。 如果你很快地就完成了，你可以再仔细考虑一下，如何提高程序的性能，比如同样大小的一个文件，你能否让压缩和解压的实践更短一些？如果你可以分析一下，算法中，时间是如何分配的，你又是如何优化的，那么你的收获将会是巨大的。

PK与Zip压缩算法

在中国，由于版权意识不够，所以Rar格式的压缩文件用的较多，但是在世界范围内，绝对是Zip格式的压缩软件占绝对的比例。每个Zip格式的文件的开头两个字母都是PK。这就来自于下面出场的第三个历史人物 —— 菲尔·卡茨 Phil Katz, 1962－2000) 。可以看到，1962年出生的他本来完全不应该成为历史人物，但是已经早早地离开了这个世界，他的命运令人唏嘘。他发明了Zip软件和Zip文件格式。

我们先来简单介绍一下Zip压缩的基本原理。哈夫曼的算法，考虑的是核心是不同字节（字符）出现的频率的不同带来的冗余，通过消除这种冗余实现了信息的压缩。Phil Katz 的算法则考虑了另外一种冗余 —— 短语带来的冗余。

比如英语中，the 这三个字母连在一起，出现的频率非常高，ese 这三个三字母连在一起，也是比较经常的，它们都占用了3个字节，假设我们有办法用两个字节来代替这三个字节，就可以实现数据的压缩。别小看这1个字节的缩小，但是带来了本质的变化。进一步，我们可以考虑，在一段有意义的文字中，有很多重复的短语，这都造成了信息的冗余，如果我们消除这些由于短语重复带来的冗余，就可以实现对信息的压缩。也就是说，一段纯随机的字母组成的段落，用这种方法压缩是无效的。但是实际上，我们生活中用到的文件，基本上都是有意义的，而非随机的。除了文本之外，比如一个图像，按像素排列，也存在着大量重复的样式，都是可以大幅度压缩的冗余。

在经典的Zip压缩算法中，使用一种称为“滑动窗口”的算法。在编码过程中，随时检查是否出现出现了重复的短语，一旦发现出现了重复的短语，就用这个短语的长度和到当前位置的距离两个数值代替这个短语，这样就可以实现压缩了。

而理论已经证明，世界上只存在上面说的这两种方法，即字节编码和短语编码，可以实现无损压缩。在Zip的压缩中，首先使用短语编码，压缩一次，然后再使用哈夫曼编码压缩一次。

当然，具体要实现一个Zip算法还是有许多问题要解决的，希望读者仔细到网上搜索一下相关的资料。此外，要实现高效的算法，需要更多地技巧。网上有不少文章介绍，都很有帮助。如果读者有兴趣，可以把Zip算法实现出来，虽然可能不是那么精致完善，压所的效率（空间和时间两方面）没有那么高，但是我想，写这么一个程序你对自己的写程序的帮助一定会非常巨大。

说起Phil Katz，他是一个非常有性格的程序员，他坚持自己的理想，坚持使用自由软件的方式发布自己的软件，拒绝与商业公司合作，并与商业软件公司对抗，很不幸的是他年仅37岁，因酗酒死于一家汽车旅馆。如果感兴趣，可以看一下这篇文章，算是一篇纪实文学，尽管里面唯一句涉及Zip算法的话，原文或者翻译的是不准确的，但是这篇文章还是很有意思的。

现在几乎全世界的每一台PC上都有用Phil创造的压缩算法生成的文档。现在虽然他的生活并不算成功，但是所有ZIP格式的文档的最开头，都嵌有他姓名的字头缩写“PK”两个字母，也算是他的生命走遍了世界这个世界的各个角落吧。

希望我的文章对您有所帮助。

您可以到新浪微博联系我： http://t.sina.com.cn/1906984307 。

在前几天的文章里谈了如何学习C#语言，实际上学习任何语言都具有相当大的共性。最重要的一点就是必须实践，真正用某个语言写一个有定规模的程序。

在那篇文章的末尾，我给出几个选题建议，如果你正在学习某种语言（什么语言都可以），以下可以作为实践题目，自己来写一个程序：

1）写一个能够和人对弈的五子棋程序，看看你的程序下棋的水平能到达什么程度。

2）用面向对象的思想，写一个电梯运行的模拟程序。

3）研究压缩算法，写一个文件压缩和还原程序。例如最简单的，你可以研究一下哈夫曼算法，然后以此为基础，你可以找到很多压缩算，都可以综合在一起，实践一下。

下面分别解释一下这三个题目。今天说第一个，另外两个以后说。

五子棋

1998年我本科的毕业设计，指导教师研究的领域是人工智能，给我们的题目是写一个能够下围棋的程序。

不过我当时研究了一下之后，感觉这个题目实在太大了，对于博弈程序，核心是两个方面，一个是搜索的基本算法，另一个是对博弈的实际游戏（比如围棋、象棋）的理解。也就是说，如果写围棋程序，就得懂围棋。对于一个本科生来说，写一个博弈程序，能做的就是两件事，第一是搭出一个相对完善的基于搜索的算法，第二是给出对于棋局的形势，给出一个不完全离谱的估值函数。两个方面缺一不可，否则无法实现有意义的自动对弈。搜索算法，对于棋的类型相差不多；但是对于棋局形势的判断，各种棋类就相差很多了。大家都知道，围棋是最复杂的棋种，棋盘特别大，一盘棋的步数非常多，开始的阶段的很多步，都不是搏杀性质的，二是大形势的布局，这样计算对于编写算法来说，非常困难。

于是我就跟老师申请，要求改成五子棋，这样对棋局形势的估计就简单多了，比如一个“双活三”的形态是赢棋，一个“活三”比“活二”的价值更大。从而可以更专心在搜索算法的实现上夺下一些功夫。老师不同意，说五子棋太简单没意思。最后折中了一下，做了一个中国象棋的程序。中国象棋比围棋确实简单一些，而且能够较快地进入搏杀阶段，这样搜索算法就能派上用场。对于布局阶段，搜索算法基本没有作用，比如你是用“当头炮”开局，还是“仙人指路”开局，是没法评价孰优孰劣的。只有到进入到一定阶段以后，开始搏杀，搜索算法才能派上用场。因此，我就在开始阶段，事先准备好一些开局定势，不用搜索，直接用定式走开局的若干步。然后到了一定步数以后再开始使用搜索算法来计算下一步棋的走法。

最终的效果还不错，最后这个毕业论文得了95分。回头来看，做这个程序，其实还是收获挺多的。但是有一点小小的遗憾，一个本科生，2、3个月的时间，写一个象棋的博弈程序，其实还是太困难了，如果当时能使用五子棋作为题目，效果会更好一些，因为估值函数简单，可以更多地探讨一下搜索算方面的问题。事实上，国际国际上早期的人工智能领域的研究者，在研究波一问题的时候，开始选择的也是特别简单的跳棋程序。其实我的整个毕业设计的程序的算法，没有超出陆汝钤编写的《人工智能》上册中的讲解的搜索算法。不过很遗憾，我做的那个程序没有保存下来，现在也没有了。

总体来说，要编写一个自动博弈的程序，最好先看一本人工智能的教课书（比如陆汝钤编写的《人工智能》上册就很好），里面一般都会有关于博弈问题的讲解。了解一些基本的概念之后，掌握几种基本的搜索算法，从简单的博弈树开始，增加一些剪枝和启发技术，这些算法都不是很复杂。而五子棋的估值函数就很简单了，比如活三冲四、直四的都是杀招，依次排列，情况并不太多，分别赋一个适当的分值即可。

此外，我找到了一篇荷兰 Louis Victor Allis 博士的博士论文：“Searching for Solutions in Games and Articial Intelligence”（《在博弈和人工智能中对解的搜索》），里面讨论了好几种棋类的博弈算法，并给出了很多性能分析。非常实用的是给出了一个五子棋的非常有效的算法，把普通的博弈树转化成搜索树进行求解。我试验了一下，非常好用。2010年春节假期，我花了几天根据这篇论文的算法，写了一个小程序，我用一些五子棋网站上给出的五子棋题目进行试验，效果非常好。很多需要十几步甚至几十步的解，都能非常快的计算出来。

因此，这个题目实际上还是很有意思的，需要对数据结构有所了解，在此基础上对人工智能有所了解，《数据结构》+ 陆汝钤的《人工智能》上册 + 某一种高级语言，基本刹功能就可以做出一个可以下的五子棋程序了。如果希望程序的棋力在高一些，可以参考我上面提到的“Searching for Solutions in Games and Articial Intelligence”这篇博士论文的第5章。

如果有做出来的，可以和我联系，让我也跟你的程序下一下哦。

如果大家感兴趣，又觉得自己做起来比较困难，我也可以考虑是否可以写一本C#开发实践的书，就已这几个小项目为案例，深入的讲解一下。大家也可以给点建议和意见？

顺便提一句，这位 Louis Victor Allis 博士1994年博士毕业以后，1997年创建了一家软件公司，利用人工智能和算法上的技术优势，从事物流和排程相关的软件研发。现在这家公司已经使跨国企业了，在中国也有业务，中国的总部在上海。这是一个很好利用自己的技术创业的榜样。

好了，今天就介绍到这里，下次再介绍另外的题目。也都是很有意思的题目，学习完一门语言之后，作为实践，会对掌握这门语言有很大帮助。

希望我的文章对您有所帮助。

您可以到新浪微博联系我： http://t.sina.com.cn/1906984307 。