文章目录
1、递归实现指数型枚举
题目
从 1∼n这 n个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。对于没有选任何数的方案，输出空行。
n=int(input())
path=[]
def dfs(u):
if u>n:
for i in path:
print(i,end=' ')
print()
return
dfs(u+1)
path.append(u)
dfs(u+1)
path.pop()
dfs(1)2、递归实现排列型枚举
题目
把 1∼n这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 11 个。首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
n=int(input())
status=[0 for i in range(n+1)]
used=[False for i in range(n+1)]
def dfs(u):
if u>n:
for i in status[1:]:
print(i,end=' ')
print()
return
for i in range(1,n+1):
if used[i]==False:
used[i]=True
status[u]=i
dfs(u+1)
used[i]=False
status[u]=0
dfs(1)3、递归实现组合型枚举
题目
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 11 个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
n,m=map(int,input().split())
status=[0 for i in range(n+1)]
used=[False for i in range(n+1)]
def dfs(u):
if u>=m:
for i in range(m):
print(status[i],end=' ')
print()
return
for i in range(1,n+1):
if used[i]==False and (u==0 or i>status[u-1]):
used[i]=True
status[u]=i
dfs(u+1)
used[i]=False
status[u]=0
dfs(0)
4、简单斐波那契
题目
以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。这个数列从第 33 项开始，每一项都等于前两项之和。输入一个整数 N，请你输出这个序列的前 N 项。
输入格式
一个整数 N。
输出格式
在一行中输出斐波那契数列的前 N项，数字之间用空格隔开。
n=int(input())
a=[0 for i in range(n+1)]
a[1]=1
for i in range(2,n+1):
a[i]=a[i-1]+a[i-2]
for i in range(n):
print(a[i],end=' ')5、带分数
题目
100 可以表示为带分数的形式：100=3+69258/714 还可以表示为：100=82+3546/197注意特征：带分数中，数字 1∼9分别出现且只出现一次（不包含 0）。类似这样的带分数，100 有 11种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9不重复不遗漏地组成带分数表示的全部种数。
def check(a,c):
global ans
b = c*(n-a)
nums = set('123456789')
tmp = str(b)+str(c)+str(a)
if( len(tmp) == 9 and set(tmp) == nums):
ans += 1
def dfs_c(a,c):
if(len(str(c)) > 7):
return
b = c*(n-a)
if(len(str(b)) > 7 ):
return
if(c>0):
check(a,c)
for i in range(1,10):
if(not used[i]):
used[i] = True
dfs_c(a,c*10+i)
used[i] = False
def dfs_a(a):
if (a>=n or len(str(a))>7):
return
if a>0:
dfs_c(a,0)
for i in range(1,10):
if used[i]==False:
used[i]=True
dfs_a(a*10+i)
used[i]=False
n = int(input())
used = [False for _ in range(10)]
ans = 0
dfs_a(0)
print(ans)6、翻硬币
题目
小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。比如，可能情形是：**oo***oooo如果同时翻转左边的两个硬币，则变为：oooo***oooo现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
def turn(a,s):
if a[s]=='o':
a[s]='*'
else: a[s]='o'
s11=input()
s1=list(s11)
s22=input()
s2=list(s22)
ans=0
for i in range(len(s1)-1):
if s2[i]!=s1[i]:
turn(s2,i)
turn(s2,i+1)
ans+=1
print(ans)