鱼C论坛

 找回密码
 立即注册
查看: 1191|回复: 2

[已解决]求帮忙看一下代码问题出在哪

[复制链接]
发表于 2023-9-28 22:25:08 | 显示全部楼层 |阅读模式

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

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

x
题目是输入描述
输入一个整数数n。0≤n≤1e12


输出描述
输出一个整数表示在[0,n]
中,有多少个数可以被3或5整除,如果结果是0,请输出“zero”,否则请输出结果。
我的代码是
#include<stdio.h>
int main()
{
    int n,i=0,sum=0;
    scanf("%d",&n);
    for(;i<=n;i++)
    {
        if(i%3==0||i%5==0)
            sum=sum+1;
    }
    if(sum==0) printf("zero");
    if(sum>0) printf("%d",sum);
}
平台显示时间超限,错在哪了啊
最佳答案
2023-9-28 22:25:23
您的代码时间复杂度为O(n),当输入n较大时,程序需要循环极多次,导致超时。可以考虑优化算法,将时间复杂度降为O(1)。

根据题目,我们需要统计在[0,n]中,有多少个数可以被3或5整除。我们可以先分别统计出在[0,n]中,有多少个数可以被3或5整除,再减去在[0,n]中,有多少个数可以被15整除(因为15同时是3和5的倍数,会被重复计算)。具体代码如下:

#include <stdio.h>

int main()
{
    long long n;
    scanf("%lld", &n);

    long long cnt3 = n / 3;  // 可以被3整除的数的个数
    long long cnt5 = n / 5;  // 可以被5整除的数的个数
    long long cnt15 = n / 15;  // 可以被15整除的数的个数

    long long ans = cnt3 + cnt5 - cnt15;  // 最终答案

    if (ans == 0) printf("zero");
    else printf("%lld", ans);

    return 0;
}

注意,由于n的范围较大,需要使用long long类型存储。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-9-28 22:25:23 | 显示全部楼层    本楼为最佳答案   
您的代码时间复杂度为O(n),当输入n较大时,程序需要循环极多次,导致超时。可以考虑优化算法,将时间复杂度降为O(1)。

根据题目,我们需要统计在[0,n]中,有多少个数可以被3或5整除。我们可以先分别统计出在[0,n]中,有多少个数可以被3或5整除,再减去在[0,n]中,有多少个数可以被15整除(因为15同时是3和5的倍数,会被重复计算)。具体代码如下:

#include <stdio.h>

int main()
{
    long long n;
    scanf("%lld", &n);

    long long cnt3 = n / 3;  // 可以被3整除的数的个数
    long long cnt5 = n / 5;  // 可以被5整除的数的个数
    long long cnt15 = n / 15;  // 可以被15整除的数的个数

    long long ans = cnt3 + cnt5 - cnt15;  // 最终答案

    if (ans == 0) printf("zero");
    else printf("%lld", ans);

    return 0;
}

注意,由于n的范围较大,需要使用long long类型存储。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-9-28 22:26:05 | 显示全部楼层
代码问题分析与解决方法

代码中出现时间超限的问题似乎是由于输入上限较大(1e12)导致的。为了优化程序性能,避免不必要的循环和计算,可以采取以下改进措施:

1. 修改循环范围:由于题目要求在[0, n]范围内计算能被3或5整除的数的个数,可以将循环条件修改为i <= n,而不是i <= n。这样可以避免多余的计算。

2. 计算方法优化:使用循环逐个判断每个数是否能被3或5整除并计数的方法较为低效。可以尝试使用数学方法来直接计算满足条件的数的个数。假设n大于等于3,我们可以分别计算出能被3整除的数的个数以及能够被5整除的数的个数,然后再减去同时能被3和5整除的数的个数,即可得到最终结果。

下面是经过改进后的代码:
#include <stdio.h>int main(){    long long n;    scanf("%lld", &n);    long long count3 = n / 3; // 能被3整除的数的个数    long long count5 = n / 5; // 能被5整除的数的个数    long long count15 = n / 15; // 能被3和5同时整除的数的个数    long long result = count3 + count5 - count15; // 最终结果    if (result == 0)        printf("zero");    else        printf("%lld", result);    return 0;}
这样修改后的代码应该能更高效地计算出满足条件的数的个数,并且避免了时间超限的问题。

希望以上解决方法对您有帮助!如果还有其他问题,请随时提问。

球一个最佳答案谢谢啦!这对我非常重要!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-12-23 22:51

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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