这是今天看的第二篇和概率有关的文章——《数学之美番外篇：进化论中的概率论》。
文章的开始就提到了：
偶然性在进化中确实存在（例如，偶然性的突变可以产生新的特征），但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是，自然选择，作为进化中已知的最主要机制，却会明确保留“需要的”（能适应的）特性，消除“不需要的”（无法适应的）特性。只要选择的影响力存在，自然选择就能把进化向一个方向推进，在出乎意料的短时间内产生复杂的结构。举个例子，现有由13个字母构成的序列“TOBEORNOTTOBE”，假设有几百万只猴子，每只猴子每秒钟挑一条短语，需要78,800年才能从26^13种可能中选出这样的排列。不过，Glendale College的Richard Hardison在20世纪80年代写过一个程序，它能够在随机产生序列的同时，保证那些已经出现在正确位置上的字母不会变化（这样做倒有点《汉姆雷特》 的味道。译注：这个句子看了大半天才明白，嘿嘿）。这个程序平均只需要336次迭代就能生成上文提到的短语，时间少于90秒。更神奇的是，把莎士比亚的整个剧本重新生成一遍也只需要四天半时间。
很好奇是否真的是336，所以也写了个程序
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
int GenerateRandomString(const string &sTarget, const string &sNow, string &sResult)
{
char cBase = 'a';
int iCounter = 0;
for( unsigned int i = 0; i < sTarget.size(); i++ )
{
if( sTarget[i] != sNow[i] )
{
int r = rand() % 26;
sResult[i] = (cBase+r);
iCounter++;
}
}
return iCounter;
}
int CountDifference(const string &s1, const string &s2, string &s3)
{
unsigned int i = 0;
unsigned int iCount = 0;
for(; i < s1.size() && i < s2.size(); i++ )
{
if( s1[i] == s2[i] && s3[i] != s1[i] )
{
iCount++;
s3[i] = s1[i];
}
}
return iCount;
}
int evolution(int iSeed)
{
string sTarget = "tobeornotobe";
string sNow;
for( unsigned int i = 0; i < sTarget.size(); i++ )
{
sNow += ' ';
}
int iNotMatch = sTarget.size();
int iCounter = 1;
int iRandTime = 0;
srand(time(NULL) + getpid() + iSeed);
while( iNotMatch > 0 )
{
string sTemp = " ";
iRandTime += GenerateRandomString(sTarget, sNow, sTemp);
int iMatch = CountDifference(sTarget, sTemp, sNow);
iNotMatch -= iMatch;
cout << iCounter++ << ":t" << iRandTime << "t" << iMatch << "t" << sTemp << "t" << sNow << endl;
}
return iRandTime;
}
int main(int c, char **v)
{
unsigned int iLoop = ( c == 2 )? atoi(v[1]) : 100;
int iRandTime = 0;
for( unsigned int i = 0; i < iLoop; i++)
{
cout << i << "----------------------------" << endl;
iRandTime += evolution(i);
cout << iRandTime << " / " << iLoop << " = " << double(iRandTime) / iLoop << endl;
}
return 0;
}而根据这个程序的结果，生成10000次”tobeornottobe”，平均每次需要331次随机，结果还是相当接近的，当然速度就快多了。
另外，原文作者说他自己写的程序是82次，这应该是生成整个句子的次数，而不是random的次数吧。
反映到上面的程序中，就是输出结果的行数均值，也和实际结果吻合。
附上其中一次的结果：
1: 12 1 cmraiithaosb o
2: 23 0 pvzordffr ha o
3: 34 0 bxyneoxtr hx o
4: 45 0 pdxyfkmly lc o
5: 56 0 nifwqerkv tt o
6: 67 0 khhcrjsep en o
7: 78 0 huvvzxphl du o
8: 89 0 ppkcrewns kt o
9: 100 0 qzaqfoilf ky o
10: 111 0 cghkflbzz vo o
11: 122 1 wvopvraux df r o
12: 132 0 flvlw lwy yi r o
13: 142 0 wprip wsx db r o
14: 152 0 mpigu cub oo r o
15: 162 1 lmjwn fdt pd r to
16: 171 0 kwegg xz fd r to
17: 180 0 vxaku tf iv r to
18: 189 1 gtbka sm vc b r to
19: 197 0 ac gk qb nd b r to
20: 205 0 hz oc dx gy b r to
21: 213 0 lf xz sx kz b r to
22: 221 1 fe ph qo hu b r oto
23: 228 0 pp ql b qv b r oto
24: 235 0 ug yn g vg b r oto
25: 242 0 uj my i jt b r oto
26: 249 0 nq rd p fg b r oto
27: 256 1 pw oo b ta b or oto
28: 262 0 xc x g jk b or oto
29: 268 0 yt r y mt b or oto
30: 274 0 el d v jz b or oto
31: 280 0 ls l e wm b or oto
32: 286 1 tt m u vn t b or oto
33: 291 0 p d z wa t b or oto
34: 296 0 r n f gb t b or oto
35: 301 1 a t r se t b or oto e
36: 305 0 q b p y t b or oto e
37: 309 0 c p e x t b or oto e
38: 313 0 e y b r t b or oto e
39: 317 0 x p s f t b or oto e
40: 321 0 l x w o t b or oto e
41: 325 0 n n i l t b or oto e
42: 329 0 q c t o t b or oto e
43: 333 0 l b t y t b or oto e
44: 337 1 i s n k t b ornoto e
45: 340 0 s c e t b ornoto e
46: 343 0 m v z t b ornoto e
47: 346 0 x c q t b ornoto e
48: 349 0 r m u t b ornoto e
49: 352 0 x h r t b ornoto e
50: 355 0 z o p t b ornoto e
51: 358 0 y m z t b ornoto e
52: 361 0 e m g t b ornoto e
53: 364 0 q w g t b ornoto e
54: 367 0 q l f t b ornoto e
55: 370 0 t o i t b ornoto e
56: 373 0 k d p t b ornoto e
57: 376 0 q v c t b ornoto e
58: 379 0 z i h t b ornoto e
59: 382 0 n t i t b ornoto e
60: 385 0 a j d t b ornoto e
61: 388 0 q y e t b ornoto e
62: 391 0 s t f t b ornoto e
63: 394 0 a r u t b ornoto e
64: 397 1 o j o tob ornoto e
65: 399 0 b a tob ornoto e
66: 401 2 e b tobeornotobe
近期评论