要說的話好多，列個(gè)提綱先 
TAOCP初讀感受
《The Art of Computer Programming》的第一卷,大理石花紋的封皮,拿在手里沉甸甸的,這部書給我的第一印象就是這樣--"厚重"--帶有著神秘感和歷史感。
其實(shí)這部書的中文版前言,我早就有幸拜讀過,不過和英文原文相比較,在中文翻譯的味道真的是差了很多，我覺得只有讀原文才能感到Knuth略帶詼諧的而又同是不是嚴(yán)謹(jǐn)?shù)娘L(fēng)格，他寫文章的風(fēng)格其實(shí)真的挺天馬行空的，從寫程序扯到做飯，從算法這個(gè)詞聊起，追著這個(gè)詞的來歷，竟然還帶出了萊布尼茨？真暈，開句玩笑，Knuth絕對是那種老頑童型的人物，他這本書達(dá)到如此厚度估計(jì)此類"廢話"功不可沒。
從Algorithm到Euclid's Algorithm也就是我們熟悉的輾轉(zhuǎn)相除求最大公約數(shù)法，我這個(gè)算法小白開始進(jìn)入了他打開的算法世界......
Knuth行文很喜歡比較、比喻、對比，這讓讀者看起來很輕松愉悅，不過當(dāng)他真的玩起數(shù)學(xué)來，我就有點(diǎn)吃不消了，最后面對算法的一個(gè)形式化描述，消耗了我不少精力，不過目前看來還是大致明白了
總之，這本盛名之下的書，也的確有很多獨(dú)到的地方，作為計(jì)算機(jī)科學(xué)領(lǐng)域的史詩，它給我的第一印象的確很棒。希望我能堅(jiān)持著看下去，從中吸收營養(yǎng)。
今天的收獲
雖然只看了一節(jié)，不過也消耗了我不少的時(shí)間和精力（看來別的一些事情也不能太耽誤，也要抓緊了）
今天的收獲很多，首先對算法這個(gè)名詞有了更多一些的感性認(rèn)識，Knuth提出的“有限、明確定義、有輸入、有輸出、有效率”這幾個(gè)原則總結(jié)得真是不錯(cuò)，尤其最前面的兩點(diǎn)和效率問題，往往構(gòu)成了很多復(fù)雜的問題，著名的圖靈機(jī)停機(jī)問題大概就是在說這個(gè)問題吧……
另外對于輾轉(zhuǎn)相除法的一些數(shù)學(xué)上的推導(dǎo)也給了我不錯(cuò)的感覺，雖然書上沒有明確的給一個(gè)嚴(yán)格的證明，但是根據(jù)他的敘述我馬上就體會到了用比較嚴(yán)格的方法如何寫這個(gè)證明，以及這個(gè)證明的關(guān)鍵點(diǎn)（我覺得證明中其實(shí)用到了通過雙包含來爭相等的手法，這個(gè)是關(guān)鍵）
算法的形式化描述應(yīng)起了我大的興趣，回來的路上想，貌似這個(gè)好像形成了某種數(shù)學(xué)結(jié)構(gòu)，而其上的f映射，構(gòu)成了某種代數(shù)結(jié)構(gòu)，沒有仔細(xì)想過，不過好像是這樣子的哦，我覺得貌似算法的本質(zhì)就是某種自動(dòng)狀態(tài)機(jī)，只不過不一定是有限狀態(tài)的吧，至少從他的意思上看是這樣的
開始沒有理解第二個(gè)，加上了效率約束的的形式化表達(dá)方法的意思，后來花了點(diǎn)時(shí)間看了下Ex1.1.8,我覺得我似乎明白了點(diǎn)
我認(rèn)為Ex1.1.8是這樣的一個(gè)狀態(tài)表
| j |
Theta_j |
Phi_j |
a_j |
b_j |
| 0 |
a |
a |
5 |
1 |
| 1 |
ab |
c |
3 |
2 |
| 2 |
bc |
cb |
1 |
2 |
| 3 |
b |
a |
4 |
3 |
| 4
| c
| b
| 0
| 4 |
| 5
| c
| c
| 5 |
5 |
為了驗(yàn)證，我寫了個(gè)簡單的程序來試驗(yàn)我的狀態(tài)表（真是不行了，好多東西要翻看手冊，寫程序的速度總是上不來）
1
#include <iostream>
2#include <string>
3
4using namespace std;
5int main ( int argc, char *argv[] )
6
{
7
// 0, 1, 2, 3, 4, 5
8
string theta[]={ "a", "ab", "cb", "b", "c", "c"};
9 string phi []={ "a", "c", "bc", "a", "b", "c"};
10 int a []={ 5, 3, 1, 4, 0, 5};
11 int b []={ 1, 2, 2, 3, 4, 5};
12
13 int j=0;
14 int i=0;
15 string stat;
16 getline (cin,stat);
17 while(true)
18 {
19 unsigned int loc=stat.find(theta[j],0);
20 if (loc==string::npos)
21 {
22 j=a[j];
23
}
24 else
25 {
26 string temp=stat.substr(0,loc)+phi[j]+stat.substr(loc+theta[j].length());
27 stat=temp;
28 j=b[j];
29 }
30 cout<<i++<<":\tj("<<j<<")\tloc("<<loc<<")\t"<<stat<<endl;
31 cin.get();
32 }
33 return EXIT_SUCCESS;
34} /**//* ---------- end of function main ---------- */
35 最后一定要提的是，我好像發(fā)現(xiàn)了書里的一處小Bug，而且好像官方網(wǎng)站里的Errata里面沒有這個(gè)（中文版同樣有這個(gè)問題），我已經(jīng)寫信給Knuth了，希望我是真的找到了一個(gè)沒人發(fā)現(xiàn)的Bug啊（其實(shí)我知道這個(gè)不可能）
關(guān)于Galgo庫的"瞎想"
念叨做一個(gè)泛型的算法庫已經(jīng)有好長時(shí)間了，我覺得這個(gè)事情與其一直這么YY，還不如高興了就寫一點(diǎn)，不高興，就扔著,
其實(shí)，這個(gè)世界是不缺泛型算法庫的，STL，Boost，Blitz++中的泛型算法很全面了，我的計(jì)劃是把他們中間缺少的部分補(bǔ)起來，不能互操作的地方粘合起來，再有就是增加對MetaProgramming的支持
呵呵，應(yīng)該還算是一個(gè)比較雄偉的計(jì)劃吧
我希望這套庫能盡可能的高效率、容易使用、同事保證安全，理想的境地是能夠代替ACM集訓(xùn)隊(duì)使用的模塊
目前我的設(shè)想是整個(gè)庫放在Galgo這個(gè)namespace里，這個(gè)namespace分為兩個(gè)子namespace，分別是泛型算法Generic和元編程算法Meta
我覺得這樣一個(gè)庫的建立與維護(hù)，任重而道遠(yuǎn)不說，沒準(zhǔn)前人已經(jīng)作過360遍了，不過沒關(guān)系，權(quán)當(dāng)娛樂了。
First Step——Euclid GCD的一個(gè)實(shí)現(xiàn)
不說什么廢話了，先貼代碼：
1//-------------------------------BEGIN:GAlgo_Euclid_GCD.hpp--------------------------//
2#ifndef _GAlgo_Euclid_GCD_H_
3#define _GAlgo_Euclid_GCD_H_
4namespace GAlgo
5{
6 namespace Generic
7 {
8 template <typename T>
9 T Euclid_GCD(const T& a,const T& b)
10 {
11 return ((a%b)==0)?b:Euclid_GCD(b,a%b);
12 }
13 }
14 namespace Meta
15 {
16 template <int A,int B>
17 struct Euclid_GCD
18 {
19 static const int value=Euclid_GCD<B,A%B>::value;
20 };
21
22 template <int A>
23 struct Euclid_GCD<A,0>
24 {
25 static const int value=A;
26 };
27 }
28
}
29#endif
30
31//-------------------------------END:GAlgo_Euclid_GCD.hpp--------------------------// 應(yīng)該沒什么好說的，比較中規(guī)中矩，常規(guī)手法，不過根據(jù)TAOCP上的說法，可能在某些m，n的取值上需要很多重的遞歸這時(shí)候Meta的方法可能會遇到困難（其實(shí)第一種也有運(yùn)行時(shí)堆棧溢出的危險(xiǎn)），所以說……說什么好呢，就這樣了
下面是個(gè)簡單的測試
1#include "GAlgo_Euclid_GCD.hpp"
2#include <iostream>
3using namespace std;
4int main()
5{
6 cout<<GAlgo::Generic::Euclid_GCD(6,9)<<endl;
7 cout<<GAlgo::Meta::Euclid_GCD<6,9>::value<<endl;
8 return 0;
9}
10
個(gè)人覺得今后有研究價(jià)值的方向
我覺得對于算法描述和圖靈機(jī)、有限狀態(tài)機(jī)、以及隱隱約約我看到的馬爾科夫的某些工作（馬爾科夫鏈）之間的關(guān)系深入挖掘一下應(yīng)該會有不少收獲，那個(gè)我對這個(gè)問題可能會有一個(gè)數(shù)學(xué)結(jié)構(gòu)的猜想估計(jì)也可能可以在這個(gè)方向上證實(shí)或證偽……
突然想去向偶像黃兆鎮(zhèn)請教一下……還是等我把膽子先練大再去吧……