计算杨辉三角前6行(升级版),list实现
值如下: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
-
思路:
上一个实现的思路,下一行的数字是基于上一行的数字求得而来,那么则只需要使用两 个内存空间,分别来保存这两行数字.一个保存上一行的数字,另一行则保存求得的下一 行数字.一轮循环后,新生成的下一行变成了旧行,新行清空重新计算并填充.
-
优化思路:
直接开辟一个足够大的内存空间,在此内存空间中来模拟旧行和新行的关系,如直接将新行的内容覆盖旧行的内容. 优点: 内存空间的消耗减少,时间复杂度不比上一个实现差.
-
代码实现:
l1=[1]*6 # 开辟一个长度为6的列表 print(l1[:1]) print(l1[:2]) for i in range(2,6): a=[1] # 定义及重置 for j in range(1,i//2+1): a.append(l1[j]) # 将用于计算的数附加至此列表 if len(a)>2: # 列表长度大于2时,进行元素处理 a[0]=a[1] a[1]=a[2] a.remove(a[2]) l1[j]=a[0]+a[1] if i!=2j: l1[i-j]=l1[j] print(l1[:i+1]) # 根据切片,只打印所需部分
-
实现想法:
上一行与下一行的关系,无非就是两个数相加所得结果是下一行的某一值.在同一列表 中操作,需要防止生成的新值将用于计算的旧值覆盖.因此需要将用于计算的值保存下 来. 我使用的是用列表保存,而且此列表只需要两个值即可,当列表长度超过了3,则代表第 一个用于计算的值已经使用完,便用后面的两个值覆盖掉.
-
更优方案:
每次计算前将要被覆盖的值保存至一个变量中,在下次计算时使用此变量和下一个索引 的值进行相加同样可以求出此结果. 优点: 此处变量比列表效率更高 注意: 这个变量要在原值修改之前保存 在下一轮的计算之前,变量的值没有改变
-
代码实现:
l1=[1]*6 # 开辟长度为6的列表 print(l1[:1]) # 1,2行做特殊行处理 print(l1[:2]) for i in range(2,6): a=1 for j in range(1,i//2+1): # 将求下一行值分为两步 val = l1[j]+a # 第一步求值 a = l1[j] # 将原值先保存至a l1[j] = val # 第二步赋值 if i!=2j: l1[i-j]=l1[j] print(l1[:i+1])
-
实现想法:
将求值的过程分成两步,先把a和索引对应的值的和保存至变量val中,再把即将要被覆 盖的值保存至a,最后在将val的值覆盖至事先保存的变量位置.
-
本文转自 撒旦搞时间 51CTO博客，原文链接：http://blog.51cto.com/12074120/1968205，如需转载请自行联系原作者
