湖北黄石域名注册网站建设,店铺推广平台有哪些,wordpress 换轮播如,网站建设亿玛酷知名文章目录 [toc]问题描述回溯法时间复杂性Python实现 个人主页#xff1a;丷从心
系列专栏#xff1a;回溯法 问题描述
下图是由 14 14 14个“ ”和 14 14 14个“ − - −”组成的符号三角形#xff0c; 2 2 2个同号下面都是” “#xff0c; 2 2 2个异号下面都是“ −… 文章目录 [toc]问题描述回溯法时间复杂性Python实现 个人主页丷从心
系列专栏回溯法 问题描述
下图是由 14 14 14个“ ”和 14 14 14个“ − - −”组成的符号三角形 2 2 2个同号下面都是” “ 2 2 2个异号下面都是“ − - −” 在一般情况下符号三角形的第一行有 n n n个符号符号三角形问题要求对于给定的 n n n计算有多少个不同的符号三角形使其所含的“ ”和“ − - −”的个数相同 回溯法
对于符号三角形问题用 n n n元组 x [ 1 : n ] x[1 : n] x[1:n]表示符号三角形的第一行的 n n n个符号由于 x [ i ] x[i] x[i]是二值的所以在用回溯法解符号三角形问题时可以用一棵完全二叉树来表示其解空间在符号三角形的第一行的前 i i i个符号 x [ 1 : i ] x[1 : i] x[1:i]确定后就确定了一个由 i ( i 1 ) / 2 i (i 1) / 2 i(i1)/2个符号组成的符号三角形下一步确定 x [ i 1 ] x[i 1] x[i1]的值后只要在前面已确定的符号三角形的右边加一条边就可以扩展为 x [ 1 : i 1 ] x[1 : i 1] x[1:i1]相应的符号三角形最终由 x [ 1 : n ] x[1 : n] x[1:n]所确定的符号三角形中包含的“ ”个数与“ − - −”个数同为 n ( n 1 ) / 4 n (n 1) / 4 n(n1)/4因此在回溯搜索过程中可用当前符号三角形所包含的“ ”个数与” − - −“个数均不超过 n ( n 1 ) / 4 n (n 1) / 4 n(n1)/4作为可行性约束用于剪去不满足约束的子树当 i n i n in时算法搜索至叶节点得到一个新的“ ”个数与“ − - −”个数相同的符号三角形当前已找到符号三角形数 s u m sum sum增 1 1 1当 i n i n in时当前扩展结点 Z Z Z是解空间中的内部结点对当前扩展结点 Z Z Z的每个儿子结点计算其相应的符号三角形中“ ”个数与“ − - −”个数并以深度优先的方式递归地对可行子树进行搜索或剪去不可行子树对于给定的 n n n当 n ( n 1 ) / 2 n (n 1) / 2 n(n1)/2为奇数时显然不存在所包含的“ ”个数与“ − - −”个数相同的符号三角形此时可以通过简单的判断加以处理 时间复杂性
更新符号三角形矩阵需要 O ( n ) O(n) O(n)时间在最坏情况下有 O ( 2 n ) O(2^{n}) O(2n)个结点需要更新符号三角形矩阵所以解符号三角形问题的回溯算法所需的计算时间为 O ( n 2 n ) O(n 2^{n}) O(n2n) Python实现
def symbol_triangle(n):if (n * (n 1) // 2) % 2:return 0half n * (n 1) // 4count 0 # 记录符合条件的符号三角形数量# 初始化符号三角形矩阵path [[] * n for _ in range(n)]def backtrack(row, col, path, plus_count, minus_count):nonlocal count# 边界条件: 当列数等于 n 时, 表示已经生成了符号三角形的一种排列if col n:if plus_count minus_count:count 1print(path)return# 尝试当前位置为 path[row][col] plus_count 1# 更新符号三角形矩阵cur_col colfor i in range(1, cur_col 1):if path[i - 1][cur_col - 1] path[i - 1][cur_col]:path[i][cur_col - 1] plus_count 1else:path[i][cur_col - 1] -minus_count 1cur_col - 1# 检查是否满足条件, 继续生成下一行的符号if plus_count half and minus_count half:backtrack(row, col 1, path, plus_count, minus_count)# 恢复回溯之前状态cur_col colfor i in range(cur_col 1):if path[i][cur_col] :path[i][cur_col] plus_count - 1else:path[i][cur_col] minus_count - 1cur_col - 1# 尝试当前位置为 -path[row][col] -minus_count 1# 更新符号三角形矩阵cur_col colfor i in range(1, cur_col 1):if path[i - 1][cur_col - 1] path[i - 1][cur_col]:path[i][cur_col - 1] plus_count 1else:path[i][cur_col - 1] -minus_count 1cur_col - 1# 检查是否满足条件, 继续生成下一行的符号if plus_count half and minus_count half:backtrack(row, col 1, path, plus_count, minus_count)backtrack(0, 0, path, 0, 0)return countn 4print(满足条件的符号三角形如下:)count symbol_triangle(n)print(f符号三角形数量: {count})满足条件的符号三角形如下:
[[, , -, ], [, -, -, ], [-, , , ], [-, , , ]]
[[, , -, -], [, -, , ], [-, -, , ], [, , , ]]
[[, -, , ], [-, -, , ], [, -, , ], [-, , , ]]
[[, -, , -], [-, -, -, ], [, , , ], [, , , ]]
[[-, , -, ], [-, -, -, ], [, , , ], [, , , ]]
[[-, -, , ], [, -, , ], [-, -, , ], [, , , ]]
符号三角形数量: 6
