【每天进步一点点】Python解题笔记（01篇）
【每天进步一点点】系列作为新手向的Python学习笔记，会记录我在平时的解题过程中遇到的问题以及如何解决的，主要是给新人们学习一个解题的思路。同一个简单的问题可能有好几种思路，而不同的程序和算法之间的运算效率又会有非常大的区别。
同时，还会不定期得分享一些实用而强大的python标准库或者第三方库。
今天先从“欧拉计划”的第1题开始讲起。
题目：
求1000以下，3和5的倍数的所有数字之和。
先讲思路，如果例举1000以下所有数字，再依次去判断是否能被3或者5整除，如果是就累加，这种方法称作穷举法，是暴力解法的基本思路。
对于数据量小的计算，穷举法当然是没有问题，例如本题。Python一行代码就能得出结果：
print(sum())
但是我们设想一下，要是数量大的话会怎么样？比如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亿，那也是秒算的。
你看懂算法的奥秘了吗？
新人学习了，赞~
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,a[-1],3)+calc(b,b[-1],5)-calc(c,c[-1],15))
end = time.clock()
print('Running time:%s Seconds'%(end-start))
hanfeng 发表于 2017-8-18 11:15
新人学习了，赞~
import time
这个系列的学习笔记就是为了给新人们学习编程思路和算法的，希望以后能多多捧场，也希望自己能持续做下去{:5_93:}
目前初步的设想是会完整解答“欧拉计划”前100题，以及解题过程中运用的相关算法和知识点，当中会穿插讲解python实用的标准库和第三方库。 这个真是太好了！！！！！！！！！！！！！ 新人疑问：等差数列不是算首项到尾项之和的吗？ 新手·ing 发表于 2017-8-18 12:12
新人疑问：等差数列不是算首项到尾项之和的吗？
等差数列只是一个每项之间公差为常数的数列，比如1,2,3,4...这样的是等差数列；1,3,5,7...这样的也是等差数列；特例，常数数列也是公差为0的等差数列，比如1,1,1,1... list1 = []
for i in range(1000):
if i % 3 == 0:
list1.append(i)
elif i % 5 == 0 :
list1.append(i)
print(sum(list1))
但是还是感觉那个一行代码的比较简洁，但是我现在写不出这样的一行的代码啊，怎么样能get到这个技能 xi7yang3 发表于 2017-8-25 17:09
但是还是感觉那个一行代码的比较简洁，但是我现在写不出这样的一行的代码啊，怎么样能get到这个技能
熟能生巧而已 学习了，编程还是坚持很重要
页:
[1]