Re(8):无题

　apple说:
　| 哦，原来你也是用windows的，那你学的那些语言都用在什么地方？我总觉得学一个东西总要是用出来的吧，如：某个程序、某个网站、某个系统？不可能总停留在某一个函数和算法的研究上啊？
　| 而要发布或部署一个系统，又要用到windows平台，那你写代码总要ide帮助才行啊，如果用记事本写程序的话，完成一个系统那得花多长时间啊？所以好的ide帮助你处理了那些和部署相关的啰嗦的东西，然后你才能安心的处理程序逻辑~
　| 而且你的动态语言，我真的不理解，现在流行的python，及perl，这些语言自身是不可存在的吧，他们需要借助某种环境，如必须放在网页中，perl 好像还需在*nix下吧。so，我在windows下就很迷惑，我想写段python或perl代码，却找不到该在哪写？然后就算写好了，确不知道该如何运行~
　| 而在大学时也曾想转到nix下，装了freebsd，然后却发现用的很不适应，它里面的编写程序的环境也不是很友好，对着黑黑的窗口和界面普通的kde，感觉无所适从，觉得他不像传说中的那样充满吸引力~
　| 于是，在周围同学的CS枪声中我又装回了windows。
　| 现在，偶然，碰到你，我又对nix找回写兴趣，我觉得我骨子里还是希望能对nix有比较深入的了解的~
　
　我其实不算是用win的，因为很早开始我就在用*nix的方式工作。这个星期装上了freebsd，甚爽，发现以前学的知识都有了充分的发挥，bash/term好用的不行，再也不用忍受连行编辑都不支持的cmd.exe了。
　所谓“学东西拿出来用”，我是这样理解的：写程序，做网站，核心的部分、难的部分不超过20%（除非你写的就是算法库）；但这部分却要花去你 80%的时间。剩下来那80%的代码呢？普通的逻辑和简单的调用而已。就知识而言，前者是活的，后者是死的。所以我懒得去搞应用，因为我知道，凭我的能力，到时候对照着文档写都来得及。平时重在练“内功”，以期用兵一时啊。
　关于ide，这样跟你说吧。我肯定不会去用ide，但也不可能去用notepad。我们prefer高级编辑器。只要你不用java、c+ +、.net这些特别费话的语言，没怎么配置过的vim，emacs这些东西绝对比ide高效（当然，也可以把emacs弄得比eclipse还拉风，但我不用，就没兴趣了）。它们的指导思想是：让你在写程序的时候用100%的精力思考程序逻辑，用0%的时间输入代码。所以，1. 不帮助你思考。需要有程序帮你思考的语言就不是好语言；2. 不阻碍你思考。敢和人类作对的程序应该去死；3. 使你更快地输入代码。这是高级编辑器提供效率的关键，也是不阻碍你思考的一部分。你觉得ide的代码完成高效吗？vim也有，但不会没事干地帮你匹配文件里没有的单词。而其它的地方ide就没什么戏了。如果你要修改前面第4个单词，你刚把手从键盘上撤下来还没放到鼠标上，vim的用户按3个键esc,3, b就定位到了。举个对你应该特别熟悉的例子：你可能经常需要把程序中的两行并成一行，你常常把光标移过去，然后删除所有自动缩进；vim用户用数字建、k 定位到行，按下shift+j就搞定了。速度，永远不是从帮你输入废话上得来的。
　编译、发布、部署、打包程序，这种事情你可能经常让ide代劳。不过你也可能从未想过ide怎么会这么清楚的。它们的能力来源很简单，就是跟*nix学的。make程序，提供了组织程序的一条龙服务的终极武器，每个ide的必备抄袭作品。vs再怎么发展，也不会少了它的nmake.exe，否则它就成了史上最大记事本了。但李鬼终究还是敌不过李逵，nmake这样的东西怎么能敌得过新时代的gnu-make？别说是m$麾下的东西了，就是 ant在它面前也得退避三舍啊，复杂的xml怎么能比一个领域特定编程语言强大？连写makefile都嫌烦，没事还有automake、patch，好了只要把目录组织一下就行了，而且连打补丁都不用你操心了。
　这些事关ide的存在价值的东西都在*nix小工具面前黯然失色，其它的东西就更没得比了：gnu下有最强大的编译器、汇编器、调试器，各种dsl程序遍地爬，grep不行上awk，再不行上perl，连接它们的管道四通八达，你可以随心所欲地在编辑器里查看从最底层的gcc那儿传上来的经过数层处理后的信息。
　不过懒得出奇的*nixr也有嫌这个也烦的时候，如果有什么语言不用编译不要调试不用部署就更好了。动态语言就是这样的东西。在任意一个平台下装上解释器，一条命令就能执行；高阶函数的出错信息可以跟踪出调用轨迹，不需要调试器；文件间互相说声引用谁就行了，不用部署。写好了代码不知道怎么运行？把相应解释器装上运行一句 <语言名> <文件名> 就行啦！
　黑黑的窗口，闪动的光标下是行编辑库，让你在输入命令时获得相当于使用emacs的编辑效率；kde当然没什么意思，仿win仿着玩儿的大玩具一个；试试看怎么把wmaker调成Mac第二，把fvwm做成外星OS，我觉得这个比较有意思。我现在的freebsd就是用的wmaker窗口管理器，装上几个顺手的gtk程序，剩下来的让vte终端全包。性能好到不行，启动图形界面4秒钟。Unix的重点不在于刚装好时的配置如何，而在于极限的能力是否能满足你的意图。就拿winer们常指责*nix的驱动程序一项来说，其实os里这些驱动都有了，你所要做的只不过是修改某个配置文件中的一两行。这帮winer自己数典忘祖，忘了win装完后必须下载驱动才有全屏显示和声卡支持，而且如果你没有网卡驱动就只能哭去了！
　再如装软件。win装软件要搜索多长时间才能下到，还得提防有没有恶意软件，点多少个next才能装完，装完想删掉还卸不干净，装着装着注册表就破50M了。pkg、yum、apt这些东西多方便，你只要知道软件名，输一行命令就能全搞定。有些不明事理的人还指责*nix软件怎么会对其它软件包有依赖。其实这才是*nix的魅力所在：开发出来的东西大家用，做的好的就是库。事实上，只有本地安装命令才会指出依赖性问题，使用自动安装连这些被依赖的软件也一并装了，反正想删就删，*nix分区只要有5%的空间就能保证没有磁盘碎片，多装没坏处。
　最后想说的是玩游戏。我用win的时候打了一年魔兽，现在在班上几乎无敌；但又能怎么样呢？我下围棋估计能全灭学校的人，然而没什么人知道。由此我意识到，游戏终究是一种逃避，想把在其它地方失去的虚荣心找回来。领悟了这一点，我也就不再玩游戏了；有时间就下围棋，没时间下就国际象棋， *nix下的gnugo和gnuchess都是普通棋类程序中的强者（不过围棋程序现在的算法还做不了太强，前者还不是我的对手），杀败了它们还可以上 igs和ics，生活很幸福~`

OOP 诡异教程（下）

这是最终确定的 JavaScript 基于消息传递编程风格的文章“OOP 诡异教程（上）”的下篇。原文地址：http://let-in.blogspot.com/2007/06/oop.html。原来的想法是以风格开头，谈到 JavaScript 的内部机制，但作者 lichray 迟迟没有动键盘，认为不如利用已有的风格做一套机制出来，这样可能更有意义。于是，就有了这个更加“诡异”的下篇。

四. 扩展的实现
上文最后给出了一个“看上去很美”的基于消息传递的编程风格，比如构造一个 People 类的代码类似：

function People () {
　　var money = 0
　　function setMoney (dollars) {
　　　　money = dollars
　　}
　　function pay (dollars) {
　　　　money -= dollars
　　}
　　return (function (verb) {
　　　　return eval(verb)
　　})
}

有了这样的语法我们就可以描述不少句子了。但是存在一个问题：现实中的 Objects 之间是存在关系的——比如，forrest 是个 IQ 为 75 的傻子，傻子是 People 的一种。而我们仅仅是生搬硬套了一种语法而割裂了这种 "is-a" 关系。现在我们的工作，目的之一就是让这样一个“真切”的世界从我们已有的编程风格的地基上拔地而起。
到底应该怎样做才能使 Fool 产生的对象都能响应 People 的消息呢？我们要给 Fool 产生的对象（也就是返回的那个匿名函数啦）都添加这样一种能力：如果在 Fool 中响应不了消息，那就反馈给 People 响应。

function Fool (iq) {
　　var IQ = iq || 0
　　function init (iq) {
　　　　IQ = iq
　　}
　　return (function (verb) {
　　　　try {
　　　　　　return eval(verb)
　　　　} catch (e) {
　　　　　　return People()(verb)
　　　　}
　　})
}

js> forrest = Fool()
js> forrest('init')(75)
js> forrest('IQ')
75
js> forrest('money')
0

五. 语法扩展和代码生成
这下代码量增加了很多，强迫潜在的使用者们在创建每个类时都这样写那实在是令人抓狂。本来这篇文章应该不提此类问题的解决，但考虑到有益于读者理解“机制”这个抽象概念，这里给出一个可行的方案——把普通的类代码用 Function() 函数重编译为可用的 JavaScript 函数。也就是说，我们能给出类扩展的代码并指定被扩展的类来获取类似上文的代码：

Fool = extend('People()', function (iq){
　　var IQ = iq || 0
　　function init (iq) {
　　　　IQ = iq
　　}
})

为了方便字符串操作，我们希望编译后的代码的参数部分（如 People()）都集中出现在一个位置且尽可能便于定位。在函数头添加一句

var origin = People()

当然是可行的，这样还能使 Fool 内部显式引用到其超类。但这样还不够漂亮。我们修改编译后的样例代码为：

function () {
　　return (function (origin) {
　　　　var IQ = 0
　　　　function init (iq) {
　　　　　　IQ = iq
　　　　}
　　　　return (function (verb) {
　　　　　　try {
　　　　　　　　return eval(verb)
　　　　　　} catch (e) {
　　　　　　　　return origin(verb)
　　　　　　}
　　　　})
　　})(People())
}

这个利用参数传递变量的小技巧不值得学习，实际效率不高。但在这篇文章中，这样绑定特殊变量的技术是标准方案。
那么，extend() 函数的实现为：

function extend (originc, code) {
　　function argsArea (code) {
　　　　// 题外话，正则表达式也有不值得使用的时候
　　　　return code.slice(code.indexOf('(')+1, code.indexOf(')'))
　　}
　　function bodyCode (code) {
　　　　// 不用 trim() 了，没事儿找事儿
　　　　return code.slice(code.indexOf('{')+1, code.lastIndexOf('}'))
　　}
　　function format (body) {
　　　　var objc = bodyCode(function () {
　　　　　　return (function (verb) {
　　　　　　　　try {
　　　　　　　　　　return eval(verb)
　　　　　　　　} catch (e) {
　　　　　　　　return origin(verb)
　　　　　　　　}
　　　　　　})
　　　　}.toString())
　　　　return 'return (function (origin) {'+body+objc+'})('+originc+')'
　　}
　　var $ = code.toString()
　　return Function(argsArea($), format(bodyCode($)))
}

这样前文提到过的 extend 的实例代码就可以正常运行了，测试代码不再重复。

六. 机制完备化
这样，我们的基于消息传递编程风格的一套面向对象机制就确定下来了。机制是宪法，是语言的根本大法，有了它，我们就可以通过修改代码生成器，很快地给这套机制进行完备化。
想法有很多，例子只举两个。
第一个例子：类的定义中应该能直接引用到将产生的对象 self。答案只有一句话：把返回的那个作为对象的匿名函数命名为 self。
第二个例子：既然是单继承模式，应当存在一个顶层类 AbsObj，使没有指定继承的类自动继承它。答案也只有一句话：在 extend 函数体第一行添加代码：

if (arguments.length == 1) {
　　code = originc
　　originc = 'AbsObj()'
}

然后手工构造设计 AbsObj 类，为空也无所谓。不过当然了，一般都会给顶层类添加一些全局性质的消息绑定。由于是“底层操作”，基本上都需要修改 extend 函数。做了一个简单的：

function AbsObj () {
　　//检测是否能响应此 verb，要再用一次异常处理
　　function canHandle(verb){
　　　　try {
　　　　　　// 别担心这里的 self 会传递不过去
　　　　　　self(verb)
　　　　} catch (e) {
　　　　　　return false
　　　　}
　　　　return true
　　}
　　function toString() {} // 这个搞起来其实很麻烦~`
　　var self = function (verb) {
　　　　return eval(verb)
　　}
　　return self
}

