回路计数#回溯法#python

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

#回路计数#回溯法
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.纯暴力

#回路计数的解法二#纯暴力
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.回溯算法二

#哈希表求解
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)

最后

以上就是默默枫叶为你收集整理的回路计数#回溯法#python的全部内容，希望文章能够帮你解决回路计数#回溯法#python所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。