原题解答

本次的题目如下所示：

杨辉三角形又称Pascal三角形，它的第i+1行是的展开式的系数。

它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
下面给出了杨辉三角形的前4行：
1
1 1
1 2 1
1 3 3 1
给出n，输出它的前n行。

输入：

输入包含一个数n。

输出：

输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。

输入样例：

4

输出样例：

1

1 1

1 2 1

1 3 3 1

这道题我们先要寻找规律，看一下每一行中的数字是如何来的。首先，第n行有n个数，左右两端的数字永远都是1，而中间的数字来源于上面一行相邻两个数相加的和。即a[i][j] = a[i-1][j-1] + a[i-1][j]。

​ 杨辉三角的规律

（以上图片来源于网络，如有侵权请联系）

通过以上规律我们可以一行一行推出杨辉三角了：

第一行a[0][0] = 1第二行a[1][0] = 1 a[1][1] = 1第三行a[2][0] = 1 a[2][2] = 1，a[2][1] = a[1][0] + a[1][1]第四行a[3][0] = 1 a[3][3] = 1，a[3][1] = a[2][0] + a[2][1]，a[3][2] = a[2][1] + a[2][2]……

当j = 0或i = j时，值为1；当i ≠ j时，值为上一行相邻两数相加。通过以上规律，我们很容易都可以得到代码：

n = int(input())a = [] # 存放杨辉三角for i in range(n): t = [0] * (i + 1) # 第i行有i个元素 for j in range(i + 1): if j == 0 or i == j: t[j] = 1 # 第一个元素和最后一个元素都是1 else: t[j] = a[i-1][j-1] + a[i-1][j] a.append(t)for row in a: for i in row: print(i, end=' ') print()

这道题除了使用递推算法外，还可以使用递归算法解决：

我们看杨辉三角除了上述规律外，还可以找出这样的规律：

[1，1] = [0，1] + [1，0]
[1，2，1] = [0，1，1] + [1，1，0]
[1，3，3，1] = [0，1，2，1] + [1，2，1，0]
[1，4，6，4，1] = [0，1，3，3，1] + [1，3，3，1，0]

相当于第n行等于第n-1行分别首尾补0，然后按位相加。

因此我们可以使用递归的方法解决这道问题，具体代码如下：

def triangle(n): t = [1] if n == 0: return t return [x + y for x, y in zip([0] + triangle(n - 1), triangle(n - 1) + [0])]n = int(input())for i in range(n): print(*triangle(i))

本题拓展

本题考查的是递推算法和递归算法，题目难度★★★★★

涉及到递推算法的题型最关键的地方在于找规律，找规律的过程相当于做一道数学题。当我们得到相应的规律时，题目的代码就迎刃而解了。而此类题目的难点就在于找规律上，对于数学的要求较高，因此使用递推算法处理的问题难度一般较高。

使用递推算法解决的问题还有很多，我们看下面一道题目：

N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。
输入：
输入包括一个整数N。
输出：
输出当楼梯阶数是N时的上楼方式个数。
输入样例：
6
输出样例：
13

这道题我们分析一下如何能找到它的规律：

如果只有1个台阶，很明显只有1种可能性。如果有2个台阶，有2种可能性如果有3个台阶，我们可以先到第1个台阶，从第1个台阶到第3个台阶有2种可能性；也可以先到第2个台阶，再到第3个台阶有1种可能性。因此1 + 2 = 3，共3种可能性。如果有4个台阶，我们可以先到第2个台阶，再从第2个台阶到第4个台阶；也可以先到第3个台阶，然后从第3个台阶到第4个台阶。……

因此可以得到以下规律：

f(1) = 1f(2) = 2f(n) = f(n + 1) + f(n + 2)

通过这个规律，我们可以将结果存入列表中，逐个递推就可以得到程序的代码如下：

n = int(input()) f = [0] * n # f[i] 为 i + 1级台阶的可能性f[0] = 1f[1] = 2for i in range(2, n): f[i] = f[i - 1] + f[i - 2]print(f[n - 1]) # 最后一个元素为我们需要对答案

同样，我们也可以使用递归的方式处理这个问题：

def f(n): if n == 1: return 1 elif n == 2: return 2 else: return f(n-1) + f(n-2)n = int(input())print(f(n))

写在最后：能够使用递推解决的问题，首选使用递推，只有在实在写不出递推的情况下才使用递归。因为递归的效率是明显低于递推的。

版权声明：本文转载于今日头条，版权归作者所有，如果侵权，请联系本站编辑删除