作者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)