知新_RL

这个屌丝很懒，什么也没留下！

热门标签

递推与递归经典问题的python实现_m行n列逆转矩阵python递推

作者：知新_RL | 2024-05-18 23:57:40

踩

m行n列逆转矩阵python递推

title: 递推与递归经典问题的python实现
date: 2020-03-26 22:13:26
categories: 算法
tags: [python, 递推与递归]

递归实现指数型枚举

从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤151≤n≤15

输入样例：

3
1

输出样例：

代码

每一个位置枚举有选或者不选两种选项

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

递归实现排列型枚举

把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数n。

输出格式

按照从小到大的顺序输出所有方案，每行1个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归实现组合型枚举

从 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

输出样例：

思考题：如果要求使用非递归方法，该怎么做呢？

代码

其实只需要把例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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

带分数

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

输出样例1：

11
1

输入样例2：

105
1

输出样例2：

6
1

暴力枚举

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

飞行员兄弟·

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。

但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数N，表示所需的最小切换把手次数。

接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤41≤i,j≤4

输入样例：

-+--
----
----
-+--
1
2
3
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))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

翻硬币

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数

数据范围

输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

**********
o****o****
1
2

输出样例1：

5
1

输入样例2：

*o**o***o***
*o***o**o***
1
2

输出样例2：

1
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/590491