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

比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算法的一种改进型。

找到的一个八皇后问题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

递归算法入门-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为止。统计最后有几张牌正面朝上，以及它们的位置号。