python中的Pascal三角形，不使用任何循环

Question

所以我正在尝试实现一个帕斯卡三角形，它在python中产生以下内容：

pascal_triangle(5) prints:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

问题是我试图在不使用任何类型的循环的情况下做到这一点，但无法弄清楚如何做到这一点。任何帮助将不胜感激。比你。

这是我到目前为止所拥有的：

def factorial(x):
if x == 0:
return 1
else: 
x * factorial(x - 1)
def pascal_triangle(n):`

更新：

print_pascal_line(r):
if r == 0:
return 1
else:
R = print_pascal_line(r-1)
return 1 +

Answer 1

帕斯卡三角形的每个元素都使用二项式系数进行评估。这个值通常被称为nCr，询问"给定n物品，您可以有多少种方式Cr事物？

以a、b和c项为例。我们可以通过多少种方式创建以下尺寸的组合？

只有
0. 一种方法可以选择 0 个项目：{}
1. 有 3 种可能的组合：{a}、{b}或{c}
2. 同样，3种方式：{a, b}，{a, c}或{b, c}
3. 只有{a, b, c}

你知道什么，恰好是帕斯卡三角形的3级*：1 3 3 1！事实证明，我们可以在每个级别上使用它。

0: nCr(0, 0)
1: nCr(1, 0) nCr(1, 1)
2: nCr(2, 0) nCr(2, 1) nCr(2, 2)
3: nCr(3, 0) nCr(3, 1) nCr(3, 2) nCr(3, 3)
etc
etc

那么，我们如何为此编码呢？看看这个答案，我们得到了我们的nCr函数

In [454]: import functools as ft
In [455]: import operator as op
In [456]: def nCr(n, r):
...:     r = min(r, n-r)
...:     numer = ft.reduce(op.mul, range(n, n - r, -1), 1)
...:     denom = ft.reduce(op.mul, range(1, r + 1), 1)
...:     return numer // denom
...:

最后，让我们创建一个递归函数来将它们联系在一起。

In [457]: def pascal(n):
...:     if n >= 1:
...:         pascal(n - 1)
...:         print(' '.join(str(nCr(n - 1, r)) for r in range(n)))
...:
In [463]: pascal(5)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

从技术上讲，这应该是pascal(4)，因为帕斯卡的三角形是零索引*，但我只是按照 OPs 的要求去做。如果我们想改变这一点，我们会将我们的pascal函数更改为

In [468]: def pascal(n):
...:     if n >= 0:
...:         pascal(n - 1)
...:         print(' '.join(str(nCr(n, r)) for r in range(n + 1)))
...:

Answer 2

一个纯粹的递归解决方案(没有循环，没有赋值，没有外部模块，只使用python函数是可以避免的sum)。这段代码可以很容易地翻译成 LISP 家族语言。

def pascal_line(n):
def nextline(thisline):
if thisline == []:
return []
else:
return [sum(thisline[:2])] + nextline(thisline[1:])
if n == 1:
return [1]
elif n == 2:
return [1, 1]
else:
return [1]+nextline(pascal_line(n-1))
def pascal_triangle(n):
def printline(m):
if m <= n:
print(*pascal_line(m))
printline(m+1)
return printline(1)
pascal_triangle(6)
# output =>
# 1
# 1 1
# 1 2 1
# 1 3 3 1
# 1 4 6 4 1
# 1 5 10 10 5 1

内部函数nextline基于当前线递归推导出帕斯卡三角形中的下一行(不带前导 1)。

函数pascal_line通过递归调用nextline第 (n-1)行(它自己的先前解决方案)来导出帕斯卡三角形中的第 n行。

函数pascal_triangle通过递归调用pascal_line来打印出帕斯卡三角形中的线条。

三个递归函数很好地说明了递归方法的典型分而治之的性质。

Answer 3

首先创建一个打印帕斯卡三角形第 N 行的函数，我建议您使用组合而不是使用阶乘手动计算每行中的值，这样会更有效。假设此函数称为 print_pascal_line 并接收一个整数，即行号。

那么你只需要：

def pascal_triangle(n):
aux(0, n)
def aux(current_line, n):
if current_line < n:
print_pascal_line(current_line)
aux(current_line + 1, n)

或者，您可以使用默认参数仅在一个函数中将其包含：

def pascal_triangle(n, current_line = 0):
if current_line < n:
print_pascal_line(current_line)
pascal_triangle(n, current_line + 1)

Answer 4

这个怎么样？

def pascal_triangle(n, line=None):
if n == 0: return
if line is None: 
line = [1]
print(" ".join(map(str, line)))
pascal_line(line)
pascal_triangle(n-1, line)
def pascal_line(line, i=0, add=0):
if i >= len(line):
line.append(add)
return
add, line[i] = line[i], line[i] + add
pascal_line(line, i+1, add)

Answer 5

我之前在这里回答过这个问题。点击链接了解如何设计像这样的递归函数。

def pairs (xs):
if 2 > len(xs):
return []
else:
return [xs[0:2]] + pairs(xs[1:])
def pascal (n):
def compute (prev):
return [1] + [x + y for (x,y) in pairs(prev)] + [1]
def aux (m, prev):
if (m > n):
return []
else:
return [prev] + aux(m + 1, compute(prev))
return aux(1, [1])
for line in pascal(5):
print(line)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]

上面我们在三个地方创建了一个新的[1]单例;其中两个是compute循环的一部分。我们应该创建它一次并重用它。

def pascal (n):
one = [1]
def compute (prev):
return one + [x + y for (x,y) in pairs(prev)] + one
def aux (m, prev):
if (m > n):
return []
else:
return [prev] + aux(m + 1, compute(prev))
return aux(1, one)

我可能建议的最后一个改进是使用生成器而不是急切地返回所有行

def pascal (n):
one = [1]
def compute (prev):
return one + [x + y for (x,y) in pairs(prev)] + one
def aux (m, prev):
if (m > n):
return
else:
yield prev
yield from aux(m + 1, compute(prev))
yield from aux(1, one)

现在，您可以在使用输出时延迟计算输出。但是，如果您一次想要全部，则可以使用list.

list(pascal(5))
# [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Answer 6

一个更简单的递归解决方案，它使用数学来构造没有任何隐藏循环的三角形：

def pascal(n, row=0):
def pascal_row(numerator, denominator=1, number=1):
if numerator > 0:
number = number * numerator // denominator
return [number, *pascal_row(numerator - 1, denominator + 1, number)]
return []
if row < n:
return [[1, *pascal_row(row)], *pascal(n, row + 1)]
return []
print(*pascal(10), sep='n')

输出

% python3 test.py
[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]
%