js> Obj=extend(function(){x=5})
js> o=Obj()
js> o('canHandle')('x')
true
js> o('canHandle')('y')
false

文章写完了，小结一下。消息传递的编程不仅仅是一种代码风格，还可以成长为一种完备的机制。这种完备性远不只是这两篇加起来不到300行的文章所能覆盖的（例如非常彻底的“万物皆对象”，因为只要是能响应消息的函数，连接一下 AbsObj 就是合法对象了；类，函数都可以），大家可以试着玩一玩，顺便体会一下这个计算模型的透明和强大。
另外，熟悉函数式编程的朋友可以帮忙思考一下：这样一个基于闭包变换的计算模型实质上是函数式的，再配合动态的函数式的对象级继承（用一个匿名类代换一下）就能在纯 FP 真正下实现 OOP 了。可惜的是每一次更新操作都要重新生成对象，性能代价大了点，不知道大家有什么好想法。

新人报到！

大家好，我叫Ｂ...不是不是，我姓叶，叫 Ｂ哥葉。我是氷の鋭 同班同学，他教我学 Python 几个月了，前天我终于第一次在仅有师父提示的情况下自己写出了一个程序，耶！
原题是这样的：

一个六位数，分别用2，3，4，5，6乘它，得到的五个新数仍是由原数中的六个数字组成，只是位置不同，则此六位数是多少？

