下载 做网站的原型文件,天水市建设局网站吊篮管理通知,关键词排名查询工具有什么作用?,做外卖网站目录 1 DFS简介
1.1 DFS与n重循环
1.2 代码实现
1.3 例题
1.3.1 分糖果
1.3.2 买瓜
2 回溯
2.1 定义
2.2 代码实例
2.1.1 排列数 2.1.2 找子集
2.3 例题
2.3.1 N皇后
2.3.2 小朋友崇拜圈
2.3.3 全球变暖
3 剪枝
3.1 定义
3.2 分类
3.3 例子
3.3.1 数字王国之…
目录 1 DFS简介
1.1 DFS与n重循环
1.2 代码实现
1.3 例题
1.3.1 分糖果
1.3.2 买瓜
2 回溯
2.1 定义
2.2 代码实例
2.1.1 排列数 2.1.2 找子集
2.3 例题
2.3.1 N皇后
2.3.2 小朋友崇拜圈
2.3.3 全球变暖
3 剪枝
3.1 定义
3.2 分类
3.3 例子
3.3.1 数字王国之军训练队
3.3.2 特殊的多边形
4 记忆化搜索
4.1 定义
4.2 例子
4.2.1 斐波那契数列
4.2.2 混沌之地
4.2.3 地宫取宝 1 DFS简介
1.1 DFS与n重循环
DFS 就是枚举 和n重循环 1.2 代码实现 #dfs和n重循环
x int(input())
n int(input())
path [0]*n
#depth从0开始哦def dfs(depth):#depth表示当前的深度#采用递归的思想#写递归出口if depth n:for i in range(1,n):if path[i] path[i-1]:continueelse:returnif sum(path) ! x:returnprint(path)returnelse:for i in range(1,x1):path[depth] idfs(depth1)dfs(0) 1.3 例题
1.3.1 分糖果 #糖果总数
#一共有7个小朋友9个第一种糖果16个第二种糖果
ans 0
def dfs(depth,n,m):#depth当前是第几个小朋友#n表示剩余几个第一种#m表示剩余几个第二种if depth 7:if n0 and m0:global ansans 1# print(ans)returnelse:for i in range(0,6):for j in range(0,6):if 2ij5 and i n and jm:dfs(depth1,n-i,m-j)dfs(0,9,16)
print(ans) 1.3.2 买瓜 #买瓜def dfs(depth,weight,cnt):#depth表示第depth个瓜#weight表示当前的重量#cnt表示砍了几刀if weight m:returnif weight m:global ansans min(ans,cnt)if depth n:returnelse:#买全部dfs(depth1,weighta[depth],cnt)#卖一半dfs(depth1,weighta[depth]//2,cnt1)#没买dfs(depth1,weight,cnt)n,m list(map(int,input().split()))
a list(map(int,input().split()))
weight 0
cnt 0
m*2
a [i*2 for i in a]
ans n1
dfs(0,0,0)if ans n1:ans -1print(ans)
2 回溯
2.1 定义 2.2 代码实例
2.1.1 排列数 回溯判断是否能选、打标记、记录路径、下一层、回到上一层是怎么回去的啊老铁清楚标记、清楚路径储存
回到上一层通过debug我得出回到上一层其实是递归自己过程中的实现 递归会造成多个函数的运行只有运行完才会结束语言描述能力有限具体可以自己debug一下感受
n int(input())
vis [False]*(n1)
path []def dfs(depth):if depth n:print(path)returnelse:for i in range(1,n1):if vis[i]: #如果已经被标记过就不选这个数直接跳出循环continuevis[i] Truepath.append(i)dfs(depth1)vis[i] Falsepath.pop(-1)dfs(0) 2.1.2 找子集
和买瓜一样瓜是这个瓜买不买
子集是这个数选不选 一模一样哦哦哦
找到人任意集合的所有子集
#求子集
#和卖瓜的一样
n int(input())
a list(map(int,input().split()))path []def dfs(depth):if depth n:print(path)returnelse:#选的话path.append(a[depth])# print(path)dfs(depth1)path.pop(-1)#不选的话dfs(depth1)
dfs(0) 2.3 例题
2.3.1 N皇后 不能在同一行同一列和对角线上
# N皇后
#主要是对角线的处理如果在主对角线上 横纵坐标的值相加为0在副对角线上横纵坐标相减为0
n int(input()) #表示有几个皇后
ans 0
vis1 [False]*(n1)
vis2 [False]*2*(n1)
vis3 [False]*2*(n1)def dfs(x): #x表示第几行if xn:global ansans 1returnelse:for y in range(0,n):#判断是否能放if vis1[y] is False and vis2[xy] is False and vis3[x-yn] is False:vis1[y] vis2[xy] vis3[x-yn] Truedfs(x1)vis1[y] vis2[x y] vis3[x - yn] Falseelse:continuedfs(0)
print(ans)
2.3.2 小朋友崇拜圈 就是要围成一个圈图论的知识相关 从1出发 开始找环length用于记录步长--走到之后判断是否可以走如果不可以走说明到了原来走过的点了
#小朋友崇拜环
import sys
sys.setrecursionlimit(10000000) #例如这里设置为十万
def dfs(x,length):#从x出发找环#length走了多少步vis[x] length #这个点走了一步现在#接下来走下面的点了if vis[a[x]] ! 0:#说明在a[x]这一点形成环了那么这个点出的length值应该是第一步global ansans max(ans,length - vis[a[x]] 1)return#说明下一个点已经走过了#这时就要输出环长了else:#说明可以走dfs(a[x], length1) #步长加1n int(input())
a [0] list(map(int,input().split()))
vis [0]*(n1) #标记该点是否走过
ans 0
an []for i in range(1,n1):dfs(i,1)
print(ans)2.3.3 全球变暖 高地上下左右都是#
对于每一个#都看看是不是高地
思路
1、从左到右 从上到下对于未标记的陆地“#”做一遍dfs
2、dfs目的拓展可以到达的所有点并打上标记
3、可以统计出有多少个岛屿、有多少个高地上下左右都是#
#全球变暖
import sys
sys.setrecursionlimit(10000000) #例如这里设置为十万def dfs(x,y):#表示现在搜索的点的坐标#标记该点vis[x][y]1#判断是不是高低if a[x-1][y] # and a[x1][y] # and a[x][y-1] # and a[x][y1] # :#说明上下左右都是高低不会被淹没global flagflag True#把四周的未遍历的土地继续遍历!!!!!!!#所有连在一起的就是一座岛屿#这个坐标周围如果还有陆地说明他们是一个岛屿 没有结束接着运行for i in range(4):xx,yy xdir[i][0],ydir[i][1]if 0xx n-1 and 0 yyn-1:if a[xx][yy] # and vis[xx][yy] 0:dfs(xx,yy)else:continue#先写输入
dir [(1,0),(0,1),(-1,0),(0,-1)]
n int(input())
a []
vis [] #表示标记
flag False#表示是否是高地
for i in range(n):a.append(list(input()))vis.append([0]*n)ans 0
for i in range(n):for j in range(n):if a[i][j] # and vis[i][j] 0:flag Falsedfs(i,j)if flag is False:ans 1
print(ans)
3 剪枝
3.1 定义 当前状态无解就不要向下搜索了
3.2 分类 3.3 例子
3.3.1 数字王国之军训练队 把学生分组
则dfs的参数就是学生
#数字王国之军训练队
#学生分成多少组--学生————所以depth是学生
n int(input())
a list(map(int,input().split()))
group []def check(x,group):for y in group:if x%y0 or y%x 0 or xy:return Falsereturn Truedef dfs(depth):if depth n:global ansans min(ans,len(group))# print(group)return ans#放入已有的组中for ever_group in group:if check(a[depth],ever_group):ever_group.append(a[depth])dfs(depth1)ever_group.pop(-1)#自己变成一个组group.append([a[depth]])dfs(depth1)group.pop(-1)#最后要输出一个最小组数
ans n
dfs(0)
print(ans) 3.3.2 特殊的多边形 #剪枝-特殊的多边形
import sys
sys.setrecursionlimit(100000) #例如这里设置为十万
t,n list(map(int,input().split()))
a []
for i in range(t):a.append(list(map(int,input().split())))
# print(a)def dfs(depth,last_i,tot,mul,list):if depth n:if tot 2*path[-1] and list[0] mul list[1]:global ansans 1# print(path)returnelse:for i in range(last_i1,100001):if mul*(i**(n-depth)) list[1]:path.append(i)dfs(depth1,i,toti,mul*i,list)path.pop(-1)else:breakfor list in a:path []ans 0dfs(0,1,0,1,list)print(ans)
4 记忆化搜索
4.1 定义 4.2 例子
4.2.1 斐波那契数列 考虑使用递归写法直接递归的时间是指数级别增加的 重复计算的地方发在字典里
#斐波那契数列
#没有存储的写法
def f(n):if n0:return 1if n1:return 1else:return f(n-1)f(n-2)
n int(input())
print(f(n))#存储的写法dict{0:1,1:1}
def f(n):if n in dict.keys():return dict[n]else:dict[n] f(n-1)f(n-2)return dict[n]
print(f(40))
但是有一个更牛*的
记忆化搜索的第二种方法
#实现把普通的递归变成记忆化的递归
from functools import lru_cache
lru_cache(maxsizeNone)
def f(n):if n0:return 1if n1:return 1else:return f(n-1)f(n-2)
n int(input())
print(f(n))
4.2.2 混沌之地 dfs的参数确定 坐标
from functools import lru_cache
lru_cache(maxsizeNone)
def dfs(x,y,z):#x,y 表示当前的坐标#z表示喷气背包有没有用if x c and yd:return Trueelse:for detle_x,detle_y in [(0,1),(1,0),(-1,0),(0,-1)]:xx xdetle_xyy ydetle_yif 0xxn-1 and 0yym-1:if A[xx][yy] A[x][y]:dfs(xx,yy,z)if A[xx][yy] A[x][y]k and zFalse:dfs(xx,yy,True)return False#输入
n,m,k list(map(int,input().split()))
a,b,c,d list(map(int,input().split()))
a -1
b -1
c -1
d -1A []
for i in range(n):A.append(list(map(int,input().split())))#输出
out dfs(a,b,False)
if out True:print(Yes)
else:print(No)
5 5 30
1 1 5 5
3 20 13 12 11
19 17 33 72 10
12 23 12 23 9
21 43 23 12 2
21 34 23 12 14.2.3 地宫取宝 ####当没有不使用记忆搜素并且加入的是当前位置的val值时
def dfs(x,y,tot,w) : #在x,y)的数量tot,最大价值为wif xn and ym :global ansif totk:ans 1returnreturnfor delta_x,delta_y in [(0,1),(1,0)]:xx,yyxdelta_x,ydelta_yif 0xxn and 0yym:if w val[xx][yy]: #把上一个位置的value加进去了dfs(xx,yy,tot1,val[xx][yy])dfs(xx, yy, tot, w) # 不选择else:continuereturnn,m,kmap(int,input().split())
val[[0]*(m1)]
for i in range(n):val.append([0]list(map(int,input().split())))
print(val)ans 0
dfs(1,1,1,1)
dfs(1,1,0,-1)
print(ans)
###当不使用记忆力搜索加入的是上一个位置的val值
def dfs(x,y,tot,w) : #在x,y)的数量tot,最大价值为wif xn and ym :global ansif totk:ans 1returnelif totk-1 and wval[n][m]:ans1returnreturnfor delta_x,delta_y in [(0,1),(1,0)]:xx,yyxdelta_x,ydelta_yif 0xxn and 0yym:if w val[x][y]: #把上一个位置的value加进去了dfs(xx,yy,tot1,val[x][y])dfs(xx, yy, tot, w) # 不选择else:continuereturnn,m,kmap(int,input().split())
val[[0]*(m1)]
for i in range(n):val.append([0]list(map(int,input().split())))
print(val)ans 0
dfs(1,1,0,-1)
print(ans)
###当使用记忆力搜索时【和之前所有的不同的就是return一定要有返回值不能是空了要不然记忆什么 我请问呢小姐姐】
from functools import lru_cache
lru_cache(maxsizeNone)
def dfs(x,y,tot,w) : #在x,y)的数量tot,最大价值为wif xn and ym :if totk:return 1elif totk-1 and wval[n][m]:return 1return 0ans 0for delta_x,delta_y in [(0,1),(1,0)]:xx,yyxdelta_x,ydelta_yif 0xxn and 0yym:if w val[x][y]: #把上一个位置的value加进去了ans dfs(xx,yy,tot1,val[x][y])ans dfs(xx, yy, tot, w) # 不选择else:continuereturn ansn,m,kmap(int,input().split())
val[[0]*(m1)]
for i in range(n):val.append([0]list(map(int,input().split())))print(dfs(1,1,0,-1))
