【回溯】符号三角形问题Python实现

文章目录

    • @[toc]
      • 问题描述
      • 回溯法
      • 时间复杂性
      • `Python`实现

因上努力

个人主页:丷从心

系列专栏:回溯法

果上随缘


问题描述

  • 下图是由 14 14 14个“ + + +”和 14 14 14个“ − - ”组成的符号三角形, 2 2 2个同号下面都是” + + +“, 2 2 2个异号下面都是“ − -

1

  • 在一般情况下,符号三角形的第一行有 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(i+1)/2个符号组成的符号三角形,下一步确定 x [ i + 1 ] x[i + 1] x[i+1]的值后,只要在前面已确定的符号三角形的右边加一条边,就可以扩展为 x [ 1 : i + 1 ] x[1 : i + 1] x[1:i+1]相应的符号三角形
  • 最终由 x [ 1 : n ] x[1 : n] x[1:n]所确定的符号三角形中包含的“ + + +”个数与“ − - ”个数同为 n ( n + 1 ) / 4 n (n + 1) / 4 n(n+1)/4,因此在回溯搜索过程中,可用当前符号三角形所包含的“ + + +”个数与” − - “个数均不超过 n ( n + 1 ) / 4 n (n + 1) / 4 n(n+1)/4作为可行性约束,用于剪去不满足约束的子树
  • i = n i = n i=n时,算法搜索至叶节点,得到一个新的“ + + +”个数与“ − - ”个数相同的符号三角形,当前已找到符号三角形数 s u m sum sum 1 1 1
  • i < n i < n i<n时,当前扩展结点 Z Z Z是解空间中的内部结点,对当前扩展结点 Z Z Z的每个儿子结点,计算其相应的符号三角形中“ + + +”个数与“ − - ”个数,并以深度优先的方式递归地对可行子树进行搜索,或剪去不可行子树
  • 对于给定的 n n n,当 n ( n + 1 ) / 2 n (n + 1) / 2 n(n+1)/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 0

    half = n * (n + 1) // 4

    count = 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 += 1

                print(path)

            return

        # 尝试当前位置为 +
        path[row][col] = '+'
        plus_count += 1

        # 更新符号三角形矩阵
        cur_col = col
        for 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 += 1
            else:
                path[i][cur_col - 1] = '-'
                minus_count += 1

            cur_col -= 1

        # 检查是否满足条件, 继续生成下一行的符号
        if plus_count <= half and minus_count <= half:
            backtrack(row, col + 1, path, plus_count, minus_count)

        # 恢复回溯之前状态
        cur_col = col
        for i in range(cur_col + 1):
            if path[i][cur_col] == '+':
                path[i][cur_col] = ''
                plus_count -= 1
            else:
                path[i][cur_col] = ''
                minus_count -= 1

            cur_col -= 1

        # 尝试当前位置为 -
        path[row][col] = '-'
        minus_count += 1

        # 更新符号三角形矩阵
        cur_col = col
        for 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 += 1
            else:
                path[i][cur_col - 1] = '-'
                minus_count += 1

            cur_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 count


n = 4

print('满足条件的符号三角形如下:')

count = symbol_triangle(n)

print(f'符号三角形数量: {count}')
满足条件的符号三角形如下:
[['+', '+', '-', '+'], ['+', '-', '-', ''], ['-', '+', '', ''], ['-', '', '', '']]
[['+', '+', '-', '-'], ['+', '-', '+', ''], ['-', '-', '', ''], ['+', '', '', '']]
[['+', '-', '+', '+'], ['-', '-', '+', ''], ['+', '-', '', ''], ['-', '', '', '']]
[['+', '-', '+', '-'], ['-', '-', '-', ''], ['+', '+', '', ''], ['+', '', '', '']]
[['-', '+', '-', '+'], ['-', '-', '-', ''], ['+', '+', '', ''], ['+', '', '', '']]
[['-', '-', '+', '+'], ['+', '-', '+', ''], ['-', '-', '', ''], ['+', '', '', '']]
符号三角形数量: 6

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/270148.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何编写高效清晰的嵌入式C程序

作为嵌入式工程师&#xff0c;怎么写出效率高、思路清晰的C语言程序呢? 要用C语言的思维方式来进行程序的构架构建 要有良好的C语言算法基础&#xff0c;以此来实现程序的逻辑构架 灵活运用C语言的指针操作 虽然看起来以上的说法很抽象&#xff0c;给人如坠雾里的感觉&…

智能优化算法应用:基于厨师算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于厨师算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于厨师算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.厨师算法4.实验参数设定5.算法结果6.参考文献7.MA…

reactive和TypeScript标注数据类型-ts使用方法

一、vite项目中<script setup lang"ts"> : lang"ts" 是表明支持ts校验&#xff08;ts 全称typescript,是es6语法&#xff0c;是javascript的超集强类型编程语言&#xff0c;类似java&#xff0c;定义变量类型后&#xff0c;赋值类型不一致&#xff0…

网站管理员应该知道的:一款免费、简单、强大的 WAF(雷池社区版)

作为网站管理员&#xff0c;一定会关注网站是否安全&#xff0c;是否能够抵御黑客的攻击&#xff0c;是否能够保护数据和用户。可能已经听说过 WAF&#xff08;Web Application Firewall&#xff0c;Web 应用防火墙&#xff09;&#xff0c;一种能够在应用层对 Web 流量进行检测…

图灵日记之java奇妙历险记--输入输出方法数组

