1.寻找符合条件的平方数组
requirement：找三个完全平方数，它们的数字从1-9中选择，且不重复，找到所有满足条件的平方数组。例如16，25，73984符合条件。
1.1 确定范围
要寻找符合条件的数字，一定要用到循环，这样就要先找到循环的范围。下限很容易确定，是数字1，上限的确定需要思考。
上限一定小于986754321，可这个数字不合适，循环和计算时间往往是成指数倍的关系，要尽可能缩小范围。接着思考，共有三个数，且都是完全平方数，那么最大的数应该是从986754321中拿掉两个最小的完全平方数剩下的部分。最小的完全平方数是1，4，这样就确定了上限的数字，应该是9876532。
1.2 确定条件
为了满足题中要求的不重复的1-9的数字，选中平方数使用的数字需要记录。接下来考虑到细节，虽然1-9的数字是题中要求的，但是在遍历数字的过程中一定还会有数字0，所以初始出现的数字不能是空集，应该是一个包含数字0的数据类型，比如dict或者set。
接着写一个函数记录出现过的数字：
def f(number, digits_seen_so_far):
number_as_string = str(number)
new_digits = digits_seen_so_far | set(number_as_string)
#符号|用来快速连接set，比如{'1', '2'} | {'3'}，输出{'1', '2', '3'}
#符号|其实是OR，同样还有AND，用&，例如，{1, 2} & {1, 2, 3}，输出是{2}
if len(new_digits) == len(digits_seen_so_far) + len(number_as_string):
return new_digits
else:
return None
1.3 寻找合适的数组
使用string进行比较，寻找合适的数组
from math import sqrt
def f(number, digits_seen_so_far):
number_as_string = str(number)
new_digits = digits_seen_so_far | set(number_as_string)
if len(new_digits) == len(digits_seen_so_far) + len(number_as_string):
return new_digits
else:
return None
N = round(sqrt(9876532))
#不要忘记round，不然N是float，不可以直接用于range函数
all_digits = {str(i) for i in range(10)}
for a in range(1, N+1):
digits_seen_0 = {'0'}
#初始条件要包含数字0，注意前后set中的数据类型保持一致，都是str
x = a * a
digits_seen_1 = f(x, digits_seen_0)
if not digits_seen_1:
continue
for b in range(a + 1, N + 1):
y = b * b
digits_seen_2 = f(y, digits_seen_1)
if not digits_seen_2:
continue
for c in range(b + 1, N + 1):
z = c * c
digits_seen_3 = f(z, digits_seen_2):
if not digits_seen_3:
continue
if digits_seen_3 == all_digits:
print(f'{x}, {y}, and {z} is a solution')
1.4 使用set优化程序
使用string比较判断出现过的数字效率低，换成set比较，使用int数据类型。
from math import sqrt
def f(number, digits_seen_so_far):
while number:
d = number % 10
if d in digits_seen_so_far:
return
digits_seen_so_far.add(d)
#{set}.add(number)是set添加元素的方法
number //= 10
return digits_seen_so_far
N = round(sqrt(9876532))
all_digits = set(range(10))
for a in range(1, N + 1):
digits_seen_0 = {0}
x = a * a
digits_seen_1 = f(x, digits_seen_0)
if not digits_seen_1:
continue
for b in range(a + 1, N + 1):
y = b * b
digits_seen_2 = f(y, digits_seen_1)
if not digits_seen_2:
continue
for c in range(b + 1, N + 1):
z = c * c
digits_seen_3 = f(z, digits_seen_2)
if not digits_seen_3:
continue
if digits_seen_3 == all_digits:
print(f'{x}, {y} and {z} is a solution')
1.5 使用binary进阶优化
set的算法速度已经很快，但是对于更加庞大的运算依然有提升空间。程序的优化往往是从方便程序员思考，走向模拟计算机内存处理过程而实现的。
这个问题判断数字是否出现过，可以进一步进阶到二进制中判断。
引入位运算的概念：
1 << 0, 1 << 1, 1 << 2, 1 << 3
>>>(1, 2, 4, 8)
#含义是向左侧0，1，2，3位添加数字1，这样在binary中1代表1，10代表2，100代表4，1000代表8
这个题目中数字要求是1-9，所以可以把它替代为二进制的9位数，例如，如过出现数字1，则1<<1，已有的数字是10；再出现数字3，则1<<3，已有的数字是1010。直到9个数字都出现，那么二进制显示的数字是1111111110。如果在考虑数字0，可以放在defalut中，初始是二进制的1，它等于十进制的1；终止是二进制的111111111，它是十进制的2**10 - 1。
接着思考如何判断一个数字是否出现过，可以使用&，添加一个出现的数字，使用OR运算。例如，出现过的数字是1，2，3，那么二进制中的数字是1110。此时新的数字出现3，对应的二进制是1000，判断3是否出现过对比的是1000的1所对应的位置上的数字，1110对应的是数字1，这样1&1为True，说明出现过，如果原来没有出现过3，那么记录中的这一位应该是数字0，则0&1为False，说明没出现过。
这样程序优化为：
from math import sqrt
def f(number, digits_seen_so_far):
while number:
d = number % 10
if (1 << d) & digits_seen_so_far:
return
digits_seen_so_far |= 1 << d
number //= 10
return digits_seen_so_far
N = round(sqrt(9876532))
all_digits = 2 ** 10 - 1
for a in range(1, N + 1):
digits_seen_0 = 1
x = a * a
digits_seen_1 = f(x, digits_seen_0)
if not digits_seen_1:
continue
for b in range(a + 1, N + 1):
y = b * b
digits_seen_2 = f(y, digits_seen_1)
if not digits_seen_2:
continue
for c in range(b + 1, N + 1):
z = c * c
digits_seen_3 = f(z, digits_seen_2)
if not digits_seen_3:
continue
if digits_seen_3 == all_digits:
print(f'{x}, {y} and {z} is a solution')
2.寻找质数
例如，寻找50以内的质数，那么循环范围很容易确定，是range(2, 51)，最简单的方法是遍历所有数字，只要有除了自身以外的数能整除，则不是质数。
def print_primes(L):
for i in range(2, len(L)):
if L[i]:
print(i, end = ' ')
print()
L = [True] * 50
print_primes(L)
for i in range(2, len(L)):
j = 2
while i * j < len(L):
L[i * j] = False
j += 1
print_primes(L)
但很显然这样的两个循环嵌套做了很多重复运算。
优化程序，首先思考给定50的范围，循环范围是否可以缩小，之前是直接用range(2, 51)，可实际上25之后就不需要遍历，因为25*2=50。
from math import sqrt
def print_primes(L):
for i in range(2, len(L)):
if L[i]:
print(i, end = ' ')
print()
L = [True] * 51
print_primes(L)
max_number = len(L) - 1
upper_bound = round(sqrt(max_number))
for i in range(2, upper_bound + 1):
j = 2
while i * j <= max_number:
L[i * j] = False
j += 1
print_primes(L)
进一步思考发现，两个循环遍历i和j，j可以从i * i开始，如果i不是质数，则可以跳过。
from math import sqrt
def print_primes(L):
for i in range(2, len(L)):
if L[i]:
print(i, end = ' ')
print()
L = [True] * 26
print_primes(L)
max_number = len(L) - 1
upper_bound = round(sqrt(max_number))
for i in range(2, upper_bound + 1):
if not L[i]:
continue
j = i * i
while i * j <= max_number:
L[i * j] = False
j += 1
print_primes(L)
3.Python运行效率初探
python初始会有一个固定的运算空间，当越界的时候会重新规划申请更多的运算空间，所以运行效率不是平稳改变的，在越界的时候会花更多的时间进行布置。
例如，list的append只需要在最后加一个数，程序复杂度应该是线性的，但实际上会有波动，这些波动就是python在重新安排运算空间。
%matplotlib inline
from matplotlib.pyplot import plot
from time import time
data = []
for i in range(1000, 50001, 1000):
L = []
before = time()
for _ in range(i):
L.append(None)
after = time()
data.append((i, after - before))
plot(*tuple(zip(*data)))
print()
例如，list的insert运算每次都要把所有存在于list中的数向后一位保存，复杂度是指数性的。
%matplotlib inline
from matplotlib.pyplot import plot
from time import time
data = []
for i in range(1000, 50001, 1000):
L = []
before = time()
for _ in range(i):
L.insert(0, None)
after = time()
data.append((i, after - before))
plot(*tuple(zip(*data)))
print()
