此Blog已停止更新

因为www.blogger.com技术水平有限，本博客已停止更新，新博客见
lichray.blogspot.com
新博客将成为lichray的全方位日志，已经建立完成。但以前发表在本博客上的文章不会随之移动，下面是其中一部分自觉优秀的原创文章列表：

• Scheme语言

1. 古老，但很神奇
2. 数据结构——神奇的pair
3. 数据结构——简单二叉树
4. 数据结构——list数组
5. 数据结构——向量也疯狂

• C语言

1. 数组左旋问题（上）
2. 数组左旋问题（下）
3. 一个新想法
4. 线性复杂度的菲波那契函数

• Python语言

1. 称球问题
2. 称球问题（代码）

• Lua语言

1. 排列组合算法（问题）
2. List类接口

• 软件工程

1. 上帝是个程序员
   

献给新访客的一则笑话——古老，但很神奇

• 诶，我的Blog已经很久没更新了——得菌痢住院5天啦，今天终于出来啦！
  
• Lava-Lava平台上“科技自主创新网”部落的同仁们可能已经看到了我的Blog荣幸进入你们的“酋长推荐”标签页，但似乎没有人给我的文章留下评论。我估计这是大家都没有接触过Scheme语言的缘故。所以我决定写一篇这样的文章，让新来的访客们看一看Scheme时间的精彩——当然，我没有要贬低其它语言（除了Java）的意思，事实上我最喜欢的语言之一就是C。好了，不罗嗦了，让我们一起来推开Scheme那道门吧。

人物：XX大学计算机系的社友Go4——8呆，F1，老农和小四。
时间：“晚汇报”时间…
（老农在计算机系混的时间不短了，可惜技术一直没长进——连打电脑游戏都“不上档次”（小四语）。这不，昨天打CS又被F1欺负了，现在正郁闷着呢。）

老农（上网无聊中）：这年头，电脑好的人就是吃香啊~~（旁白）俺编程也差，游戏也差，废啦~~有了，上CSDN.net，找点文章进修一下。
F1：老农，怎么样，CS技术不行啊！好好练啊！
小四（推推眼镜）：老农伯伯！算了吧，我看你还是把编程学学好吧，哈哈，你那本《数据结构》好像还是新的吧？
（老农翻着最新的Blog文章，忽然眼睛一亮。）
小四：嘿，发现什么了？
老农（连忙把Firefox最小化）：没什么，又不是黄网激动什么？！
老农（旁白）：不错，就用这篇文章K.O.他们。
老农（满脸堆笑）：嘿，你们仨过来，我在网上发现一道数据结构方面的面试题目，想不想试试？
（正在上铺捧着SICP发呆的8呆忽然从发呆状态切换到亢奋状态，人啊~~）
8呆：废话，快说！
老农（奸笑中）：设计一个函数visit_tail，要求通过一次遍历找到链表中倒数第n个节点，然后从它开始用函数func例遍后面的所有链表元素，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。还有，不需要给出链表的其它操作函数。
8呆（再次切换回发呆状态）：无聊…这也能叫题目…
老农（怒）：那你做啊！
（8呆在他的SICP上写了点什么，然后很潇洒地离开了寝室）
老农（专向另两个人）：既然他不参加，那我们三个比吧。
小四、F1（信心实足）：那现在开始计时吧。
……
（老农把刚才背下来的代码改了改，花了3分钟抄在终端里）
老农（觉得时机移到）：我好了，你们呢？
小四（大喊）：解决解决！
F1：恩，我也好了，只是还没做单元测试。
（老农、小四：寒~~）
（3个人凑在老农的电脑上开始比拼）
老农：你们看，我是用C写的，已经测试过的，思想是，用两根指针，第一根先出发，相距n步后第二根出发。然后同时步进，直到第一根指针达到末尾，然后用func()函数对第二个指针开始的子链表进行例遍。
（小四和F1仔细一看，大笑不止。老农的代码如下（注释是笔者所加，其实是F1和小四看到各句时的反应）：）

typedef struct{ //哟，终于不用struct Node了，
int data;
Node * next;
} Node;
Node * visit_tail(iNode * head,int n,void (* func)(int cur)){ //K&R时代的函数指针，见到老佛爷啦！！

Node *pfirst; //吓，终于用到匈牙利命名法了（老农：寒~）
Node *psecond;

pfirst=head;

for(int i=0;inext;
}
psecond=head;
while(pfirst!=NULL) {
pfirst=pfirst->next;
psecond=psecond->next;
} //什么破编程风格，真实版初学者啊
for(int i=0;idata)
psecond=psecond->next;
}
} //靠，一个函数解决所有问题，高耦合啊！

老农（再怒）：小四少罗嗦！你的呢！
小四：在这儿，好好学学吧！
（大家一看，小四也用了C，但…好漂亮啊。代码如下（注释是小四的解释）：）

typedef int int
//没有C++一样“泛型”！
typedef struct {
T data;
Node * next;
} Node;

typedef struct {
Node * pre;
Node * curr; //当前结点与List绑定，不但可以分步例遍，还能保证正确初始化
} List;

void init_curr (List * l) {
l->curr = l->pre; //什么叫“编程风格”，知道不？！
}

void visit (List *l, void (* func)(T data)) {
while (l-curr) { //少用!=NULL
(* func)(l-curr->data);
l-curr = l->curr->next;
}
} //使用内联结点的公用访问函数，降低耦合

