【每日一题】备战冲击蓝桥杯国赛——Python程序设计 | Day09 | 数字三角形 | 真题代码解析
每天刷一道题，话不多说，先刷近两年的题吧，从2020的开始，如果有一起的可以加入我们！！！
一起来刷题，冲击国赛！！！
2020年第十一届蓝桥杯赛题总览
2020年的题就是这些，类型分为两种，分别是结果填空和程序设计，我们每天刷一道题，省赛没问题！
数字三角形（题目）
（本题总分：10分）
官方练习系统：https://www.lanqiao.cn/problems/505/learning/
—>【问题描述】
<div style="color:orange; border-bottom: 1px solid #d9d9d9; display: inline-block; color: #999; </center>
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
—>【输入描述】
输入的第一行包含一个整数 ，表示三角形的行数。
下面的 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
—>【输出描述】
输出一个整数，表示答案。
—>【输入输出样例】
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：
27
解析
通过阅读题干，本题——难度一般：⭐⭐
考察类型：动态规划、遍历
考察知识点：map()，max()
分析：
直接遍历吧！
从题干来看，输入第一行为一个整数N，代表一共有多少行。从三角形的结构可知，从上到下，依次加一，五行也就是，1，2，3， 4，5个数分别各行。数字为（0~100）之间的整数。
往下走的条件为：向左下走的次数和右下走的次数相差不能超过1.比如示例的走法如下：
此上图来看，红色的路径走法结果为：27
下面直接开干！！！
代码
Python代码实现：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2022/3/3 14:52
# @Author : 府学路18号车神
# @Email ：yurz_control@163.com
# @File : Day09.py
n = int(input("输入三角形的行数："))
in_set = [list(map(int, input("输入每行的数：").split())) for i in range(n)] # [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
print(in_set)
# insert
# 循环遍历计算每行的和最大值
for i in range(1, n): # i代表遍历的行，外层
for j in range(0, i+1): # 内层循环，遍历每一层中数字
if j == 0: # 判断最左边的数字，只能由右上方得到
in_set[i][j] += in_set[i-1][j]
elif j == i: # 判断最右边的数字只能由左上方得到
in_set[i][j] += in_set[i-1][j-1]
else: # 排除玩左右两边的，现在只剩下中间的了
in_set[i][j] += max(in_set[i-1][j-1:j+1])
# 当遍历计算完成数值后，设置判断输出
if n & 1: #判断如果行数N为奇数，则返回中间值
print(in_set[-1][n//2]) # 平板除//
else:
print(max(in_set[-1][n//2], in_set[-1][(n//2)-1])) #相反，n为偶数的时候，则返回中间数值最大的一个
示例1：
其实还可以用dp动态规划来实现，由于理解和普适性，还是用遍历判断可能通俗易懂一些，加油！
由此，我们可以快速得出结果，验证完毕！
- 点赞
- 收藏
- 关注作者
评论（0）