作者wope (独立黑色色彩)
看板Examination
标题Re: [考题] 95年地方特考计算机概论(演算法)
时间Wed May 8 16:45:07 2013
※ 引述《jokeking (笑话王)》之铭言：
: 各位大大好~~
: 小弟想问一下演算法的问题
: 95年地特，计概的第四题
: http://wwwc.moex.gov.tw/ExamQuesFiles/Question/095/024333500.pdf
: 请设计一个演算法来产生只可以被5及 7整除的数列 5, 7, 25, 35, 49, 125, 175,
: 245, 343, …, M, M<10^9
: 我看鼎茂的解答，看得不知所匀 Orz
: 我另外google找答案，知识+有人问，也有人回答
: 但回答主要写程式码，小弟太浅看不懂 QQ
: http://tw.knowledge.yahoo.com/question/question?qid=1507011709814
: 能否请各位高手帮小弟解惑，用文字解释一下该怎麽得到这串数列
: 话说这题再考机会也不高，不会也就算了，不过有点兴趣想知道怎麽作就是了..
: 先谢谢各位高手~
刚刚想到有一个算法
先设这个数列为
Zi={Z0,Z1,Z2,....Zn}
可以想成 Z0=5, Z1=7, Z2=25....
因为只能被5与7整除
所以Zi=(5^a)*(7^b) 其中a,b为整数
再来求a的最大值为a_max
int a_max=0 //宣告a_max
while(pow(5.0,a_max)<pow(10.0,9)){a_max++;}//找到第一个超过10^9的a_max
再来求b的最大值b_max
int b_max=0 //宣告b_max
while(pow(7.0,b_max)<pow(10.0,9)){b_max++;}//找到第一个超过10^9的b_max
此数列最长的长度为i_max
int i_max=(a_max+1)(b_max+1);
所以可以造出Zi矩阵的长度
int*Z[i_max]=0; //这里要注意在GCC 下可以这样写
//如果在VC下要用malloc最後要记得free
把有可能的都计录下来
int i_r=0;//实际的个数
int TempZ;
for(int ai=0,ai<a_max;ai++){
for(int bi=0;bi<n_max;bi++){
TempZ=pow(5.0,ai)*pow(7.0,bi);
if(TempZ<pow(10.0,9)){
Z[i_r]=TempZ;
}//小於10^9的记录下来
}
}
最後我们在Z方向排序就可以了
int Change=1;//记录交换次数
while(Change>0){
Change=0;//重新记录
for(int i=0;i<i_r;i++){
if(Z[i]>Z[i+1]){ //排序的条件
TempZ=Z[i];
Z[i]=Z[i+1];
Z[i+1]=TempZ;
Change++;
}
}
}
排完了所以现在
Z[0],Z[1],...Z[i_r-1]
就是我们要找的
--
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.133.104.111
※ 编辑: wope 来自: 220.133.104.111 (05/08 16:45)
1F：→ carterdunk:没规定复杂度 直接用回圈和mod就解决这题了 05/08 16:47
※ 编辑: wope 来自: 220.133.104.111 (05/08 16:47)
刚刚做了一些效率分析要找小於N的数(本题N=10^9)
本法的时间复杂度为O((Log(N)/Log(5))^2)
暴力法时间复杂度为O(N)
所以
暴力法要花的时间为 k1*N
本法要花的 K2*(Log(N)/Log(5))^2
因为本法比较多的判断所以K2>k1
那就先设k2/k1=1000000 (当然不可能慢那麽多)
=> N=2时
暴力法速度比较快
约为本法的10^5倍
=> N=10^9(本题)
本法速度为暴力法的6.03倍
量大时还是不能用暴力法
※ 编辑: wope 来自: 140.112.4.189 (05/10 08:11)