void index (List * l, int n) {
if (n) return NULL; //结点下标从1开始
init_curr(l);
if (n > 0) {
for (int i = 0; i <>curr = l->curr->next;
} //小四（自我陶醉）：漂亮啊
if (n < n =" -n;" tmp =" l-">curr;
for (int i = 0; i < tmp =" tmp-">next;
}
while (tmp) {
l->curr = l->curr->next;
tmp = tmp->next;
}
}
return l->curr; //方便用户，增强鲁棒性能
}

void visit_tail (List * l, int n, void (* func)(T data)) {
index(l, -n);
visit(l, func);
} //多清爽

老农（倒）：我的挽回面子计划就这么，完了…
小四（偷笑）：你还是面对现实吧…
F1：小四你先别得意，我的你们还没拜读过呢！
（大家跑到F1电脑前一看，先是被长度吓了一跳，然后，无语。）

package datastruct.fifi.com.baidu.hi; //加入我的数据结构Java包

//当然只有包内成员才能创建Node对象
protected class Node {
private Object data; //多态性，让你们的typedef去死吧！
private Node next;

//构造函数
Node (data) {
this.data = data;
}

//获取下一个元素
public Node next () {
return this.next;
}

//变换下一个元素，用户不能调用
protected void setNext (o) {
this.next = o;
}

//取数据
public Object getData () {
return this.data;
}

//换数据
public void setData (data) {
this.data = data;
}

//根据Effective Java的最高指导，要重写toString()方法
public String toString () {
return this.data.toString();
}

//自定义异常类，数据结构下标越界
public class IndexOutOfRangeException extend IndexOutOfBoundsException {
public IndexOutOfRangeException (int lower, int upper, int index) {
super("Lower: " + lower +", Upper: " + upper + ", index: " + index);
}
}

//用于被继承的访问类
public class Visitor {
public operation (Object o) { //访问操作
System.out.println(o);
}

public class List {
private Node preFix;
private Node current;
private int size;

List () {
current = preFix = new Node();
size = 0;
}

//自定义异常类，数据结构下标越界
public class IndexOutOfRangeException extend IndexOutOfBoundsException {
public IndexOutOfRangeException (int lower, int upper, int index) {
super("Lower: " + lower +", Upper: " + upper + ", index: " + index);
}
}

//用于被继承的访问类
public class Visitor {
public operation (Object o) { //访问操作
System.out.println(o);
}
}

public class List {
private Node preFix;
private Node current;
private int size;

List () {
current = preFix = new Node();
size = 0;
}

//定位函数
private void index (int i) throws IndexOutOfRangeException {
if (i > size || i < -size-1) { thows new IndexOutOfRangeException(0, size+1, i); } this.init(); if (i >= 0) {
for (int j=0; j < current =" current.next();" i =" -" j="0;" current =" current.next();" current =" current.next();">_< 。。。 F1：we得意。 （3人正在争执着，忽然门“吱”的一声（什么破门）开了，8呆走了进来。） 8呆：吵什么呢，比完了没？我是第一吧？ F1、小四、老农：什么啊，你不是自顾自走了啦？！ 8呆（诧异）：我走之前已经写好啦。 （8呆拿来他的SICP，只见上面写了一行Scheme代码：） (define (list-visit-tail l n func) (for-each (list-tail l n) func)) （编辑公曰：上面这段Scheme代码滴意思斯酱紫滴：先定义一个名为list-visit-tail的过程，然后用内置宏list-tail取list的后n位组成list返回，再用操作for-each进行例遍。） （完） 结语： 这个题目其实对于任何函数式编程语言来说都是一两句话。Scheme、Haskell它们都来自于世界上第二古老的语言Lisp，但它们的思想博大精深——基于lambda演算理论的函数式编程，古老，但很神奇。 参考资料：

• 老农说的“这篇文章”：一次遍历找链表倒数第n个节点
• 8呆的书SICP：Structure and Interpretation of Computer Programs
• 命令式语言的劣势：为何 Java（以及很多其他编程语言）令人不爽
• 函数式语言的优势：为什么函数式编程至关重要？
• Scheme入门推荐书：Teach Yourself Scheme in Fixnum Days
• 如果你还没学过编程的话：How to Design Programs
• 其它有关Scheme的东东详见：我的Scheme学习笔记(1 2 3 4 5)
  

上帝是个程序员——从《黑客帝国》看软件设计

上个星期我把《黑客帝国(The Matrix)》三步曲完完整整看了一遍，联想到《UNIX程序设计的艺术》一书中所说的17条UNIX哲学，深感古老的UNIX确实是软件设计思想的集中体现。Robert Metaclf说过：“如果将来有什么技术取代了以太网，那么它仍会叫以太网。”也许，The Matrix的内部开发代号中就有"UNIX"这个单词吧！

1. 模块性原则：写简单的，通过干净的接口可被连接的部件。相比UNIX，The Matrix绝对是一个超巨大的软件，它的设计中也充分体现了模块化思想：整个系统有后台数据库（这可是墨菲斯说的）用来存储任何物件；前台有和人脑后插座相连的输入/输出接口，当然程序还可以使用电话工作；前后台之间有由知情者们组成的控制程序，标准的MVC模式。
2. 清楚原则：清楚要比小聪明好。The Matrix的源代码我们是没法儿研究啦。不过，整个人类世界居然能被显示在3个小小的液晶屏里，而且接线员告诉我们…他能…知道这儿有个金发美女，从这一点你应该能想像出The Matrix有多么的清晰。
3. 合并原则：设计能被其它程序连接的程序。这个还用的着多罗嗦吗？天哪，与人类的物理接口，用手机可以和真实世界交流，通过固定电话进行接入和切断，还有那个设计近乎完美的、和外界传输意识的火车站，真是一应俱全
4. 分离原则：从机制分离从策略，从实现分离出接口。The Matrix的实现相当复杂，但设计了很好的接口；看看墨菲斯他们使用的训练场吧，它其实是早期The Matrix版本的一个变型，程序员能很轻松地控制它（最拉风的是第一部中凭空制造的那两排枪，无敌了）这说明了The Matrix的接口设计非常简洁而有序。
5. 简单原则：设计要简单；只有当你需要的时候，增加复杂性。The Matrix的简单恐怕初看电影的人体会不深：看这那些标志性的绿色字符就烦。但你仔细想想，这可是一个时间啊！从接线员的一些操作细节也能感受到The Matrix的简单——火线教学只需要搜索内容然后按下LOAD按钮，我晕。
6. 节俭原则：只有当被证实是清晰，其它什么也不做的时候，才写大的程序。The Matrix的的在节俭上下的功夫我们很难研究，毕竟这只存在于源代码中。个人感觉，至少从电影上看是非常华丽的，不过那是为了票房而下的功夫。
7. 透明原则：为使检查和调试明显更容易而设计。The Matrix的调试只提供了输出部分（安全的需要吗，设计师本人是不能搬演上帝的），在每艘飞船上都有一个GUI程序来检索它的调试信息，黑客们用它作了GIS，哈哈。
8. 健壮性原则：健壮性是透明和简单的追随者。没有一个软件没有Bugs，但有的软件可以让Bug在关键时刻失去用武之地，比如那个火车站，即便是尼奥这样的超人也无能为力啊，只能从这个出口跑会另一个出口啊。
9. 表现原则：把知识整理成资料，于是程序逻辑能变得易理解和精力充沛的。不知道设计师是怎样开发The Matrix的，不过从它那5个前世可以看出它的进步是卓有成效的。犯错误不要紧，把经验记下来是最重要的，不是吗？
10. 最小意外原则：在接口设计中，总是做最小意外事情。当然The Matrix也有让人超意外的时候，比如莫罗恩手下那些打不死的程序们。但别忘了他们来自于黑客帝国的早期版本。后来的莫罗恩自己和开锁人不都是普通人吗？
11. 沉默原则：当一个程序令人吃惊什么也不说的时候，他应该就是什么也不说。《UNIX程序设计的艺术》的作者对这个原则的解释有问题（或者是翻译问题）。沉默原则应当是这样：当一个程序按照用户已有的知识完成了工作是，他应该什么也不说。UNIX命令行的程序通通是这样，尤其是gcc。The Matrix是不是为一群人按照自己的意志控制另一群人而设计的，也不存在除维护人员以外的用户，当然不会“说”什么。
12. 修补补救：当你必须失败的时候，尽可能快的吵闹地失败。这也就是The Matrix中偶尔出现的幻象、上帝、狼人的出现了就很快消失的原因。
13. 经济原则：程序员的时间是宝贵的；优先机器时间节约它。无语了，The Matrix工作的硬件系统都是算法设计复杂度度量是使用的“理想计算机”，感觉起来一切都是原子操作，只有与人传输数据时有忽略不计的延迟。
14. 产生原则：避免手工堆砌；当你可能的时候，编写可以写程序的程序。这个原则的前提是，系统本身必须是可以被自描述的，就像Lisp语言。The Matrix也是被高度自描述的，那些维护程序不都是用The Matrix本身创建的吗即便是莫罗恩或史密斯这样的大拿？利用系统本身工作可是黑客帝国的一大特色啊。
15. 优化原则：在雕琢之前先有原型；在你优化它之前，先让他可以运行。这就是The Matrix有6个版本的原因——事实上人们讨论的最多的第一个版本就是一个原型，设计师自己也说，仅仅用作测试，后来“庄稼全死了”。
16. 差异原则：怀疑所有声称的“唯一真理“。最后这个The Matrix版本有它的“唯一真理”，可惜设计师在努力之后仍然留下了尼奥这个“余数bug”。设计师是绝对的马克思主义者，也只有在他的眼中，世界是物质的。
17. 可扩展原则：为将来做设计，因为它可能比你认为来的要快。The Matrix的可扩展能力具体有多强我们不得而知，不过在电影中它确实被扩展了：希安的程序员们为他们的训练场程序编写了原本不存在的应急保护模块，能让可能损坏人体的元素失去真实（什么是真实？）质地，否则尼奥第一次“跳楼”就要被摔死了。:)

《黑客帝国》绝对是一部不看人生不完整的电影，不但充满了哲理，而且对于UNIX/Linux的爱好者们而言很有感召力，不是吗？:)

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元素的平等地位）和必要性（比如有向图结点拥有边与其起始结点的偏序关系），是使用它的重要前提。

let, let* 和 letrec（转）

使用 let, let*, letrec 都可以在当前环境中构造局部变量。这种 变量的生命会延续到这个环境消失为止。

这就像 C 语言里的

{  int x = 10;
int y = 20;

foo(x,y);
}

但是有一点不同就是，Scheme 的 let 生成的环境是分配在堆里而不 是像 C 那样分配在栈里的。所以 let 的局部变量有可能在 let 的 block 执行完毕以后还继续存在，只要有某些东西引用到它们。

这样我们可以制造一些返回函数的函数，这些函数拥有自己的状态记 忆，而这些记忆并不是全局变量，它们有点像 C 函数的 static 变 量。

下面是几个例子：

(define (function-gen n)
(let ((local-var 0))
 (lambda ()
   (display "The local-var is ")
   (display local-var)
   (newline)
   (set! local-var (+ 1 local-var)))))

(define f1 (function-gen 0))
(define f2 (function-gen 100))

(f1)
(f2)

函数 function-gen 接受一个参数 n，并且把它保存到自己的局部变 量 local-var. 它返回一个新的函数，这个函数被调用就会打印 local-var 的值，并且把 local-var 的值加 1.

我们用 0 和 100 作为参数传递给 function-gen，生成了两个函数 f1 和 f2. 这是两个起点不同的计数器。f1 从 0 开始，而 f2 从 100 开始。每次被调用两个函数都打印自己的数字，并且加 1.

可见，f1 和 f2 所见到的 local-var 是两个不同的空间。也就是说， 每次调用 function-gen，都会由 let 生成一个新的变量 local-var, 这个变量将一直伴随新生成的函数。

注意 let 里的 binding 是这样产生的。首先，进入 let 时，我们 只看到外层的绑定，然后每个 let 绑定的右边被 eval，然后这些值 被放到临时的一些空间，所有的右边都求值完毕后，这些值被一一赋 给左边的名字。

如果我们的代码不是那么简单，我们在 let 里生成了一个函数。比 如这样：

(define (func-gen)
(let ((x 10) (y 20))
 (lambda (a b)
       (+ x y a b))))

(define bar (func-gen))

func-gen 函数中被调用时，它在 let 空间中生成了一个函数，并且 作为 func-gen 的返回值送到外层，它被绑定到最外层的环境中的 bar 变量。那么这个函数引用了这个环境，这个 let frame 不会被 回收。

bar 如果在外层层环境被调用，那么它的名字绑定环境仍然是 let 里面的环境。也就是说，它仍然可以使用局部变量 x 和 y!

如果我们调用

(f 1 2)

就得到结果 33.

这相当于同时赋值。

所以在下面这种情况里，内层的 let 绑定 b 时，实际上使用的是外 层的 x 在计算。

(let ((x 10)    ; bindings of x
   (a 20)))  ; and a
+----------------------------------------------------------+
| (foo x)                                 scope of outer x |
| (let ((x (bar))                           and a          |
|       (b (baz x x)))                                     |
|  +------------------------------------------------+      |
|  | (quux x a)                    scope of inner x |      |
|  | (quux y b)                    and b            | )    |
|  +------------------------------------------------+      |
| (baz x a)                                                |
| (baz x b)                                                |
+----------------------------------------------------------+

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))))

比Boyer-Moore更快的字符串查找算法（转）

字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍。但是BM算法还不是最快的算法，这里介绍一种比BM算法更快一些的查找算法。

例如我们要在"substring searching algorithm"查找"search"，刚开始时，把子串与文本左边对齐：

substring searching algorithm
search
^

结 果在第二个字符处发现不匹配，于是要把子串往后移动。但是该移动多少呢？这就是各种算法各显神通的地方了，最简单的做法是移动一个字符位置；KMP是利用 已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符（上图中的 'i')。

显然，不管移动多少，这个字符是肯定要参加下一步的比较的，也就是说，如果下一步匹配到了，这个字符必须在子串内。所以，可以 移动子串，使子串中的最右边的这个字符与它对齐。现在子串'search'中并不存在'i'，则说明可以直接跳过一大片，从'i'之后的那个字符开始作下 一步的比较，如下图：

substring searching algorithm
　　　　search
　　　　^

比较的结果，第一个字符就不匹配，再看子串后面的那个字符，是'r',它在子串中出现在倒数第三位，于是把子串向前移动三位，使两个'r'对齐，如下：

substring searching algorithm
　　　　　 search
　　　　　　　^

哈！这次匹配成功了！回顾整个过程，我们只移动了两次子串就找到了匹配位置，是不是很神啊?!可以证明，用这个算法，每一步的移动量都比BM算法要大，所以肯定比BM算法更快。

下面是这个算法的c代码。注意我假设了每个字符的值都介于0-127之间（即纯ascii码）。

char *qsearch(const char *text, int n, const char *patt, int m)
{
// get the length of the text and the pattern, if necessary
if (n < 0)
n = strlen(text);
if (m < 0)
m = strlen(patt);
if (m == 0)
return (char*)text;

// construct delta shift table
int td[128];
for (int c = 0; c < 128; c++)
td[c] = m + 1;
const char* p;
for (p=patt; *p; p++)
td[*p] = m - (p - patt);

// start searching...
const char *t, *tx = text;

// the main searching loop
while (tx + m <= text + n) {
for (p = patt, t = tx; *p; ++p, ++t) {
if (*p != *t) // found a mismatch
break;
}
if (*p == 0) // Yes! we found it!
return (char*)tx;
tx += td[tx[m]]; // move the pattern by a distance
}
return NULL;
}

注：这个查找算法称为Sunday算法，它是BM算法的一种改进型。

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），书中自有黄金物，早日摆脱索然无趣的代码！

Scheme学习笔记（五）

（这应当是最后一篇了，明天来继续数组左旋...）

八. 宏

• MIT-Scheme的宏定义：

  (define-syntax 宏名
  (syntax-rules()
  ((模板) 操作))
  . . . ))

