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()