95年地方特考計算機概論(演算法) - 特考

※ 引述《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]
就是我們要找的

--

--