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 华夏之火 阅读(3215) 评论(5)  编辑 收藏 引用