2020软件工程作业03

Wesley13
• 阅读 579

这个作业属于那个课程

https://edu.cnblogs.com/campus/zswxy/software-engineering-2017-1

这个作业的要求在哪里

https://edu.cnblogs.com/campus/zswxy/software-engineering-2017-1/homework/10494

这个作业的目标

实现一个命令行程序,不妨称之为Sudoku。

作业正文

https://www.cnblogs.com/liutaodashuaige/p/12539391.html

其他参考文献

www.baidu.com
https://www.cnblogs.com/ouyangpeng/p/8537616.html
https://blog.csdn.net/sunyanxiong123/article/details/76401590
https://github.com/zxw0621/demo/blob/master/20177596/src/sudoku.py

一、GitHub url:https://github.com/liutaodashuaige/LT_DEMO/tree/master/20177569

二、PSP表格

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

2020软件工程作业03


三、解题思路

1.理解问题

  • 该算法题的需求是实现一个称之为Sudoku命令行程序。
  • 程序要实现利用逻辑和推理,在在数独盘面的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。
  • 输入要求输入文件名以命令行参数传入。
  • 输出要求输出n个程序解出的盘面,每两个盘面间空一行,每个盘面中,每两个小格之间有一个空格。

2.思考如何实现

  • 由于不同阶的数独盘面虽然空格数量上有差异,但对每一个空格合法性的判断方法和区块的构造都是相似的,同时这是一个查找最优策略的问题,因此我认为应该使用递归的方式解题。

3.寻找参考资料

四、设计实现过程

1.函数模块的设计

  • 根据本题的解题要求和思考中确定的递归解题思想,应设计以下模块:
    • 主函数模块
    • 递归查找模块
    • 合法性判断模块
    • 输出文件生成模块

2.具体功能函数设计

  • main(argv)函数

    • 接受命令行参数,并进行解析
    • 读取input文件,并进行解析
    • 根据盘面数量调用DFS()深度优先搜索递归函数
  • DFS(i, x, y)函数

    • 对当前递归状态进行判断
    • 对当前坐标格状态进行判断
    • 尝试填入数值,并调用judge()函数验证其合法性
    • 根据不同条件进行递归
    • 验证失败时,回溯
  • judge(i, x, y)函数

    • 对传入的坐标进行行列重复判断
    • 对传入的坐标进行区块定位
    • 对传入的坐标进行区块重复判断
    • 根据是否合法返回布尔值
  • MY_OTP(i)函数

    • 根据传入的盘面序号将该盘面矩阵写入output文件
  • 简单流程图 2020软件工程作业03

3.全局变量设置

  • M(盘面阶数)
  • N(盘面数目)
  • MY_MAPS(储存所有盘面矩阵的三维列表)
  • op(文件对象)

五、改进思路

1.代码静态分析

  • 首先我们使用pylint进行代码静态分析

2020软件工程作业03

很明显代码已经是炸了,不过比起第一次用pylint已经好不少了...第一次可是负分XD

  • 让PyCharm帮我整理一下...

2020软件工程作业03

看下效果,有所进步,剩下的就是命名的规范了 2020软件工程作业03

  • 修改不符合规范的命名后

2020软件工程作业03

经过一阵捣鼓评分提升了不少,但仍然没有达到满分,测试了一下代码正常运行 只能说,有时候投降不失为一种优雅的退场,我就不折磨自己了

2020软件工程作业03


2.代码性能优化

#改为直接给予参数,而不是从命令行接受
if __name__ == '__main__':
    # sys.argv[1:]为要处理的参数列表,sys.argv[0]为脚本名,因此弃之不用
    #main(sys.argv[1:])
    main(['-m', '9', '-n', '2', '-i', 'input.txt', '-o', 'output.txt'])
  • 利用PyCharm的profile进行代码性能分析

2020软件工程作业03

显然对于我来说这个图是天书

2020软件工程作业03


2020软件工程作业03

由此表中可得知被调用次数最多和耗时最多的是judge()合法性判断函数和_DFS_()递归函数

  • 性能优化集中于judge()和_DFS_()两个函数

