huaxiazhihuo

質樸的C++代碼（1）因數分解

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

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;
}

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

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

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;
}

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

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