时间复杂度

image-20230310200428612

递归实现指数型枚举

image-20230310113023637

image-20230310113236310

直接输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
st = [0]*16  # 记录每一个位置的状态，0为还未考虑，1选择，2不选
def dfs(u):
    if u > n:
        for i in range(1,n+1):
            if st[i] == 1:
                print(i)
        print()
        return
    st[u] = 2   # 第一分支
    dfs(u+1)
    st[u]=0 # 恢复现场

    st[u] = 1  # 第二分支
    dfs(u+1)
    st[u]=0    # 恢复现场

if __name__ == '__main__':
    n = int(input())
    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
path =[]
res = []
st = [0]*16  # 记录每一个位置的状态，0为还未考虑，1选择，2不选
def dfs(u):
    path = []
    if u > n:
        for i in range(1,n+1):

            if st[i] == 1:
                print(i)
                path.append(i)
        res.append(path[:])

        print()
        return

    st[u] = 2   # 第一分支
    dfs(u+1)
    st[u]=0 # 恢复现场

    st[u] = 1  # 第二分支
    dfs(u+1)
    st[u]=0    # 恢复现场

if __name__ == '__main__':
    n = int(input())
    dfs(1)
    print(res)

递归实现排列型枚举

image-20230310195811153

全排列的理解

例如n=3，全排列如下:

123

132

213

231

321

312

一共6种。

两种顺序: 依次枚举每一个数放到哪个位置 和 依次枚举每个位置放哪个数（以次为例）

image-20230310201230631

数据范围为1—9

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
path = []
res = []
state = [0] * 10
used = [False] * 10
def dfs(u):
    path = []
    if (u>n):
        for i in range(1,n+1):
            # print(state[i])
            path.append(state[i])
        res.append(path[:])
        return

    # 依次枚举每个分支，即当前位置可以填那些数字
    for i in range(1,n+1):
        if (not used[i]):
            state[u] = i
            used[i] = True
            dfs(u+1)
            state[u] = 0
            used[i] = False

if __name__ == '__main__':

    n = int(input())
    dfs(1)
    print(res)

递归实现组合型枚举

链接:https://www.acwing.com/problem/content/95/

image-20230310214454286

列表展现

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
path = []
res = []

def dfs(u,m,start):
    path = []
    if (u>m):
        for i in range(1,m+1):
            # print(state[i])
            path.append(state[i])
            # print('数字',state[i])
        res.append(path[:])
        return

    # 依次枚举每个分支，即当前位置可以填那些数字
    for i in range(start,n+1):
        if (not used[i]):
            state[u] = i
            used[i] = True
            # print('这是u',u)
            dfs(u+1,m,i+1)

            state[u] = 0
            used[i] = False

if __name__ == '__main__':

    n,m = map(int,input().split())
    state = [0] * (n+1)
    used = [False] * (n+1)
    dfs(1,m,1)
    print(res)

按照题意展现:

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
def dfs(u,m,start):

    if (u>m):
        for i in range(1,m+1):
            print(state[i],end = ' ')
        print()
        return

    # 依次枚举每个分支，即当前位置可以填那些数字

    for i in range(start,n+1):

        if (not used[i]):
            state[u] = i
            used[i] = True

            dfs(u+1,m,i+1)
            state[u] = 0
            used[i] = False

if __name__ == '__main__':

    n,m = map(int,input().split())
    state = [0] * (m+1)
    used = [False] * (n+1)
    dfs(1,m,1)

带分数

题目链接蓝桥杯2013年第四届真题-带分数 - C语言网 (dotcpp.com)

题目描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。

输入格式

从标准输入读入一个正整数N (N< 1000*1000)

输出格式

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法

样例输入

复制

1
100

样例输出

复制

1
11

思路一：

image-20230311102138312

Python全排列

permutations（）

1
2
itertools.permutations(iterable, r = None)
1
  • 返回由 iterable序列中的元素生成的长度为r的排列，r默认设置为 iterable 的长度
  • 如果有相同的元素，不同位置的元素被认为不同
1
2
3
from itertools import *
s = ['b','a','c']
print(list(permutations(s)))

用Python此方法会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from itertools import *
n = int(input())
# 首先对1-9进行全排列
s = ['1','2','3','4','5','6','7','8','9']

cnt=0
res = list(permutations(s))
for item in res:
    for it_a in range(len(item)):
        a = ''.join(item[:it_a+1])

        list_b = item[it_a+1:]
        for it_b in range(len(list_b)-1):
            b = ''.join(list_b[0:it_b+1])

            list_c = list_b[it_b+1:]
            c = ''.join(list_c)

            sum = a+'+'+b+'/'+c

            if n ==eval(sum):
                cnt = cnt+1
print(cnt)

思路二:

image-20230311102640527