标签归档：名题

　　在用“筛法”求素数时，每次筛除素数的动作，其实有很多是重复的！比如，如果一个数是3*5*7*9，那么删除的时候，它会被作为3的倍数，5的倍数，7的倍数，9的倍数，被重复判断删除4次。类似的，较大的数有较多的因数，那么，删除它所耗费的时间会很多！如何来优化“筛法”的算法，使之不重复呢？ 　　思路如下：从2开始，先删除2²，2³，2³，···，接着删除2·3，2²·3，2³·3，···，而此时并不删除3。再删除2·5，2²·5，2³·5，···，接下来2·7，2²·7，2³·7，···。一般而言，当发现p是一个素数时，先删除p²，p³，p³，···这一系列合数。因为p是素数，所以p²，p³，p³，···不可能被其它数整除。接着，找出比p大，但是第一个没有被删除的数q。再删除p·q，p²·q，p³·q，···。因为p是素数，q为目前为止未删除。所以p^¡·q之前也没有被删除。

　　如果整数 n ≠ 0，±1。如果除了显然因数 ±1 和 ±n 以外，n没有其他因数，那么 n 叫做素数。如：2，3，5，7是素数，4，6，10，15是合数。 　　根据素数的性质，有这样的定理：1、设 n 是一个正合数，p 是 n 的一个大于1的最小正因数，则 p 一定是素数。2、设 n 是一个正整数，如果对所有的素数 p ≤ √n，都有 p 不整除 n，则 n 一定是素数。 　　根据两条定理，可以得到寻找素数的群定性方法，通常叫做 埃拉托斯散筛法。 　　筛法具体描述如下：对于任意给定的整数 N ，要求出所有不超过 N 的素数。列出 N 个整数，从中删除小于等于√n的所有素数p1, …, pk的倍数。然后依次删除余下的整数（不包括1）就是所要求的不超过 N … 继续阅读 →

　　假设有一个数组x[]，它有n个元素，每一个都大于零，称x[0]+x[1]+…+x[i]为前置和(Prefix_Sum)，而x[j]+x[j-1]+…+x[n-1]为后置和(Suffix_Sum)。写一个程序，求出数组x[]中有多少组相同的前置和与后置和！ 　　如果x[]的元素是3,6,2,1,4,5,2，于是x[]的前置和有以下7个，即3,9,11,12,16,21,23，而后置和有2,7,11,12,14,20,23;于是11,12与23这3对就是值相同的前置和与后置和，因为：11=3+6+2=2+5+4, 12=3+6+1=2+5+4+1。而23是整个数组的和，所以前置和与后置和相同。 　　

　　题目：已知两个元素从小到大排列的数组x[]与y[]，请编写一个程序算出两个数组元素间彼此之间的绝对值中最小的一个数，此值叫做数组的最短距离！

　　题目：给定两个由递增排序好的数组，找出他们有多少等值对。如f[]:1,2,3,5,7,8和g[]:2,3,7,8有四对相等的值，所以答案为4。 　　分析：要写出好的算法还是要充分利用数组已排序好这一特性！因为两个数组都已经排序好！如果f[i]g[j]，则将g[j+1]与f[i]比较！否则它们相等，总数累加后，两个数组都向后比较。这样一来，当其中一个数组的元素被访问完时，则得到答案！其实比较的过程是两个数组一上一下，轮流向前推进的过程！ 　　

　　题目：给定两个排序好的数组f[]和g[]，计算满足f[i]>g[j]的对数！如f：2，3，5，7，9和g：1，2，4，6，7中，2>1,3>1,3>2,5>1,5>2,5>4,7>1,7>2,7>4,7>6,9>7,9>6,9>4,9>2,9>1！有15组这样的关系，所以答案为15。 　　老规矩，尽量使代码简短！最少的元素访问次数！ 　　本题的关键在于，利用数组排序好的性质！思路如下：f[i]大于g[j]，则f[i]后面的元素都大于g[j]。利用一个变量count来记录满足大于关系的对数，如果f[i]>g[j]时，count增加f中i后的元素个数，并将j后移，否则将i后移，拿f中更大的元素与当前g[j]比较！这样一来，当访问完其中一个数组的元素时，便得出了答案！没有必要将两个数组都走一遍！