当前位置: 首页 > news >正文

软工第三次作业--结对作业

廖永祺
谭钧灏 3123004628
GitHub项目地址:

这个作业属于哪个课程 <班级的链接>
这个作业要求在哪里 https://edu.cnblogs.com/campus/gdgy/Class12Grade23ComputerScience/homework/13470
这个作业的目标 熟悉小组合作的形式并在该形式中思考团队完成开发任务时需考虑的具体细节

PSP表格

PSP2.1 Personal Software Process Stages 预估耗时(分钟) 实际耗时(分钟)
Planning 计划 15 10
· Estimate · 估计这个任务需要多少时间 15 10
Development 开发 165 155
· Analysis · 需求分析(包括学习新技术) 20 15
· Design Spec · 生成设计文档 10 8
· Design Review · 设计复审 5 5
· Coding Standard · 代码规范(为目前的开发制定合适的规范) 10 12
· Design · 具体设计 25 22
· Coding · 具体编码 60 70
· Code Review · 代码复审 15 13
· Test · 测试(自我测试,修改代码,提交修改) 20 10
Reporting 报告 20 20
· Test Report · 测试报告 10 10
· Size Measurement · 计算工作量 5 5
· Postmortem & Process Improvement Plan · 事后总结,并提出过程改进计划 5 5
合计 200 185

效能分析

函数性能消耗分布 (基于算法复杂度):

排名 函数名 占比
1 ExpressionGenerator.generateCompoundExpr 32%
2 AnswerValidator.parseExpression 28%
3 Fraction.gcd() 15%
4 ExpressionGenerator.normalizeExpression 10%
5 AnswerValidator.parseWithoutBrackets 8%
6 FileHandler.readFileLines 4%
7 Fraction.valueOf() 2%
8 Other Functions 1%

能耗第一名:ExpressionGenerator.generateCompoundExpression()
image

性能消耗原因:
递归调用导致调用栈深度
约束检查失败时的重试循环
运算符数量增加时复杂度急剧上升
generateCompoundExpression() - 32% load
├── Complexity: O(2^n) - 指数级增长
├── Avg call depth: 3-5 levels
├── Memory alloc: 2-5KB/call
├── Issue: 递归+重试循环
└── Recommendation: 添加重试限制

能耗第二名:
image

性能消耗原因:
深度递归解析嵌套表达式
频繁的字符串拼接和子串操作
括号匹配的线性扫描
parseExpression() - 28% load
├── Complexity: O(n²) - 字符串操作
├── Max recursion: 10+ levels
├── Memory alloc: 1-3KB/call
├── Issue: 深度递归风险
└── Recommendation: 改为迭代算法

能耗第三名:Fraction.gcd()
image

性能消耗原因:
每个分数构造时调用
每次运算后构造新分数时调用
大数时迭代次数增加
gcd() - 15% load
├── Complexity: O(log(min(a,b)))
├── Calls: 高频调用 (每个分数运算)
├── Issue: 大数性能下降
└── Optimization: 已较好优化

优化方案

一、算法优化(2-3小时)
1.递归改用迭代的表达式
2.优化括号匹配算法
3.改进表达式规范化

二、设备优化(硬件设施更换)
1.优化并行处理支持
2.优化内存的使用

系统架构设计和代码说明

核心组件

1.主控制器(MathExerciseGenerator)

image
image
组件说明:函数先对终端输入的参数进行解析并判断,匹配对应的模式,随后在对应模式下选择生成题目或者验证答案,最后输出文件。

表达式生成器

image
组件说明:应用builder模式和composite模式,构建表达式树以及逐步构建复杂数学表达式

核心算法设计

1.表达树生成算法

image
算法说明:表达式树生成算法采用递归分治策略,将复杂表达式的生成问题分解为更小的子问题,通过组合子树来构建完整的表达式树。

入口控制 - generateUniqueProblem()

步骤顺序 任务
1 启动生成流程
2 循环尝试生成(防止无限循环)
3 调用 generateExpression(3) 生成表达式树
4 进行表达式规范化处理
5 检查唯一性(HashSet去重)
6 返回合格的MathProblem对象

递归生成 - generateExpression(maxOperators)

步骤顺序 任务
1 输入:最大运算符数量
2 判断:如果maxOperators=0 或 10%概率 → 生成叶子节点(基本表达式)
3 否则 → 生成复合表达式(generateCompoundExpression)
4 返回:Expression对象(包含表达式字符串和计算结果)

复合表达式生成 - generateCompoundExpression(operators)
情况1:operators = 1(单运算符)
├── 选择随机运算符(+、-、×、÷)
├── 生成左操作数 generateBasicExpression()
├── 生成右操作数 generateBasicExpression()
├── 验证运算约束(减法非负、除法真分数)
└── 构建表达式 "(左 运算符 右)"

情况2:operators > 1(多运算符)
├── 分割运算符数量:左子树 ← random(1, operators-1)
├── 计算右子树:operators - 左子树 - 1
├── 递归生成左子树 generateExpression(左子树)
├── 递归生成右子树 generateExpression(右子树)
├── 选择随机运算符
├── 验证运算约束
└── 构建表达式 "(左子树 运算符 右子树)"

基本表达式生成 - generateBasicExpression()
随机选择类型:
├── 50%概率:生成整数
│ └── 范围:[1, range-1]

