鱼C论坛

 找回密码
 立即注册
查看: 3688|回复: 8

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

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

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

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

x
问题:如果整数A的全部因子(包括1,不包括A本身)之和等于B,并且整数B的全部因子(包括1,不包括B本身)之和等于A,则称整数A和B为亲密数。求解3000以内的全部亲密数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-6 10:56:28 | 显示全部楼层
你也不说这A 和B 允不允许相等啊
以下是最直观的  求简便算法


#include "stdio.h"
#include "math.h"
void main()
{
        int A,i,sumB,sumA;
        for(A=2;A<=3000;A++)
        {
                sumA=0;sumB=0;
                for(i=1;i<=A/2;i++)
                {
                        if(!(A%i)) sumB+=i;
                }
                for(i=1;i<=sumB/2;i++)
                {
                        if(!(sumB%i))sumA+=i;
                }
                if((sumA==A)&&(A<=sumB))
                {
                        printf("%d,%d\n",A,sumB);
                }
       
        }

}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-6 11:18:34 | 显示全部楼层
纯穷举...
  1. #include<stdio.h>
  2. #include<math.h>
  3. int get_facts_sum(int n);
  4. int main(){
  5.         int n;
  6.         for(n=210;n<=3000;++n){
  7.                 int s = get_facts_sum(n);
  8.                 if(s<=n)        continue;
  9.                 if(n==get_facts_sum(s)){
  10.                         printf("%d\t%d\n",n,s);
  11.                 }
  12.         }
  13. }
  14. int get_facts_sum(int n){
  15.         int s=1,i;
  16.         for(i=2;i<=sqrt(n);++i){
  17.                 if(n%i==0)        s+=i+n/i;
  18.         }
  19.         return s;
  20. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-6 11:27:40 | 显示全部楼层
光光 ,  他这个是求因子 不是质因子  你用sqrt 是不行的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-6 12:41:35 | 显示全部楼层

为什么不行?每次得到一对因子,这一对因子里必定有一个<=sqrt(n)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-6 12:43:10 | 显示全部楼层
asd82937121 发表于 2011-7-6 10:56
你也不说这A 和B 允不允许相等啊
以下是最直观的  求简便算法

不允许相等的,相等就变成“完全数”了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-6 13:13:30 | 显示全部楼层
程序没看明白   不过运行起来确实比我的快一点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-7-6 20:47:33 | 显示全部楼层
题目分析:由于亲密数是两个数之间的关系。也就说,不能立刻判断一个整数A是否有亲密数,更不知道它的亲密数是多少。因此,在算法的选择上,我采用了一种具有选择性质的算法来查找一定范围内的亲密数,此算法效率不高,但直观有效。

在一个数集{ a1, a2, a3,..........., an }中寻找亲密数,可以针对某一个元素,在其他的元素中寻找该元素的亲密数。这样即划分两个集合:A、B;最初数集中所有的元素都放在集合B中,然后从B中任意选择一个元素放入集合A中,同时在集合B中删去该元素。然后在集合B中的其他元素中寻找刚刚放入集合A中的那个元素的亲密数。

重复上述过程,直到B集合为空。



  1. #include "stdio.h"

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

  10. return sum;
  11. }

  12. int isfriend( int elem_a_factor, int elem_b_factor, int elem_a, int elem_b ) //判断A、B两个数是否是完全数其中elem_a、elem_b分别是A、B;elem_a_factor、elem_b_factor 分别是A的因数和、B的因数和

  13. {
  14. if( elem_a_factor == elem_b && elem_b_factor == elem_a )
  15. return 1;
  16. else
  17. return 0;
  18. }

  19. void friendly( void )
  20. {
  21. int elem_a, elem_b, temp[3001];
  22. for( elem_a = 1; elem_a <= 3000; elem_a++ )
  23. temp[elem_a] = factorSum(elem_a);
  24. for( elem_a = 1; elem_a <= 3000; elem_a++ )
  25. {
  26. if( temp[elem_a] != -1 )
  27. {
  28. for( elem_b = elem_a + 1; elem_b <= 3000; elem_b++ )
  29. {
  30. if( isfriend( temp[elem_a], temp[elem_b], elem_a, elem_b ) )
  31. {
  32. printf("(%d,%d) ",elem_a,elem_b);
  33. temp[elem_b] = -1;
  34. }
  35. }
  36. }
  37. }
  38. }

  39. int main()
  40. {
  41. printf("There are following friendly numbers from 1 to 30000\n");
  42. friendly();
  43. printf("\n");
  44. return 0;
  45. }
复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2015-11-28 11:16:24 | 显示全部楼层
:smile:smile:smile:smile:smile:smile
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 00:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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