作者waterdisney (飛過鷹族的訕笑)
看板TransCSI
標題Re: [問題] 找出所有因數的演算法
時間Thu Dec 7 00:10:51 2006
※ 引述《dgf130 (JoyChen)》之銘言：
: ※ 引述《buoyance (buoyance)》之銘言：
: : design an algorithm for finding all the factors of a positive integer
: factors( int num )
: {
: printf("%d factors are ",num);
: for( int i = 1; i <= num; i++ )
: if( num%i )
: printf( "%d, ",i );
: }
: 就檢查1~自己本身的數能不能整除就好啦～應該不難
dgf130說的是一種作法。
可是如果真的這樣寫，時間複雜度為 O(n)
一般來說，for迴圈的條件終止式可檢查至 sqrt(n) 即可。
即 for(int i=1;i<=
sqrt(n);i++){
if(num % i){
printf("%d,%d",num,n/num);
}
}
sqrt(n)的意思是 「對n取根號」
另外。此種寫法，仍不盡理想。
最好的作法為利用dynamic programming
採動態填表的方式求n的所有因數。
如此於程式重複執行時，可不用重複計算之前已經做過的檢查..
至於dynamic programming怎麼寫...
這個..翻書比較快。bbs講不清楚。 XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.233.70.185
1F：推 dgf130:因為題目說是找一個正整數的所有因數..所以應該這樣就可以ꐠ 12/07 00:52
2F：→ dgf130:找多數個正整數的因數..才需要用到DP吧？殺雞焉用牛刀?.@@ 12/07 00:54
3F：推 waterdisney:原po題目為"design an algorithm" 他要的是演算法~ 12/07 01:30
4F：→ waterdisney:所以...XD XD 12/07 01:30
5F：推 buoyance:謝謝兩位的解答喔!! 12/07 02:06
6F：推 dgf130:演算法不就是作法嗎...小弟駑鈍..不知道差在哪裡..囧rz 12/07 03:18
7F：推 Daiblo2:演算法都是用虛擬碼寫 這樣會比較好一點 12/07 10:08