杨辉三角形-第11届蓝桥杯选拔赛Python真题精选

2023-12-14 13:29:20

[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第17讲。

杨辉三角形,本题是2019年12月15日举办的第11届蓝桥杯青少组Python编程选拔赛真题,题目要求编写程序输出指定行数的杨辉三角形。

先来看看题目的要求吧。

一.题目说明

提示信息:

杨辉三角形,是二项式系数在三角形中的一种几何排列。中国南宋数学家杨辉在1261年所著的 《详解九章算法》一书有明确记载。欧洲数学家帕斯卡在1654年发现这一规律,所以又叫做帕斯卡三角形。

其定义为:其顶端(第1行)是1;第2行是两个1;第3行是'1 2 1',中间的'2'是其上方相邻的两个数字的和;依此类推,产生如图所示的杨辉三角形。

图片

编程实现:

对于任意输入的3~15之间的正整数n,请编程输出前n行数字、以及由其组成的杨辉三角形。?

函数提示:

print('{:< 3}'.format(10))能够以3个字符宽度、左对齐的方式显示数字10。

输入描述:

一个正整数n(2 ≤ n ≤ 15)

输出描述:

由两部分组成。第一部分输出由n行数字组成的列表;第二部分输出n行数字组成的杨辉三角形,具体输出格式参考如下样例。

样例输入:

6

样例输出:

图片

评判标准:

下列各评分项单独计分,得分累加,共35个计分点。

  • 15分:正确输出n行数字组成的列表;

  • 9分:正确输出n行数字组成的杨辉三角形,输出格式不需要完全符合样例;

  • 11分:正确输出n行数字组成的杨辉三角形,且格式符合样例,即要求各数字间距相同、左右对称、上下隔行对齐。

二.思路分析

这是一道算法题,考查的知识点主要包括循环、列表操作、输出控制和算法等。

你知道吗,中国古代数学史曾经有自己光辉灿烂的篇章,在数学的许多重要领域中处于遥遥领先的地位,杨辉三角形的发现就是十分精彩的一页。

图片

要解决本题,首先需要找到这其中的规律,相信聪明的你已经发现了,杨辉三角形具有如下4个特性:

1). 第n行的数字有n个

2). 每行首位数字和末位数字都是1;

3). 每行中间的各项数字都是它肩上两个数字的和;

4). 第n行的项数总比第n-1行多1。

尤其是第3点,这是关键,我们可以结合动图来理解:

图片

但是,我们的数据是保存在列表中的,将上图转换成规则的表格形式,如下:

图片

这样看起来就比较清楚了,除了第1行和第2行之外,从第3行开始,每一行的中间项(除首尾两项)都满足如下公式:

a[i][j] = a[i-1][j-1] + a[i-1][j]

这里的i表示行,j表示列,其中,a[i-1][j-1]是左上方的列表项,a[i-1][j]是正上方的列表项。

这其实就是递推算法,那什么是递推算法呢?

递推算法是一种简单的算法,其核心思想是根据已有的数据和关系,逐步推导而得到结果。

递推算法的特点是,一个问题的求解需要一系列的计算,在已知条件和所求问题之间总存在着某种相互联系的关系,在计算时,需要找到前后项之间的关系,即推导公式。

根据上面的分析,我们可以将本题分成如下几步来实现:

  • 初始化列表,包括前两行;

  • 使用递推算法构造整个列表

  • 输出列表

  • 输出杨辉三角形

思路有了,接下来,我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析,我们分4步来编写程序:

  • 初始化列表;

  • 使用递推算法构造整个列表

  • 输出列表

  • 输出杨辉三角形

1. 初始化列表

这一步,非常简单,只需要完成两个任务,一是获取用户输入的行数,二是创建一个二维列表,编写代码如下:

图片

由于这里只需要初始化列表的前两项,所以在构造的时候直接写上即可,和行数n没有关系。

2. 使用递推算法构造整个列表

