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

《由几个问题看搜索中内存的使用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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

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

3、arI,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

4、：完全数及类似问题完全数：一个正数所有因子的和等于自身(包括1，不包括自身)，就是一个完全数。求小于N的完全数6=1+2+328=1+2+4+7+14解法：1：直接搜索：2：构造数表检索：选一数组，全置为一，然后I由2到max/2循环，每次给I的整数倍加上I，直到此整数倍超过max；检查以上数组，如果一个位置上的结果等于位置，此数为完全数。派生题：Q2-1：两个数的因数之和分别等于对方，求这样的完全数对；Q2-2：五个数排成一队，每个数的因数和各等于下一个数，最后一个的等于第一个数，求这样的数列；这两题用此方法

5、可大大减小时间复杂度，特别是Q2-2。Q2解法2的缺陷与解决解法二的时间复杂度极低(ms级算到30K)，但对空间要求极高，若要求算到231(2G)，显然不行；这时我们要用时间换空间：设立数组[max_len]，及其偏移量shift，每次用此数组计算从shift到shift+max_len之间的完全数。注意：max_len要尽可能的大：Shift变大后，从一加一遍的代价也较高，max_len较大可以减少加的次数；这里的时间可以换空间，但不能过头，因为最开始搜索时是用空间换的时间；最好是整片的数(e.g.:30K)

6、，这样有利于编程和调试遗留问题：大范围情况下，Q2-1与Q2-2的低时间复杂度解法尚未解决；欢迎大家讨论。谢谢