└── 50%概率:生成分数
├── 分母:随机[2, range-1]
├── 分子:随机[1, 分母-1](确保真分数)
└── 50%概率转为带分数
├── 整数部分:随机[1, range-2]
└── 组合:整数部分'分子/分母

算法复杂度分析

时间复杂度
最好情况:O(1) - 直接生成基本表达式
最坏情况:O(2^n) - 递归生成复合表达式
平均情况:O(n) - 受最大运算符数限制

空间复杂度
调用栈:O(n) - 递归深度
内存使用:O(m) - 唯一表达式存储

2.表达树解析算法

主解析入口 - parseExpression(expr)

步骤顺序 任务
1 输入:表达式字符串并移除所有空白字符
2 检查表达式是否为空
3 查找最外层括号位置
4 如果找到括号,则定位匹配并递归解析括号内容,随后用计算结果替换括号内容,生成新的表达式
5 如果没有括号,则调用 parseWithoutBrackets(expr) 解析无括号表达式
6 返回:Fraction计算结果

括号匹配算法 - findMatchingBracket(expr, start)
输入:表达式字符串和左括号位置

初始化括号计数器 bracketCount = 1

从左括号后一个字符开始遍历:
├── 遇到 '(' → bracketCount++
├── 遇到 ')' → bracketCount--
├── 遇到 ''' → 跳过带分数部分(避免误判)
├── 当bracketCount = 0时 → 找到匹配右括号
└── 继续遍历直到找到匹配或字符串结束

返回:匹配右括号位置,未找到返回-1

分数解析算法 - parseFraction(str)
输入:分数字符串

检查是否包含 "'"(带分数):
├── 是:按 "'" 分割为整数部分和分数部分
├── 解析整数部分
├── 递归解析分数部分
├── 计算:整数部分 + 分数部分
└── 返回组合结果

检查是否包含 "/"(普通分数):
├── 是:按 "/" 分割为分子和分母
├── 验证分母不为0
├── 创建Fraction对象
└── 返回分数

否则(整数):
├── 解析为整数
├── 创建Fraction(整数, 1)
└── 返回结果

算法复杂度分析
时间复杂度
最好情况:O(n) - 简单表达式线性扫描
最坏情况:O(n²) - 深度嵌套括号,多次字符串操作
平均情况:O(n log n) - 递归解析平衡的表达式树

空间复杂度
调用栈:O(d) - d为括号嵌套深度
临时存储:O(n) - 分词列表和临时字符串

测试运行

测试数据

image

测试结果

image

测试成绩

image

对于题目的生成:
生成完全按照要求所给的参数生成,同时满足没有负数和其他不合适的符号,题目也没有产生重复或者空白。
对于题目的判断:
判断按照要求对真分数进行额外的识别,加之整数的运算判断,并且根据输入的答案判断出正确和错误的对应题号,符合作业要求。

http://www.hskmm.com/?act=detail&tid=36006

相关文章:

  • Day1HTML的基本骨架
  • 树上依赖性背包 学习笔记 | P6326 Shopping 题解
  • java标识符
  • 题解:uoj961【UR #30】赛场设计
  • 位运算快速卷积 快速沃尔什变换 FWT
  • 嵌合抗体:破解二抗选择难题,赋能多重分子检测的核心工具
  • 原来用聊天记录就可以创造数字分身!WeClone项目在Lab4AI平台上的复现
  • 自监督提示优化SPO
  • Java中的注释
  • 实测!不同场景下,哪款 AI IDE 能真正帮你少加班?
  • CSP-S模拟36 2025.10.21
  • 2025 年 AI 编程工具生成效果全景比拼:从技术实力到综合评分
  • 打造AI IDE标杆产品,腾讯CodeBuddy深度全方位解析
  • C语言项目开发常用目录结构 - Invinc
  • 2025年不锈钢水箱厂家权威推荐榜:方形/圆形/消防/生活/保温/承压/装配式/焊接水箱及水塔水罐全解析
  • day03-Coze记忆-对话体验
  • 2025年流量计厂家权威推荐榜单:电磁流量计、超声波流量计、涡街流量计、质量流量计专业制造商深度解析
  • RNDIS让Air8000的USB上网更智能、更快速!
  • 如果k8s有三个calico节点A,B,C 使用bgp模式的话是如何进行BGP对等会话的
  • 10.21
  • home-assistant-Onboarding Home Assistant(入职家庭助理)
  • Day1标签语法
  • home-assistant-Concepts and terminology概念和术语
  • 2025年印染水洗机厂家权威推荐榜:高效水洗设备与环保节能技术深度解析,专业水洗机厂家精选
  • 高级语言程序设计第二次作业
  • 有关K8s calico IPIP模式的一些疑惑和思考
  • 1.正手握拍
  • 2025年角接触轴承厂家推荐排行榜,高精度/高承载/高精密/机床主轴/汽车/定制/可替代进口/高转速/高刚性角接触球轴承公司推荐
  • 7-Zip最新版 7-Zip25.01
  • 2025年精密球轴承厂家权威推荐榜:半导体设备轴承,机床主轴轴承,真空泵轴承,国产高端精密球轴承,晶圆搬运机械手臂不锈钢轴承