鱼C论坛

 找回密码
 立即注册
查看: 4084|回复: 11

[争议讨论] 算法每日一题(二)

[复制链接]
发表于 2011-7-5 09:52:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
问题:如果一个数恰好等于它的因子之和,那么这个数就被称为完全数。例如6的因子为1,2,3,而6 = 1 + 2 + 3,因此6是一个完全数。请编写一个程序,求出1000以内的完全数。  
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-5 10:19:19 | 显示全部楼层
貌似是 C语言经典例题100 里面的题目
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-5 10:21:40 | 显示全部楼层
翻了下,果然写过

  1. #include <stdio.h>

  2. int main(void)
  3. {
  4.     int i,j,m;
  5.     for(i=4;i<1000;i++)
  6.         for(j=1,m=0;j<i;j++)
  7.         {
  8.             if(i%j==0)
  9.             {
  10.                 m+=j;
  11.                 //printf("%d+",j);
  12.             }
  13.             if(j==i-1)
  14.             {
  15.                 if(m==i)
  16.                     printf("%d\n",i);
  17.             }
  18.         }
  19. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-5 12:59:14 | 显示全部楼层
  1. #include<stdio.h>
  2. #include<math.h>

  3. //判素数
  4. int ispri(int n);
  5. int main(void){
  6.         int i;
  7.         for(i=2;i<=7;++i){
  8.                 int m = pow(2,i)-1;
  9.                 //用欧几里德完全数定理
  10.                 if(ispri(i)&&ispri(m)){
  11.                         int k = pow(2,i-1);
  12.                         printf("%d\n",k*m);
  13.                 }
  14.         }
  15. }

  16. int ispri(int n){
  17.         int i,m=sqrt(n)+1;
  18.         for(i=2;i<=m && i<n;++i)
  19.                 if(n%i==0) return 0;
  20.         return 1;
  21. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-5 14:21:22 | 显示全部楼层
继续努力。。
  1. /*
  2. **        问题:如果一个数恰好等于它的因子之和,
  3. **        那么这个数就被称为完全数。
  4. **        例如6的因子为1,2,3,
  5. **        而6 = 1 + 2 + 3,因此6是一个完全数。
  6. **        请编写一个程序,求出1000以内的完全数。
  7. **        By 小锅
  8. **        7/5/11
  9. */

  10. #include <stdio.h>

  11. int main()
  12. {
  13.         int i, j, sum;

  14.         for( i = 2; i < 1000; i++ )
  15.         {
  16.                 sum = 0;
  17.                 for( j = 1; j < i; j++ )
  18.                 {
  19.                         if( i % j == 0 )
  20.                         {
  21.                                 sum += j;
  22.                         }
  23.                         if( j == i-1 )
  24.                         {
  25.                                 if( sum == i )
  26.                                         printf( "%-5d\n", sum );
  27.                         }
  28.                 }
  29.         }
  30.         return 0;
  31. }
复制代码

评分

参与人数 1荣誉 +1 鱼币 +2 收起 理由
LNH_Sniper + 1 + 2 继续努力。

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-7-5 17:51:50 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-7-5 18:04:14 | 显示全部楼层
  1. #include "stdio.h"

  2. int factorSum( int a ) //i是a的一个因子
  3. {
  4. int i, sum = 0;
  5. for( i = 1; i < a; i++ )
  6. {
  7. if( a % i == 0 )
  8. sum = sum + i;
  9. }

  10. return sum;
  11. }

  12. int perfextnumber( int a ) //判断a是否是完全数
  13. {
  14. if( a == factorSum(a) )
  15. return 1;
  16. else
  17. return 0;
  18. }

  19. int main()
  20. {
  21. int a;
  22. printf("There are following perfect numbers 1~10000 are:\n");
  23. for( a = 1; a <= 1000; a++ )
  24. {
  25. if( perfextnumber(a) )
  26. printf("%d ", a);
  27. }

  28. return 0;
  29. }
复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-5 19:11:17 | 显示全部楼层
LNH_Sniper 发表于 2011-7-5 17:51
数据测试有些问题,
6、28、496、8128,最后一个数据不是规定数据。

多求出一个超过1000范围的完全数而已。算法主要应该注重效率。用该算法效率极高,是其它算法的将近100倍。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-5 19:27:07 | 显示全部楼层
LNH_Sniper 发表于 2011-7-5 17:51
数据测试有些问题,
6、28、496、8128,最后一个数据不是规定数据。

其实只要把
for(i=2;i<=7;++i)
改为
for(i=2;i<7;++i)
就可以得到LZ的答案,但仅仅在1000内找实在提现不出算法的力量,我觉得应该把这道题改为:求出1到18位的所有完全数,才能真正体现算法的力量。(一般的算法就等着死机吧)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-7-5 22:07:10 | 显示全部楼层
仰望天上的光 发表于 2011-7-5 19:27
其实只要把
for(i=2;i

没错,算法注重效率,但,同时对不同问题,采取最佳的解决方式,方为上品。

因此,此题,范围很小,我选择了穷举法。

与君共勉吧。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-6 11:05:25 | 显示全部楼层
如果不算这个数本身的话  最大的因子不过是这个数的二分之一, 循环到二分之一即可
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-11-18 15:33:45 | 显示全部楼层
谢谢啦~有空的话我会看一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 02:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表