这是今天看的第二篇和概率有关的文章——《数学之美番外篇：进化论中的概率论》。
文章的开始就提到了：
偶然性在进化中确实存在（例如，偶然性的突变可以产生新的特征），但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是，自然选择，作为进化中已知的最主要机制，却会明确保留“需要的”（能适应的）特性，消除“不需要的”（无法适应的）特性。只要选择的影响力存在，自然选择就能把进化向一个方向推进，在出乎意料的短时间内产生复杂的结构。举个例子，现有由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
最近评论