FreedomLy's blog.

【每周一坑】杨辉三角形

字数统计: 709阅读时长: 3 min
2017/05/19 Share

问题描述

本周题目

杨辉三角形,也称帕斯卡三角,其定义为:
顶端是1,视为(row0).
第1行(row1)是两个1,这两个1是由它们上头左右两数之和(不在三角形内视为0).
以此类推
第2行(row2):0+1=1; 1+1=2; 1+0=1.
第3行(row3):0+1=1; 1+2=3; 2+1=3; 1+0=1.

根据上述方法可产生杨辉三角。如下所示:

1
2
3
4
5
6
7
n = 0              1                     
n = 1 1 1
n = 2 1 2 1
n = 3 1 3 3 1
n = 4 1 4 6 4 1
n = 5 1 5 10 10 5 1
n = ... ... ...

根据上述定义,定义一个函数,传入正整数参数m、n,分别代表杨辉三角第M行,左起第N个数字(m,n都从0开始计算)。如超出范围则返回 Invalid query

示例代码:

1
2
3
4
5
6
7
8
9
def yang_hui(m, n):
'''
>>>yang_hui(1, 1)
1
>>>yang_hui(3,2)
3
>>>yang_hui(1,4)
Invalid query
'''

附加题
生成杨辉三角形
定义一个函数,传入M<1000,生成前M行杨辉三角形。
示例代码:

1
2
3
4
5
6
7
def generate_yh(m):
'''
generate_yh(3):
1
1 1
1 2 1
'''

思路

根据题目的描述,我们已经知道杨辉三角是怎么生成的了,不过还要判断超出范围的情况:N > M时,返回的应该是 Invalidquery。还有 n=0n=m 时,返回的值应该为1.
要求第(M,N)个数字,可以用递归的方式来求得:

1
yang_hui(m, n) = yang_hui(m-1,n-1) + yang_hui(m-1,n)

Python实现

yang_hui(m,n):

1
2
3
4
5
6
7
# 输出杨辉三角中第m行第n列的数值
def yang_hui(m, n):
if n and n > m:
return "Invalid query!"
if n == 0 or n == m:
return 1
return yang_hui(m-1,n-1) + yang_hui(m-1,n)

triangles(m):

1
2
3
4
5
6
7
8
9
10
打印输出杨辉三角
def triangles(m):
ret = [1]
while m:
yield ret
for i in range(1,len(ret)):
ret[i] = pre[i] + pre[i-1]
ret.append(1)
pre = ret[:]
m = m - 1

在生成杨辉三角的时候,用到了生成器(generator)。generator在执行过程中,遇到yield语句就返回,再次执行时从上次返回的yield语句处继续执行。
普通函数和generator函数的区别:
普通函数调用直接返回结果:

1
2
3
>>> r = abs(6)
>>> r
6

generator函数的“调用”实际返回一个generator对象:

1
2
3
>>> g = fib(6)
>>> g
<generator object fib at 0x1022ef498>

关于generator,可以参考这里

测试

1
2
3
4
5
6
7
8
9
10
11
12
# 测试
if __name__ == '__main__':
print(yang_hui(0, 0))
print(yang_hui(1, 1))
print(yang_hui(1, 2))
print(yang_hui(6, 3))
print(yang_hui(4, 9))

# 打印杨辉三角
triangle = triangles(10)
for i in triangle:
print(i)

输出结果

输出结果如下:

1
1
Invalid query
20
Invalid query
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

End~


CATALOG
  1. 1. 问题描述
  2. 2. 思路
  3. 3. Python实现
  4. 4. 输出结果