论坛 › C\C++交流 › 高效输入和高效算法

不爱听课的同学 发表于 2020-11-16 15:54:07

高效输入和高效算法

本帖最后由 不爱听课的同学 于 2020-11-17 12:24 编辑

自己找了快速输入的代码，但算法过程太慢超时了，看了一下答案不懂为什么答案比较快



自己的超时代码
#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, q = {0};
        scan_d(&N);
        for (int i = 1;i <= N;i++) {
                scan_d(&score);         
                q+=1;         //计算分数余数并增加改分数段人数
        }
        cout << q + q<<' ' << q<< ' ' << q<< ' ' << q<<' ' << q + q + q + q + q+q;
}



答案代码
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;
}
其他部分一样，所以没打出来
疑问，为什么用if选择结构处理更快

永恒的蓝色梦想 发表于 2020-11-16 18:22:42

除法费时

xieglt 发表于 2020-11-17 10:23:18

E+=a;
D+=a;
是什么？

不爱听课的同学 发表于 2020-11-17 10:34:33

永恒的蓝色梦想 发表于 2020-11-16 18:22
除法费时

为什么除法费时

xieglt 发表于 2020-11-17 10:46:41

本帖最后由 xieglt 于 2020-11-17 10:48 编辑

除法的本质是循环减法
125/25 = 5 表达的意思 125 按每份 25 来分可以平均分成 5 份
计算方法是
125-25 = 100       count = 1
100-25 =75          count = 2
75-25 = 50         count = 3
50-25 = 25         count = 4
25-25 =0            count = 5
所以125/25=5

计算机不会列竖式试商。

不爱听课的同学 发表于 2020-11-17 10:58:16

xieglt 发表于 2020-11-17 10:46
除法的本质是循环减法
125/25 = 5 表达的意思 125 按每份 25 来分可以平均分成 5 份
计算方法是


哦，我懂了，除法简单来说每次是进行多步操作，谢谢解答，再冒昧地提个问题，if中的比较操作是只进行一步操作吗？

xieglt 发表于 2020-11-17 11:11:34

本帖最后由 xieglt 于 2020-11-17 11:18 编辑

不爱听课的同学 发表于 2020-11-17 10:58
哦，我懂了，除法简单来说每次是进行多步操作，谢谢解答，再冒昧地提个问题，if中的比较操作是只进行一步 ...

代码里没看到 IF
if ( i >= 60 && i <=70)翻译成汇编指令大概是这样的。
         MOV EAX,I
         CMPEAX,60
         JL    _false
         CMPEAX,70
         JG   _false
_true:
         .....
_false:
         .....

score/10 除法指令大概是这样的

xor edx,edx
mov eax,score
mov ebx,10
div ebx

从指令来看，除法指令更简单一些。但是每个指令执行时间是不一样的。

不爱听课的同学 发表于 2020-11-17 11:23:46

xieglt 发表于 2020-11-17 11:11
代码里没看到 IF
if ( i >= 60 && i

谢谢解答，不过我看不懂汇编语言，以后课程才会学，所以说是if操作的时间更短吗？

xieglt 发表于 2020-11-17 11:30:39

不爱听课的同学 发表于 2020-11-17 11:23
谢谢解答，不过我看不懂汇编语言，以后课程才会学，所以说是if操作的时间更短吗？

我没看到代码里有IF，不知道你说的IF是指的什么。

不过我觉得，这种级别的数据处理，根本感觉不出来差异。
数据上10万，百万才能感觉到差异。

不爱听课的同学 发表于 2020-11-17 12:00:06

本帖最后由 不爱听课的同学 于 2020-11-17 12:08 编辑

xieglt 发表于 2020-11-17 11:30
我没看到代码里有IF，不知道你说的IF是指的什么。

不过我觉得，这种级别的数据处理，根本感觉不出来差 ...

啊看错了，答案是用for循环，我表述得不明确，应该是判断指令和除法指令那个耗时更多。其实这个题目要求算法高效，我一直在想为什么答案的算法这么快，是否有其他解法？实在想不通。

永恒的蓝色梦想 发表于 2020-11-17 12:42:42

xieglt 发表于 2020-11-17 10:46
除法的本质是循环减法
125/25 = 5 表达的意思 125 按每份 25 来分可以平均分成 5 份
计算方法是


你这就离谱，难道你算除法是循环减法？

xieglt 发表于 2020-11-17 12:44:45

永恒的蓝色梦想 发表于 2020-11-17 12:42
你这就离谱，难道你算除法是循环减法？

请编程计算
98765432101234567890987654321234567890 / 1234567890987654321

永恒的蓝色梦想 发表于 2020-11-17 12:45:06

xieglt 发表于 2020-11-17 11:30
我没看到代码里有IF，不知道你说的IF是指的什么。

不过我觉得，这种级别的数据处理，根本感觉不出来差 ...

题目的数据量是六百万。

xieglt 发表于 2020-11-17 12:54:48

永恒的蓝色梦想 发表于 2020-11-17 12:45
题目的数据量是六百万。

还请你解释一下为什么除法慢。

15909574023 发表于 2020-11-17 12:54:51

{:10_269:}

永恒的蓝色梦想 发表于 2020-11-17 19:52:24

xieglt 发表于 2020-11-17 12:44
请编程计算
98765432101234567890987654321234567890 / 1234567890987654321

https://www.zhihu.com/question/55707696
麻烦学会利用网络……
要真的是纯减法，你用到的电脑就得慢死了……

xieglt 发表于 2020-11-17 19:58:59

永恒的蓝色梦想 发表于 2020-11-17 19:52
https://www.zhihu.com/question/55707696
麻烦学会利用网络……
要真的是纯减法，你用到的电脑就 ...

我说用减法实现除法有错吗有错吗?
而且,你的链接给的代码算不出我出的题。

永恒的蓝色梦想 发表于 2020-11-17 20:04:56

xieglt 发表于 2020-11-17 19:58
我说用减法实现除法有错吗有错吗?
而且,你的链接给的代码算不出我出的题。

是说 125/5 不得 5 吗？

xieglt 发表于 2020-11-17 20:06:07

永恒的蓝色梦想 发表于 2020-11-17 20:04
是说 125/5 不得 5 吗？

98765432101234567890987654321234567890 / 1234567890987654321
这个它算不出来，当然，还有更长的。比如说计算PI，计算e

永恒的蓝色梦想 发表于 2020-11-17 20:07:31

xieglt 发表于 2020-11-17 20:06
98765432101234567890987654321234567890 / 1234567890987654321
这个它算不出来，当然，还有更长的。 ...

你这是离谱，C语言能存这么大的数？uint64 都装不下，你逗我呢

查看完整版本: 高效输入和高效算法