正文

Python杨辉三角

IP云
IP云V管理员/9 阅读
12/01
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

杨辉三角，是二项式系数在三角形中的一种几何排列，在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年

第一种解决方法：

1.一次性开辟每行的内存空间

2.利用对称性解决 

triangle = []

n = 6

for i in range(n):

    #row 定义了left的1 ，索引第二层循环的范围就是i，第0行0个值，第一行1个值，第二行2个值

    row = [1]

    #此层循环每层的个数，抛除已经定好的1，当2行i=1，k=0.实际一个空位

    #k=i-1的时候填充1，不等的时候填充0

    for k in range(i):

        if k == i-1:

            row.append(1)

        else:

            row.append(0)

    #每行都是1 然后append到triangle，因为列表调用列表，所以更改row就好了（浅copy）

    triangle.append(row)

    #特殊情况，当i=0的时候 跳过本次循环，进行下一次循环i = 1

    if i == 0:

        continue

    #找对称，前2行特殊情况，i=0 or i=1 带入此循环不执行，第三行的时候就对称只有一个，第四行的时候

#对称还是一个，第五行的时候对称是2个，对称的时候划一条竖线分析，排除左右2边的1

    for j in range(i//2):

#第三层通过第2层的2个数相加，然后更改对应的值，

        value = triangle[i-1][j]+triangle[i-1][j+1]

        row[j+1] = value

#利用负索引找到对应的位置把value的值赋值

        row[-j-2]=value

print(triangle)
triangle = []

n = 6

for i in range(n):

    row = [1]*(i+1)

    triangle.append(row)

    for j in range(i//2):

        vaule = triangle[i-1][j]+triangle[i-1][j+1]

        row[j+1]=vaule

        row[-j-2]=vaule

print(triangle)

第二种方法：

1.下一行依赖上一行所有元素，是上一行所有元素的两两相加的和，再在两头各加1。 

#把前2行特殊情况单独拿出，用列表嵌套来表示

triangle = [[1],[1,1]]

#从第三行开始循环

for i in range(2,6):

#定义新列表放每行的数字元素

    newline = []

#每行先从空列表append 一个1 [1]

    newline.append(1)

#在每行列表中增加对应的数字，i行应该有i个数字，但是已经定义好了左侧第一个元素为1 ，所以range（i）

    for j in range(i-1):

#i行的j元素等于（i-1)行的值相加

        value = triangle[i-1][j]+triangle[i-1][j+1]

        newline.append(value)

#填充右侧的1

    newline.append(1)

    triangle.append(newline)

print(triangle)
triangle = []

n = 6

for i in range(n):

    newline = [1]

    triangle.append(newline)

    if i == 0:

        continue

    for j in range(i-1):

        val = triangle[i-1][j]+triangle[i-1][j+1]

        newline.append(val)

    #利用到了深浅拷贝的知识，复杂列表，调用的引用地址，更改了newline列表 索引triangle列表也随之更改

    newline.append(1)

print(triangle)

第三种方法

1.除了第一行以外，每一行每一个元素（包括两头的1）都是由上一行的元素相加得到。如何得到两头的1呢？ 目标是打印指定的行，所以算出一行就打印一行，不需要用一个大空间存储所有已经算出的行 

triange = [1]

print(triange)

#triange.insert(0,0)

triange.append(0)

n = 6

for i in range(1,n):

    newline = []

    for j in range(i+1):

        value = triange[j]+triange[-j-1]

        newline.append(value)

    print(newline)

    triange=newline

#    triange.insert(0,0)

    triange.append(0)

第四种方式：单行覆盖

1.每次都要在循环里清除列表有点浪费时间，值开辟一个列表，利用对称和覆盖
2.明确最大行的元素个数，前6行最大的元素个数是6个，下一行等于首元素不变覆盖中间元素 

#row = [1,1,1,1,1,1]

# n = 6

# [:1]    i==0  offset==6        j=range(1,1)    jump

# [:2]    i==1  offset==5        j=range(1,1)    jump

#

# [:3]    i==2  offset==4        j=range(1,2)

# [:4]    i==3  offset==3        j=range(1,2)

# [:5]    i==4  offset==2        j=range(1,3)

# [:6]    i==5  offset==1        j=range(1,3)

n = 6

row = [1]*n

for i in range(n):

#4行和6行对称的负所以是-2；-2，-3；定义的偏移量offset和j做运算方便找到符所以的位置

    offset = n-i

#所以为1的位置都是1+x,所以z=1是定义第一个1，定义在for循环外，规避覆盖影响

#此处不用z=1来设置临时变量，val=row[0]+row[j]的话 在算到索引位2的时候就错了，因为row[0]是固定值

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

相关阅读

目录[+]