我把这题给做出来了！

def pcb(i):
　　if a(i)==a(i*2):
return pcb_3(i)

def pcb_3(i):
　　if a(i)==a(i*3):
　　　　return pcb_4(i)

def pcb_4(i):
　　if a(i)==a(i*4):
　　　　return pcb_5(i)

def pcb_5(i):
　　if a(i)==a(i*5):
　　　　return pcb_6(i)

def pcb_6(i):
　　if a(i)==a(i*6):
　　　　return i

def a(i):
　　c=b(i)
　　c.sort()
　　return c

def b(i):
　　return list(str(i))

# 这个原来我写的是错的，后来师父改滴——其实改滴也不好！
for i in range(100000,1000000):
　　if i and pcb(i):
　　　　print i
　　　　break

师父在学校那台破电脑上输代码滴时候抱怨说我的程序可以用程序写唠。这有什么关系，反正我的代码的速度超过师父的啦！

def list_equ (ls):
　　for cond in map(lambda x: ls[0] == x, ls):
　　　　if not cond:
　　　　　　return False
　　　　return True

def sort (ls):
　　ls.sort()
　　return ls

def test_num (num):
　　return list_equ(map(lambda x: reduce( \
　　　　lambda i,j: i+j, sort(list(str(x * num)))), range(2,7)))

def give_rst ():
　　return filter(test_num, range(100000,1000000))

for i in range(100000,100000):
　　if (test_num(i)):
　　　　　　print i

但是，最后师父使出了杀手锏，把这题用数学方法解出来唠，他个DB。。。
以后一定要超过他！

OOP 诡异教程（上）

• 本文分上、下两篇，站在一个难以名状的角度上研究了 JavaScript 语言中面向对象机制的起源、内涵和发展，带领读者从原始森林走向高楼大厦。文章作者 lichray 是个 ECMAScript 的狂热追随者，mozilla.org 邮件列表里的无名潜水员。
• 文章中使用了 Rhino 解释器，行开头有 "js>" 表示那是输入，输入下一行没有这个标记的表示解释器回馈消息。
• PS: 读懂本文需要对 JavaScript 闭包和逃逸变量有较深入的了解。

