有没有做推文的网站,计算机网站开发实现总结,wordpress 文章字体大小,做网站编辑我能力得到提升★引子 前天#xff0c;俺在《俺的招聘经验[4]#xff1a;通过笔试答题能看出啥#xff1f;》一文#xff0c;以求质数作为例子#xff0c;介绍了一些考察应聘者的经验。由于本文没有政治敏感内容#xff0c;顺便就转贴到俺在CSDN的镜像博客。 昨天…★引子 前天俺在《俺的招聘经验[4]通过笔试答题能看出啥》一文以求质数作为例子介绍了一些考察应聘者的经验。由于本文没有政治敏感内容顺便就转贴到俺在CSDN的镜像博客。 昨天某个CSDN网友在留言中写道 老实说,这个程序并不好写,除非你背过这段代码 如果只在纸上让别人写程序,很多人都会出错 但是如果给一台电脑,大多数人都会把这个程序调试正确 出这个题目没啥意义 只能让别人觉得你出题水平低 首先这位网友看帖可能不太仔细。俺在文中已经专门强调过了评判笔试答题思路和想法远远比对错更重要而他/她依然纠结于对错其次这位网友居然觉得这道题目没啥意义这让俺情何以堪啊看来有相当一部分网友完全没有领略到此中之奥妙啊 算了俺今天就豁出去了给大伙儿抖一抖这道题目的包袱。当然抖包袱的后果就是从今天开始就得把求质数这道题从俺公司的笔试题中去掉然后换上另外一道全然不同的。这么好的一道题要拿掉真是于心不忍啊 :-( ★题目 好言归正传。下面俺就由浅入深从各种角度来剖析这道题目的奥妙。 为了避免被人指责为玩文字游戏有些同学自己审题不细却抱怨出题的人玩文字游戏在介绍各种境界之前再明确一下题意。 前一个帖子已经介绍过求质数可以有如下2种玩法。 ◇需求1 请实现一个函数对于给定的整型参数 N该函数能够把自然数中小于 N 的质数从小到大打印出来。 比如当 N 10则打印出 2 3 5 7 ◇需求2 请实现一个函数对于给定的整型参数 N该函数能够从小到大依次打印出自然数中最小的 N 个质数。 比如当 N 10则打印出 2 3 5 7 11 13 17 19 23 29 ★试除法 首先要介绍的当然非试除法莫属啦。考虑到有些读者是菜鸟稍微解释一下。 试除顾名思义就是不断地尝试能否整除。比如要判断自然数 x 是否质数就不断尝试小于 x 且大于1的自然数只要有一个能整除则 x 是合数否则x 是质数。 显然试除法是最容易想到的思路。不客气地说也是最平庸的思路。不过捏这个最平庸的思路居然也有好多种境界。大伙儿请看 ◇境界1 在试除法中最最土的做法就是 假设要判断 x 是否为质数就从 2 一直尝试到 x-1。这种做法其效率应该是最差的。如果这道题目有10分按照这种方式做出的代码即便正确无误俺也只给1分。 ◇境界2 稍微聪明一点点的程序猿会想x 如果有除了自身以外的质因数那肯定会小于等于 x/2所以捏他们就从 2 一直尝试到 x/2 即可。 这一下子就少了一半的工作量哦但依然是很笨的办法。打分的话即便代码正确也只有2分 ◇境界3 再稍微聪明一点的程序猿会想了除了2以外所有可能的质因数都是奇数。所以他们就先尝试 2然后再尝试从 3 开始一直到 x/2 的所有奇数。 这一下子工作量又少了一半哦。但是俺不得不说依然很土。就算代码完全正确也只能得3分。 ◇境界4 比前3种程序猿更聪明的就会发现其实只要从 2 一直尝试到√x就可以了。估计有些网友想不通了为什么只要到√x 即可 简单解释一下因数都是成对出现的。比如100的因数有1和1002和504和255和2010和10。看出来没有成对的因数其中一 个必然小于等于100的开平方另一个大于等于100的开平方。至于严密的数学证明用小学数学知识就可以搞定俺就不啰嗦了。 ◇境界5 那么如果先尝试2然后再针对 3 到√x 的所有奇数进行试除是不是就足够优了捏答案显然是否定的嘛写到这里才刚开始热身哦。 一些更加聪明的程序猿会发现一个问题尝试从 3 到√x 的所有奇数还是有些浪费。比如要判断101是否质数101的根号取整后是10那么按照境界4需要尝试的奇数分别是3579。但是你发现 没有对9的尝试是多余的。不能被3整除必然不能被9整除......顺着这个思路走下去这些程序猿就会发现其实只要尝试小于√x 的质数即可。而这些质数恰好前面已经算出来了是不是觉得很妙。 所以处于这种境界的程序猿会把已经算出的质数先保存起来然后用于后续的试除效率就大大提高了。 顺便说一下这就是算法理论中经常提到的以空间换时间。 ◇补充说明 开头的4种境界基本上是依次递进的。不过境界5跟境界4是平级的。在俺考察过的应聘者中有人想到了境界4但没有想到境界5反之也有人想到境界5但没想到境界4。通常这两种境界只要能想到其中之一俺会给5-7分如果两种都想到了俺会给8-10分。 对于俺要招的初级软件工程师的岗位能同时想到境界4和境界5应该就可以了。如果你对自己要求不高仅仅满足于浅尝辄止。那么看到这儿你就可以打住了无需再看后续的内容反之如果你比较好奇或者希望再多学点东西请接着往下看。 ★筛法 说完试除法再来说说筛法维基百科的解释在这里。俺不妨揣测一下本文的读者应该有2/3以上从来没有听说过筛法。所以捏顺便跟大伙儿扯扯蛋聊一下筛法的渊源。 这个筛法啊真的是一个既巧妙又快速的求质数方法。其发明人是公元前250年左右的一位希腊大牛——埃拉托斯特尼。为啥说他是大牛捏因为他本人精通多个学科和领域至少包括数学、天文学、地理学地理学这个词汇就是他创立的、历史学、文学他是一个诗人。真的堪称跨领域的大牛。 他最让俺佩服的是仅仅用简单的几何方法测量出了地球的周长、地球与月亮的距离、地球与太阳的距离、赤道与黄道的夹角......而且这些计算结 果跟当代科学家测出的相差无几。要知道他生活的年代大概相当于中国的春秋战国。而咱们的老祖宗一直到明朝还顽固地坚信天是圆的、地是方的、月亮会 被天狗给吃喽...... 好了扯蛋完毕言归正传。 估计很多人把筛法仅仅看成是一种具体的方法。其实筛法还是一种很普适的思想。在处理很多复杂问题的时候都可以看到筛法的影子。那么筛法如何求质数捏说起来很简单 首先2是公认最小的质数所以先把所有2的倍数去掉然后剩下的那些大于2的数里面最小的是3所以3也是质数然后把所有3的倍数都去掉剩下的那些大于3的数里面最小的是5所以5也是质数...... 上述过程不断重复就可以把某个范围内的合数全都除去就像被筛子筛掉一样剩下的就是质数了。维基百科上有一张很形象的动画能直观地体现出筛法的工作过程。 明白了筛法的原理大伙儿应该看出筛法在速度上是明显优于试除法的。当然筛法的程序实现也分为不同的境界。而且筛法可讲究的门道更多了。下面俺分别从不同角度聊一聊筛法都有哪些讲究。 ◇如何确定质数的分布范围 这是采用筛法首先会碰到的问题。文本开头给出的那两种需求其处理的方式完全不同俺分别说一下。需求1 对于需求1这个自然不是问题。因为在需求1中质数的分布范围就是 N已经给出了很好办。需求2 但是对于需求2就难办了。因为需求2给出的 N表示需要打印的质数的个数那么这 N 个质数会分布在多大的范围捏这可是个头疼的问题啊。 但是来应聘的程序猿如果足够牛的话当然不会被这个问题难倒。因为素数的分布是有规律可循滴——这就是大名鼎鼎的素数定理。 稍微懂点数学的应该知道素数的分布是越往后越稀疏。或者说素数的密度是越来越低。而素数定理说白了就是数学家找到了一些公式用来估计某个范围内的素数大概有几个。在这些公式中最简洁的就是x/ln(x)公式中的 ln 表示自然对数估计很多同学已经忘了啥叫自然对数。假设要估计1,000,000以内有多少质数用该公式算出是72,382个而实际有78,498个误差约8个百分点。该公式的特点是估算的范围越大偏差率越小。 有了素数定理就可以根据要打印的质数个数反推出这些质数分布在多大的范围内。因为这个质数分布公式有一定的误差通常小于15%。为了保险起见把反推出的素数分布范围再稍微扩大15%应该就足够了。 可能有同学会质疑俺谁有这么好的记性能够在笔试过程中背出这些质数分布公式捏 俺觉得背不出来是正常滴。但是对于有一定数学功底的应聘者假如他/她知道质数分布公式即便不能完整写出来只要在答题中体现出此处通过质数分布公式推算范围那么俺也是认可滴。 再啰嗦一次关键是看idea ◇如何设计存储容器 知道了分布范围接下来就得构造一个容器来存储该范围内的所有自然数然后在筛的过程中把合数筛掉。那么这个容器该如何设计捏不同层次的程序猿自然设计出来的容器也不同啦。境界1 照例先说说最土的搞法——直接构造一个整型的容器。在筛的过程中把发现的合数删除掉最后容器中就只剩下质数了。 为啥说这种搞法最土捏 首先整型的容器浪费内存空间。比方说你用的是32位的C/C或者是Java那么每个 int 都至少用掉4个字节的内存。当 N 很大时内存开销就成问题了。 其次当 N 很大时频繁地对一个大的容器进行删除操作可能会导致频繁的内存分配和释放具体取决于容器的实现方式而频繁的内存分配/释放会导致明显的CPU占用并可能造成内存碎片。境界2 为了避免境界1导致的弊端更聪明的程序猿会构造一个定长的布尔型容器通常用数组。比方说质数的分布范围是1,000,000那么就构造一个 包含1,000,000个布尔值的数组。然后把所有元素都初始化为 true。在筛的过程中一旦发现某个自然数是合数就以该自然数为下标把对应的布尔值改为 false。 全部筛完之后遍历数组找到那些值为 true 的元素把他们的下标打印出来即可。 此种境界的好处在于其一由于容器是定长的运算过程中避免了频繁的内存分配/释放其二在某些语言中布尔型占用的空间比整型要小。比如C的 bool 仅用1字节 注C标准ISO/IEC 14882没有硬性规定 sizeof(bool)1但大多数编译器都实现为一字节。境界3 虽然境界2解决了境界1的弊端但还是有很大的优化空间。有些程序猿会想出按位bit存储的思路。这其实是在境界2的基础上优化了空间性能。俺觉得C/C出身的或者是玩过汇编语言的比较容易往这方面想。 以C为例。一个bool占用1字节内存。而1个字节有8个比特每个比特可以表示0或1。所以当你使用按位存储的方式一个字节可以拿来当8个 布尔型使用。所以达到此境界的程序猿会构造一个定长的byte数组数组的每个byte存储8个布尔值。空间性能相比境界2提高8倍对于C而 言。如果某种语言使用4字节表示布尔型那么境界3比境界2空间利用率提高32倍。 ★总结 看到俺写总结二字很多网友心想总算看完了知道该怎么求质数才是最优的了。 其实你们又错了本文才写了不到一半。考虑到篇幅已经有点长而且俺打了这么多字也有点累了暂时刹住话匣子下次接着聊。 希望看了今天这个介绍大伙儿应该明白一个道理山外有山、天外有天。每一个技术领域里面的每一个细小的分支深究下去都有很多的门道与奥妙。在你深究的过程中必然会学到很多东西。深究的过程也就是你能力提高的过程。 本文后续的内容会介绍刚才提到的按位存储法还有哪些缺陷该如何解决。另外还会介绍其它一些求质数的方法。 版权声明 本博客所有的原创文章作者皆保留版权。转载必须包含本声明保持本文完整并以超链接形式注明作者编程随想和本文原始地址http://program-think.blogspot.com/2011/12/prime-algorithm-1.html转载于:https://www.cnblogs.com/end/archive/2013/05/08/3067117.html
