永成科技C++笔试题

首页 > 永成科技C++笔试题

永成科技C++笔试题

最后几个题有点难度,在这里说一下:

永成科技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
#include 
#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<




 


 


 


 


 2.二叉树求值?


 要求使用递归和循环这两种方法实现.


 


 


 3.设计简单的文本编辑器,写出架构设计及思路?


            
                
                    更多相关：
                    
                        
                    
                        java 读取excel_Java12POI操作Excel
                    
                    
                        
                                    Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...
                            
                        
                    
				

                    
                        C++ 生成随机数
                    
                    
                        
                            要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 
要取得a到b之间的...
                            
                        
                    
				

                    
                        基于C++的本征图像分解(Intrinsic Image Decomposition)
                    
                    
                        
                            利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。
Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...
                            
                        
                    
				

                    
                        剑指offer：面试题39. 数组中出现次数超过一半的数字
                    
                    
                        
                            题目：面试题39. 数组中出现次数超过一半的数字 
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 
你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
示例 1: 
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2 
限制： 
1 <= 数组长度 <= 50000 

解题： 
cl...
                            
                        
                    
				

                    
                        剑指offer：面试题33. 二叉搜索树的后序遍历序列
                    
                    
                        
                            题目：二叉搜索树的后序遍历序列 
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
参考以下这颗二叉搜索树： 
     5     /     2   6   /   1   3示例 1： 
输入: [1,6,3,2,5]
输出...
                            
                        
                    
				

                    
                        ACM_求N^N的前5位数和后5位数（数论）
                    
                    
                        
                            NNNNN   Time Limit: 2000/1000ms (Java/Others)   Problem Description: 对于整数N，求N^N的前5位和后5位（1057题加强版)   Input: 多组测试数据，每组测试数据输入为一个整数n（6 <= n <= 10^9），n为0时结束。   Output: 对每组...
                            
                        
                    
				

                    
                        数字特征值
                    
                    
                        
                            题目内容： 对数字求特征值是常用的编码算法，奇偶特征是一种简单的特征值。对于一个整数，从个位开始对每一位数字编号，个位是1号，十位是2号，以此类推。这个整数在第n位上的数字记作x，如果x和n的奇偶性相同，则记下一个1，否则记下一个0。按照整数的顺序把对应位的表示奇偶性的0和1都记录下来，就形成了一个二进制数字。比如，对于342315...
                            
                        
                    
				

                    
                        NYOJ 90 —— 求正整数n划分为若干个正整数的划分个数
                    
                    
                        
                            整数划分 时间限制：3000 ms  |  内存限制：65535 KB 描述  将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，...