一. 对象和消息
考虑一下我们平常怎么说话的。我们叫某某人做某事，用下面的句式：
forest run!
其中"!"是语气的标志，对于编程语言来说是没有意义的，全部换成"."：
forrest run.
不知道如果我告诉大家上面这句话就是 Smalltalk 语言中一个合法语句大家会怎么想。好了，不谈这个。这样我们就得到了一种语法，"宾"谓结构：
ObjectVerb ::
　　Object Verb.
如果让它支持多个 Verb，比如
forrest run, jump, stop.
可以扩展成这样：
ObjectVerb ::
　　Object VerbList.
VerbList ::
　　Verb
　　Verb , VerbList
很明显，对于 JavaScript 来说，上面的 BNF 不可能和任何一个产生式匹配。问题出在哪儿？我们要帮 JavaScript 指定，谁是 Object，谁是 Verb。鉴于 Object 只有一个，Verb 有多个，我们可以用括号来区分它们，然后把最后那个句号去掉：
ObjectVerb ::
　　Object ( VerbList )
这样上面的那句话就变成了下面的形式：
forrest (run, jump, stop)
很像函数调用，是吧？不过还有一个问题，现在这些 Verb(s) 对于 JavaScript 来说是“裸词”（Perl 语），我们可以避开再去定义这些标识符，用字符串代替；最后再说明一下 Object 是什么：
forrest ('run', 'jump', 'stop')
那么现在我们第一个“模仿”自然语言的程序版本出现了，加上下面针对 JavaScript 的文法：
Object ::
　　Identifier
Verb ::
　　StringLiteral

