《蓝桥杯》30天拿下Python算法设计与分析【Day 11】
做你想做的，错的算我的
这里是Want595，欢迎光临我的世界 ~
系列文章目录
《蓝桥杯》30天拿下Python算法设计与分析
目录
系列文章目录
前言
一、最大油田问题
问题引入
程序设计
算法分析
二、员工派对
问题引入
程序设计
算法分析
总结
前言
深度优先算法是图中的一个主要算法，简称DFS算法 。
一、最大油田问题
问题引入
【问题描述】政府现勘探到一片油田，在这一片油田中有很多散落的石油资源。因为经费原因，政府只能开采一处油田，所以需要找到最大的油田进行施工。油田的地理情况被简化成了一个矩阵，其中每一个方格代表一块土地，0代表陆地，1代表是石油资源。如果一处石油资源和另一处石油资源相连接，则其算一块油田。现要找到最大的相互连接的石油资源，并输出它的面积。
【输入形式】
第一行为油田的长和宽，第二行为油田。
【输出形式】
最大油田的面积.
【样例输入】
7 7
0 0 0 0 1 1 0
0 1 1 0 1 1 0
0 1 1 0 0 0 0
0 0 1 0 0 1 1
0 0 0 0 0 0 0
0 0 1 1 0 0 0
0 0 0 1 0 0 1
【样例输出】
5
程序设计
def MaxArea(lst,m,n):
arrived=[[0 for j in range(n)] for i in range(m)]
s=0
def DFS(x,y):
if x>=0 and x<m and y>=0 and y<n and not arrived[x][y] and lst[x][y]==1:
arrived[x][y]=1
return 1+DFS(x-1,y)+DFS(x+1,y)+DFS(x,y-1)+DFS(x,y+1)
else:
return 0
for i in range(m):
for j in range(n):
t=DFS(i,j)
if t>s:
s=t
return s
m,n=map(int,input().split())
lst=[]
for i in range(m):
lst.append(list(map(int,input().split())))
print(MaxArea(lst,m,n))
算法分析
深度优先搜索所有的可开采油田即可。
二、员工派对
问题引入
【问题描述】
公司要举办一个员工派对，公司里所有的员工都有资格来参加。该公司的组织结构是一个二叉树结构。如果一个结点A有双亲结点B，则代表B是A的上司。实际上，每一个员工为派对带来的贡献不一样，有的人幽默，就能使派对更加有趣，而有的人恰恰相反。然而，假如该公司里的所有员工都对自己的上司不满意（假设其有上司），那么如果一个员工来到派对，其上司就不能来到派对，反之亦然。但员工和员工上司的上司可以一起参加派对，因为他们互相不熟悉。如果你是董事长的秘书，并且已知公司组织结构，应该怎么邀请员工，使得任何一组员工和上司不会同时出现在派对中，并且使得邀请的所有员工的贡献值之和最大。
【输入形式】
按二叉树层序输入员工的价值。
【输出形式】
贡献值之和的最大值。
【样例输入】
3 4 5 1 3 1
【样例输出】
9
程序设计
class treenode():
def __init__(self,val):
self.val=val
self.left=None
self.right=None
Input=list(map(int,input().split()))
tree=[treenode(0)]
for i in Input:
tmp=treenode(i)
tree.append(tmp)
for i in range(1,len(tree)):
if tree[i].val==0:
continue
if 2*i<=len(tree)-1 and tree[2*i].val!=0:
tree[i].left=tree[2*i]
if 2*i+1<=len(tree)-1 and tree[2*i+1].val!=0:
tree[i].right=tree[2*i+1]
def ans(root):
at_val,ab_val=DFS(root)
return max(at_val,ab_val)
def DFS(node):
if (node==None):
return 0,0
left_at,left_ab=DFS(node.left)
right_at,right_ab=DFS(node.right)
Attend_Value=int(node.val)+left_ab+right_ab
Absent_Value=max(left_at,left_ab)+max(right_at,right_ab)
return Attend_Value,Absent_Value
print(ans(tree[1]))
算法分析
牢牢掌握二叉树的性质，对递归算法灵活应用。
总结
DFS算法是二叉树的重要应用，在解决很多问题时都需要灵活使用，主要是一种递归的思想