3.单元测试

  • 函数judge()有返回值,并且是一个布尔值,对该函数进行单元测试

  • 卡了很久,一直无法导入py文件的函数,通过参考资料中的方法解决了

  • 涉及到全局变量,先对judge()函数进行一些调整,添加一段代码

    M = 9
    MY_MAPS = []
    # 上面都是给judge()函数运行提供必要的全局变量
    with open('output.txt', 'r', encoding='utf-8') as _fp_:  # 此处直接读取已解矩阵用来判断合法性
        _MYMAP_ = []
        for line in _fp_.readlines():
            if line != '\n':  # 用换行符分割矩阵
                _MYMAP_.append(list(map(int, line.strip().split(" "))))
            else:
                MY_MAPS.append(_MYMAP_)
                _MYMAP_ = []
        MY_MAPS.append(_MYMAP_)  # MY_MAPS是集合了所有数据的三维数组
    #单元测试时用来提供全局变量...
    
    #################
    #global M, MY_MAPS
    # 行列不重复判断
    
  • 测试代码编写

    import unittest from Sudoku import judge

    class test_judge(unittest.TestCase): def test_myfun(self): test_num = judge(0, 1, 2)#测试数值 self.assertEqual(test_num, 1)#期望值 if name == 'main': unittest.main()

  • 测试结果 2020软件工程作业03

GOOOOOD!测试符合预期结构

4.对代码全面检测和优化后,更新GitHub上的仓库

六、代码说明

0.导包和定义全局变量

# -*- coding: UTF-8 -*-
import sys
import getopt

# 全局变量
M = ""
N = ""
MY_MAPS = []
OP = ""

1.主函数

if __name__ == '__main__':
    # sys.argv[1:]为要处理的参数列表,sys.argv[0]为脚本名,因此弃之不用
    main(sys.argv[1:])

2.main()函数

def main(argv):
    """
    通过sys模块来识别参数
    :return:
    """
    # 声明全局变量
    global M, N
    global MY_MAPS, OP
    in_put = ""
    out_put = ""
    try:  # 获取参数并处理异常
        opts, args = getopt.getopt(argv, "m:n:i:o:", ["help"])
    except getopt.GetoptError:
        print('Error: Sudoku.py -m -n -i -o')
        sys.exit(2)
    # 处理获取的参数
    for opt, arg in opts:
        if opt in "--help":  # 给予帮助提示
            print('Error: Sudoku.py -m -n -i -o')
            sys.exit()
        elif opt in "-m":
            M = int(arg)
        elif opt in "-n":
            N = int(arg)
        elif opt in "-i":
            in_put = arg
        elif opt in "-o":
            out_put = arg
    with open(in_put, 'r', encoding='utf-8') as _fp_:  # 以读状态打开指定文件读取矩阵
        _MYMAP_ = []
        for line in _fp_.readlines():
            if line != '\n':  # 用换行符分割矩阵
                _MYMAP_.append(list(map(int, line.strip().split(" "))))
            else:
                MY_MAPS.append(_MYMAP_)
                _MYMAP_ = []
        MY_MAPS.append(_MYMAP_)  # MY_MAPS是集合了所有数据的三维数组

    OP = open(out_put, 'w', encoding='utf-8')

    for i in range(N):
        if i > 0:
            OP.write('\n')  # 分割矩阵
        _DFS_(i, 0, 0)  # 递归求解
    OP.close()

3.DFS()递归函数

def _DFS_(_i_, _x_, _y_):
    """
    【DFS】深度优先搜索递归方式
    :return:
    """
    # 声明引用全局变量
    global M, MY_MAPS
    if _x_ > M - 1:  # 完成条件
        _MY_OTP_(_i_)  # 保存数值
    elif MY_MAPS[_i_][_x_][_y_] != 0:  # 当前格子不可填
        if _y_ == M - 1:  # 右边界换行
            _DFS_(_i_, _x_ + 1, 0)
        else:
            _DFS_(_i_, _x_, _y_ + 1)  # 下一格
    else:  # 当前格可填
        for i in range(1, M + 1):
            MY_MAPS[_i_][_x_][_y_] = i  # 试探填入数值
            if judge(_i_, _x_, _y_):  # 判断其试探值的合法性,当判断函数返回值为1即合法
                if _y_ == M - 1:  # 边界情况
                    _DFS_(_i_, _x_ + 1, 0)
                else:
                    _DFS_(_i_, _x_, _y_ + 1)
            # 回溯
            MY_MAPS[_i_][_x_][_y_] = 0