二. 实现消息传递
有了文法，一切都好办。看得出来，我们下面的工作是定义能创建一个新 Object 的函数，函数中有一些动作，产生的新 Object 是一个能处理这些消息的函数。创建 Forrest Gump 的函数还可以创建 Tom，Mike 等等；他们都是 People：
function People () {
　　function run () {
　　　　print("I'm running!")
　　}
　　function jump () {
　　　　print("I'm jumping!")
　　}
　　function stop () {
　　　　print("I can't stop!")
　　}　　
　　return (function (verb) {
　　　　switch (verb) {
　　　　　　case 'run': run(); break
　　　　　　case 'jump': jump() ;break
　　　　　　case 'stop': stop() ;break
　　　　}
　　})
}
为了简单起见还可以把返回的那个函数写成这样：
　　　　(function (verb) {
　　　　　　eval(verb)();
　　　　}
　　})
Ok。现在我们来试一试这个智商低于 85 的 Forrest Gump 怎么样：
js> forrest = People()
js> forrest('run')
I'm running!
js> forrest('jump')
I'm jumping!
js> forrest('stop')
I can't stop!
事情就是这样。我们成功地创造了对象，还让他做动作、说话。
不过，这个实现并不是我们上文中最后一个文法所指出的。它不支持连续发送指令。改一改。要加入顺序执行指令的办法：
function People () {
　　function run () {
　　　　print("I'm running!")
　　}
　　function jump () {
　　　　print("I'm jumping!")
　　}
　　function stop () {
　　　　print("I can't stop!")
　　}
　　function _do_verbs_ (verblist) {
　　　　for (var i=0; i <> forrest = People()
js> forrest('jump','run','jump','stop')
I'm jumping!
I'm running!
I'm jumping!
I can't stop!

三. 利用消息传递处理状态
什么是状态？我们在进行面向对象编程时，把状态表示为对象的一组数据，我们称之为“属性(property)”。在我们的消息传递编程风格中，可以直接把这些数据堆到产生对象的那个函数中去。下面给 Forrest 加入一个状态，Forrest 口袋里的钱。先得声明原先有多少钱：
forrest = People(1000)
然后，我们希望可以执行这样的代码，让 forrest 支出 200 美元：
forrest('pay', 200)
但很明显，我们无法分清 200 是 Verb 还是 'pay' 所要求的数据。我们只得简化文法，只允许一次发送一个消息，以保全我们的脑细胞：
forrest('pay')(200)
也就是说，我们需要让 forrest('pay') 这一表达式返回一个能改变状态的函数，而不仅仅是调用函数来显示一句话。也就是说，如果我们想让 Forrest 急得跳起来，我们先得跳起来：
forrest('jump')()
新时代的 Forrest 实现如下（省略了一点多余的代码）：
function People (money) {
　　//var money = money
　　function pay (dollars) {
　　　　money -= dollars
　　}
　　function restMoney () {
　　　　return money
　　}
　　function run () {
　　　　print("I'm running!")
　　}
　　return (function (verb) {
　　　　return eval(verb)
　　})
}
试一下。先支出 200 美元，然后看看他还剩多少钱：
js> forrest=People(1000)
js> forrest('restMoney')()
1000
js> forrest('pay')(200)
js> forrest('restMoney')()
800
当然，我们的 Forrest 还可以赚钱。下面这个版本比较彻底地说明了消息传递编程风格的一切。可以直接修改钱之后，我们可以不需要在创建 Object 的时候就说明原有多少钱；当然，使用注释中的版本更自然：
function People (/* money */) {
　　var money = 0; // var money = money ? money : 0;
　　function setMoney (dollars) {
　　　　money = dollars
　　}
　　function addMoney (dollars) {
　　　　money += dollars
　　}
　　function pay (dollars) {
　　　　money -= dollars
　　}
　　function restMoney () {
　　　　return money
　　}
　　return (function (verb) {
　　　　return eval(verb)
　　})
}
试一下吧：
js> forrest = People()
js> forrest('addMoney')(1000)
js> forrest('restMoney')()
1000
js> forrest('pay')(200)
js> forrest('restMoney')()
800
上篇完。小结一下：消息传递的编程风格指的是，把函数 A 的执行上下文当作对象的数据环境，在此定义对象的动词（函数），然后从此上下文中返回一个可以接受、处理消息的函数（常为匿名）。用函数 A 产生消息处理器作为对象，向此对象传递参数作为消息，以此执行函数 A 环境中定义的动作，这些动作还可能改变所在上下文中用一组数据定义的对象状态。

(To be continue)

恶搞 qsort 测试代码

//Array类的交换和判断是否有序的方法
Array.prototype.swap = function (a, b) {
var tmp = this[a];
this[a] = this[b];
this[b] = tmp;
}

Array.prototype.isInOrder = function () {
for (var i =0; i <> this[i+1]) return false;
return true;
}

//简短的快速排序，只需一个数组作参数
function qsort (arr, l, u) {
l = l || 0;
u = ((u != 0) &&amp; (u == undefined)) ? arr.length : u;
if (l >= u) return;
var m = l;
for (var i = l+1; i <= u; i++)
if (arr[i] < arr[l])
arr.swap(++m, i);
arr.swap(l, m);
qsort(arr, l, m-1);
qsort(arr, m+1, u);
}

Math.rand = function (start, end) {
if (end == undefined) {
end = start;
start = 0;
}
return start+Math.random()*(end-start);
}

Math.randInt = function (start, end) {
return Math.round(Math.rand(start, end));
}

//生成待排序的大规模随机整数数组
function randRange (len, start, end) {
var range = new Array(len);
for (var i = 0; i < len; i++)
range[i] = Math.randInt(start, end);
return range;
}

//把测试代码绑定在qsort()函数上
qsort.test = function (len, start, end) {
var tmpArr = randRange(len, start, end);
this(tmpArr);
return tmpArr.isInOrder();
}

PS: 我一个同学在电脑课上用Firefox玩randRange(10000)之类的东西玩了半节课……

Scheme数据结构——向量也疯狂

学过数据结构的人都知道，一棵完全二叉树（除去最低层元素从左到右排列，其它的层都为满的）可以保存在一个数组中 这个完全二叉树存储在vector中就像这样：#(4 6 2 8 7 3) 可以看出一个结点下标 i 与它的左右孩子结点下标 j1，j2具有如下关系： j2 = 2*i+1，j2 = 2*i +2 然后，我们通过调整数组上结点的排列，把它变成一个“二叉堆”。这里显示的是一个最大堆，即：对于(vector-length a) => n，当(< (+ (* 2 i) 1) n) => #t时，有(> (vector-ref a (+ (* 2 i) 1)) (vector-ref a i) => #t；当(< (+ (* 2 i) 2) n) => #t时，有(> (vector-ref a (+ (* 2 i) 2)) (vector-ref a i) => #t。
这么复杂的S-exp，说白了，就是每个结点的左右孩子结点（如果有的话）都小于这个结点。 知道了这些，我们就可以来考虑一下怎么把完全二叉树转成最大堆了。方法是，先根据公式求出第一个非叶结点下标(define n (/ (- n 1) 2))，然后比较左孩子结点(vector-ref a (+ (* 2 i)与右孩子结点(vector-ref a (+ (* 2 i)的大小，将较大者与(vector-ref a i)比较，如果更大就互换。然后对于(- i 1)，(- i 2)完成以上步骤，于是，最大堆就构造完成了。

• 调整结点8：
  

• 调整结点3：

• 调整结点8：最后，最大堆有什么用呢？废话，当然是堆排序了；我最喜欢的排序算法就是它，因为它充分体现了“数形结合”的思想。 因为排序过程中整个堆都在大规模地变化（当然反应到数组上不是这么回事），所有就不再进行图解了；大致将一下即可：先将整个vector调整为最大堆，然后将堆顶的那个最大的元素与堆中最后一个元素互换，接着调整前 (- n 1) 个元素为最大堆，再将堆顶元素与堆中最后一个元素互换。。。如此反复（其实就是逐个排出最大元素），时间复杂度为O(n*log2 n)。

大致代码（缺少heep的实现）：
(define (heep-sort a)
(let* ((n (vector-length a))(tmp 0) (i (- n 1)))
(begin (make-heep a) ;调整a为最大堆
(when (> i 0)(set! tmp (vector-ref a 0))
(vector-set! a 0 (vector-ref a 1))
(vector-set! a 1 tmp)
(heep a i 0) ;在向量a上从下标0开始调整长度为i的一段为最大堆
(set! i (- i 1)))))) ;最好用尾递归代替循环

Scheme数据结构——list数组

（By the way，我终于知道如何删除list的头节点了。必须要使符号指向一个头节点，再由它确定当前节点，否则无非实现元素“脱链”）

list数组，顾名思义，由list构成的数组（或矩阵），学名不明。它不是一种具体的数据结构，但常被用作表示其它数据结构。它的一般形式如下：
当然，这里的vector也可以是一个矩阵。用Scheme实现时，注意list不需要随机插入元素的功能，但能随机脱链，且只能从尾部插入（技巧：(set-cdr! (list-tail l (- (length l) 1)) obj)）——list中的数据往往是无序的。可以把它设计得更强，但并不实用。
下面讲它的两种典型应用。

一. 图的邻接表存储结构

• 用矩阵的第一列存储结点，第二列存储结点的号码，第三列保存此行所对应结点链接的边的结束结点号码（当然还可以再用一列保存权值）。这样说有点绕人，我们看个例子好了：
• 这是一个有向图。让我们看看它是怎样用邻接表存储的：
• 复杂吗？吓，一点也不。它可以用来对付边较稀疏的有向图。

二. 链表法解决哈希冲突

• 讲解哈希表关键字冲突的一般思路是建立哈希函数组，逐个调用。但这个方法有个明显缺点：如果把哈希表作为一种服务提供给操作对象的话用户就麻烦大了。用向量上链接的list来保存hash code相同的元素是个不错的办法。
• 例子：这个哈希表的元素是 a={16, 54, 66, 43, 29, 55...}，m=13，哈希函数为 h(K)=K mod m（省略了其它7个元素）：
• 用矩阵的第一列存储基本元素，多于的“同位素”保存在临时开辟的list中。这样的设计重点考虑了效率，比较使用，但会给元素的删除带精神分裂般的麻烦，插入元素也够戗；如果你追求程序的“漂亮”，可以把所有元都平起平坐地存储在list里，不使用矩阵，元素的删除操作全是脱链。

从上面两个例子可以看出，list数组主要用于解决稀疏的“同位素”的存储问题。确定“同位素”的同位存储性质（比如同hash code元素的平等地位）和必要性（比如有向图结点拥有边与其起始结点的偏序关系），是使用它的重要前提。

Scheme数据结构——简单二叉树

终于把用Scheme写的二叉树发出来了，前两天网卡没钱拉。
层序例遍算法写出来了，可惜用不了——没法儿用Scheme实现队列！我折腾了半天，写出这么一个怪物：
(define queue list)
(define (queue-push! q o)
(set-cdr! (list-tail q (- (length q) 1)) (cons o null)))

可pop还是实现不了——不知道怎么删除pair，于是放弃。
把简单二叉树的实现贴在这儿吧，虽然没有一点实用价值。

(define null '()) ;用null代替空list

(define (child data left right) ;用它来申明一个“孩子”
(cons data (cons left right)))
(define (child? o)
(and (pair? o) (pair? (cdr o))))
(define (child.data o)
(if (child? o)
(car o)))
(define (set-child.data! o data)
(if (child? o)
(set-car! o data)))
(define (child.left o)
(if (child? o)
(cadr o)))
(define (set-child.left! o p)
(if (child? o)
(set-car! (cdr o)) p))
(define (child.right o)
(if (child? o)
(cddr o)))
(define (set-child.right! o p)
(if (child? o)
(set-cdr! (cdr o) p)))

;先序例遍递归版，用一句(if (not (null? o)...)省了不少判断
(define (child-tree-pre o func)
(if (not (null? o))
(begin
(func (child.data o))
(child-tree-pre (child.left o) func)
(child-tree-pre (child.right o) func))))
;后序例遍
(define (child-tree-post o func)
(if (not (null? o))
(begin
(child-tree-post (child.left o) func)
(child-tree-post (child.right o) func)
(func (child.data o)))))
;。。。中序~~可怜没有层序和分步例遍~~
(define (child-tree-mid o func)
(if (not (null? o))
(begin
(child-tree-mid (child.left o) func)
(func (child.data o))
(child-tree-mid (child.right o) func))))

Scheme数据结构——神奇的pair

Scheme中提供了两种可以存储泛型数据的数据结构——list和vector。list其实是一个链表，它是由pair实现的。学了Scheme很久才发现，原来pair其实是其它语言中我们超常用的Node（节点）！这下我总算理解了Scheme是怎样架起数据结构的了。

一. 链表（内部已实现）

• 每个pair的左值存储数据，右值存放指针（Scheme中cons值即引用）：
• 然后用指针指向（其实是赋值）下一个pair，链中最后一个为null（空值）：
• 这个语法树转换成Scheme代码就是(value . (value . (value . null)));当然只是“意思”一下，实际不可能有同名符号。

二. 二叉树（正在编写中…）

• 又一个用节点连起来的基本数据结构。每个二叉树child（孩子）可以这样设计，用第一个pair的左值保存数据，右值为另一个pair，它的左右值表示孩子的指针：
• 代码为(value . (left . right))
  
• 然后，n个这样的child组合为一棵二叉树。同样，没有孩子时指针为null：

• 上面这棵树的代码大致是这样：(value . ((value . ((value . (null . null)) . (value . (null . null)))) . (value . (null . null))))。
• 我的二叉树实现正在写着，面前至少可以用(child)代替(cons(cons))申明孩子节点，下一步编写tree的整个数据结构支持，最好能支持一次例遍。

有了链表和二叉树，队列，栈，线索二叉树之类就都能直接实现了。其它的数据结构如集合，树，图，HashTable等等多是由向量＋pair构成的，不典型，暂且不提。

谈谈数组元素左旋问题（下）

上篇中 ，我给出了一些解决数组元素左移问题的不符合要求或很慢的解法。在下篇中，我将讲解3个很有“来头”（至少出现在《编程珠玑》里了:)）的O(n)级算法。
第一个算法思想上和我曾经想到的一个直接插入元素的算法基本相同，也是通过递归地逐个放置数组元素来左旋数组的。只不过我使用的方法是逐个临时测试是否可以按照公式放置，而这个算法经过周密计算，直接给出了符合各种情况的通用下标计算方法：
对于任意的元素下标 i，它的新下标 i` = ((k - m) + i ) % k。
代码如下：

//先求最大公约数，其实有很多方法，这个叫“辗转相除法”
int facter (int i, int j) {
while (i != j) {
if (i > j) {
i -=j;
} else {
j -= i;
}
}
return i;
}
//元素互换函数，无聊。。。
void swap (int *n1, int *n2) {
int tmp;
tmp = *n1;
*n1 = *n2;
*n2 = *tmp;
}
void turn_left (int *a, int m, int k) {
int i, tmp, f;
k = k % m;
if (k == 0) {
return;
}
f = facter(m, k);
if (f == 1) {
i = 0;
do {
i = (i+k)%m;
swap(a, a+1);
} while (i != 0);
} else {
for (i = 0; i < tmp =" i;" tmp =" (tmp+k)%m;" href="http://lichray.blogspot.com/2006/09/blog-post_25.html">那篇文章中用图示详细分析了数组元素的位移过程。如果你想找到一点新的灵感，可以把一些代表元素的卡片（凯库勒？！）用线穿起来反复地排，看看开始时和结束时，数组产生了哪些变化：
似乎看不出什么端倪。。。但如果把每种颜色的线都反序一下，
呵，很漂亮啊。再分析一下——原来，要让数组元素左旋m位，只需先将数组全部反序，然后将下标0~m-1和m~k-1的两部分分别反序就行了！最快的算法居然就这么简单！
用Python表示一下（这个代码是可运行的）：

def turn_left (a, m):
a.reverse()
a[:m].reverse()
a[m:].reverse()
return

C代码就不用写了吧，用上面那个swap()函数＋循环将数组反序而已啊。
最后一个方法，说真的，我没看懂。。。据说利用了数论知识，也很快，原理和本文第一个其实区别不大，只是计算新下标的算法更先进了：

/*照抄编程珠玑，伪代码（汗~），懒得翻译。n是数组长度，r是左旋位数，gcd()函数计算最大公约数，for后面的式子表示i的取值范围。*/
for i = [0, gcd(r, n))
t = x[i]
j = i
loop
k = j + r
if k >= i
k -= n
if k == i
break
x[j] = x[k]
j = k
x[j] = t

还得好好学数学啊！理解这个会有时！
真希望所有的程序员（代码书写er就算了）人手一本《编程珠玑》（Programming Pearls），书中自有黄金物，早日摆脱索然无趣的代码！

极度经典的二分法搜索

很easy。闲着无聊写出来。建议背下来。

#define datatype
#define ERROR -1

int bsearch (datatype * arr, int n, datatype obj) {
int l = 0;
int u = n-1;
int m;
while (l <= u) {
m = (l+u)/2;
if (arr[m] <>
l = m+1;
} else if (arr[m] == obj) {
return m;
} else {
u = m-1;
}
}
return ERROR;
}
这么简单注释就免了吧，哈哈~~

谈谈数组元素左旋问题（上）

终于把《编程珠玑》那本书给买来了。第一章2.3提出了一个“数组元素左旋问题”，《程序员》杂志上出过，描述如下：
对于有K个元素的数组int a[K] = {...}，写一个高效算法将数组内容循环左移m位。比如：int a[6] = {1,2,3,4,5,6}循环左移3位结果是{4,5,6,1,2,3}。注：不允许返回其它内存空间，但可使用少许变量。
《程序员》上面给的解答抄自书后答案，网友给出的两次倒排算法抄自书上解法1~~晕死。
对于这个问题有已经有不少解决办法了。我上个星期教网友算法时讲到了这个问题，现在把这些算法整理出来罢。
先将一个不符合要求但很基本的想法：先在数组后扩充数组的前一部分，然后再删掉数组自己的前一部分。用Python表示一下：
def move(a,m):
a.extend(a[:m])
return a[m:]
这个算法用C来实现我用了溢出的方法获得了更多内存（没必要管它能否通过编译），然后直接返回一个假的数组首地址。
int * move (int *a, int k, int m){
for (int i = 0; i <>
*(a+k+i) = *(a+i);
}
return (a+m-1);
}
很甩是不是？太猥琐了（但它说明了一个问题：大家都赞扬动态语言灵活，其实C也很灵活）。
更合适一点的做法是用一个线形数据结构保存前半部，再将原数组左移，最后将前半部分加回去。用Python表示一下（其实和上面那个也没多大区别）：
def move (a, m):
j = i = 0
tmp = []
while i <>
tmp[i] = a[i]
a[i] = a[i+m]
i += 1
while j <>
a[j+m] = tmp[j]
i += 1
return a #其实数组已改变，这句可以不要
后悔了——实在是没有比这更别扭的Python代码了~~改成C就免了吧，初始化tmp是把长度设为m，编译时要加这个参数：-std=c99（gcc）。
好了，我就不再无聊了，开始讲点正经的吧：在原数组上操作。
先回忆一下冒泡排序法：当处理一个处在最左边但又是最大的项时，这个项是怎样移动的？
在纸上画一画——哦，它和每个元素交换，然后到了最右边……等等，呓？其它的项的顺序都没有变？！整个数组左移了！
那么，我们第一个符合要求的答案就出来了：把数组当成是反排序的，从最左边进行m次冒泡即可！
吸取教训，我还是写C代码吧：
int * move (int a[], int k, iny m) {
for (int j = 0, j <>
for (int i = 0; i <>
int tmp = a[i+1];
a[i+1] = a[i];
a[i] = tmp;
}
} //算了，不写返回语句了
}
嗯，两层循环，照书上的说法这个算法的时间复杂度应当是O(n2)——但是，那个m好像不足k吧？可以认为是O(n*m)，但这样说是不严密的，因为O()仅处理上界情况。
好了，不多罗嗦了，下篇将揭晓真正有效率的算法——3个都是O(n)级的。

递归算法入门-pascal（转）

程序调用自身的编程技巧称为递归（ recursion）。
　　一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
　　 注意：
　　 (1) 递归就是在过程或函数里调用自身;
　　 (2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

　　一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山， ……。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。

　　反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。

阶乘的算法可以定义成函数

当 n>0时，用 f(n-1)来定义 f(n)，用 f(n-1-1)来定义 f(n-1)……，这是对递归形式的描述。

当 n=0时， f(n)=1，这是递归结束的条件。

例：用递归策略求N!的解。
　　　 N!=1*2*3*...*N
　　 分析：
　　　 (1) 不运用递归的解法
　　　 (2) 运用递归策略
　　　　　 N!=1*2*3*...*N
　　　　　　 =[1*2*3*...*(N-1)]*N
　　　 (N-1)!=1*2*3*...*(N-1)
　　　 设 f(N)=N!
　　　 那么 f(N-1)=(N-1)!
　　　 则 f(N)=f(N-1)*N
　　　 这就是递归式子，由于式子中有N-1，所以N>=1，递归出口的条件是N=1时。
　　 函数模式：
　　　 function f(n:integer):longint;
　　　 var
　　　　 ...
　　　 begin
　　　　 if 递归出口的时候 then
　　　　　　 f:=1
　　　　 else
　　　　　　 f:=f(n-1)*n;
　　　　 end;

递归算法一般用于解决三类问题：

⑴. 数据的定义形式是按递归定义的。

比如阶乘的定义。

例 1　又如裴波那契数列的定义： f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2

对应的递归程序为：

var n:integer;
function f(n:integer):longint;
begin
case n of
0:f:=1; { 递归结束条件 }
1:f:=2;
else
f:=f(n-1)+f(n-2) 　　｛递归调用｝
end
end;
begin
readln(n);
writeln(f(n))
end.

这类递归问题往往又可转化成递推算法，递归边界作为递推的边界条件。

⑵. 问题解法按递归算法实现。例如回溯等。

⑶. 数据的结构形式是按递归定义的。如树的遍历 , 图的搜索等。

递归解决实际问题的例子很多，如经典的梵塔问题。

例 2　梵塔问题：有 n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在 A柱上，另外还有 B、 C两根空柱。要求将 A柱上的 n个圆盘全部搬到 C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。

在移动盘子的过程当中发现要搬动 n个盘子，必须先将 n-1个盘子从 A柱搬到 B柱去，再将 A柱上的最后一个盘子搬到 C柱，最后从 B柱上将 n-1个盘子搬到 C柱去。搬动 n个盘子和搬动 n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。

程序如下：

var a,b,c,number:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'->',c)
else
begin
move(n-1,a,c,b);
writeln(a,'->',c);
move(n-1,b,a,c)
end;
end;
begin
write('the number of dish:');
readln(number);
move(number,1,2,3);
readln
end.

自然数的拆分，数字的拆分等都可以用到递归算法。

例 3　要求找出具有下列性质的数的个数 (包含输入的自然数 n)：

先输入一个自然数 n(n<=500),然后对此自然数按照如下方法进行处理 : ①. 不作任何处理 ; ②. 在它的左边加上一个自然数 ,但该自然数不能超过原数的一半 ; ③. 加上数后 ,继续按此规则进行处理 ,直到不能再加自然数为止 . 样例 : 输入 : 6 满足条件的数为 6 16 26 126 36 136 输出 : 6 这道题只需求出满足条件的数的个数，在 n值不大的情况下用递归求解比较方便，因为它本身题目的条件就是递归定义的。 递归的样例程序如下： var n,i:integer; s:real; procedure qiu(x:integer); var k:integer; begin if x<>0 then
begin
s:=s+1;
for k:=1 to x div 2 do qiu(k)
end
end;
begin
readln(n);
s:=0;
qiu(n);
writeln(s:2:0)
end.

递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。



[习题] 用递归完成：
1、如下图，打印0－N的所有路径(0=〈N〈=9)：
　 1―> 3―> 5―> 7―> 9
　 ^　　 ^　　 ^　 ^　　 ^
　 |　　 |　　 |　　 | 　　 |
　 0―> 2―> 4―> 6―> 8
(说明：图中须加上0－>3，2－>5，4－>7，6－>9的连线)
2、打印杨辉三角。
3.用递归的算法把数组中的N个数按颠倒的次序重新存放。
4. 用递归算法完成：有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第一张要翻的牌超过52为止。统计最后有几张牌正面朝上，以及它们的位置号。