| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 447 人关注过本帖
标题:程序超时问题怎么解决 求帮助
只看楼主 加入收藏
luciferxiaoz
Rank: 1
等 级:新手上路
帖 子:13
专家分:5
注 册:2013-11-23
结帖率:100%
收藏
 问题点数:0 回复次数:6 
程序超时问题怎么解决 求帮助
题目:
如果整数a的全部因子(包括1,不包括a本身)之和等于b;
且整数b的全部因子(包括1,不包括b本身)之和等于a,则将整数a和整数b称为亲密数。求3000以内的全部亲密数。

程序代码:
#include <stdio.h>
int sum(int x)
{
    int i,su=0;
    for (i=1;i<x;i++)
    {
        if (x%i==0)
        {su=su+i;}
    }
    return su;
}
void main()
{
    int i,j;
    for (i=1;i<3000;i++)
    {
        for (j=i+1;j<3000;j++)
        {
            if (sum(i)==j&&sum(j)==i)
            {printf ("%d...%d\n",i,j);}
        }
    }
}
搜索更多相关主题的帖子: color 
2013-12-16 19:40
pangshch
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:2
帖 子:443
专家分:1966
注 册:2013-4-9
收藏
得分:0 
你的算法把很多数重复了,
我修改了一下
程序代码:
#include <stdio.h>

 int sum(int x)

 {
     int i,su=0;
     for (i=1;i<=x/2;i++)    // 求因子算到x/2就可以了,少了一半
     {
         if (x%i==0)
         {su=su+i;}
     }
     return su;

 }

 void main()

 {
     int i,j;
     for (i=1;i<=3000;i++)
     {
         j = sum(i);    // 这里的算法是,先用i的因子之和求出j, 然后,计算j的因子之和是不是等于i, 这样只要一次循环。
           if (i == sum(j) && i != j && i < j)  // i < j 是去重复的,因为有六对,其中三对是另外三对的前后位置对换一下。所以你要不去重复的话,可以把i < j这个条件删除。
             printf ("%d...%d\n",i,j);
     }

 }

结果是 :220...284
         1184...1210
         2620...2924
如果不去重复就还有三对:
284...220
1210...1184
2620...2924
2013-12-16 21:30
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
楼主的结果并没有重复,只不过算法太差。

实际在我电脑上测试了一下。

楼主的代码执行完用时30993毫秒。

2楼的代码效率提高不少,31毫秒。

不过还可以更快。

下面是我的代码,用时3毫秒。
程序代码:
#include<stdio.h>
#define N    3000
int main()
{
    int a[N + 1] = {0}, i, j;

    for(i = 1; i <= N; i++)
    for(j = i; (j += i) <= N; a[j] += i);
    
    for(i = 2; i <= N; i++)
        if(a[a[i]] == i && i < a[i]) printf("%d...%d\n", i, a[i]);

    return 0;
}

重剑无锋,大巧不工
2013-12-16 23:04
luciferxiaoz
Rank: 1
等 级:新手上路
帖 子:13
专家分:5
注 册:2013-11-23
收藏
得分:0 
回复 2楼 pangshch
太感谢了~!解释的很清楚。谢谢啦~!
2013-12-16 23:05
luciferxiaoz
Rank: 1
等 级:新手上路
帖 子:13
专家分:5
注 册:2013-11-23
收藏
得分:0 
回复 3楼 beyondyf
能不能稍微解释一下= =我刚刚大一 学C语言一学期不到。还很学渣的  不太理解这个程序的意思
2013-12-16 23:12
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
就这么两行,我还真不知道该怎么解释的好。

这么说吧,你们的思路都是从一个数出发找它的因子,而我的思路是从因子出发找包含它的数。

重剑无锋,大巧不工
2013-12-16 23:29
luciferxiaoz
Rank: 1
等 级:新手上路
帖 子:13
专家分:5
注 册:2013-11-23
收藏
得分:0 
回复 6楼 beyondyf
哦哦 这样啊 谢谢了。
2013-12-17 00:06
快速回复:程序超时问题怎么解决 求帮助
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.047175 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved