由几个问题看搜索中内存的使用

1、由几个问题看搜索中内存的使用畅明Cs03-21程序中内存的大小及分配总内存的限制：1000K or Higher程序自身：100200K；普通变量：less than 1K；系统栈：单参数无变量函数递归到 11K层但每一次调用使用较大内存(至少 10B)临时状态区：搜索中占内存较多 2Q1：超级素数一个至少二位的素数，如果每次去掉最高位后还是一个素数，直到一个一位数，则称其为超级素数。例如：223-23-3；求出所有小于 N 的超级素数。3解法：1：直接搜索：11max ，穷举2：直接构造：2-23-2233：构造素数表检索：常规；动态规划；4构造素数表检索：动态规划常规过程：构造素数表；从最

2、小数检索；折半搜索一个数去最高位后是否还在表中，直至只有一位。动态规划：任何一个三位或更高阶超级素数去掉最高位后还是一超级素数 (有点像构造了)。5Q1总结直接搜索：最慢，内存占用为零；构造：时间短，但需要考虑清构造方法，防止结果不全；素数表搜索：时间短，速度较快，结果全，但搜索范围受素数数组的牵制(在第二题中讨论)，且制备素数数组要花时间(由于范围要尽可能的大，数组要利用好，常规筛法显然不行；但常规方法优化后速度也不错 )6var I , j , sqrti: integer;s MAX of integer;ok : boolean;s1:=2;s2:=3;count:=2; i:=5;w

3、hile i=max-1 doj:=2;ok:=true; sqrti= trunc ( sqrt(i) );while s j= sqrti doif i mod s j=0 then goto 1;inc (j) else goto 1;inc (count);s count:=i;1:inc(i,2);7局部筛法常规筛法不行时，可以分部分使用筛法，然后存在另一个数组里。8Q2：完全数及类似问题完全数：一个正数所有因子的和等于自身(包括1，不包括自身)，就是一个完全数。求小于 N 的完全数6=1+2+328=1+2+4+7+149解法：1：直接搜索：2：构造数表检索：选一数组，全置为一，然

4、后 I 由 2 到 max/2 循环，每次给 I 的整数倍加上 I，直到此整数倍超过 max；检查以上数组，如果一个位置上的结果等于位置，此数为完全数。10派生题：Q2-1：两个数的因数之和分别等于对方，求这样的完全数对；Q2-2：五个数排成一队，每个数的因数和各等于下一个数，最后一个的等于第一个数，求这样的数列；这两题用此方法可大大减小时间复杂度，特别是 Q2-2。11Q2 解法 2 的缺陷与解决解法二的时间复杂度极低(ms级算到30K)，但对空间要求极高，若要求算到 231 (2G)，显然不行；这时我们要用时间换空间：设立数组max_len，及其偏移量 shift，每次用此数组计算从 shift 到 shift + max_len 之间的完全数。12注意：max_len 要尽可能的大：Shift 变大后，从一加一遍的代价也较高，max_len较大可以减少加的次数；这里的时间可以换空间，但不能过头，因为最开始搜索时是用空间换的时间；最好是整片的数(e.g.: