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

评论

# re: 质朴的C++代码(1)因数分解 2011-07-11 15:00 虚心学习

无知者无谓,这样的水平就不要装B了,建议也学学算法  回复  更多评论   

# re: 质朴的C++代码(1)因数分解 2011-07-11 15:29 华夏之火

@虚心学习
不劳你建议了,只知道算法的人,其实很可怜。后面我会介绍猎人过河、24点算法等经典问题,逐步引入动态规划、回溯、定界分支等算法,旨在希望用C++清晰地表达想法。搭理你这类人,很有失身份,唉!
  回复  更多评论   

# re: 质朴的C++代码(1)因数分解 2011-07-11 20:49 千暮(zblc)

楼主的出发点是好的,思路也很朴素,标题也写得很清楚加入了“质朴”二字。

保持围观  回复  更多评论   

# re: 质朴的C++代码(1)因数分解[未登录] 2011-07-11 21:04 Enic

@华夏之火
楼主已经很客气了,,,
并不非要全部用a b c 1 2 3代码揉成一团才是牛逼算法,,,  回复  更多评论   

# re: 质朴的C++代码(1)因数分解 2011-07-12 09:10 华夏之火

争取让你一直围观下去@千暮(zblc)
  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