四项一起对得上吗
运行下面这段程序:
def perm(a):
res = []
path = []
used = [False] * len(a)
def dfs():
if len(path) == len(a):
res.append(list(path))
return
for i in range(len(a)):
if used[i]:
continue
used[i] = True
path.append(a[i])
dfs()
used[i] = False
path.pop()
dfs()
return res
def subs(a):
res = []
path = []
def dfs(s):
res.append(list(path))
for i in range(s, len(a)):
path.append(a[i])
dfs(i + 1)
path.pop()
dfs(0)
return res
def pruned(n):
st = {"c": 0, "v": 0}
path = []
used = [False] * (n + 1)
def dfs():
st["v"] += 1
if len(path) == n:
st["c"] += 1
return
for x in range(1, n + 1):
if used[x]:
continue
if path and abs(path[-1] - x) == 1:
continue
used[x] = True
path.append(x)
dfs()
path.pop()
used[x] = False
dfs()
return st["c"], st["v"]
def ok(col, c):
r = len(col)
for i in range(r):
if col[i] == c or abs(col[i] - c) == r - i:
return False
return True
def queens(n):
st = {"c": 0, "v": 0}
col = []
def dfs():
st["v"] += 1
if len(col) == n:
st["c"] += 1
return
for c in range(n):
if not ok(col, c):
continue
col.append(c)
dfs()
col.pop()
dfs()
return st["c"], st["v"]
ok4 = (len(perm([1, 2, 3])) == 6
and len(subs([1, 2, 3])) == 8
and pruned(5) == (14, 70)
and queens(4)[0] == 2)
print(ok4)
全部评论