高效输入和高效算法
本帖最后由 不爱听课的同学 于 2020-11-18 16:07 编辑自己找了快速输入的代码，但算法过程太慢超时了，看了一下答案不懂为什么答案比较快
自己的超时代码
#include <iostream>
using namespace std;
inline void scan_d(int* num) //快速输入函数代码
{
char in;
in = getchar();
if (in == EOF) return;
while (in != '-' && (in < '0' || in>'9')) in = getchar();
if (in == '-') { *num = 0; }
else *num = in - '0';
while (in = getchar(), in >= '0' && in <= '9') {
*num *= 10, * num += in - '0';
}
return;
}
int main()
{
int N, score, A=0,B=0,C=0,D=0,E=0;
scan_d(&N);
for (int i = 1;i <= N;i++) { //成绩处理部分
scan_d(&score);
if (score >= 90) A++;
else if (score >= 80) B++;
else if (score >= 70) C++;
else if (score >= 60) D++;
else E++;
}
printf("%d %d %d %d %d", A, B, C, D, E);
return 0;
}
答案代码
int a; //创建包含每个成绩的数组
int main()
{
int A = 0, B = 0, C = 0, D = 0, E = 0;
int N = 0, score, i = 0;
scan_d(&N);
for (i = 1; i <= N; i++)
{
scan_d(&score);
a++;
}
i = 0; //成绩录入
for (; i < 60; i++)
E += a;
for (; i < 70; i++)
D += a;
for (; i < 80; i++)
C += a;
for (; i < 90; i++)
B += a;
for (; i <= 100; i++)
A += a;
printf("%d %d %d %d %d", A, B, C, D, E);
return 0;
}
为什么答案的方法更快，而我的方法超时了，答案是用了某种算法吗？还有没有其他解法？ 首先，答案代码的语法是错的，没有E += a 这种语法，只有 E += *(a+i) 或者 E+= a 这样的语法。
这个代码里最耗执行时间的是循环 for (i = 1; i <= N; i++)，
所以，这个循环里执行的语句越少，总的执行时间越快。
a++;
这行代码的意思是统计不同成绩的数量，比如说输入的第一次输入成绩是61，那么 a ++
表示 61 这个分数有了 1 人，再输入一个89，则 a++，表示 89 这个分数有了 1 人。
输入循环结束后，再将数组 a 中每个分数段中的人数求和则可获得每个分数段的总人数了。
后面的5个循环 i 从 0 循环到 100，只执行了100次加法，如果 N > 10000，那么，这个100次循环几乎可以忽略。
scan_d(&score); 这行代码是一样的，不对执行时间产生影响。
而你的代码里的一堆 if 执行时间必然超过 a++;
int a; //创建包含每个成绩的数组
int main()
{
int A = 0, B = 0, C = 0, D = 0, E = 0;
int N = 0, score, i = 0;
scan_d(&N);
for (i = 1; i <= N; i++)
{
scan_d(&score);
a++;
}
i = 0; //成绩录入
for (; i < 60; i++)
E += a;
for (; i < 70; i++)
D += a;
for (; i < 80; i++)
C += a;
for (; i < 90; i++)
B += a;
for (; i <= 100; i++)
A += a;
printf("%d %d %d %d %d", A, B, C, D, E);
return 0;
} 本帖最后由 sunrise085 于 2020-11-18 15:33 编辑
不知道你是否理解答案的执行过程，这是一分一档汇总人数，然后再按照划分层次再次汇总。
a就是分数为score的人数，后面按照数组a的下标进行汇总即可。
你的写法在N特别大的时候就会显得很慢。
因为你的程序运算次数多，每输入一个分数，需要执行1~4次比较运算，然后再执行一次加法运算，总运算次数是2N~4N，此外，分支也会很消耗时间，是的程序更慢
答案，每输入一个分数执行一次加法，输入结束后，执行100加法进行人数汇总，总的计算次数是N+100 sunrise085 发表于 2020-11-18 15:32
不知道你是否理解答案的执行过程，这是一分一档汇总人数，然后再按照划分层次再次汇总。
a就是分数 ...
我明白啦，多谢大佬解答 xieglt 发表于 2020-11-18 15:31
首先，答案代码的语法是错的，没有E += a 这种语法，只有 E += *(a+i) 或者 E+= a 这样的语法。
这个代 ...
谢谢大佬回答，我搞懂啦
页:
[1]