1.递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
数据范围
1≤n≤15

n=int(input())
status=[0]*n
def dfs(x):
    if x==n:
        count+=1
        l=[]
        for i in range(n):
            if status[i]==1:
                l.append(str(i+1))
        print(' '.join(l))
    else:
        status[x] = 1
        dfs(x + 1)
        status[x] = 0

        status[x]=2
        dfs(x+1)
        status[x]=0

dfs(0)

2.递归实现排列型枚举

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1≤n≤9

n=int(input())
status=[False]*(n+1)
ans=['0']*(n+1)
def dfs(x):
    if x>n:
        print(' '.join(ans[1:]))
        return
    for i in range(1,n+1):
        if not status[i]:
            ans[x]=str(i)
            status[i]=True
            dfs(x+1)
            ans[x]='0'
            status[i] = False

dfs(1)

3.简单斐波那契

以下数列 0 1 1 2 3 5 8 13 21 … 被称为斐波纳契数列。
这个数列从第 3 项开始，每一项都等于前两项之和。
输入一个整数 N，请你输出这个序列的前 N 项。
输入格式
一个整数 N。
输出格式
在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。
数据范围
0<N<46
输入样例：
5
输出样例：
0 1 1 2 3

n=int(input())
if n==1:
    print(0)
elif n==2:
    print('0 1')
else:
    l = [0, 1]
    for i in range(n-2):
        l.append(l[-1]+l[-2])
    print(' '.join(map(str,l)))

4.费解的开关

你玩过“拉灯”游戏吗？
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。
数据范围
0<n≤500

T = int(input())
dx,dy = [0,1,0,-1,0],[1,0,-1,0,0]

def doit(f,x,y):
    for i in range(5):
        xx,yy = x + dx[i],y + dy[i]
        if xx < 0 or xx >= 5 or yy < 0 or yy >= 5:continue

        if f[xx][yy] == '0':
            f[xx][yy] = '1'
        else:
            f[xx][yy] = '0'

for i in range(T):
    lis = []
    for j in range(5):
        lis.append(list(input()))

    res = 10
    for j in range(32):
        lis2 = []
        for ii in range(5):lis2.append(lis[ii][:])
        ans = 0
        its = True
        for k in range(5):
            if  (j >> k) & 1:
                ans += 1
                doit(lis2,0,k)
        for k in range(4):
            for wk in range(5):
                if lis2[k][wk] == '0':
                    doit(lis2,k+1,wk)
                    ans += 1
        for wk in range(5):
            if lis2[4][wk] == '0':
                its = False
                break
        if its and res > ans:
            res = ans

    if res <= 6:
        print(res)
    else:
        print(-1)
    if i != T -1:
        ttt = input()

5.递归实现组合型枚举

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围
n>0 ,
0≤m≤n ,
n+(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
思考题：如果要求使用非递归方法，该怎么做呢？

用栈模拟电脑的递归

n,m=map(int,input().split())
status=[0]*(n)

def dfs(x):
    if sum(status)==m:
        for i in range(n):
            if status[i]:
                print(i+1,end=' ')
        print('')
        return
    if x>=n:
        return

    status[x]=1
    dfs(x+1)
    status[x]=0

    status[x]=0
    dfs(x+1)
    status[x]=0

dfs(0)

6.飞行员兄弟

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。
但是，这会使得第 i 行和第 j 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 N，表示所需的最小切换把手次数。
接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
1≤i,j≤4
输入样例：
-±-

-±-
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4

def copy_ll(ll):
    new_ll=[]
    for i in range(4):
        new_ll.append(ll[i][:])
    return new_ll

def turn(m,n):
    if l[m][n]=='-':
        l[m][n]='+'
    else:
        l[m][n]='-'

def press(x,y):
    for i in range(4):
        turn(i,y)
        turn(x,i)
    turn(x,y)

def get(o,p):
    return 4*o+p

def judge(ll):
    ans=True
    for i in range(4):
        for j in range(4):
            if ll[i][j]=='+':
                ans=False
    return ans

def trans(num):
    for i in range(16):
        if num>>i&1:
            print(f'{
  i // 4 + 1} {
  i%4+1}')

ll=[]
for i in range(4):
    ll.append(list(input()))
res=17
status=0
for i in range(1<<16):
    l=copy_ll(ll)
    step=0
    for j in range(4):
        for k in range(4):
            if i>>get(j,k)&1:
                press(j,k)
                step+=1
    if judge(l):
        if step<res:
            status=i
            res=step
print(res)
trans(status)

7.翻硬币

小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：oooooo
如果同时翻转左边的两个硬币，则变为：oooo**oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1：

oo
输出样例1：
5
输入样例2：
ooo***
ooo***
输出样例2：
1

def turn(x):
    if n[x]=='o':
        n[x]='*'
    else:
        n[x]='o'

n=list(input())
m=list(input())
ans=0
for i in range(len(n)-1):
    if n[i]!=m[i]:
        turn(i)
        turn(i+1)
        ans+=1
print(ans)