• 在操作时，先用let绑定参数，然后用lambda定义过程：

  (let ((本地操作 (lambda 参数 宏主体 ...)))
  (lambda (e r)
   (apply 本地操作 (cdr e))))

• (define-syntax start
   (syntax-rules ()
       ((start exp1)
           exp1)
        ((start exp1 exp2 ...)
   (let ((temp exp1)) (start exp2 ...))) ))

• 实现的短小的定义：
  

  (define-macro MACRO-NAME
  (lambda MACRO-ARGS
  MACRO-BODY ...))

九. 结构

• 结构模板定义：(defstruct 结构名 属性（不构成list）)

(defstruct tree height girth age leaf-shape leaf-color)

• 新建结构：(make-结构名 属性符号 值 符号 值)

(define coconut
(make-tree ’height 30
’leaf-shape ’frond
’age 5))

• 使用结构：(结构名.属性名 结构对象);返回属性值，(set!结构名.属性名 结构对象 新属性值);更改属性值

(tree.leaf-shape coconut) => frond
(set!tree.height coconut 40)
(tree.height coconut) => 40

• defstruct本身未提供，需要宏来定义，具体不再写出。

十. 面向对象

• Scheme标准默认未提供！我看也用不着。

祝所有Sceme的爱好者们早日摆脱无聊和世俗的coder世界！

