回顧過(guò)去自己寫(xiě)得還比較幼稚的代碼算法 是不是進(jìn)步很大了？

 你真的了解過(guò)去的自己?jiǎn)�？別急著回答，先看看我的故事：

    一個(gè)計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的大學(xué)新生，經(jīng)過(guò)一個(gè)學(xué)期的洗禮，在學(xué)習(xí)了《c語(yǔ)言程序設(shè)計(jì)》的課程之后，對(duì)計(jì)算機(jī)有個(gè)懵懂的概念。同時(shí)，另外一門(mén)課程《線性代數(shù)》也按部就班的進(jìn)行著，數(shù)學(xué)在那時(shí)還是他擅長(zhǎng)并喜愛(ài)的，但習(xí)題中枯燥的數(shù)字矩陣計(jì)算徹底摧毀了他的底線，尤其是計(jì)算n階行列式(尤其是n>3時(shí))的值的時(shí)候，一次次錯(cuò)誤的計(jì)算結(jié)果讓他萌生了用計(jì)算機(jī)代替解題的想法，于是乎他安靜的坐在電腦前開(kāi)始思考合適的算法和方案。感嘆他此時(shí)還不知道有全能的Google，經(jīng)過(guò)短暫的思考，他找到了一個(gè)方便計(jì)算機(jī)實(shí)現(xiàn)的公式：

(其中sgn(σ)是排列σ的符號(hào)差)

    先算乘再求和，如此枯燥的計(jì)算對(duì)計(jì)算機(jī)來(lái)說(shuō)最拿手了，剩下的問(wèn)題就是搞定這個(gè)σ，其實(shí)看上去神秘，說(shuō)起來(lái)大家都明白，利用這個(gè)公式計(jì)算行列式的值核心的部分就是生成n的全排列，然后把每個(gè)排列的乘積加(減)起來(lái)。問(wèn)題的核心已經(jīng)明了，就是如何根據(jù)n生成全排列。當(dāng)時(shí)的他不懂遞歸，不懂算法，更加不懂Google，懂的只有剛剛學(xué)會(huì)的一點(diǎn)點(diǎn)c的基本語(yǔ)法，甚至連指針都玩不明白，但是沒(méi)關(guān)系，他懂?dāng)?shù)學(xué)，他覺(jué)得這就夠了，于是經(jīng)過(guò)數(shù)天的冥思苦想，他寫(xiě)出了下面的代碼(部分截取，已經(jīng)轉(zhuǎn)換成C#)

1: public int[,] Pn(int n)

2: {

3: int[,] a = new int[GetFactorial(n), n];

4: for (var k = 0; k < n; k++)

5: {

6: for (int i = 0, length = GetFactorial(k + 1); i < length; i++)

7: {

8: a[i, k] = k;

9: }

10: for (int i = GetFactorial(k), s = i, length = GetFactorial(k + 1); i < length; i++)

11: {

12: int m = i - s;

13: int p = m / k;

14: int q = m % k;

15: for (int j = 0; j < k + 1; j++)

16: a[i, j] = (a[p, j] + q + 1) % (k + 1);

17: }

18: }

19: return a;

20: }

    其中GetFactorial(n)是計(jì)算n!(n的階乘)的函數(shù)，代碼就不貼了，反正沒(méi)用遞歸來(lái)計(jì)算階乘。

    相信大家對(duì)全排列問(wèn)題并不陌生，在網(wǎng)上可以Google一大把實(shí)現(xiàn)，各種語(yǔ)言和各種算法的版本，這些算法無(wú)論是遞歸的實(shí)現(xiàn)還是非遞歸的實(shí)現(xiàn)都是基于一個(gè)核心運(yùn)算，那就是“交換”，并且這些全排列算法都是一個(gè)一個(gè)“有序”生成的，而這段代碼是縱向(亂序)填充出來(lái)的，而且全部的序列是通過(guò)“計(jì)算”而非“交換”得來(lái)的，加、減、除和取模，從嚴(yán)格意義上講，雖然代碼中沒(méi)有遞歸，但每次計(jì)算都利用之前生成的數(shù)字再次計(jì)算，也算是借鑒遞歸的思想吧。然而這些都不重要，重要的是故事的主人公是8年前的我，而8年后的我在翻出這段代碼的時(shí)候竟然不知道從前的自己是如何寫(xiě)出來(lái)的，因?yàn)槲业浆F(xiàn)在還沒(méi)想起來(lái)當(dāng)時(shí)是如何思考的，這真的是我寫(xiě)的嗎？代碼的原始版本(c版本)沒(méi)有注釋?zhuān)踔翛](méi)有縮進(jìn)，變量命名也是現(xiàn)在的i,j,k,a,m,p,q…

    由于最近有一個(gè)地方用到了全排列，就把當(dāng)年的代碼翻出來(lái)了，沒(méi)想到是這個(gè)結(jié)果。起初我還試圖在上面改進(jìn)一下，把它變成可以一個(gè)一個(gè)順序生成的，在努力了幾個(gè)小時(shí)后我放棄了，因?yàn)閷?shí)在想不起來(lái)當(dāng)初是怎么想的了。既然想不起來(lái)就測(cè)試一下性能吧，因?yàn)檫@段代碼只能生成序列的索引排列，而且由于是縱向生成的要一起申請(qǐng)內(nèi)存，所以應(yīng)用起來(lái)有一定的局限性，我們知道n的全排列的個(gè)數(shù)是n!個(gè)，當(dāng)n變大的時(shí)候，生成時(shí)間會(huì)大幅提高，傳統(tǒng)的遞歸方式在n到達(dá)一定大小時(shí)性能會(huì)急劇下降(不僅僅因?yàn)閿?shù)量還因?yàn)樯疃冗f歸)，而該算法卻意外的很“穩(wěn)定”，當(dāng)n較小時(shí)(我的機(jī)器上測(cè)試n<7)，它沒(méi)有遞歸快，但當(dāng)n再變大的時(shí)候，它的優(yōu)勢(shì)就體現(xiàn)出來(lái)了，表現(xiàn)出優(yōu)于遞歸的良好性能，當(dāng)n再變的更大的時(shí)候，內(nèi)存overflow了-_-!

    總結(jié)一下，這個(gè)故事給我們?nèi)齻€(gè)啟示(歡迎大家補(bǔ)充)：

一是對(duì)于理解上復(fù)雜的代碼一定要寫(xiě)注釋?zhuān)奖銊e人閱讀，更何況這個(gè)別人可能就是自己；

二是一定要花點(diǎn)時(shí)間在變量的名字上，否則后患無(wú)窮，對(duì)自己好點(diǎn)吧；

三是不要相信自己的大腦跟電腦一樣，什么都記得，尤其是一些靈機(jī)一動(dòng)的思路或靈感，動(dòng)手記下來(lái)吧，像我現(xiàn)在在做的事情一樣。

    最后，善待你的代碼，這等于在幫助未來(lái)的自己。

    最后的最后，誰(shuí)能幫忙解釋下這段代碼的數(shù)學(xué)原理:)