【每天进步一点点】Python解题笔记（01篇）

jerryxjr1220

【每天进步一点点】系列作为新手向的Python学习笔记，会记录我在平时的解题过程中遇到的问题以及如何解决的，主要是给新人们学习一个解题的思路。

同一个简单的问题可能有好几种思路，而不同的程序和算法之间的运算效率又会有非常大的区别。

同时，还会不定期得分享一些实用而强大的python标准库或者第三方库。

今天先从“欧拉计划”的第1题开始讲起。

题目：
求1000以下，3和5的倍数的所有数字之和。

先讲思路，如果例举1000以下所有数字，再依次去判断是否能被3或者5整除，如果是就累加，这种方法称作穷举法，是暴力解法的基本思路。

对于数据量小的计算，穷举法当然是没有问题，例如本题。Python一行代码就能得出结果：

print(sum([i for i in range(1000) if i%3==0 or i%5==0]))

但是我们设想一下，要是数量大的话会怎么样？比如100万以下，那我们就需要比较100万次，这样速度就会变慢了。

那么，我们可以考虑要是我们把所有3的倍数的数字和5的倍数的数字全加起来不就好了？这里我们需要注意，15既是3的倍数，又是5的倍数，所以最终还要减去15的倍数，不然就会重复计算了。

这样做的话，我们就可以不用每次都去判断了，可以大大减小计算量。Python同样一行代码：

print(sum(range(0, 1000, 3))+sum(range(0, 1000, 5))-sum(range(0, 1000, 15)))

那还可不可以继续优化？当然是可以的。

还记得，我们学过的等差数列的计算公式吗？（首项+末项）* 项数 / 2，对了，我们只需要完成一个算式就可以知道和了，何必一个一个去加呢？

def calc(start, end, step=1):
        return (start+end)*((end-start)//step+1)//2

有了这个公式，哪怕要算1000亿，那也是秒算的。

你看懂算法的奥秘了吗？

hanfeng

新人学习了，赞~

import time

def calc(start, end, step=1):
    return (start+end)*((end-start)//step+1)//2

start = time.clock()

a = range(0,100000000000000000,3)
b = range(0,100000000000000000,5)
c = range(0,100000000000000000,15)
print(calc(a[0],a[-1],3)+calc(b[0],b[-1],5)-calc(c[0],c[-1],15))

end = time.clock()

print('Running time:%s Seconds'%(end-start))

jerryxjr1220

hanfeng 发表于 2017-8-18 11:15
新人学习了，赞~

import time

这个系列的学习笔记就是为了给新人们学习编程思路和算法的，希望以后能多多捧场，也希望自己能持续做下去

目前初步的设想是会完整解答“欧拉计划”前100题，以及解题过程中运用的相关算法和知识点，当中会穿插讲解python实用的标准库和第三方库。

新手·ing

这个真是太好了！！！！！！！！！！！！！

新手·ing

新人疑问：等差数列不是算首项到尾项之和的吗？

jerryxjr1220

新手·ing 发表于 2017-8-18 12:12
新人疑问：等差数列不是算首项到尾项之和的吗？

等差数列只是一个每项之间公差为常数的数列，比如1,2,3,4...这样的是等差数列；1,3,5,7...这样的也是等差数列；特例，常数数列也是公差为0的等差数列，比如1,1,1,1...

xi7yang3

list1 = []
for i in range(1000):
    if i % 3 == 0:
        list1.append(i)
    elif i % 5 == 0 :
        list1.append(i)
print(sum(list1))

但是还是感觉那个一行代码的比较简洁，但是我现在写不出这样的一行的代码啊，怎么样能get到这个技能

jerryxjr1220

xi7yang3 发表于 2017-8-25 17:09
但是还是感觉那个一行代码的比较简洁，但是我现在写不出这样的一行的代码啊，怎么样能get到这个技能

熟能生巧而已

较劲儿

学习了，编程还是坚持很重要