根据前面的思路分析,从第3行开始,使用递推算法逐步构造列表项,继续编写代码如下:

图片

这部分代码是本题的关键,也是难点,重点说明一下。

由于列表的第1行和第2行已经有了,所以在循环的时候,i从2开始,表示第3行,到n-1行结束,包括第n-1行。

对于第i行,首先构造一个一维列表,并将所有的初始值设为1。

比如i = 2时,表示第3行,有3项数据,构造的列表为:

[1, 1, 1]

再如i = 3时,表示第4行,有4项数据,构造的列表为:

[1,?1, 1, 1]

又如i = 4时,表示第5行,有5项数据,构造的列表为:

[1, 1, 1, 1, 1]

将构造好的列表追加到tri列表中,然后使用循环,对中间项进行推导,所以变量j的范围是(1,i),第一项和最后一项则保持1不变。

3. 输出列表

列表构造完毕,直接使用for循环输出即可,代码如下:

图片

4. 输出杨辉三角形

按照题目要求,需要输出三角形的形状,并且各数字间距相同、左右对称、上下隔行对齐,这个该怎么实现呢?

关于对齐效果,Python提供了center()函数,用法如下:

str.center(width[,?fillchar])

其中,width表示字符串的总宽度,fillchar则表示填充字符,默认为空格。

有了这个函数,问题就变得简单了,只需要将数字转成字符串,然后调用center()方法即可,那么,这里的width设置多少比较合适呢?

题目中明确给出了n的取值范围为[2,15],当n=15时,最大的数字为3432,所以宽度必须要大于4,同时确保左右各空一格,所以设置为6比较合适。

然后就是每一行需要输出空格,空格的数量和行数有关系,以n=6为例,

图片

根据上面的表格,我们可以总结出如下规律:??????

第1行,左边要空出5个单元格,即6?-?0?-?1第2行,左边要空出4个单元格,即6?-?1?-?1第3行,左边要空出3个单元格,即6?-?2?-?1......第i行,左边要空出n?-?i?-?1个单元格

注意,这里的i是从0开始的。

所以,对于第i行而言,要输出的空格数为:

 (n - i - 1) * 3

之所以乘以3,是因为每个数字的宽度为6,6/2 = 3。

分析完毕,就可以编写代码了,如下:

图片

运行程序,输入数字6,效果如下:

图片

再输入数字15,效果如下:

图片

怎么样,对齐效果还是非常nice的吧,至此,整个程序就全部完成了,你也可以输入不同的数字来测试效果。

四.总结与思考

本题的分数为35分,代码在15行左右,涉及到的知识点包括:

  • 循环语句,主要for...in循环;

  • 列表运算,尤其是二维列表;

  • 输出格式控制;

  • 递推算法;

题目难度较大,尤其是对于初学者。难点有两个,一是如何找到杨辉三角数据之间的规律,这是实现递推算法的关键所在,二是如何使用二维列表来表示杨辉三角,并构造出列表。

考生除了要具备扎实的Python语法基础之外,同时还需要具备一定的算法思维,随着学习的不断深入,算法会变得越来越重要。

递推法是一种重要的数学方法,在数学的各个领域中都有广泛的运用,也是计算机用于数值计算的一个重要算法。这种处理问题的方法能将复杂运算简化为若干步重复的简单运算,充分发挥出计算机擅长于重复处理的特点。

使用递推算法,把一个复杂的问题的求解,分解成了连续的若干步简单运算,从这个角度来讲,可以将递推算法看成是一种特殊的迭代算法。

超平老师给你留一道思考题,除了上面讲到的方法外,还有没有其它的方法,具体又是如何实现的呢?

你还有什么好的想法和创意吗,也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助,别忘了点赞和转发,予人玫瑰,手有余香😄

需要源码的,可以移步至“超平的编程课”gzh。

文章来源:https://blog.csdn.net/diamondwang2012/article/details/134988196
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。