杨辉三角是由中国古代数学家杨辉所创造的,它的形式是一个数字三角形,其规律是上一行两个数字相加等于下一行对应位置的数字。
一、基本思路
Python编写杨辉三角的基本思路是使用二维数组来存储数字三角形,然后通过循环依次计算每一层的数字,并将其存储在数组中。
首先,我们需要定义一个空的二维数组,然后使用for循环依次计算每一层的数字,最后将其存储在数组中。
def yanghui_triangle(n): triangle = [[1]] for i in range(1, n): row = [1] for j in range(1, i): row.append(triangle[i-1][j-1] + triangle[i-1][j]) row.append(1) triangle.append(row) return triangle
在这个代码中,我们将二维数组初始化为[[1]],表示第一层只有一个数字1。
然后,我们使用for循环依次计算从第二层到第n层的数字,其中i表示当前层数。
对于每一层,我们先初始化一个空的列表row,然后使用内部的for循环计算每一个数字,最后将row添加到triangle数组中。
最后,我们将triangle作为函数的返回值,即可得到一个n层的杨辉三角。
二、优化思路
虽然上面的代码已经能够正确地生成杨辉三角,但是它的时间复杂度为O(n^2),当n变大时,程序的执行速度将变得非常慢。
因此,我们需要考虑优化代码,使其时间复杂度变为O(n)。
一种优化思路是利用杨辉三角的对称性质,仅需要计算一半的数字,然后将其对称复制到剩余的部分。
def yanghui_triangle_optimized(n): triangle = [[1]] for i in range(1, (n+1)//2): row = [1] for j in range(1, i): row.append(triangle[i-1][j-1] + triangle[i-1][j]) row.append(1) triangle.append(row) for i in range(len(triangle)-1, (n-1)//2, -1): triangle.append(triangle[i][:i+1][::-1]) return triangle
在这个代码中,我们仍然使用二维数组来存储数字三角形,但是只计算了n的前一半行数(注意,当n为奇数时,需要再多计算一行),然后将其对称复制到后一半的部分。
具体而言,我们使用两个for循环,分别计算前一半和后一半的数字,并将其添加到triangle数组中。
最后,我们将triangle作为函数的返回值,即可得到一个n层的杨辉三角。
三、应用场景
杨辉三角在数学中有着广泛的应用,下面介绍几个典型的应用场景:
1. 组合数学
杨辉三角在组合数学中有着广泛的应用,可以通过杨辉三角求得组合数的规律。具体而言,杨辉三角的每一个数字都表示C(n,m),即从n个元素中取出m个元素的组合数。
2. 等差数列和
杨辉三角可以用来求解等差数列的和。对于一个等差数列a1, a2, a3, ..., an,其和可以通过杨辉三角的左下半角和来计算。具体而言,等差数列的和为S = C(n+1,2) * a1 + C(n,2) * (a1 + d) + C(n-1,2) * (a1 + 2d) + ... + C(1,2) * (a1 + (n-1)d),其中d为公差。
3. 概率统计
杨辉三角可以用来计算二项式分布和正态分布的概率。对于二项式分布,可以使用杨辉三角来计算投掷n次硬币,正好出现k次正面朝上的概率;对于正态分布,可以使用杨辉三角来计算$x^k * e^(-(x-a)^2/2*b^2)$的积分。