{炒冷飯}“母牛數(shù)量算法”一年后我的總結(jié)。

leeon868

這里面有幾個(gè)稱呼，請(qǐng)注意，我稱作使用面向?qū)ο蟮娜耸�，“面向�(qū)ο笸婕摇�，只是玩笑，不是貶低。
題記：
很簡(jiǎn)單的題目，1+2+3+...+100，你是寫個(gè)循環(huán)扔給計(jì)算機(jī)呢？還是學(xué)高斯那樣想一想呢？
以前在ChinaUnix遇到過(guò)一個(gè)母牛生小牛的問(wèn)題。題目很簡(jiǎn)單：
若一頭小母牛，從出生起第四個(gè)年頭開始每年生一頭母牛，按此規(guī)律，第n年有多少頭母牛？
原地址：http://72891.cn/viewthread.php?tid=130156
如果大家有耐心的話，可以看看這個(gè)非常長(zhǎng)的帖子。里面有非常多各自實(shí)現(xiàn)的代碼。
拿到題目了，我們是直接解題？還是思考一下再解題？
或許很多人就直接上手求解了。讓我們看一段自認(rèn)為很NB的c++代碼，
呵呵，這個(gè)是ChinaUnix活躍用戶flw的代碼，比較典型：
# include <stdio.h>
class cow
{
public:
        static cow *head;
        static cow *tail;
        static unsigned long cowCount;
        int age;
        cow *next;
        cow()
        {
                age = 0;
                next = ( cow * ) NULL;
        }
        void grow(void)
        {
                age++;                // 年齡長(zhǎng)了一歲。
                if ( age >= 4 )
                {                        // 第四個(gè)年頭起，下崽。
                        cow *child = new cow;
                        tail->next = child;
                        tail = child;
                        cowCount++;
                }
        }
};
unsigned long cow::cowCount = 0;
cow *cow::head = NULL;
cow *cow::tail = NULL;
int main( void )
{
        int years = 30;
        cow *cows = new cow;
        cow::head = cows;
        cow::tail = cows;
        cow::cowCount = 1;
        for( int i=0; i<years; i++ )
                // 一年過(guò)去了，每牛（注意：不能叫“每人”）給我長(zhǎng)一歲。
                for( cow *ptr = cow::head; ptr != NULL; ptr = ptr->next )  
                        ptr->grow();
        printf( "result: [%ld]\n", cow::cowCount );
        ptr = cow::head;
        while( ptr != NULL )
        {
                cow *temp = ptr;
                ptr = ptr->next;
                delete temp;
        }
        return 1;
}   
嗯，非常NB，不但面向?qū)ο�，還用上了鏈表。此君估計(jì)是狂熱的面向?qū)ο笸婕彝饧訑?shù)據(jù)結(jié)構(gòu)愛好者。是個(gè)好員工啊。
如果按照大O標(biāo)記復(fù)雜度，相信有些算法基礎(chǔ)的都會(huì)感覺很恐怖。當(dāng)然，這個(gè)是可以求解的。
當(dāng)我看到這個(gè)，我第一就感嘆，flw的高中數(shù)學(xué)算是白學(xué)了。

仔細(xì)想一想。4年生一頭牛。其實(shí)就是Fibonacci斐波那契數(shù)列的小擴(kuò)展，
原始的的數(shù)列遞進(jìn)間隔是3。f(n) = f(n-1) + f(n-2)
而這個(gè)題目是4，也就是：f(n) = f(n-1) + f(n-3)
因此我們也可以總結(jié)一個(gè)公式，第step年生產(chǎn)小母牛就是：n(i)=n(i-1)+n(i-step+1)

我們可以用遞歸去求解。這就是高級(jí)語(yǔ)言的特性。
#include <iostream>
typedef unsigned int qty_type;
int i = 0;
qty_type cow( qty_type _year )
{
qty_type c = ( _year < 4 ) ? 1 : cow( _year - 1 ) + cow( _year - 3 );
cout << "No." << ++i
           << "|year:"<< _year
           << "|quantity: "<< c
           << endl;
return c;
}

int main()
{
    cow(10);
    return 0;
}

Oh，這個(gè)雖然比較好了，我們其實(shí)不用“先進(jìn)”的面向?qū)ο笠材茏龅健?br /> 但，這個(gè)不行，這個(gè)一樣會(huì)折磨我們的電腦，我們小小編譯一下，小小輸出一下就知道了。
不要輸入太大，10就夠了。
No.1|year:3|quantity: 1
No.2|year:1|quantity: 1
No.3|year:4|quantity: 2
No.4|year:2|quantity: 1
No.5|year:5|quantity: 3
No.6|year:3|quantity: 1
No.7|year:6|quantity: 4
No.8|year:3|quantity: 1
No.9|year:1|quantity: 1
No.10|year:4|quantity: 2
No.11|year:7|quantity: 6
No.12|year:3|quantity: 1
No.13|year:1|quantity: 1
No.14|year:4|quantity: 2
No.15|year:2|quantity: 1
No.16|year:5|quantity: 3
No.17|year:8|quantity: 9
No.18|year:3|quantity: 1
No.19|year:1|quantity: 1
No.20|year:4|quantity: 2
No.21|year:2|quantity: 1
No.22|year:5|quantity: 3
No.23|year:3|quantity: 1
No.24|year:6|quantity: 4
No.25|year:9|quantity: 13
No.26|year:3|quantity: 1
No.27|year:1|quantity: 1
No.28|year:4|quantity: 2
No.29|year:2|quantity: 1
No.30|year:5|quantity: 3
No.31|year:3|quantity: 1
No.32|year:6|quantity: 4
No.33|year:3|quantity: 1
No.34|year:1|quantity: 1
No.35|year:4|quantity: 2
No.36|year:7|quantity: 6
No.37|year:10|quantity: 19
OH，賣糕的，37次，只是算了10年而已，雖然我們得出了19就這個(gè)正確的數(shù)字，但是代價(jià)慘重，
并不是臆想的那樣，我們算10次就夠了，是遠(yuǎn)遠(yuǎn)超過(guò)的37次。如果是16年將增長(zhǎng)到恐怖的377步。50年達(dá)到恐怖的166632769次。
我試圖計(jì)算100年計(jì)算多少次，嗯，在寫到這里的時(shí)候，這個(gè)簡(jiǎn)單的代碼還沒(méi)有計(jì)算出。真的急死人了。
竟然比“面向?qū)ο笸婕摇贝鷥r(jià)要大！
難道比“面向?qū)ο笸婕摇币�凄慘就放棄這個(gè)簡(jiǎn)單的算法嗎？一下否定了？
算法也是需要分析的。
來(lái)，看看輸出的結(jié)果，我們可以看到這一組數(shù)據(jù)：
No.1|year:3|quantity: 1
No.2|year:1|quantity: 1
No.3|year:4|quantity: 2
No.4|year:2|quantity: 1
1、類似這樣3、1、4、2年的計(jì)算重復(fù)了很多次，而且隨著后面的計(jì)算次數(shù)增加，會(huì)越來(lái)越多。問(wèn)題就出在這些3、1、4、2上。每次都持續(xù)累加計(jì)算這些最初的年份的值。這個(gè)其實(shí)在最初早已經(jīng)計(jì)算好了啊。我們需要把這個(gè)計(jì)算后的值保存下來(lái)。
2、第4年才有數(shù)據(jù)的增加，此前的3年都沒(méi)有數(shù)據(jù)。而隨著4年4年的增加，中間間隔的2年的數(shù)據(jù)是需要逐漸保存下來(lái)的。要不然，中間這些數(shù)據(jù)就需要重新再計(jì)算一遍。
3、顯而易見，我們已經(jīng)知道前4年的情況了，何必要計(jì)算前四年的情況呢？
經(jīng)過(guò)這三點(diǎn)分析，可以寫出如下偽碼：
function(總值, 計(jì)算間隔2年的和, 保留的間隔和1, 保留的間隔和2, 年數(shù))

#include <iostream>
typedef unsigned int qty_type;
int i = 0;
qty_type cow( qty_type all_cow, qty_type a, qty_type b, qty_type c, qty_type year )
{
    cout << "No." << ++i
         << "|year: " << 100 - year
         << "|all_cow: " << all_cow
         << "\n";
    return !year ? all_cow : cow( all_cow + a, a + c, a, b, --year );
}
int main()
{
cow( 1, 1, 0, 0, 97 );
    return 0;
}
顯而易見，其實(shí)我們是從第4年算起的，所以說(shuō)，10年，其實(shí)我們算了7年而已。100年，但是我們僅僅算了97年而已。
不要太多，我們還是測(cè)試10次。
輸出看看：
No.1|year: 3|all_cow: 1
No.2|year: 4|all_cow: 2
No.3|year: 5|all_cow: 3
No.4|year: 6|all_cow: 4
No.5|year: 7|all_cow: 6
No.6|year: 8|all_cow: 9
No.7|year: 9|all_cow: 13
No.8|year: 10|all_cow: 19
呵呵，結(jié)果是正確的。而且只計(jì)算了8次而已。
我們輸入97，來(lái)看看結(jié)果。等等。怎么得到的越來(lái)越小了？在第60年的時(shí)候出現(xiàn)問(wèn)題了：
……
No.58|year: 60|all_cow: 3808901426
No.59|year: 61|all_cow: 1287249059
No.60|year: 62|all_cow: 3886168404
No.61|year: 63|all_cow: 3400102534
……
原來(lái)是這里：
typedef unsigned int qty_type;
換一下
typedef unsigned long int qty_type;
得到的結(jié)果是一樣的，原來(lái)現(xiàn)在的C++編譯器早已經(jīng)把int提升為和long一樣的長(zhǎng)度了。
不得已，我們只能
typedef unsigned long long int qty_type;
也就是int64類型來(lái)表示了，這樣才得出了正確的結(jié)果：
year: 100|all_cow: 16637075746565861

