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