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

由几个问题看搜索中内存的使用畅明00348274Cs03-2程序中内存的大小及分配•总内存的限制：1000KorHigher–程序自身：100~200K；–普通变量：lessthan1K；–系统栈：单参数无变量函数递归到11K层但每一次调用使用较大内存(至少10B)–临时状态区：搜索中占内存较多Q1：超级素数•一个至少二位的素数，如果每次去掉最高位后还是一个素数，直到一个一位数，则称其为超级素数。•例如：223-23-3；•求出所有小于N的超级素数。解法：•1：直接搜索：11~max，穷举•2：直接构造：2-23-223•3：构造素数表检索：–常规；–动态规划；构造素数表检索：动态规划•常规过程：–构造素数表；–从最小数检索；–折半搜索一个数去最高位后是否还在表中，直至只有一位。•动态规划：–任何一个三位或更高阶超级素数去掉最高位后还是一超级素数(有点像构造了)。Q1总结•直接搜索：最慢，内存占用为零；•构造：时间短，但需要考虑清构造方法，防止结果不全；•素数表搜索：时间短，速度较快，结果全，但搜索范围受素数数组的牵制(在第二题中讨论)，且制备素数数组要花时间(由于范围要尽可能的大，数组要利用好，常规筛法显然不行；但常规方法优化后速度也不错)varI,j,sqrti:integer;s[MAX]ofinteger;ok:boolean;{s[1]:=2;s[2]:=3;count:=2;i:=5;whilei=max-1do{j:=2;ok:=true;sqrti=trunc(sqrt(i));whiles[j]=sqrtido{ifimods[j]=0thengoto1;inc(j)elsegoto1;}inc(count);s[count]:=i;1:inc(i,2);}}局部筛法•常规筛法不行时，可以分部分使用筛法，然后存在另一个数组里。Q2：完全数及类似问题•完全数：一个正数所有因子的和等于自身(包括1，不包括自身)，就是一个完全数。•求小于N的完全数•6=1+2+3•28=1+2+4+7+14解法：•1：直接搜索：•2：构造数表检索：–选一数组，全置为一，然后I由2到max/2循环，每次给I的整数倍加上I，直到此整数倍超过max；–检查以上数组，如果一个位置上的结果等于位置，此数为完全数。派生题：•Q2-1：两个数的因数之和分别等于对方，求这样的完全数对；•Q2-2：五个数排成一队，每个数的因数和各等于下一个数，最后一个的等于第一个数，求这样的数列；•这两题用此方法可大大减小时间复杂度，特别是Q2-2。Q2解法2的缺陷与解决•解法二的时间复杂度极低(ms级算到30K)，但对空间要求极高，若要求算到231(2G)，显然不行；•这时我们要用时间换空间：–设立数组[max_len]，及其偏移量shift，每次用此数组计算从shift到shift+max_len之间的完全数。•注意：–max_len要尽可能的大：•Shift变大后，从一加一遍的代价也较高，max_len较大可以减少加的次数；这里的时间可以换空间，但不能过头，因为最开始搜索时是用空间换的时间；–最好是整片的数(e.g.:30K)，这样有利于编程和调试遗留问题：•大范围情况下，Q2-1与Q2-2的低时间复杂度解法尚未解决；•欢迎大家讨论。谢谢