在根據(jù)需求的時(shí)候，數(shù)字長(zhǎng)度是否夠長(zhǎng)，這是一個(gè)大問(wèn)題。還好我們的題目只是100年，如果int64得不出來(lái)，那就需要拓展考慮了。
如果涉及到大數(shù)字計(jì)算，問(wèn)問(wèn)自己，數(shù)夠不夠大呢？
總結(jié)：拿到需求，或者題目的時(shí)候，別看到題目如何就如何設(shè)計(jì)。

我前一段時(shí)間寫代碼，動(dòng)不動(dòng)就用class封裝，但仔細(xì)反思一下，有必要封裝嘛？真的有必要弄個(gè)類才可以嘛？
寫了一個(gè)buffer類，很多操控都寫進(jìn)了這個(gè)類，其實(shí)，寫個(gè)函數(shù)又如何？只不過(guò)多添加了個(gè)buffer的引用而已，其他沒(méi)有多大區(qū)別。
大伯是建筑工程師，也是數(shù)學(xué)專家，上初中的時(shí)候，他曾經(jīng)有過(guò)一句話：如果你能用算術(shù)方法直接解應(yīng)用題，就別用方程式，雖然方程式解題會(huì)很簡(jiǎn)單。
現(xiàn)在才理解他當(dāng)初的這句話。我現(xiàn)在的編程理念就是：能用functional就不用OO。

后記：在寫完這個(gè)的時(shí)候，我的那個(gè)第一個(gè)遞歸，還沒(méi)有結(jié)束，計(jì)算了將近3個(gè)小時(shí)。那個(gè)ChinaUnix的帖子，可能還有人在跟帖，把自己的想法寫出來(lái)，但是沒(méi)有看別人的回答。其實(shí)在那個(gè)帖子里的第一頁(yè)就已經(jīng)有人給出了非常好的答案了。沒(méi)人看他的答案，那個(gè)人，2006年后就沒(méi)有再上ChinaUnix……

朋友Yonsm曾經(jīng)和我吃飯的時(shí)候的時(shí)候說(shuō)過(guò)一句話：我們寫程序的，就是不斷修正自己本身的問(wèn)題才能獲得提高。

參考書目：《Structure and Interpretation of Computer Programs》
--------------
LeeoNix
2009-01-15

虎皮尖椒

這個(gè)世界上難道只有一個(gè)運(yùn)行效率么？

帖子里面評(píng)論某斑竹的話灰常牛a.

leeon868

我并不是唯效率至上論。但有時(shí)候，效率就是一切。

我其實(shí)就想說(shuō)，用腦子去想想，比不想就開始做要好。

看看別人的想法，也會(huì)有更好的答案的，但是很少人缺少耐心去看看。

那位叫：“灰色軌跡”的朋友，雖然現(xiàn)在已經(jīng)不來(lái)CU了，但是他當(dāng)初在當(dāng)初7樓第一時(shí)間給出了最好的代碼，但是沒(méi)人看。

hellioncu

LZ，所謂“牛人”不是每個(gè)方面都牛的

leeon868

flw曾經(jīng)很狂放的說(shuō)，不符合他的就是錯(cuò)的。

我這里再回復(fù)一下，不要狂，狂沒(méi)用。

如果他耐心看看前面的人的帖子。

DQP

真的很汗
估計(jì)flw是在搞怪吧。。。。
這道題是個(gè)很基本的問(wèn)題 很明顯就能看出和 Fibonacci很像
而應(yīng)該把會(huì)重復(fù)用到的結(jié)果cache住 這也是很明顯的事。。。 很多地方就用Fibonacci問(wèn)題來(lái)作為用cache中間結(jié)果來(lái)提速的例子。
作為functional programming的版主不太可能不知道這個(gè)。。。

leeon868

具體見原帖，長(zhǎng)達(dá)25頁(yè)，估計(jì)除了我，不會(huì)有人耐心看完了。

win_hate

2003 年的帖子，現(xiàn)在是 2009 年，很多東西都變了。

fineamy

總結(jié)的很好。

cc520

菜鳥學(xué)習(xí)!!