huaxiazhihuo

質(zhì)樸的C++代碼（1）因數(shù)分解

            本節(jié)的代碼編寫，足以顯示中規(guī)中矩的質(zhì)樸的代碼風(fēng)格， 雖不十分高明，但起碼無屬大雅，在下自問對(duì)得起黨，對(duì)得國(guó)家，對(duì)得起人民。本文的任務(wù)是要顯示一個(gè)自然數(shù)的質(zhì)因數(shù)分解的結(jié)果，不需要涉及算法數(shù)據(jù)分析，所以可以集中精力專注于代碼的設(shè)計(jì)上。
            一般來說，程序可分為三部分，輸入，運(yùn)算，輸出。所以，編寫程序的首要任務(wù)是將程序分解為三大部件，逐一地理解它們。
輸入：為一個(gè)自然數(shù)，為簡(jiǎn)化起見，可直接在代碼中寫死進(jìn)一個(gè)變量當(dāng)中。
運(yùn)算：將該自然數(shù)分解為一串質(zhì)數(shù)，用數(shù)組來儲(chǔ)存這些質(zhì)因子，不失為一良策
輸出：顯示該數(shù)的串質(zhì)因子的連乘的式子，好比：
78 = 2 * 3 * 13
又或者
13 = 13
按此思想，可以快速地寫出這個(gè)程序的骨架了。

int main()
{
    const int NUM_SIZE = 10;
    int num = 1178;
    int products[NUM_SIZE] = { 0 };
    
    int count = factorize(num, products);
    display(num, products, count);
    return 0;
}

            似乎輸出部分較易解決，先搞掂它。代碼非常直白易懂，如果你堅(jiān)持看不懂，只能說，你不適合寫代碼，學(xué)點(diǎn)其他的吧，你的專長(zhǎng)不在這里。

void display(int num, int products[], int count)
{
    using namespace std;
    assert(count > 0);
    cout << num << " = " << products[0];
    for (int i=1; i<count; i++)
        cout << " * " << products[i];
    cout << endl;
}

            很明顯，factorize為本程序的運(yùn)算部分，也為核心所在，其中數(shù)組的大小并沒有傳進(jìn)去，那是故意的，因?yàn)檫@樣可以減少很多不必要的代碼，當(dāng)函數(shù)對(duì)數(shù)組的大小要求不大時(shí)，我們完全可以假設(shè)數(shù)組足夠大，這足以解決大部分的問題，特別是寫自己模塊的時(shí)候。如果事事都要求吹毛求疵，那是相當(dāng)痛苦的事情。
            那么該如何分解質(zhì)因數(shù)呢？撇開代碼，先思考我們自己是如何分解質(zhì)因數(shù)的。如果用人腦都無法解決此問題，就算搬出多少流程圖，多少算法語言，都無濟(jì)于事，如果有了問題的算法，最清晰的表達(dá)方式依然是代碼本身。自打接觸程序設(shè)計(jì)到現(xiàn)在，我一直嚴(yán)重鄙視流程圖等東西。幸好因數(shù)分解的方法并不難，其法如下：從2開始，一個(gè)質(zhì)數(shù)一個(gè)質(zhì)數(shù)地逐個(gè)整除待分解之?dāng)?shù)N，如果取遍了N以內(nèi)的所有質(zhì)數(shù)，都無法整除它，即表示N是一質(zhì)數(shù)，分解結(jié)束。如果可以整除，那就表示該質(zhì)數(shù)為N之一因子，將其記下來，N也隨之取為整除的商，再次重復(fù)此步驟，一直到N變成一質(zhì)數(shù)。最后匯總所有能夠整除的質(zhì)數(shù)因子，連同最后的N。還沒忘記因數(shù)分解的同學(xué)，相信會(huì)明白上面的意思。
            現(xiàn)在的問題，是如何將上面的算法翻譯成C++表達(dá)式。琢磨一下，發(fā)現(xiàn)最后匯總質(zhì)數(shù)因子的時(shí)候，還要匯總最后的N，這兩步其實(shí)是同一回事，其實(shí)當(dāng)N為質(zhì)數(shù)時(shí)，N為其自身的一因子，因此，最后一步，可直接簡(jiǎn)化為匯總?cè)康馁|(zhì)數(shù)因子，只要在整除的過程中，多做一步運(yùn)算，將N存起來即可。因此，上面的分解方法可變換為，用N以內(nèi)包括N本身的所有質(zhì)數(shù)整除N，重復(fù)此整除過程，直到N變?yōu)?為止。很明顯，這對(duì)應(yīng)于一個(gè)循環(huán)，且此循環(huán)的條件是必須N>1。
           接下來，就要考慮當(dāng)質(zhì)數(shù)能夠整除N時(shí)，程序?qū)⒆瞿切┦虑椤?、N = N/質(zhì)數(shù)；2、記下質(zhì)數(shù)。
            那么是否必須要求用質(zhì)數(shù)來整除N呢？其實(shí)沒必要，只要用小于或等于N以內(nèi)的所有大于1的自然數(shù)來整除N就可以保證到N以內(nèi)的所有質(zhì)數(shù)了，這樣雖然效率低了那么一點(diǎn)點(diǎn)，但代碼更易于編寫，清晰度更高，編碼時(shí)一定要抵制那種不顧一切地優(yōu)化的沖動(dòng)。無傷大雅之時(shí)，沒必要精益求精。因數(shù)分解的代碼如下： 

int factorize(int num, int products[])
{
    assert(num > 1);
    const int MINNEST_PRIME = 2;
    int count = 0;
    while (num > 1)
    {
        int prime = MINNEST_PRIME;
        while (num%prime != 0)
            prime++;
        num /= prime;
        products[count++] = prime;
    }
    return count;
}

將以上代碼組織起來，添加必要的頭文件，感受一下辛苦的勞動(dòng)果實(shí)吧，很有成就感！

posted on 2011-07-11 12:06 華夏之火 閱讀(3317) 評(píng)論(5)  編輯 收藏 引用