本文共 2053 字,大约阅读时间需要 6 分钟。
最后几个题有点难度,在这里说一下:
永成科技C++笔试题
2013-11-19 1.将1亿以内的质数存到一个超级大的数组中,用算法如何实现? 使用"筛法"求解1亿以内的质数的程序的思路: 先动态分配1亿个bit(总计12500000字节),用字节中的每一位代表每一个整数,首先将代表奇数的那些bit位置1,也就是代表偶数(合数)的位,接着再进一步从这些奇数位中筛掉合数. 筛掉合数的方法是,先从100000000(1亿)的开方10000范围内的质数i(3,5,7,11,13,17,19,23,29)开始,去找它在1亿内的奇数倍数i*i,i*i+2i,i*i+4i,...,这里 没有i*i+i是因为它可以写成(i+1)i是2的倍数,已经被过滤掉,将代表这些合数的bit位置0, 那么最后剩下的bit为1的那些bit,就是代表质数的,统计出它们的个数就可以了. 这样做的原理是,基于如下的事实: (1)任意连续的6个数中,就只会测试2个而已,以6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5为例,只需测试6n+1和6n+5, 工作量减少到1/3 (2)判断一个数i是否是素数的话,只需要测试2->sqrt(i)之间的质数就可以了 理由如下: 按素数的定义,也就是只有 1 与本身可以整除,所以可以用 2→i-1 去除 i,如果都除不尽,i 就是素数。观点对,但却与上一点一样的笨拙。当 i>2 时,有哪一个数可以被 i-1 除尽的?没有!为什么?如果 i 不是质数,那么 i=a×b,此地 a 与 b 既不是 i 又不是 1;正因为 a>1,a 至少为 2,因此 b 最多也是 i/2 而已,去除 i 的数用不着是 2→i-1,而用 2→i/2 就可以了。不但如此,因为 i=a×b,a 与 b 不能大于 sqrt(i),为什么呢?如果 a>sqrt(i),b>sqrt(i),于是 a×b > sqrt(i)*sqrt(i) = i,因此就都不能整除i了。如果i不是质数,它的因子最大就是 sqrt(i);换言之,用 2→sqrt(i)去检验就行了 但是,用 2→sqrt(i) 去检验也是浪费。就像前面一样,2 除不尽,2 的倍数也除不尽;同理,3 除不尽,3 的倍数也除不尽……最理想的方法就是用质数去除i。 如果只检查 6n+1 和 6n+5 ?不难发现,它们的距离是4、2、4、2……所以,可以先定义一个变量 gab=4,然后 gab=6-gab; (3)不能用开方而应该用平方 比较是不能用 sqrt(i),因为它不精确。举个例子,i=121,在数学上,sqrt(i) 自然是 11,但计算机里的结果可能是 10.9999999,于是去除的数就是 2、3、5、7,而不含 11,因此 121 就变成质数了。解决这个问题的方法很简单,不要用开方,用平方即可。例如,如果 p*p<=i,则就用 p 去除 i。而且它的效率比开方高。 为此需要先将2,3,5,7,11,13这样的质数先定位到32bit长度的整数内,这个整数的四字节中的每个字节是10101010,将这个质数放到32bit中的唯一一个bit位上面. 最后计算的结果是5761455个素数,而且程序用时9.375秒 下面是一个老外提供的实现代码,但是我们还有比这个更高效的处理://Platform: Ubuntu 12.04.3 64bit//gcc -std=c99 -g primer_demo.c -o primer_demo#include2.二叉树求值? 要求使用递归和循环这两种方法实现. 3.设计简单的文本编辑器,写出架构设计及思路?#include #include #include int count(unsigned int a) //统计每个整数中的非0位个数,也就是素数的个数(素数没被筛掉,相对应位为1){ int sum = 0; for (unsigned int x=a; x; x>>=1) //x不断作右移运算 { if (x & 1) //x与1作与运算 sum++; } return sum;}void sieve(unsigned int* p) //筛选法求1亿以内素数{// for(int i=2;i<=10000;i++)// for (int i=3; i<=10000; i+=2) //只筛选奇数显然快于原算法 for(int istep=4,i=3; i < 10000 ;i+=(istep^0x6)) //进一步优化,%6余1和5时才可能是素数,即只检查交替相隔2和4的数 { if (p[i/32] & (1<
转载地址:http://qzcoi.baihongyu.com/