【算法】蓝桥杯 算法提高 简单加法

文章信息

• 原文链接：https://jiayq.blog.csdn.net/article/details/103214394
• 发布时间：2019-11-23 15:29:45
• 阅读量：396
• 分类：算法专栏收录该内容, 订阅专栏
• 标签：#算法分析, #暴力循环优化, #增加循环效率, #减少循环次数, #算法

摘要

文章浏览阅读396次。本文对比分析了暴力循环与逆推两种算法在处理特定数学问题时的性能表现，通过实验证明，逆推算法在处理大规模数据时具有明显的时间优势。

---

这道题有两种思路：
1.暴力循环；
2.逆推。

怎么说呢：
在算法题中，小数据最好用的方法就是暴力破解方法，虽然有时间、内存的限制，但是因为数据量小，所以还是够用的。

所以对于这道题，写一个for循环，从1循环到1000，用取余判断即可。
代码如下：

public class Main {

    public static void main(String[] ars) {
    	long alltime = 1000;
		System.out.println("start time:\t" + System.currentTimeMillis());
        int sum = 0;
        int num = 0;
        for (int i = 1; i < alltime; i++) {
            if (i % 3 == 0 || i % 5 == 0) {
                sum += i;
            }
            num++;
        }
        System.out.println("loop time:\t" + num);
        System.out.println("result:\t" + sum);
        System.out.println("end time:\t" + System.currentTimeMillis());
    }

}

【换个思路】
假设一个数x能够除尽3，那么也就是说，一定存在一个整数m*3=x
因为存在这个关系，所以对于暴力的思路就可以转换为逆推了。
代码如下：

public class Main {

    public static void main(String[] ars) {
    	long alltime = 1000;
        System.out.println("start time:\t" + System.currentTimeMillis());
        int x = 1;
        int y = 0;
        int n = 0;
        while (x * 3 < alltime) {
            y += x * 3;
            x++;
            n++;
        }
        x = 0;
        while (x * 5 < alltime) {
            if (x * 5 % 3 == 0) {
                x++;
                n++;
                continue;
            }
            y += x * 5;
            x++;
            n++;
        }
        System.out.println("loop time:\t" + n);
        System.out.println("result:\t" + y);
        System.out.println("end time:\t" + System.currentTimeMillis());
    }

}

为了更好的对比这两种算法的性能，我们不断的增加总数的数量级，看看差距：
1000以内:alltime=1000

start time:	1574493454522
loop time:	999
result:	233168
end time:	1574493454523
start time:	1574493454523
loop time:	533
result:	233168
end time:	1574493454523

可以看到循环次数暴力是逆推的一倍

10000以内:alltime=10000

start time:	1574493530032
loop time:	9999
result:	23331668
end time:	1574493530032
start time:	1574493530032
loop time:	5333
result:	23331668
end time:	1574493530032

玩把大的10亿
10 0000 0000以内:alltime=10 0000 0000

start time:	1574493591597
loop time:	999999999
result:	631780268
end time:	1574493593545
start time:	1574493593545
loop time:	5 3333 3333
result:	631780268
end time:	1574493594090

暴力循环10亿次
1574493593545-1574493591597 = 1948毫秒
逆推循环5亿次
1574493594090-1574493593545 = 545毫秒

所以，对于这道题，如果是求10亿内的，用暴力循环就无法满足时间要求了。

用逆推满足时间要求。（应该与jvm对循环有优化，否则我们的理论时间应该是1948毫秒的一半，不是现在的1/4）

友好提示：真正算法验证时，不需要这么多的输出。。。