Shellex.info

如何判定一个数能否被3整除? 比如6。
如果你有Python，可以在交互式解释器里面输入：
import re
print re.match(“1((10*1)|(01*0))*10*$”, “110″)!=None
或者直接在你的浏览器地址栏或者Firebug终端输入：
javascript:document.write(/^1((10*1)|(01*0))*10*$/.test(“110″)); document.close();
其中那个”110″部分为任何正整数的二进制形式。
如果返回/打印出 True，则说明被测试数能被3整除；如果结果是False则是无法被3整除。
看上去很神奇，其实道理很简单。首先我们知道，对于任何一个二进制数总是可以表示为如下形式：
Ac
其中A表示前N个字符，c表示最后一个字符。比如对于12的二进制表示”1100″，A指代的是”110″，c指定”0″
我们知道，2进制中，末尾添0直观地表示原数的两倍，那么末尾添1就是原数的两倍再加一。
基于这个事实，要使得Ac被3整除即 Ac mod 3 == 0，则
存在这么一个函数
f(A, c) =
当c为0时：(A×2) mod 3 = ((A mod 3) × 2) mod 3
当c为1时：(A×2+1) mod 3 = ((A mod 3) × 2 + 1) mod 3
只需要函数f(A, c) == 0就可以了。但是这得求A mod 3，只需要向前递归，把A分解成A’和a’，然后求f(A’, a’)就可以了。现在我们把函数f作为状态转换函数，f的值作为状态，待判断二进制串作为接受串，当然了，终止态必须在0，就有如下自动机：

这样不难得出对应的，判定能否被3整除的正则表达式(^1((10*1)|(01*0))*10*$)
想了解更多正则表达式的在算术上的乐趣，不妨阅读Matrix67同学的文章：http://www.matrix67.com/blog/archives/475
以及http://blog.stevenlevithan.com/archives/algebra-with-regexes

写下这个题目的时候哈，shellex又一次，情不自禁地，为我们汉语的博大精深而热泪盈眶。多么美妙的翻译啊，大脑操，要是鹰语就不行咯，彻底沦于庸俗：brainfuck。当然了，还有一些女士叫法，比如brainf**k（请看我的文章分类），b*fuck，brainf*ck等等。但是不管你怎么叫它，它都是brainfuck，是为了fuck你的brain而生的。
这个语言绝对是世界上最淫荡的语言之一了。虽然Shellex很早就知道它的淫荡，但是直到今天才介绍给大家，还望见谅咯。
好吧，这么说有点无聊，但是它不是为了fuck你的brain而生的。按照作者的说法，他想写一个最小的图灵完备的计算机语言，那么如果稍微接触一下brainfuck你会发现他也许真的达到目标了。因为brainfuck程序就是像一个图灵机那样运作。
语言说明：
Brainfuck 程序中有一个隐含的指针, 被称为 “the pointer”, 它能在一个长度为30 000字节的数组上来回移动。这个数组总是被初始化为0，而指针则总是被初始化指向数组的头部。
Brainfuck 语言很简单，只有8个指令，都用一个字符来表示

