title: 递推与递归经典问题的python实现
date: 2020-03-26 22:13:26
categories: 算法
tags: [python, 递推与递归]
递归实现指数型枚举
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤151≤n≤15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
代码
每一个位置枚举有选或者不选两种选项
import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())
n=int(input())
sta=[0 for i in range(n+1)]
def dfs(i):
if i> n:
for i in range(n+1):
if sta[i]==1:
print(i,end=" ")
print()
return
sta[i]=0
dfs(i+1)
sta[i]=1
dfs(i+1)
dfs(1)
递归实现排列型枚举
把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
代码
枚举每一位，选择了每一个数就OK。
import sys
sys.setrecursionlimit(10**9)
n = int(input())
st = [0 for i in range(n)]
ways = []
def dfs(u):
if u >= n:
for i in range(n):
print(ways[i] + 1, end = " ")
print()
return
for i in range(n):
if st[i] == 0:
st[i] = 1
ways.append(i)
dfs(u + 1)
ways.pop()
st[i] = 0
dfs(0)
n=input()
n=int(n)
path=[]
def dfs(u,state):
if(u==n):
for each_path in path:
print(each_path,end=" ")
print()
return
for i in range(0,n):
if((state>>i&1)==0):
path.append(i+1)
dfs(u+1,state|1<<i)
path.pop()
dfs(0,0)
递归实现组合型枚举
从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,mn,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。
数据范围
n>0n>0 ,
0≤m≤n0≤m≤n ,
n+(n−m)≤25n+(n−m)≤25
输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
思考题：如果要求使用非递归方法，该怎么做呢？
代码
其实只需要把例1的代码稍加修改就可以了。再增加两个情况，一种是动态数组所选择的数已经超过了m个，或者剩余的数凑不够m个，排除这两种情况就是我们所要的答案了
或者
根据例二，只能一直往后选
一看代码就懂了
IA = lambda:map(int, input().split())
n, m = IA()
res = []
def dfs(u):
global n, m
# 剪枝
if len(res) > m or len(res) + (n - u) < m:
return
if u == n:
for it in res:
print(it + 1, end=" ")
print()
res.append(u)
dfs(u + 1)
res.pop()
dfs(u + 1)
dfs(0)
n,m=map(int,input().split())
ans=[0 for i in range(m+1)]
def dfs(u,start):
if n-start+1<m-u+1:return
if u==m+1:
for i in range(1,m+1):
print(ans[i],end=" ")
print()
return
for i in range(start,n+1):
ans[u]=i
dfs(u+1, i+1)
ans[u]=0
dfs(1,1)
带分数
100 可以表示为带分数的形式：100=3+69258/714
还可以表示为：100=82+3546/1971
注意特征：带分数中，数字 1∼9分别出现且只出现一次（不包含 00）。
类似这样的带分数，100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼91∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<1061≤N<106
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
暴力枚举
m=int(input())
n=9
sta=[0 for i in range(n+1)]
vis=[0 for i in range(n+1)]
ans=0
def f():
a=0
for i in range(1,n):
a=a*10+sta[i]
b=0
for j in range(i+1,n):
b=b*10+sta[j]
if b%a!=0:continue
c=0
for k in range(j+1,n+1):
c=c*10+sta[k]
if c+b//a ==m:
global ans
ans+=1
def dfs(u):
if u>n:
f()
return
for i in range(1,n+1):
if vis[i]==1:continue
vis[i]=1
sta[u]=i
dfs(u+1)
vis[i]=0
sta[u]=0
dfs(1)
print(ans)
n=a+b/c
b=nc-ac 先枚举a后枚举c
m=int(input())
n=9
ans=0
vis=[0 for i in range(n+1)]
backup=[0 for i in range(n+1)]
def f(a,c):
b=m*c-a*c
if b==0:return 0
backup=[x for x in vis]
while b:
x=b%10
if x==0 or backup[x]==1:return 0
backup[x]+=1
b//=10
#print(":"+str(vis))
for i in range(1,n+1):
if backup[i]!=1:
return 0
return 1
def dfs_c(u,c,a):
if u>=n:return
if c:
if f(a,c)==1:
global ans
ans+=1
for i in range(1,n+1):
if vis[i]==0:
vis[i]=1
dfs_c(u+1,c*10+i,a)
vis[i]=0
def dfs_a(u,a):
if u>=n:return
if a:dfs_c(u,0,a)
for i in range(1,n+1):
if vis[i]==0:
vis[i]=1
dfs_a(u+1,a*10+i)
vis[i]=0
dfs_a(1,0)
print(ans)
飞行员兄弟·
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。
但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数N，表示所需的最小切换把手次数。
接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
1≤i,j≤41≤i,j≤4
输入样例：
-+--
----
----
-+--
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4
代码
import copy
mp=[[] for i in range(0,4)]
for i in range(0,4):
mp[i]=list(input())
ans=[]
path=[]
minn=1e18
def turn(x,y):
for i in range(0,4):
if mp[i][y]=='+':mp[i][y]='-'
else:mp[i][y]='+'
for j in range(0,4):
if mp[x][j]=='+':mp[x][j]='-'
else:mp[x][j]='+'
if mp[x][y]=='+':mp[x][y]='-'
else:mp[x][y]='+'
def check():
for i in range(0,4):
for j in range(0,4):
if mp[i][j]=='+':
return 0
return 1
def dfs(x,y,step):
#print(str(x)+" "+str(y))
if x>=3 and y>=4 :
if check()!=1: return
global minn,ans
if step<minn:
minn=step
ans=copy.deepcopy(path)
#print(ans)
return
if y==4:
y=0
x+=1
path.append([x,y])
step+=1
turn(x,y)
dfs(x,y+1,step)
turn(x,y)
path.pop()
step-=1
dfs(x,y+1,step)
dfs(0,0,0)
print(minn)
for it in ans:
print(str(it[0]+1)+" "+str(it[1]+1))
翻硬币
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1：
**********
o****o****
输出样例1：
5
输入样例2：
*o**o***o***
*o***o**o***
输出样例2：
1
| 难度：简单 |
|---|
| 时/空限制：1s / 64MB |
| 总通过数：574 |
| 总尝试数：829 |
| 来源：第四届蓝桥杯省赛C++B组 |
| 算法标签 |
s1=input()
s2=input()
le=len(s1)
pre=-1
ans=0
for i in range(0,le):
if s1[i]!=s2[i]:
if pre==-1:
pre=i
else:
ans+=i-pre
pre=-1
print(ans)
