项目相关要求
Github 项目地址:https://github.com/zjwml4581792/Software-engineering
第一次的真软工实践作业就是这种题目,想想还有点小激动,终于又要敲代码啦。看着自己现在的编程的“纸飞机阶段”,想完成,还是等待~并心怀希望吧!
先看题目。
度娘说:数独(百度百科)
数独(Sudoku,Crosswords)是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。
数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。
工具清单
- 编程语言: C/C++
- 编程IDE:Visual Studio 2017 社区版
- 效能分析工具:Visual Studio Profiling Tools
- 源代码管理平台:Github
- markdown 编辑器:有道云笔记
解题思路
遇到的困难及解决方法
- 困难描述
看到的第一眼就是,这个题目跟程序语言综合设计的那个马踏棋盘和N皇后问题好像啊,一百度,果然三个题目经常绑定出现,用的很多都是回溯。
然而自己并不是很懂回溯,于是自己找了找不是回溯算法的大神写的博客。可惜大神写的算法我基本看不懂。
各种各样的问题显示了自己的功力不足,函数什么时候开始回溯啊,调用函数自己的那行到底写在哪里啊,比较好的想法到底是哪一种啊……
- 做过哪些尝试
自己什么都不懂,直接开始写是不现实的,于是开始问学长。
先问了个直系老乡研究生谷歌(还是微软)大佬,说“数独问题用 dancing links 算法来写”,,一百度好像dancing links 真的很厉害的样子,但是好像这么复杂的双向链表我真的写不出来。
自己百度“数独生成算法”吧,看看前辈们都用的是什么算法,用的思想是不是太超前自己能不能接受。
找到的比较看得懂自己印象比较深有启发的:
于是自己尝试了生成 9 个随机数组一行一行填进矩阵,一个一个数字地填,一个九宫填一个九宫地填等等各种方法。
- 是否解决
最后采用了 0~9 轮流逐行地填的方法,即从1开始填,从第0行填到第8行,1填完了填2,直到9。
事实证明采用了某种方法如果理论没问题一定要坚持到底,如果不断地尝试别的方法真的没有效率,就跟《构建之法》里的画扇面一样,过早想着优化,都还没完成必要功能和需求就不要考虑太多。先写出来了再说。
- 有何收获
从 【1】 中汲取了“按九宫格从左到右从上到下,从 1-9 轮流填,填完了再填下一个数”的思想并改造;
从 【2】 中得到了先把无依赖的主对角线上的三个小九宫填满,再填其他九宫的思想(但是最终并没有用到这方法)
从 【3】 中了解了怎么写回溯算法。
自己的搜索能力暴涨,code能力小幅升,熬夜能力MAX,泡面技巧infinite
。拖延症已病入膏肓
关键代码
习惯看到题目就先创建个类,这个数独类至少需要有构造函数、析构函数、创建矩阵、打印矩阵四个函数,数独矩阵二维数组,然后根据需要添加了初始化函数,判断函数,文件变量等,详见代码注释。
class Sudo
{
public:
Sudo(int id); //构造函数
~Sudo(); //析构函数
void createSudoku(int id);//创建数独矩阵
void print(); //打印
void init(); //初始化
private:
ofstream outfile; //输出文件
int arr[9][9]; //数独矩阵数组
int flag; //是否把每一行的该数都填好的标志
int firstNumber; //题目要求的跟学号有关的数
bool isRight(int row, int column, int num);//判断row行column列是否可以填num
vector<int> randVector(); //生成随机数组
void fillNumber(int num, int row); //从row开始每一行开始填充num
void clean(int i); //填充失败,把i数清除,重新填过
};
看到题目想到要写的第一个函数就是判断函数,在写的时候先分别写了行判断、列判断、九宫判断三个函数,以及调用三个函数的isRight原始版,后来整合到一起了就成了下面的新生版。由于是逐行填充的,只需要检查列和九宫符不符合要求即可。
后来思考如果按照每个九宫来填数,只需要判断行和列会不会更快,但是按九宫来填数,填数就麻烦了,根据第一个博客里的来看,应该按九宫来会快些。
bool Sudo::isRight(int row, int column, int num)
{//判断所在位置是否可行
for (int i = 0; i < 9; i++)
{//检查列可不可以
if (arr[i][column] == num)
return false;
}
int northwestX = row / 3 * 3;//算小九宫的第一个位置
int northwestY = column / 3 * 3;
//检查九宫
for (int i = 0; i < 3; i++)//横向检查
{
for (int j = 0; j < 3; j++)//竖向检查
{
if (arr[i + northwestX][j + northwestY] == num)
return false;
}
}
return true;
}
如果是普通的随机数的生成的话,一定会生成重复的随机数,于是生成一个0-8的随机数组,需要用的时候遍历数组。
如何生成随机数组的方法是网上找的,C++下数组随机shuffle的方法解
vector<int> Sudo::randVector()//生成随机数组
{
vector<int> result;
result.clear();
for (int i = 0; i < 9; i++)
result.push_back(i);
random_shuffle(result.begin(), result.end());
return result;
}
创建数独,先填要求的数,再从1-9填,没法填了就退回上一个数重新填过。
void Sudo::createSudoku(int hhhhhh)//创建数独
{
fillNumber(firstNumber, 1); //先把要求的那个数填进去
for (int i = 1; i < 9; i++) //从1到9开始填充
{
if (i == firstNumber)//如果是要求的那个数
continue; //则跳过
fillNumber(i, 0); //逐行填充数i
if (flag) //如果填充好了
flag = false; //将flag置false,准备下一个数
else //如果没填好
{
clean(i);//把上一个数清掉,重填
i -= 2; //先-2,待会+1,从上一个数重新开始
}
}
for (int i = 0; i < 9; i++)//发现上面填完了之后9是空的
{
for (int j = 0; j < 9; j++)//就写一个循环把9补上
{
if (arr[i][j] == 0)
arr[i][j] = 9;
}
}
}
最重要的填数,不过这个回溯挺最简单,从第0行开始填num。
void Sudo::fillNumber(int num, int row)//从row行开始填充num
{
if (row > 8) //如果0-8行都填完了
{
flag = true; //将填好的标志flag置true
return; //返回
}
vector<int>temp = randVector(); //生成随机数组,
for (int i = 0; i < 9; i++) //从数组第一个数开始测试第row行temp[i]列行不行
{
if (arr[row][temp.at(i)] != 0)//如果这个位置填过了
continue; //跳过这列
if (isRight(row, temp.at(i), num))//如果这个位置可以
{
arr[row][temp.at(i)] = num; //填上去
fillNumber(num, row + 1); //填下一个行
if (flag) //如果填好了
return; //返回
arr[row][temp.at(i)] = 0;//如果这个数这行填不成,把上一行该数置0,换temp下一个数试试
}
}
}
程序运行截图
图中的运行时间是测试用的,暴露了自己这个算法有待改进,很大的改进。
效能分析
摘要
调用关系树
从中可以看出,主要是填充数函数占了最多时间,因此算法本身有很大的改进空间,比如判断函数,从周同学的作业中,可以看出自己和TA的差距;也可以把fillNumber函数的返回值设为Bool,也能少个变量flag。另外vector系列也是比较耗时的,用的不多的话,自己写个随机生成数组的函数,借助库函数是比较耗时。
关于执行力、泛泛而谈的理解
百毒百科说
执行力是指有效利用资源、保质保量达成目标的能力,指的是贯彻战略意图,完成预定目标的操作能力。是把企业战略、规划、目标转化成为效益、成果的关键。
执行力包含完成任务的意愿,完成任务的能力,完成任务的程度。对个人而言执行力就是办事能力;对团队而言执行力就是战斗力;对企业而言执行力就是经营能力。
简单来说就是行动力。
我的理解就是,在拿到任务之后,用自己最专注的热情去完成这件事,最及时地完成,对待任务当机立断、雷厉风行,以秋风扫落叶之势,脚踏实地、贯彻始终,知行合一。
其实上面的这段话就是泛泛而谈,没有什么针对性,就比如创新创业比赛上,上台的很多学生都是侃侃而谈,对于自己的产品本身的介绍并不多,就算是客观的场面话,也没有讲到针对于自身产品最大的痛点。
PSP
PSP2.1 | Personal Software Process Stages | 预估耗时(分钟) | 实际耗时(分钟) |
---|---|---|---|
Planning | 计划 | 20 | 10 |
· Estimate | · 估计这个任务需要多少时间 | 20 | 10 |
Development | 开发 | 1775 | 1820 |
· Analysis | · 需求分析 (包括学习新技术) | 60 | 73 |
· Design Spec | · 生成设计文档 | 30 | 没有做 |
· Design Review | · 设计复审 (和同事审核设计文档) | 30 | 单干,不需要 |
· Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 15 | 7 |
· Design | · 具体设计 | 120 | 120 |
· Coding | · 具体编码 | 1440 | 1560 |
· Code Review | · 代码复审 | 60 | 20 |
· Test | · 测试(自我测试,修改代码,提交修改) | 20 | 40 |
Reporting | 报告 | 155 | 78 |
· Test Report | · 测试报告 | 30 | 30 |
· Size Measurement | · 计算工作量 | 15 | 15 |
· Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 120 | 33 |
合计 | 1960 | 1908 |
学习进度条
第 N 周 | 新增代码(行) | 累计代码(行) | 学习耗时(小时) | 累计学习耗时(小时) | 重要成长 |
---|---|---|---|---|---|
第 0 周 | 192 | 192 | 31 | 31 | 复习C++语法、学习VS2017操作、了解回溯 |