回路计数#回溯法#python

130 阅读 0 评论 86 点赞

我是靠谱客的博主默默枫叶，这篇文章主要介绍回路计数#回溯法#python，现在分享给大家，希望可以做个参考。

动态规划算法参考博主，前两种时间复杂度一样的，第三种时间复杂度相对较低。
1.回溯算法一：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#回路计数#回溯法
import math
def backroad(path):
if len(path)==21:
Length+=1
return
for num in range(2,22):
if len(path)==1:
path.append(num)
backroad(path,ss)
path.pop()
else:
if num in path or math.gcd(path[-1],num)!=1:
continue
path.append(num)
backroad(path)
path.pop()
if __name__=='__main__':
Length=[]
backroad([1],0)
print(Length)

2.纯暴力

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#回路计数的解法二#纯暴力
import itertools
num=[]
for i in range(2,22):
num.append(i)
data=[]
SS=0
AA=[]
for i in itertools.permutations(num,len(num)):
for j in range(len(num)-1):
if math.gcd(num[j],num[j+1])!=1:
break
else:
AA.append(i)
SS+=1
print(SS)

3.回溯算法二

复制代码

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
#哈希表求解
import math
Road={}
for i in range(2,22):
for j in range(2,22):
if i!=j and math.gcd(i,j)==1:
if i not in Road.keys():
Road[i]=[j]
else:
Road[i].append(j)
def ComBack(path):
global GG
if len(path)==20:
GG+=1
print(GG)
return
for j in Road[path[-1]]:
if j not in path:
path.append(j)
ComBack(path)
path.pop()
if __name__=='__main__':
GG=0
for i in range(2,22):
ComBack([i])
print(GG)