概念
递归:函数存在本身调用自身的情况,这便是递归。递的意思就是将问题拆解成子问题进行求解,子问题再进一步求解,直到无法进一步细致。归的意思就是最小子问题的求解。递归解题通用解决思路:
1.一个问题可以分解成具有相同解决思路的子问题(本质就是能调用同一个函数dfs)
2.经过层层分解的子问题最后一定是有一个不能再分解的固定值的(即终止条件)。当具备以上条件时,我们即可在一定T复杂度下使用递归实现。
递推:通过一定的公式或者堆砌将我们的结果从底层开始进行递推。
例题
Question_1
递归实现指数型枚举(原题链接)
Answer_1
对于该问题,我们每个数字都是选与不选两种情况,不妨将0视为低电平,1为高电平触发使用。
故我们可以利用二进制来表示每次的结果。
我们可以通过位运算来获取每次的值
代码如下:
n=int(input())
for i in range((1<<n)):
lst=[]
for k in range(n):
if i>>k & 1:
#说明该位为1
lst.append(str(k+1))
if len(lst)==0:
print(' ')
else:
print(' '.join(lst))
这是我们对题目进行理解后得到的结果,但我们在考场上可能很难第一时间就想到这种简洁的方式(bushi)。我们可以联想到递推。通过逐个递推每个数字是否使用,直到达到最后一个数字system.out。
代码如下:
n=int(input())
st_list=[0 for i in range(n+1)]#存储每个数是否被利用
def dfs(k):
#k:当前遍历的数字
if k>n:
str_lst=[]
for i in range(1,n+1):
if st_list[i]:
str_lst.append(str(i))
print(' '.join(str_lst))
return
st_list[k]=1
dfs(k+1)#用k
st_list[k]=0#恢复现场
dfs(k+1)#不用k
dfs(1)
以上两种代码均可AC。
Question_2
递归实现排列型枚举(原题链接)
Answer_2
典型的萝卜填坑问题,我们利用st_lst来存储每个位置当前放置的数,同时judge_lst来存储每个数的利用情况(0代表未使用,1使用,模拟布尔值)。通过由小到大的顺序来进行dfs以满足字典序。
代码如下:
n=int(input())
st_lst=[0 for i in range(n+1)]#每个位置存储的数列表
judge_lst=[0 for i in range(n+1)]
def dfs(k):
if k>n:
print(' '.join(list(map(str,st_lst[1:]))))
return
for i in range(1,n+1):
if judge_lst[i]==0:
st_lst[k]=i
judge_lst[i]=1
dfs(k+1)#下一层遍历
judge_lst[i]=0#恢复原状,不然全部都是exist
dfs(1)
Question_3
费解的开关([原题链接][https://www.acwing.com/problem/content/97/])
Answer_3
针对该问题,我们需要从题目特征中进行分析,开关两次就相当于没有任何效果,故我们对每个开关只需动一次or零次即可,而且当我们从上往下枚举时,每一个只会影响其上面的灯泡(因为后面的灯泡我们可以后考虑,无顺序性的好处)。最后只需要特判最后一行是否全亮即可(同时需要关注次数是否在六步之内)。于是这就是我们最典型的递推问题。
代码如下:
from copy import deepcopy
n=int(input())
dx=[0,0,1,0,-1]
dy=[0,-1,0,1,0]
def change(x,y):
for i in range(5):
a=x+dx[i]
b=y+dy[i]
if a>=0 and a<5 and b>=0 and b<5:
mat_copy[a][b]^=1#取反操作
for _ in range(n):
cnt=10
drag_mat=[list(map(int,list(input()))) for _ in range(5)]
#这里由于第一行的特殊情况,我们需要进行枚举,不然的话就不一定是最优解
#因为我们是从第二行开始操作的,故需要枚举第一行的操作。
for num in range(32):
#进行深复制,防止对原来的Mat造成影响
mat_copy=deepcopy(drag_mat)
ans=0
for k in range(5):
if (num>>k)&1:
change(0,k)
ans+=1
for i in range(4):
for j in range(5):
if mat_copy[i][j]==0:
change(i+1,j)
ans+=1
#对最后一行进行特判
for j in range(5):
if mat_copy[4][j]==0:
ans=10
cnt=min(cnt,ans)
if cnt>6:
cnt=-1
print(cnt)
try:
_=input()
except:
break
Question_4
递归实现组合型枚举([原题链接][https://www.acwing.com/problem/content/95/])
Answer_4
该题借鉴排列型枚举的思路,只不过我们的坑变少了而已。
代码如下:
n,m=map(int,input().split())
num=[]#引入动态数组存储结果
def dfs(k):
if len(num)>m or len(num)+(n-k+1)<m:
#长度超过m或者剩余的数无法到达m,则采取剪枝,break即可
return
if k==n+1:
print(' '.join(list(map(str,num))))
num.append(k)#选择k
dfs(k+1)
#回溯
num.remove(k)
dfs(k+1)#不选择k
dfs(1)
#体会一下动态数组的强大!
Quesion_5
带分数([原题链接][https://www.acwing.com/problem/content/1211/])
Answer_5
该题典型的全排列问题,我们可以首先进行全排列,随后进行a|b|c的分离模式进行判决等式是否成立。(但很明显该算法未实现剪枝操作,复杂度较高,无法AC)
n=int(input())
count=0
exit_list=[0 for i in range(9)]
num_list=[0 for i in range(9)]
def calc(l,r):
res=0
for i in range(l,r+1):
res=res*10+num_list[i]
return res
def dfs(num):
global count
if num==9:
for i in range(7):
a=calc(0,i)
if a>n:
continue
for j in range(i+1,8):
b=calc(i+1,j)
c=calc(j+1,8)
if (a*c+b==c*n):
#转换成乘法(算法中常用的思想)
count+=1
return
for i in range(9):
if not exit_list[i]:
exit_list[i]=1
num_list[num]=i+1
dfs(num+1)
exit_list[i]=0#回到初始状态
dfs(0)
print(count)
第二种解法:我们首先对于a进行排列型枚举,再对b进行,然后通过判决等式进行剪枝(c是否满足我们的条件:全选且不重复)。思路简单,但实操起来比较难理解(需要对栈的认知较高以及对python存储方式有所了解)。
代码如下:
n=int(input())
count=0
exit_list=[0 for i in range(9)]
num_list=[0 for i in range(9)]
def calc(l,r):
res=0
for i in range(l,r+1):
res=res*10+num_list[i]
return res
def dfs(num):
global count
if num==9:
for i in range(7):
a=calc(0,i)
if a>n:
continue
for j in range(i+1,8):
b=calc(i+1,j)
c=calc(j+1,8)
if (a*c+b==c*n):
#转换成乘法(算法中常用的思想)
count+=1
return
for i in range(9):
if not exit_list[i]:
exit_list[i]=1
num_list[num]=i+1
dfs(num+1)
exit_list[i]=0#回到初始状态
dfs(0)
print(count)
Question_6
飞行员兄弟([原题链接][https://www.acwing.com/problem/content/118/])
Answer_6
这题思路与费解的开关一致,并未变得更加复杂。但调试代码比较麻烦,不容易一次性写对。
代码如下:
bridge_matrix=[]
mat=[]
count=10000
num=0
for i in range(4):
mat.append(list(input()))
def change(i,j):
global bridge_matrix
for t in range(4):
bridge_matrix[i][t]='-'if bridge_matrix[i][t]=='+' else '+'
bridge_matrix[t][j]='-'if bridge_matrix[t][j]=='+' else '+'
bridge_matrix[i][j]='-'if bridge_matrix[i][j]=='+' else '+'
def check():
for i in range(4):
for j in range(4):
if bridge_matrix[i][j]=='+':
return False
return True
def dfs():
global bridge_matrix,count,num
for i in range(1,2**16):
#print(i)
bridge_matrix=mat.copy()
t=0
for j in range(15,-1,-1):
state=(i>>j)&1
ind=(15-j)//4
col=(15-j)%4
if state:
change(ind,col)
t+=1
if check()and(t<count):
num=i+1
count=t+1
print(count)
for j in range(15,-1,-1):
state=(num>>j)&1
ind=(15-j)//4
col=(15-j)%4
if state:
print(str(ind+1)+' '+str(col+1))
dfs()
Question_7
翻硬币([原题链接][https://www.acwing.com/problem/content/1210/])
Answer_7
该题与费解的开关也很类似,而且更为简单。我们也可以利用递推来求解。做这种题就应该想到我们的操作顺序以及次数是否会对原有state有何影响。若满足操作顺序、偶数次数没影响时,阔以利用递推的思维来进行判断。
代码如下:
str_init=list(input())
str_target=list(input())
count=0
def turn(i):
global str_init
for t in range(i,i+2):
str_init[t]='*' if str_init[t]=='o' else 'o'
def check(i):
if str_init[i]==str_target[i]:
return 0
return 1
def dfs():
global count
for i in range(len(str_target)-1):
if check(i):
turn(i)
count+=1
dfs()
print(count)
总结
我们可以得知,递推和递归的思想可以用来求解操作方式单一、问题可以逐步化解、操作顺序对结果无影响的问题。当然个人总结比较片面,仅供参考。