Re: [考題] 95年地方特考計算機概論(演算法)

看板Examination (國家考試)作者wope (獨立黑色色彩)時間13年前 (2013/05/08 16:45)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串2/4 (看更多)

※ 引述《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)

→

carterdunk

05/08 16:47, , 1^F

05/08 16:47, 1^F

※ 編輯: 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)