4.judge()合法性判断函数

def judge(_i_, _x_, _y_):
    """
    合法性判断
    :return:
    """
    global M, MY_MAPS
    # 行列不重复判断
    for i in range(M):
        if i != _x_ and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][i][_y_]:
            return 0
        if i != _y_ and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][_x_][i]:
            return 0
    # 区块重复判断
    _x1_ = _y1_ = row = col = 0  # 块内坐标初始值
    # 区块定位参考于https://github.com/zxw0621/demo/blob/master/20177596/src/sudoku.py#L42
    # 这定位写的太好了
    # 根据其阶数确定其模块规模以及所属模块
    if M % 3 == 0:
        row = 3
        col = int(M / 3)
    elif M % 2 == 0:
        row = 2
        col = int(M / 2)
    _x1_ = int(_x_ // row * row)
    _y1_ = int(_y_ // col * col)
    # 遍历所属区块,检查其合法性
    for i in range(_x1_, _x1_ + row):
        for j in range(_y1_, _y1_ + col):
            if _x_ != i and _y_ != j and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][i][j]:
                return 0
    return 1

5.MY_OTP()数据储存函数

def _MY_OTP_(_i_):
    """
    向文件内写入所得矩阵
    :return:
    """
    global N, M, MY_MAPS, OP
    # 遍历当前求解矩阵
    for _x_ in range(M):
        for _y_ in range(M):
            OP.write(str(MY_MAPS[_i_][_x_][_y_]) + ' ')
        OP.write('\n')  # 换行

6.异常处理

  • 当参数输入异常时,输出提示帮助输入

    try: # 获取参数并处理异常 opts, args = getopt.getopt(argv, "m:n:i:o:", ["help"]) except getopt.GetoptError: print('Error: Sudoku.py -m -n -i -o') sys.exit(2)

  • 当用户在命令行输入-help参数时,给予提示

    处理获取的参数

    for opt, arg in opts:
        if opt in "--help":  # 给予帮助提示
            print('Error: Sudoku.py -m -n -i -o')
            sys.exit()
        elif opt in "-m":
            M = int(arg)
        elif opt in "-n":
            N = int(arg)
        elif opt in "-i":
            in_put = arg
        elif opt in "-o":
            out_put = arg
    

7.代码运行结果

命令行 2020软件工程作业03

输入文件 2020软件工程作业03

输出文件 2020软件工程作业03

至此程序宣布完成...

七、心路历程

记录

  • 3月21日
    • 截至到12:00,目前仍然在研究代码实现思路(拖,就硬拖)
    • psp表格
    • 研究DFS递归函数
    • 设计功能模块
    • 查阅资料,实现命令行输入参数
    • 完成main()函数代码
    • 上传项目到GitHub,被网络折磨了半小时
    • 显然急于求成是愚蠢的,折磨了自己一晚上


2020软件工程作业03


  • 3月22日
    • 截至到12:00,完成了博客的基本框架
    • 完成全部代码块
    • 完成流程图
    • 代码静态检测、性能分析、单元测试(折磨王三连折磨)
    • 代码优化,贼难受
    • 更新GitHub仓库(还好这波网络没炸)
    • 写博客
    • 终于完成了!!!芜湖~
总结

——在本次任务中我深刻的认识到了不能闭门造车的道理,死钻牛角尖最后只会折磨自己,应该具有发散性的思维,充分利用网络资源查阅资料,从多个角度对问题进行分析。最终得出自己的解题思路。同时在工作学习时不能急于求成,这样反而会使得自己的效率下降,得不偿失。在遭遇挫折的时候不妨带着问题和其他人互相交流一番,或许问题会用迎刃而解。最后,事实证明写代码只占作业的10%,一系列附属操作把我给折磨的不轻...

2020软件工程作业03

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Easter79 Easter79
2年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
2年前
Java获得今日零时零分零秒的时间(Date型)
publicDatezeroTime()throwsParseException{    DatetimenewDate();    SimpleDateFormatsimpnewSimpleDateFormat("yyyyMMdd00:00:00");    SimpleDateFormatsimp2newS
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“Java进阶架构师”,点击右上角,将我们设为★“星标”!这样才不会错过每日进阶架构文章呀。  !(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)  2
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
4个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这