递归与递推算法七题-ag真人游戏

从 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)

把 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)

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

你玩过“拉灯”游戏吗？
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

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()

从 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)

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 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

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)