51、质数和杨辉三角多种解法

真正想要的东西，
不只是踮踮脚尖那么简单，
所有的收获，一定要全力以赴，奋不顾身!

现在的怕和愁，都是能力小和经历少;十年后，所有的事，都只是下酒菜。

算法里面最经典的题目：（必须掌握*****）质数、杨辉三角、矩阵

列表在Python中是最重要的数据结构，数组在Java中也是最重要的数据结构；

面试题其实就是问你在这些基础解法上有优化策略没有（进行改进，变换）
算法中玩的就是这些东西；所以我们必须学到极致；

1.杨辉三角

最朴素的想法:下一行依赖于上一行所有元素，是上一行所有元素相加的和，再在两头各加1；

# 杨辉三角的打印；
#如何思考，哪个地方卡住了；
#列表用的好，编成搞定了一小块了（高手的门槛）


方法1 二位数组 列表循坏迭代，大的框架到小框架下解决问题（二维列表的操作）；

tri=[[1],[1,1]]
n=9
for i in range(2,n):
    lst=[1]  # 头部；
    
    pre=tri[i-1]         #先命名内部列表，由大到小的简化过程；
    for j in range(i-1):    #迭代（i-1次）  计数器
        
    #算121
        val=pre[j]+pre[j+1]   #这就是加法；
        lst.append(val)
    
#这两种追加本质上不同；
    lst.append(1)       #尾巴
    tri.append(lst)   # 内部内标 放到大列表中；
print(tri)

 #问题：1.列表的层级命名不会，总想一部到位；思路断掉
可优化方案：
1.大框架迭代会消耗大量的内存，去掉大列表 tri，循环打印；
2.两个列表不停的追加，用完就丢掉了，对GC垃圾回收机制是一种负担；   

方法1.1  只把第一行当作特例处理
tri=[[1]]
n=9
for i in range(1,n):
    lst=[1]  # 头部；
    
    pre=tri[i-1]         #先命名内部列表，由大到小的简化过程；
    for j in range(i-1):    #迭代（i-1次）  for循环相当于 计数器
    
    #算121
        val=pre[j]+pre[j+1]   #这就是加法；
        lst.append(val)
    
    lst.append(1)       #尾巴
    tri.append(lst)   # 内部内标 放到大列表中；
print(tri)
    
方法1.2 第一行特例处理，进一步优化——容器处理问题（方法1变体）
tri=[]
n=6
for i in range(n):
    newline=[1]
    tri.append(newline)
    if i==0:
        continue
    
    for j in range(i-1):
        val=tri[i-1][j]+tri[i-1][j+1]
        newline.append(val)
    
    newline.append(1) #尾巴
print(tri)

方法2 杨辉三角 两头补0法；
# 锻炼思维，算法；

n=6
pre=[1]

print(pre)
pre.append(0)
for i in range(1,n):
    lst=[]
    
    for j in range(i+1):
        s=pre[j-1]+pre[j]
        lst.append(s)
        
    print(lst)
    pre=lst
    pre.append(0)
-----------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

#问题：
1.索引怎么算？一步一步算；
2.效率不太高，两头的1都是加出来的，但思维方法值得学习；
3.变量名也要规范，从现在养成习惯；
4.清楚自己循环多少次的，建议用for循环；不知道多少次，用while;

方法3 问题所在：
1.能不能一次新开辟每一行空间：列表解析式、循环迭代、乘法效率最高，减少每一次追加元素拓展带来的性能损耗；
2.能不能少算一半的数字（对称性）；

优化方案：
1.每一次append是一种效率较低的方法，每次都开辟空间；内存中给你默认开辟的列表空间往往比你想象的大；你感觉不出来；一次性开辟空间效率最高；
2.迭代+算太多次，中点和负索引可以减少计算的次数；

方法3 一次性开辟所有需要的列表空间
tri=[]
n=6
for i in range(n):
    row=[1]*(i+1)   #一次性开辟所有空间
    tri.append(row)
    for j in range(1,i//2+1):     # i=2 第三行才能进来，计算一半的值；
        val=tri[i-1][j-1]+tri[i-1][j]
        row[j]=val
        if i !=2*j: #奇数个数重点断开；（对称负索引赋值）
            row[-j-1]=val
print(tri)
--------------------------------
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]

总结优化方案;
1.对称折半思想可以大大减少计算机计算的量;
2.两边的1也可不用计算，如何开辟更有效？

方法4 杨辉三角

n=6
row=[1]*n   #一次性开辟足够的空间；

for i in range(n):
    offset=n-i
    z=1 #因为会有覆盖影响计算，索引引入一个临时变量；
    for j in range(1,i//2+1):
        val=z+row[j]
        row[j],z=val,row[j]
        if i !=2*j:
            row[-j-offset]=val
    print(row[:i+1])
----------------------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

2.素数问题

求100以内的素数
基本做法：
1.一个数能被从2开始到自己的平方根的正整数整除，就是合数；
2.一个合数一定可以分解成几个素数的乘积，也就是说，一个数如果被一个素数整除就是合数；

#素数问题

import math
n=100
for x in range(2,n):
    for i in range(2,math.ceil(math.sqrt(x))):
        if x%i == 0:
            break
    else:
        print(x)


方法2 去掉math函数部分；
#储存质数合数一定可以分解为几个质数的乘积；
n=100
lst=[2]
for i in range(3,n,2):    #
    for j in lst:  # (3,i**0.5+1,2)=lst
        if i%j==0:
            break
    else:
        print(i)  #找到了一个质数；
        lst.append(i)

方法2.1——改进方案；
n=100
lst=[2]
for i in range(3,n,2):    #
    flag=False
    for j in lst:  # (3,i**0.5+1,2)=lst
        if j>i**0.5:
            flag=True
            break
        if i%j==0:
            flag=False
            break  #合数
    if flag:
        print(i)  #找到了一个质数；
        lst.append(i)

几种优化策略