蓝桥杯 第五十九天 递推与递归（复习）

递归（复习）"/>

蓝桥杯 第五十九天 递推与递归（复习）

目录

• 递归实现指数型枚举
• 递归实现排列型枚举
• 简单斐波那契
• 费解的开关
• 递归实现组合型枚举
• 带分数
• 飞行员兄弟
• 翻硬币

递归实现指数型枚举

def dfs(cur,path):if cur==n+1:for i in path:print(i,end=" ")print()returndfs(cur+1, path)dfs(cur+1,path+[cur])return
n=int(input())
dfs(1,[])

递归实现排列型枚举

def dfs(path):if len(path)==n:for i in path:print(i,end=" ")print()returnfor i in range(1,n+1):if not vis[i]:vis[i]=Truedfs(path+[i])vis[i]=Falsereturn
n=int(input())
vis=[False for i in range(n+1)]
dfs([])

简单斐波那契

n=int(input())
a,b=0,1
for i in range(n):if i==0:print(0,end=" ")elif i==1:print(1,end=" ")else:a, b = b, b + aprint(b,end=" ")

费解的开关

数组备份问题

import copydef isvalid(x,y):if x<0 or x>=5:return Falseif y<0 or y>=5:return Falsereturn True
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def turn(x,y):adj[x][y]=1-adj[x][y]return
def click(x,y):turn(x,y)for i in range(4):nx=x+dx[i]ny=y+dy[i]if isvalid(nx,ny):turn(nx,ny)return
n=int(input())
for m in range(n):radj=[]for i in range(5):radj.append(list(map(int,list(input()))))ans=1<<31for i in range(1<<5):adj = copy.deepcopy(radj)curans=0for k in range(5):cur=i>>k&1if cur==1:click(0,k)curans+=1for row in range(4):for col in range(5):if adj[row][col]==0:click(row+1,col)curans+=1if curans>6:breakif curans>6:breakif adj[-1].count(0)==0 and curans<=6:ans=min(ans,curans)if ans>1<<30:print(-1)else:print(ans)if m!=n-1:input()

递归实现组合型枚举

def dfs(path):if len(path)==m:for i in path:print(i,end=" ")print()returnif not path:cur=0else:cur=path[-1]for i in range(cur+1,n+1):if not vis[i]:vis[i]=Truedfs(path+[i])vis[i]=Falsereturn
n,m=map(int,input().split())
vis=[False for i in range(n+1)]
dfs([])

带分数

def isvalid(path):#path="123456789"for i in range(9):if int(path[:i+1])>n:breakcur=int(path[:i+1])res=n-cur#左边是i+1，右边是8start=(i+1+8)//2for j in range(start,8):mid=int(path[i+1:j+1])right=int(path[j+1:])# print(path,cur,mid,res)if mid%right==0 and (mid//right)==res:return Truereturndef dfs(path):global ansif len(path)==9:if isvalid(path):ans+=1returnfor i in range(1,10):if not vis[i]:vis[i]=Truedfs(path+str(i))vis[i]=False
vis=[False for i in range(10)]
n=int(input())
ans=0
dfs("")
print(ans)

飞行员兄弟

import copy
def turn(x,y):global curadjif curadj[x][y]=='+':curadj[x][y]='-'else:curadj[x][y]='+'return
def click(x,y):for i in range(4):turn(x,i)turn(i,y)turn(x,y)return
def getans():global ansglobal curadjglobal pathfor k in range(1<<16):curans=0curpath=[]curadj=copy.deepcopy(adj)for i in range(3,-1,-1):for j in range(3,-1,-1):index=i*4+jif k>>index&1:click(i,j)curans+=1curpath.append((i+1,j+1))flag=Truefor i in curadj:if i.count('+')!=0:flag=Falsebreakif flag:if curans<ans:ans=curanspath=curpathelif curans==ans:path=curpath
adj=[]
for i in range(4):adj.append(list(input()))
curadj=[]
path=[]
ans=1<<31
getans()
print(ans)
for i in path[::-1]:print(i[0],i[1])

翻硬币

懵逼树下懵逼果，懵逼ac你和我

def click(x):if a[x]=='o':a[x]='*'else:a[x]='o'if a[x-1]=='o':a[x-1]='*'else:a[x-1]='o'return
a=list(input())
b=list(input())
n=len(a)
ans=0
for i in range(n-1):if a[i]!=b[i]:ans+=1click(i+1)
print(ans)