< 指针左移.
> 指针右移.
+ 指针自增.
- 指针自减.
. 输出当前指针指向的字节.
, 接受一个输入并储存在当前当前字节.
[ 如果当前指针不为0，则运行直到遇到]
] 如果当前指针不为0，跳回到匹配的 [

Shellex的brainfuck解释器的实现中，还私自添加了一个扩展指令：

$ 在内存监视器打印程序内存情况.

当然了，Brainfuck的语义可以简洁地用C语言的形式来表达（假设p是一个char *类型的变量）

> becomes ++p;
< becomes --p;
+ becomes ++*p;
- becomes [...]

问题来自SICP.
该Sample描述了一个换硬币的问题，卡卡，就是偶们是小朋友的是哈哈，父亲大人/母亲大人可能给你一张大..大的钞票，出去打酱油..:D，花不完的，老板会找你钱。找多少钱是个思想斗争，于是就有了这个问题。
给予一定的硬币种类kinds-of-coins和一定的金额amount，使用这些硬币有多少种方式能组成这个金额呢？
很简单哈，所以就书上直接就是源码鸟（这里）。
可惜哈，这个代码实现的是一个树状递归，而树状递归的效率是非常的龌龊，不信你可以试试画一下amount=11, kinds-of-coins=5时的递归计算过程，这个树的很多枝枝丫丫都是一样de，骗取社会主义劳动成功，死人领着活人工资。
所以在脚注34里就提到一种对付这些枝枝丫丫的政策，所谓“记忆技术”（memoization）就是了。
脚注里面说得很呆，其实很简单，把已经算得的结果缓存起来，然后遇到同样的计算任务的时候拿出来用就好。练习3.27就是这么搞的，可惜scheme里面木有构造Cache的现成数据结构，要我实现dic,hash table,什么的我那么lazy的所以不愿意的。不过我的实现也不大优雅，memorize和被memorize的函数杂糅到一起了，python高手告诉我，有木有办法分开？
import time

def change_coins(money):
first_denomination = {
1:1, 2:5,
3:10, 4:25,
5:50,
}
def cc((amount, kinds_of_coins)):
if amount == 0:
return 1
elif amount < 0 or kinds_of_coins == 0:
return 0
else:
return cc((amount, kinds_of_coins – 1)) \
+ cc((amount – first_denomination[kinds_of_coins], kinds_of_coins))

return cc((money, 5))

def change_coins_memoization(money):
first_denomination = {
1:1, 2:5,
3:10, 4:25,
5:50,
}
cache = {}
cc_memo = lambda x :memoize(cc) (x)
def memoize(fun):
def proc(k):
if cache.has_key(k):
return cache[k]
else:
x = fun(k)
cache[k] = [...]

在SICP的练习2.6 提到了Church计数，也就是将数据和操作引入Lambda演算，告诉我们，一旦拥有Lambda，别无所求。这些搞数学的家伙总是喜欢把可以不要的东西全全都去掉，然后用2.6这样的习题中表现出来的能力彻底雷到我。所以像我一样数学只有半桶水的同学先看看维基总是比较好：( http://en.wikipedia.org/wiki/Lambda_calculus )
Wiki：
lambda演算，也称为λ-演算，作为一个形式定义系统去研究函数定义、实现、递归。也是Lisp这类语言计算模型。
定义
一个Lambda 表达式应该由以下的东东构成
变量： v1, v2, . . .
符号：λ 和 .
括号组：( 和 )
一个合法的Lambda 表达式<expression>可以按照如下递归定义：

<expression>  = <variable> | <function> | <application>
<function>  = λ <variable>.<expression>
<application> = (<expression> <expression>)

Lambda表达式记号法
对于Lambda表达式M和N，

最外层括号可以省略:  (M N) 可以表示成 M N.
(λx. M)这样的表达式 被称为函数抽象，原因是它常常就是一个函数的定义，函数的参数就是变量x，函数体就是M，而函数名称则是匿名的。你可以认为它就是f(x)=M，匿名就意味这函数名’f’是不存在的，存在的仅仅是x映射到M这个过程。
函数应用采用左结合: M N P 表示 (M N) P.
Lambda表达式在记法上使用贪婪扩展: 也就是说 λ x. M N 表示 (λ x.M N) ，而不是(λ x. [...]

以前给别人义务普及C++，我总是说：这个iterator哈，和指向数组元素的指针差不多…. :p
好吧，GOF是这么定义迭代器模式的：提供一种方法访问一个容器（container）对象中各个元素，而又不需暴露该对象的内部细节。
我看起来这个东东，在程序的设计过程中扮演的角色是提供了一个很好的抽象，对容器操作的抽象。所以我们的STL里面的vector啦list啦都用它。iterator是在std这个命名空间下，可见有多NB。
其实也没有那么NB。由于C++这类语言不支持闭包和匿名函数，于是才进化出了用迭代器的这样子的东东。好啦，现在请大家举起手来，跟我一起喊：“一，二，三”，Bingo：
for (vecto::iterator iter = v.begin(); iter != v.end(); ++iter) {
//do sth…
}
来想象一下每次打上面这些东西时你淌着哈喇子嚼着鼻涕嘎子的样子。 因为我可以这样子：
v.each_items(lambda (x){…});
(C++的STL里面倒是提供了foreach函数，但是编写迭代器的复杂性和额外的小函数负担使我不喜欢使用他)
不管如何，iterator的表现已经很好了。作为Lazy Evaluation的实现倒也不会太丑。Lazy Evaluation这种东西其实很常用的，可以让你保持优雅的程序的程序结构的同时保证这些code有效率。
比如说我们经常会发现最容易理解的程序往往不是最高效的(还记得斐波那契函数的树型递归吗)。
再比如说聪明的MM大多不养眼，养眼的MM大多不聪明，养眼又聪明的MM大多插在便便上。就是这样令人恼火。惰性求值就可以帮你解决部分生理问题和部分心理问题。
假设我要找出区间[a, b]中第n个素数，比如a = 10, b = 100, n = 4。好吧，不够严谨，我省略了很多东西，能表达意思就行。这说明在C++里面搞个迭代器真的蛮费劲，所以我就大概…将就一下。

#include
#include
using std::cout;
using std::endl;
typedef int* prime_iterator;

class prime_set {
public:
prime_set(int low, int high) : _low(low), _high(high), _crr_pos(low){ };
prime_iterator begin() {
int i = _low;
for (; i < _high; ++i) {
if (is_prime(i)) {
_crr_pos = [...]

SICP虽然已经拿到手很长时间了，一直是懒洋洋地看，快看到完第3章了，就是没做题。昨天遇到了有关判定素数的问题，似乎见过的，决定把前面的习题做了….我错了，:( 然后我决定以后的习题每题都要做。
好吧。在1,3节的时候有提到判断素数的方法。朴素的素数判定，地球的同学都知道的，如果数n除1以外的最小因数是他自己，那么n就是素数。

;return the smallest divisor of n
(define (smallest-divisor n)
;find a divisor(for 2 to n) of n
(define (find-divisor n test-divisor)
(cond ((< n (sqrt test-divisor)) n)
((= (remainder n test-divisor) 0) test-divisor)
[...]

N久以前，王小云同学找到了能构造出能导致MD5碰撞的算法，也就是不同的明文，所得的md5值是一样的。貌似很难，原理上是这样的，特别是对我这样没有搞过密码学的同学来说。但是看看这里吧，其实体验一下很容易。
这些同学基于王小云同学的理论，加以改动，有了如下我可以体验的成果。
这里给出了一个快速生成碰撞的程序，叫MD5 Collision Generator。啊，这个生成器根据所谓的构造前缀碰撞法可以生成两个不同的文件，而这两文件的md5 sum却是一样的。
MD5 Collision Generator(win32 .exe)
MD5 Collision Generator(source)
需要boost库，我没有，就没有编译了。直接wine。
$ wine cmd5.exe
MD5 collision generator v1.5
by Marc Stevens (http://www.win.tue.nl/hashclash/)

Allowed options:
-h [ --help ]           Show options.
-q [ --quiet ]          Be less verbose.
-i [ --ihv ] arg        Use specified initial value. Default is MD5 initial
value.
-p [ --prefixfile ] arg Calculate initial value using given prefixfile. Also
copies data to output [...]