系列文章目录

《蓝桥杯》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]))