目录 输入输出输出到控制台从键盘输入使用 Scanner 读取字符串/整数/浮点数使用 Scanner 循环读取 猜数字方法方法定义方法调用的执行过程实参和形参的关系(重要)方法重载 数组数组的创建数组的初始化动态初始化静态初始化 数组的使用元素访问遍历数组 数组是引用类型null数组应…

大创项目推荐 深度学习OCR中文识别 - opencv python

文章目录 0 前言1 课题背景2 实现效果3 文本区域检测网络-CTPN4 文本识别网络-CRNN5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习OCR中文识别系统 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;…

SQL实践篇(三):什么是Redis

文章目录 简介Redis是什么&#xff0c;为什么这么快&#xff1f;Redis的数据类型字符串Hash字符串列表字符串集合有序字符串集合其他数据类型 总结参考文献 简介 Redis是一种基于内存的键值数据库&#xff0c;键值数据库会使用哈希表存储key和value。其中key和value可以是任何…

【力扣】199.二叉树的右视图

看到这个题目的一瞬间&#xff0c;我想递归&#xff0c;必须用递归。最近被递归折磨的有点狠&#xff0c;但是我感觉我快要打败它了&#xff0c;就是现在稍稍有点处于劣势。不过没关系&#xff0c;来日方长不是。 法一&#xff1a;递归 题解&#xff1a; 之前想的就是先递归&…

python:改进型鳟海鞘算法(SSALEO)求解23个基本函数

一、改进型鳟海鞘算法SSALEO 改进型鳟海鞘算法&#xff08;SSALEO&#xff09;由Mohammed Qaraad等人于2022年提出。 参考文献&#xff1a;M. Qaraad, S. Amjad, N. K. Hussein, S. Mirjalili, N. B. Halima and M. A. Elhosseini, "Comparing SSALEO as a Scalable Larg…

50个免费的 AI 工具,提升工作效率(附网址)

上次我们已经介绍了20个精选的提高工作效率的免费AI工具&#xff0c;但如果你觉得这些AI工具还不过瘾的话&#xff0c;想进一步成为职场中最了解AI的人&#xff0c;本文将汇总介绍免费最新的50个AI工具。 DeepSwap DeepSwap 是一个基于 AI 的工具&#xff0c;适用于想要制作令人…

Kafka生产环境问题总结与性能优化实践

Kafka可视化管理工具kafka-manager 安装及基本使用可参考: httos://wwwcnbloas.com/dadonaaa/o/8205302.html 线上环境规划 1. 消息丢失情况: 消

【MATLAB库函数系列】线性调频Z(Chirp-Z,CZT)的MATLAB源码和C语言实现

在上一篇博客 【数字信号处理】线性调频Z(Chirp-Z,CZT)算法详解 已经详细介绍了CZT变换的应用背景和原理,先回顾一下: 回顾CZT算法 采用 FFT 算法可以很快计算出全部 N N N点 DFT 值,即Z变换 X ( z ) X(z) <

LaTex插入图片、插入表格、插入公式

目录 一、插入图片 1&#xff09;改变图片的大小、旋转图片 2&#xff09;标签和交叉引用 3&#xff09;插入单排多图无小标题共享大标题 4&#xff09;单排变多排 5&#xff09;图片的位置 6&#xff09;图片横跨双栏 二、插入表格 1&#xff09;合并单元格 2&#…

RHCE9学习指南 第9章 权限管理

9.1 所有者所属组 为了了解所有者和所属组的概念&#xff0c;我们先看图9-1。 图9-1 用房子来帮助理解所有者和所属组 张老板是公司老板&#xff0c;买了一套房作为员工宿舍给A部门的员工居住。张老板是房主&#xff0c;所以他对房子具有很多权限&#xff0c;A部门员工只能具…

【开源】基于JAVA语言的大学生相亲网站

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 查询会员4.2 查询相亲大会4.3 新增留言4.4 查询新闻4.5 新增新闻 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的大学生相亲网站&#xff0c;包含了会员管理模块、新闻管…

k8s实战之ELK日志管理

首先查看总体流程 首先创建namespace apiVersion: v1 kind: Namespace metadata:name: kube-logging 一、首先创建es.yaml --- apiVersion: v1 #kubernetes API版本,采用最新版本v1 kind: Service #资源类型定义为Service metadata: name: elasticsearch-logging # …

【JavaScript】FileReader读取文件成功,但存储的数据为空——总结

目录 问题解决 问题 如题&#xff0c;使用下列代码读取上传的文件&#xff1a; for (let i 0; i < files.length; i) {const reader new FileReader();const fileName files[i].name;reader.onload function(e) {file_datas[fileName] e.target.result;}// 根据需要…

SQL server 数据库面试题及答案(实操3)

一、编程题 公司部门表 department 字段名称 数据类型 约束等 字段描述 id int 主键&#xff0c;自增 部门ID name varchar(32) 非空&#xff0c;唯一 部门名称 description varchar(1024) …

第三十六周:文献阅读+注意力/自注意力机制

目录 摘要 Abstract 文献阅读&#xff1a;锂离子电池RUL预测的SA-LSTM 现有问题 提出方法 提出方法的结构 SA-LSTM预测模型的结构 研究实验 研究贡献 注意力机制 Self-Attention&#xff08;自注意力机制&#xff09; 注意力与自注意力 代码实现attention、self-at…

喜报频传!百望云获评“2023数字经济独角兽”称号

“数字经济独角兽”是在数字经济领域具备高成长性、高创新性和高潜力性的企业&#xff0c;他们不仅是数字经济的先锋&#xff0c;是科技创新型企业的典范&#xff0c;也是推动经济发展的新兴引擎。 12月20日&#xff0c;“2023数字经济独角兽大会”在北京大兴区成功举办。大会以…