Neaya~

笔记、记录、总结

回溯算法

发表于 更新于 分类于 评论数：
本文字数： 2.7k 阅读时长 ≈ 2 分钟

摘要：素数环、全排列、图着色、n皇后、dfs+回溯、

素数环

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
"""
# @Time    :  2020/11/25
# @Author  :  Jimou Chen
"""
from math import sqrt

n = int(input())
num = [0 for _ in range(n + 1)]
flag = [0 for _ in range(n + 1)]


# 判断素数
def prime(x):
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            return 0

    return 1


# x 是当前的数，v是满足条件的前一个数
def dfs(x, v):
    if x == n + 1:
        # 判断最后一个数和第一个数之和
        if prime(v + 1):
            for i in range(1, n + 1):
                print(num[i], end=' ')
            print()
            return  # return的位置是和for同一级的

    for i in range(1, n + 1):
        if flag[i] == 0 and prime(i + v):
            flag[i] = 1
            num[x] = i
            dfs(x + 1, i)
            flag[i] = 0


num[1] = 1
flag[1] = 1
dfs(2, 1)

'''
6
1 4 3 2 5 6 
1 6 5 2 3 4 


8
1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2 
'''

优化

  • 把素数判断用素数表标志存储，提高效率
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

    '''
    优化的话，可以使用素数表，这样就不用每次都遍历判断了
    '''
    k = 0
    # 素数表，1表示素数
    def prime_table(x):
        global k
        l = [1 for _ in range(x + 1)]
        for i in range(2, x + 1):
            for k in range(2, int(sqrt(i)) + 1):
                if i % k == 0:
                    l[i] = 0

        return l

    prime = prime_table(n+100)

    全排列

  • 做法类似
  • 见 https://paste.ubuntu.com/p/PgwX92bBq6/

图着色

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
"""
# @Time    :  2020/11/26
# @Author  :  Jimou Chen
"""
'''
输入n个顶点，m种颜色，还有该图的邻接矩阵
假设第一个顶点是1，第一种颜色是1
'''
n, m = map(int, input().split())
graph = [[0 for _ in range(100)] for _ in range(100)]  # 存放邻接矩阵
color = [0 for _ in range(100)]  # 存放最后符合着色情况
cnt = 0  # 记录有多少种着色方案


# 检查第i个顶点的颜色是否满足条件
def check(k):
    for i in range(1, k + 1):
        # k与i之间相连并且i顶点的颜色与k顶点的颜色相同
        if graph[k][i] == 1 and color[i] == color[k]:
            return 0
    return 1


def dfs(step):
    global cnt
    # 所有的顶点已经涂完颜色
    if step == n + 1:
        for i in range(1, n + 1):
            print(color[i], end=' ')
        print()
        cnt += 1
        return

    # 遍历填m种颜色
    for i in range(1, m + 1):
        color[step] = i
        if check(step):
            dfs(step + 1)
        color[step] = 0  # 回溯，0表示没有着色


if __name__ == '__main__':
    for i in range(1, n + 1):
        temp = list(map(int, input().split()))
        for j in range(1, n + 1):
            graph[i][j] = temp[j - 1]

    dfs(1)
    print('总方案数: ', cnt)

'''

5 4 
0 1 1 1 0 
1 0 1 1 1 
1 1 0 1 0 
1 1 1 0 1 
0 1 0 1 0

48
'''
1
2
3
4
5
6
7
8
5 4 
0 1 1 1 0 
1 0 1 1 1 
1 1 0 1 0 
1 1 1 0 1 
0 1 0 1 0

48

n皇后

  • N皇后问题，输入N，输出所有解的个数
  • 解题思路：
    可以使用一个一维数组存放皇后的位置，比如chess[i] = j,表示第i行的第j列有存放一个棋子，比起二维这样会省点空间。回溯结合深搜对所有情况继续穷举，符合就继续，不符合就回退。递归出口即是将所有的棋子已经放好，此时，行数已经到达最后一行+1.这里从第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
27
28
29
30
31
32
33
"""
# @Time    :  2020/11/26
# @Author  :  Jimou Chen
"""
n = int(input())
chess = [0 for _ in range(n)]  # 下标代表第i行，若为1，则表示第j列棋盘存放棋子
cnt = 0

# 检查棋子是否冲突，i是行，j是列
def check(i):
    for j in range(i):
        # 检查列和对角线
        if chess[i] == chess[j] or abs(chess[i] - chess[j]) == i - j:
            return 0
    return 1

# i表示现在已经放到第i行了
def dfs(i):
    global cnt
    if i == n:  # 能够放到最后一行说明这种情况符合
        cnt += 1
        print(chess)
        return

    for j in range(n):
        chess[i] = j  # 表示第i行第j列放皇后
        if check(i):
            dfs(i + 1)  # 符合条件就继续放下一行

if __name__ == '__main__':
    dfs(0)
    print('一共有{}种摆放方法'.format(cnt))

  • 运行结果
Welcome to reward