【每日一题】备战冲击蓝桥杯国赛——Python程序设计 | Day14 | 路径 | 真题代码解析
每天刷一道题,话不多说,先刷近两年的题吧,现在是2021年的真题了,如果有一起的可以加入我们!!!
一起来刷题,冲击国赛!!!
扫码 我的主页 网页左边下方 群二维码。
加入方式:可以在下方的微信名片加我,然后拉你入群。(记得备注暗号:我要拿国奖)
2021年第十二届蓝桥杯赛题总览
2020年的题就是这些,类型分为两种,分别是结果填空和程序设计,我们每天刷一道题,省赛没问题!
路径 (题目)
(本题总分:10分)
官方练习系统:https://www.lanqiao.cn/problems/1460/learning/
—>【问题描述】
—>【结果描述】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
解析
通过阅读题干,本题——难度中等:⭐⭐⭐
考察类型:动态规划、Dijkstra
考察知识点:最小公倍数、gcd()、math
分析:
路径最短,一般有Dijikstra(迪杰斯特拉算法)和动态规划的方法可以解决。但更推荐动态规划的方法,更简单便捷!!!
- Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。由for循环可知,其时间复杂度是O(n^2)。
艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra,1930年5月11日~2002年8月6日),生于荷兰Rotterdam,
计算机科学家,毕业就职于荷兰莱顿大学,早年钻研物理及数学,而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖,之后,他还获得过1974年AFIPS
Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM
PODC最具影响力论文奖。 ——选自《百度百科:艾兹格·迪科斯彻》
具体算法可以看一个B站重庆小姐姐的4分钟视频讲解(贪心思想),还有一个更好一点的B站视频五分钟,感觉更通俗易懂。
下面直接开干!!!
代码
Python代码实现:
法一:(Dijkstra)
#狄克斯特拉算法
#字典 cost,graph,parents
#1:找到最便宜的结点(未访问),其邻居开销如有更小,更新(cost,parent)
def lcm(a,b):
s=a*b
while b:
a,b=b,a%b
return int(s/a)
graph={}#构图
costs={}
parent={}
for i in range(1,2022):
graph[i]={}
if i<=2020:
for j in range(i+1,i+22):
graph[i][j]=lcm(i,j)
else:
for j in range(i+1,2022):
graph[i][j]=lcm(i,j)
costs[i]=float('inf')
found=[]#查找过的结点
costs[1]=0#开始点w为最便宜的点,价格为0
def find(dict):#查找最便宜的结点
node,cost=None,float('inf')
for k,v in dict.items():
if k not in found and v<cost:
node,cost=k,v
return node
node=find(costs)
while node:
spend=costs[node]
friend=graph[node]
try:
for i in friend.keys():
if costs[i]>friend[i]+costs[node]:
costs[i]=friend[i]+costs[node]
parent[i]=node
except:#无邻居,costs会报错,说明已经达到终点,打印即可
print(costs[2021])
break
found.append(node)
node=find(costs)
end=parent[2021]#回溯广搜层数
count=1
while end!=1:
count+=1
end=parent[end]
print(count) #路径长度10266837,回溯了97次,10266837
法二(动态规划):
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2022/3/8 15:34
# @Author : 府学路18号车神
# @Email :yurz_control@163.com
# @File : DP.py
# 当然也可以用自带的库来计算最小公倍数
import math #导入math库
#print(math.gcd(a,b)) #利用函数求解最大公约数
#print(a*b/math.gcd(a,b)) #利用上面的函数求解最小公倍数
INF = 0x3f3f3f3ff3ff # 定义一个较大的值
N = 2025 # 点的个数,总多取一些
d = [INF for i in range(N)] # 下标i表示第i个点到第一个点的最小的情况的值
d[1] = 0
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
def lcm(a, b):
return int(a * b / gcd(a, b)) # 经典最小公倍数
for i in range(1, N): # 从第一个点遍历
for j in range(i + 1, min(N, i + 22)): # i每跟新一下 后面21个点就开始跟新保留最小的情况
d[j] = min(d[j], lcm(i, j) + d[i]) # 1 到第j个点的距离总是取小的
print(d[2021]) # 10266837
可以得出最终的结果为:10266837
由此,我们可以快速得出结果,验证完毕!
- 点赞
- 收藏
- 关注作者
评论(0)