Calling Extraterrestrial Intelligence Again.ppt

《Calling Extraterrestrial Intelligence Again.ppt》由会员分享，可在线阅读，更多相关《Calling Extraterrestrial Intelligence Again.ppt（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Calling Extraterrestrial Intelligence AgainPOJ 1411王栋2007.11.14问题问题抽象抽象Input：给定3个整数m、a、b，其中 4 m=100000 1=a=b=1000 Output：找到两个数p和q，满足以下条件：p和q均为质数p*q=ma/b=p/q=1要求p*q最大！问题问题分析分析一个搜索问题计算出100000内的所有质数，保存到数组对所有可能的质数对且p=q=100000判断是否符合题设条件，如果是，则计算p*q并更新最大值，记录此时的值两层循环第一层枚举p第二层枚举qThe Sieve of Eratosthenes埃拉托色

2、尼筛选法埃拉托色尼筛选法2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 x x x x x x x x 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 x x x x x x x x x x迭代进行上述过程最后剩下的没有被mark的就是质数100000以内有9592个质数getpri()int pri9592,cp;void getpri()bool ispri100000;for(int i=0;i 100000;i+)isprii=true;ispri0=ispri1=false;for(i=2;i=1

3、00000)break;ispritmp=false;j+;cp=0;for(i=2;i 0)mx=0;for(i=cp-1;i=0;i-)if(prii m)continue;for(j=i;j m|prij*prii m|a*prijb*prii)break;if(prij*prii mx)mx=prii*prij;p=prii;q=prij;printf(%d%dn,p,q);Time Limit Exceeded简简化化问题问题从题设条件：a/b=p/q=1p*q=m1=a=b=1000 可以推出：p=q=10000原来只要求10000以内的质数！Accepted 76K 3146MS

4、继续简继续简化化问题问题从题设条件：a/b=p/q=1p*q=m4 m=100000可以推出：p sqrt(m)p 317Accepted 76K 1531MSq的上限的上限从题设条件：a/b=p/q=1p*q=m可以推出：p=q=min(m/p,b*p/a)利用利用q的上限的上限进进行行优优化化如何利用q的上限：枚举p，并计算q的上限max_q=min(m/p,b*p/a)求出不大于max_q的最大质数。用此时的p*q更新最大值如何求出不大于max_q的最大质数：线性查找二分查找空空间换时间：生成不大于：生成不大于i的最大的最大质数数数数组，常数，常数时间找到不大于找到不大于i的最大的最大质

5、数。空数。空间占用有些大，占用有些大，时间一般是一般是0ms.利用利用q的下限的下限进进行行优优化化由题设条件：a/b=p/q=1p*q=m可以推出q=sqrt(m*b/a)p max且psqrt(max)两两层循循环第一第一层从上限从上限sqrt(m*b/a)向下枚向下枚举q，q的下限的下限为sqrt(max)第二第二层从上限从上限 m/q向下枚向下枚举p，即不大于，即不大于m/q的最大的最大质数数pp*q更新最大更新最大值max，q的下限的下限sqrt(max)也随之更新。也随之更新。时空效率都很好：空效率都很好：00648241 80k 0ms，本次作，本次作业最最优！另一种另一种实现实

6、现不预先计算10000以内的质数数组bool isPrime(int t)int mid=sqrt(t);for(int i=2;i 0)mx=0;for(i=317;i=2;i-)if(isPrime(i)for(j=min(m/i,i*b/a);j=i;j-)if(isPrime(j)if(i*j mx)mx=i*j;p=i;q=j;break;printf(%d%dn,p,q);空间优势不大，时间效率较低，空间优势不大，时间效率较低，120ms+作作业业中的中的问题问题1.没有根据题设条件简化问题导致时空效率低。2.没有有效剪枝，比如：for(j=i;primei*primej=m;j+

7、)if(a*primejmax)max=primei*primej;maxp=primei;maxq=primej;改为 if(a*primej b*primei)break;可以由128ms 优化到 31ms作作业业中的中的问题问题 const.3.除法 vs.乘法乘法慢，除法更慢(double)a/b(double)primei/primej)改为(a*primejb*primei)后，由188k 140ms 提升为 136 93MS 实际编程中乘除法要小心溢出，某些时候可以取log。4.报告、代码、注释一个都不能少，更不要只交一个pdf。5.提交AC的代码，很多同学提交的代码需要我修改后才能AC。6.即使不求0ms，也不要TLE或者1000ms。7.空间换时间，不是什么时候都好。Thank you！