Scheme学习笔记（四）

（下一篇是最后一篇，讨论宏，结构和面向对象（其实没什么用））

四. 流程控制

• Scheme中只有if操作是内置的，其它用宏实现。
• 应尽量用尾递归代替循环。

• (if (测试表达式) (操作) (else操作))
• 由多个语句构成的操作用(begin)语句组合

• (when (测试表达式) (多个操作))
• (when (非测试表达式) (多个操作))
• 其它的操作式不必用begin组合
• case语句：

(case c
((#\a) 1)
((#\b) 2)
((#\c) 3)
(else 4)) => 3

• 逻辑表达式操作：
• and在无非比较时返回后一个值：(and 1 2) => 2
  (and #f 1) => #f
• r在无非比较时返回前一个值：(or 1 2) => 1
  (or #f 1) => 1

六. 递归

• 不能工作的代码，因为let或let*会将操作名绑定到各自的词法定界，导致互相递归调用的函数不能互访：
  

(let ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))

• 把绑定操作换成letrec即可。
• 由begin引导的语句序列返回最后一个语句的值。
• 命名let可简化局部递归调用：

(let countdown ((i 10))
(if (= i 0) ’liftoff
(begin
(display i)
(newline)
(countdown (- i 1))))) ;输出一个整数递减过程中的每个值

• 迭代器(for-each 操作 (被操作list))
• 迭代器(map 操作 (被操作list))，返回list中每一个被操作项构成的list（python里的那个函数的同名被复制品）。

Scheme学习笔记（三）

（另一些参考资料：Scheme语言介绍，语言概要（上）（下））

三. 过程

• lambda形式：((lambda 参数 (过程)) 可选的实际参数)

((lambda (x) (+ x 2)) 5) => 7

• 带括号时为形式参数，否则被认为是一个参数list

((lambda someFriends ; 参数周围没有括号 ! (DisplayLine "hi there " someFriends)) 'mole 'bear 'tiger)

• 定义函数用define：(define add2 (lambda (x) (+ x 2)))，省略lambda：(define (add6 x) (+ x 6))
• 谓词(procedure?)来测试一个对象实际上是否为过程
• 函数名即操作名：(add2 9) => 11
• (apply 函数名 参数列表)强制调用。
• 过程的套嵌定义遵循词法定界。

五. 词法定界（下篇讲“四”）

• define定义当前定界以下对象。
  
• (set!)仅改变当前定界中的对象：

(define counter 0)
(define bump-counter (lambda ()
(set! counter (+ counter 1))
counter))

(bump-counter) => 1
(bump-counter) => 2
(bump-counter) => 3

• 相对define，(let (定义局部变量) (其它代码))绑定局部变量到过程：

(let ((x 2) (y 5)) (* x y)) => 10


• let*内的定义不改变上级定界定义的局部变量

• letrec的定义可互交引用？

(letrec ((even?
             (lambda(x)
             (if (= x 0) #t
                     (odd? (- x 1)))))
         (odd?
             (lambda(x)
             (if (= x 0) #f
                     (even? (- x 1))))))
(even? 88))  =>  #t

• letrec帮助局部过程实现递归。

• 非标准的(fluid-let)不改变上级定界变量却引作当前定界局部变量——无聊。。。

(fluid-let ((counter 99))
(display (bump-counter)) (newline)
(display (bump-counter)) (newline)
(display (bump-counter)) (newline))
输出100，101，102，但原counter不变。

Scheme学习笔记（二）

（都忘了说了，我复习用的教材是Teach Yourself Scheme in Fixnum Days，还有一本The Scheme Programming Language也很好，但太长，没看过）

2. 复合类型

比较谓词：

(eqv?   (list 'a) (list 'a)) ; 它们 "看起来一样"，
;()
(eq?    (list 'a) (list 'a)) ; 存储在不同的内存单元中。
;()
(equal? (list 'a) (list 'a))
;#t

• 字符串：申明(define str "This is a string.")
• 用字符申明：(string #\h #\e #\l #\l #\o) => "hello"
• (string-ref 字符串 位置（整数）)返回字符串该位置上的字符
• (string-append "E " "Pluribus " "Unum") => "E Pluribus Unum"
• 改变字符串（重新赋值）(string-set!)
• (string-length "mumble") => 6

• 向量（貌似数组）：值以"#"开头
• 申明(vector 0 1 2 3 4) => #(0 1 2 3 4)或(make-vector 长度)

• 对（不知道怎么翻译pairs这个词~~）
• 分为左右值，左值叫car，右值叫cdr，用他们作操作符获取左右值
• 申明(cons 左值 右值)
• (cons 1 #t) => ’(1 . #t)
• (set-car!)，(set-cdr!)
• 重要！经常右值套嵌！(cons 1 (cons 2 (cons 3 (cons 4 ’()))))形成list：(list 1 2 3 4)

• list（太有名，懒得翻译）
  

• list操作：取值(list-ref)
• list-tail 通过除去前面的 n 个元素来获得一个子表
• 添加元素(append)
• (null?) 检查它的操作对象是否是空表。
• 长度(length)
• member 和 memq 将返回它的 car 是一个指定元素的一个子表。
• 查找(assoc 'LittleBear '((HappyMole vampire) (LittleBear banshee) (LittleTiger troll))) => (LittleBear banshee)

• 类型转换：(原类型-新类型 对象)
• 类型转换方式非常自由：

(string->number "16") => 16
(symbol->string ’symbol) => "symbol"
尤其是这个：
(string->list "hello") => (#\h #\e #\l #\l #\o)

Scheme学习笔记（一）

（写这个文档并非我初学Scheme，只是为开始全面使用它作点复习准备）

一. HelloWorld

• Scheme语法即抽象语法树，只有仅有的几个内部语法支持。
• ;开启一行注释
• 用括号进行文法定界，第一项为操作，空格（换行）分割操作对象，如：

(diplay "hello, world!")
即对"hello, world!"字符串进行 display 操作。

• Scheme和Lisp一样是自描述的，脚本用 .scm 作为后缀，进入解释器后，使用(load "文件名字符串")启动程序，用(exit)退出解释器。

• 完整程序：

(begin (display "hello, world!") (newline));newline用来刷新缓存

二. 数据类型
1. 简单类型

• 布尔值：有两个取值，#t和#f
• 操作(类型名? 变量)返回一个布尔值，确认该变量是否为此类型。如：

(boolean? #t) => #t
(boolean? 32) => #f

• 宏(not 布尔值)返回这个布尔值的反取值。如：

（not (boolean? #t)) => #f

• 数字：分为complex，rational，real，integer，但申明时不必指出。
• (= 操作对象1 操作对象2)操作仅用于比较类型相同的变量值是否相同；(= 43 43) => #t，但(= 43 "ok")会报错。
• (eqv?)操作是(=)的范型版本
• 指数运算(expt 2 3) => 8，取绝对值(abs -7) => 7
  
• 字符：以#\开头的单个字符

(char=? #\a #\a) ? #t
(char=? #\a #\b) ? #f

• 忽略大小写比较：(char-ci=? #\a #\A) => #t
  
• 大小写转换（不影响原值）(char-downcase #\A) => #\a，(char-upcase #\a) => #\A
• 符号：编译原理中的东西，可作变量名，用(quote)申明，(quote a) => 'a
• 变量不与其类型绑定：
  

(quote abc) (define xyz 9) (set! xyz #\c)

关于数组左移问题的一个新想法

本来要继续写数组左旋下篇（上篇在此）的，今天在课堂上忽然想到一个新办法 ：既然可以证明每一个元素的新位置是((k - m) + i ) % k，我何不再仔细分析一下数组的直接移动过程？
对于k = 5，m = 2：
#注：蓝色线表示元素向右的移动过程，绿色表示向左的移动过程。
不难发现，向右移动时，元素下标从 i 改变到 i + k - m，而向左移动时是 i - m（显然）。
再验证一下吧：为什么这个用了两次直接移动？似乎 k % m == 0 时就需要做 m 次，否则要做1次。
没错。但算法写得可不能如此精神分裂——这个现象肯定有更深层次的原因。
再演算一下，终于弄明白了：每种方向的移动其实是个循环过程，每次寻找 k 中可存放元素的下标位置；当期望的下标大于 k 时，元素就要向反方向找位置了。
理清了算法的操作过程，大致的想法也就成型了：有一个分两种情况找位置的递归函数，当 k % m == 0 时循环调用它 m 次，当 k % m == 1时一次即可。比如：
显然这个算法只进行了 k 次赋值（计算次数可以忽略不计），效率应当非常高。
具体代码等我写完《谈谈数组左旋问题（下）》再说吧！

我设计的Lua数据结构List的接口

代码还没有测试完，先把接口并注释发一下，将来和着代码一起发看起来很不方便。
设计参考了Python的相关函数，但比Python更强。不过python中的数组分片功能不知道能否真的实现，如果不行我只好用其它函数对分片功能的支持来代替。

--域，没有多余的域
List = {n = 0}

--静态方法接口
function List.new (...) end --构造函数，将整个参数列表转为List
local function List.cons (table) end --内部构造函数，将表转为List

--成员方法接口
function List:insert (item, n) end --在位置n之前插入item，默认插在List头部
function List:append (item) end --在list尾部插入item，等价于insert(item, list.n)
function List:remove (item) end --弹出第一个等于item的项并返回
function List:pop (n) end --弹出下标为n的项并返回，默认弹出末项，pop(0)等价于pop(1)
function List:index (item) end --返回第一个值为item的项的下标
function List:qindex (item) end --对于已排序list使用二分法查找
function List:count (item) end --返回list中该item的出现次数
function List:sub (from, to) end --返回从from到to的子list，下标为from的项不包括在内；from默认为0，to默认为list.n
function List:subl (from, l) end --等价于sub(from, from+l)
function List:cut (from, to) end --从list删除下标从from到to的子list并返回...
function List:cutl (from, l) end --等价于cut(from, from+l)
function List:extend (list) end --直接在self后添加list子列表
function List:reverse () end --倒排这个list
--function List:reverse (from, to) end #如果sub函数不能实现，这个功能就十分必要了
function List:sort (func) end --接受一个函数，它比较两个参数arg1
function List:qsort (func) end --sort()的快速排序版本
function List:bsort (func) end --sort()的基数排序版本，要求所有项都为正整数
--下面3个函数是python中的同名函数，充作迭代器
local function List:map(func)
local function UNM () end --每项取负访问器
local function EXP2 () end --每项取平方访问器
local function EXP3 () end --每项取立方访问器
end
local function List:filter(func)
local function DEL (item) end --返回并删除所有等于item的项的过滤器
local function EQUAL (item) end --返回所有等于item的项的过滤器
local function MORE (item) end--返回所有大于item的项的过滤器
local function LESS (item) end--返回所有小于item的项的过滤器
end
local function List:reduce(func)
local function MAX (pre, next) end --求最大递归访问器
local function MIX (pre, next) end --求最小递归访问器
local function MUL (pre, next) end --求list各项之积递归访问器
local function SUM (pre, next) end --求list各项之和递归访问器
local function SUM_MAX (pre, next) end --求最大子序列递归访问器
end

赶快写~~赶快写~~
×补充：我已经有办法解决数组分片问题了——给list加两个域：_stat和_end，再使用函数代理访问下标，玩“虚拟下标”即可！

极度经典的二分法搜索

很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;
}
这么简单注释就免了吧，哈哈~~

《称球问题》的完整代码

晕死，上次发的那篇文章居然忘了给代码。现在把它贴出来，顺便加点注释。
（最近拼命写Lua数据结构实现中...）

#metga.py
#useage: python metga.py datefile
import sys
import string

#比较结果代码（左盘?右盘）
HEAVY = 1
LIGHT = -1
EQUAL = 0
QUESTION = 0 #问题球的问题
ANSWER = ""

#球的数据结构
class Ball:
def __init__ (self, weight):
self.weight = weight
self.number = 0

#求总质量
def sum (balls):
tmp = 0
for ball in balls:
tmp += ball.weight
return tmp

#天平函数，计算左右盘质量返回比较结果
def metage (leftBalls, rightBalls):
left = sum(leftBalls)
right = sum(rightBalls)
if left > right: return HEAVY
if left < style="color: rgb(51, 51, 255);">return LIGHT
return EQUAL

#对球进行预处理，判断问题球是轻是重
def pre (balls):
global QUESTION
n = len(balls) / 3
parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
statu = metage(parts[0], parts[1])
if statu == EQUAL:
QUESTION = metage(parts[2], parts[0])
return balls[2*n:]
QUESTION = statu
if metage(parts[0], parts[2]) == EQUAL:
return parts[1]
else:
return parts[0]

#递归地分3片称球
def test (balls):
l = len(balls)
if l == 1:
return balls[0].number
n = l / 3
if l < n =" 1" parts =" [balls[:n]," statu =" metage(parts[0]," style="color: rgb(51, 51, 255);">if statu == EQUAL:
return test(balls[2*n:])
elif statu == QUESTION:
return test(balls[:n])
else:
return test(balls[n:2*n])

#读取数据文件（内容为n个数字，每个一行，其中有一个与其它不等）
weight_list = map(string.atoi, open(sys.argv[1]).readlines())
ball_list = map(Ball, weight_list) #创建球组成的list
i = 1
for ball in ball_list: #初始化下标
ball.number = i
i += 1
if QUESTION == 1:
ANSWER = "heavier"
else:
ANSWER = "lighter"
print "The No.%d ball is %s than others." % (test(pre(ball_list)), ANSWER)

可恶的Blogger对于程序的排版支持约等于无，忙死我了。等我学完编译原理，我一定要开发一个JavaScript实现的词法分析器！

参考AllStartFromGame写了一个排列组合算法

--昨天想了半个小时才想到的一个不错的方法。
--Lua果然号称“只用表的Scheme”，库基本没有。
--代码写得很零乱，还有问题——该死的Lua默认变量为全局，搞得递归有问题。
--不过想法还是很强的，把书本上的知识扩展了一下。
--下次我来扩充一下库，顺便把这个东西改写一下，至少让它能跑起来。

function turn_left (list) --数组左移函数
table.insert(list, list[1])
table.remove(list, 1)
end
function table.extend (t1, t2) --Python中的同名函数
for i = 1, table.getn(t2) do
table.insert(t1, t2[i])
end
end
function list_all (...) --启动函数，接受n个参数作为待排列的项
h_result = list_half(arg)
table.extend(h_result, reverse(h_result))
return h_result
end
function reverse (list) --数组假反序（返回一个新数组）
temp = {}
for i = 0, table.getn(list)-1 do
table.insert(temp, list[table.getn(list)-i])
end
return temp
end
function list_half (list, n) --列表半个排列组合
result = {} or result --保存结果的二维数组
tmp = {list[1], list[2]} or tmp
if n == nil then --处理起始情况
list_half(tmp, table.getn(list)-1)
end
if n == 1 then --处理基准情况——最终排序
for i = 1, table.getn(tmp) do
turn_left(tmp)
table.insert(result, tmp)
end
return result
else --递归列出最一般的排序
table.insert(tmp, list[table.getn(list)-n])
for i = 1, n do
turn_left(tmp)
list_half(tmp, n-1)
end
return result
end
end

找到的一个八皇后问题Python版解法

原文称参考了All Start From A Game。
觉得有参考价值，虽然好像还不够快和简洁。以后我来自己写一个递归版的罢。
排版了一下，加了点注释。

size = 8 # 棋盘大小
EMPTY = "O" # 空位
QUEEN = "X" # 皇后

# 查看棋盘的信息
def show_board(cols):
for i in range(size):
for j in range(size):
if j == int(cols[i]) - 1:
print QUEEN,
else:
print EMPTY,
print "\n",

# 检测棋盘上皇后摆法是否合法
# return:
# True(不冲突), False(有冲突)
def check_board(cols):
for i in range(size - 1):
for j in range(i + 1, size):
if j - i == abs(int(cols[j]) - int(cols[i])):
return False
return True

# 得到全排列
def permute(seq):
seqn = [ seq.pop() ]
while seq:
newseq = []
new = seq.pop()
#print "seq:",seq,'seqn', seqn ,'new', new
for i in range(len(seqn)):
item = seqn[i]
for j in range(len(item)+1):
newseq.append(''.join([item[:j],new,item[j:]]))
seqn = newseq
#print 'newseq',newseq
return seqn

#测试代码
if __name__ == "__main__":
solve_count = 0
numbers = ''.join([str(i) for i in range(1, size + 1)])

for x in permute(list(numbers)):
y = list(x)
if check_board(y):
solve_count += 1
show_board(y)
print "\n",

print "found %i solves." % solve_count

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

终于把《编程珠玑》那本书给买来了。第一章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为止。统计最后有几张牌正面朝上，以及它们的位置号。

看到一道NOI2005的题目，高手上吧

篝火晚会
(fire.pas/c/cpp)
【问题描述】
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：
(b1, b2,... bm -1, bm)
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？
【输入文件】
输入文件fire.in的第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。 【输出文件】 输出文件fire.out包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。 【样例输入】 4 3 4 4 3 1 2 1 2 【样例输出】 2 【数据规模】 对于30%的数据，n <= 1000； 对于全部的数据，n <= 50000。

发生在我身边的一个算法笑话

当年老师教我们算法入门，讲到一道题目，说输入一个整数 N，要求输出所以不大于这个整数的除3可以整除的正整数。
大家都是这么写的（伪代码）：
for X from 1 to N step 1
if X%3=0
print X
end if
end for
我们班体委突然发彪，给出了一个惊世骇俗的解答：
for X from 3 to N step 3
print X
end for
老师晕死，全班人疯了~~

一个线形复杂度的菲波那契函数

所谓菲波那契数列，就是这个东西：1,1,2,3,5,8...题目为，写一个函数fib(int n)给出数列中某个数的下标，返回这个数。
菲波那契函数的数学定义为fib(x)，x=1 ? fib(x)=1 : fib(x)=fib(x-1)+fib(x-2)。
只用这个就可以给出解答：
unsigned long fib (int x) {
if (x > 2) {
return fib(x - 1) + fib(x - 2);
} else {
return 1;
}
}
测试函数如下：
int main () {
int arg;
printf("Input the length:");
scanf("%d", &arg);
printf("fibonacci(%d)=%lu\n", arg, fib(arg));
return 0;
}
但是，学过算法的人都知道，这个算法的时间复杂度是O(n2)级的，慢的要命。教科书上给出了循环方法的解答。（注：这个解答有一个超变态的一句话版本，知道的人请跟贴）
事实上，确实可以给出线形复杂度的菲波那契函数，原理来源于数列本身的性质。我大概写了一下，程序本身不好看，但肯定不会更快了：
#include
int i = 3;
unsigned long fib (int x, int y, int n) {
if (i <= n) { i++; return fib(y, x + y, n); } else { return y; } } int main () { int arg; printf("Input the length:"); scanf("%d", &arg); printf("fibonacci(%d)=%lu\n", arg, fib(1, 1, arg)); return 0; } 觉得怎么样？是不是很直白？

附：菲波那契数列有通项公式...
#python代码
import math
q = math.sqrt
def fib ( n ) :#看清楚了，这可是O( 1 )级的哦~~
return ((1 + q(5) / 2) ** n / q(5) - ((1 - 1(5)) / 2) ** n / q(5)

《称球问题》的 python 版解答

《程序员》杂志第8期上讲解了这样一个问题：在N个球中，有一个球重量与其他球重不同（偏重或偏轻），在没有砝码的天平上进行k（N<=(3^k-1)/2）次称量，得到这个球的编号，并判断它比其它球轻或重。

《程序员》上使用了将球分为0～n-1，n～2n-1，2n～N-1（n=(N%3)?(N/3+1):(N/3)）两两递归比较的方法。但由于在整个比较过程中，这个球到底偏轻还是偏重一直没有确定而进行了多次无效的比较，而且使用C++描述，对于这个需要大量出来数组的算法来说十分繁琐。我采用了支持函数式编程的Python语言优化了这个算法，脚本和测试用数据文件（举例）在附件中有下载。

主要思想与《程序员》中的类似，不过对球的列表的分片有所不同：
parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
保证3片球数相同。确定是那一片出了问题后返回它时，最后一片由于可能不是balls[2*n:3*n]（len(balls)%3!=0），所以返回balls[2*n:]。

球包括号码和质量两个属性，类定义如下：
class Ball:
def __init__ (self, weight):
self.weight = weight
self.number = 0
（注：number的默认值0是无效的，号码从1开始）
sum()用于给质量求和：
def sum (balls):
tmp = 0
for ball in balls:
tmp += ball.weight
return tmp
天平函数，返回比较结果——HEAVY = 1，LIGHT = -1，EQUAL = 0：
def metage (leftBalls, rightBalls):
left = sum(leftBalls)
right = sum(rightBalls)
if left > right: return HEAVY
if left < right: return LIGHT
return EQUAL

用全局变量QUESTION保存问题球是轻是重，这由预测量函数pre()给出，它工作后还返回有问题的分片。这样test()函数在工作时可以少一半比较次数。

test函数递归调用自身，可以采用折半比较的方式。但那样会提供算法的时间复杂度。假设n个质量数据求和要进行n次运算，折3片比较共需p=2*(x/3+x/3^2+...x/3^(N-1))次运算，化简得p=x-x/3^n，即求和运算次数不会大于球总个数。而折半比较则需(2^(N+1)-1)x（不准）次运算，明显多于使用分3片比较。

具体比较的条件详见代码，自行阅读。

最后解释一下数据文件的读入情况。数据文件是普通文本文件，每行一个数字，其中一个与其它不同。open(sys.argv[1]).readlines()返回一个由每行的字符串构成的列表，weight_list = map(string.atoi, open(sys.argv[1]).readlines())对这个列表中的每一项进行转数字操作并存入weight_list。ball_list = map(Ball, weight_list)把表中每一项创建Ball对象，最后test(pre(ball_list)计算返回球的编号。

关于python的函数式编程请初学者自己参考教材理解。感谢网友孔辉GID2257990(Lava-Lava平台)在程序调试方面给予的帮助。