软工实践第二次作业-sudoku

说明


解题思路

  • 一开始拿到的时候,有一个思路,可以先填写全盘的“1”,然后在插空填满全盘的“2”。后来觉得自己理不清那个思路。遂放弃。

    参考思路:(http://blog.csdn.net/nibiewuxuanze/article/details/47679927)
  • 第二个思路,是在一个博客上看到的,博主是把第一行随机打散然后第二行开始,从1-9测试哪一个数能填入此空,继续往下。但是这个思路是有问题的,因为选择填入的数字是一个循环,从1-9,也就是就是一旦第一行确定了,下面的数独只有一个唯一解了,重复率极高。
  • 后来改进了,通过rand( )函数随机生成数字然后测试能否填入该空格。测试条件三个:行、列、3x3小方格。
  • 为了随机性更强,又改进了一种方式:每次都随机打乱一个初始数组,然后从这个数组里抽选数字考虑是否填入。
random_shuffle(&(vi[1]), &(vi[10]));//vi一维数组打乱1-9
  • 对于左上角固定数字的思路,一开始是打算等数独终盘生成后,找到第一个3x3方格里的需要的数字,把该行该列换到第一个。后来觉得这种方法花费的时间很多,修改成了一开始就固定sudoku[1][1]=x。从第二个数开始填写,加快了运行速度,缩短时间。

    参考思路:(http://blog.jobbole.com/108488/?utm_source=tuicool&utm_medium=referral)

    注意:
  • 第一行除了第一个固定,其他地方都通过find(i,j)取得k值
  • 在选取k值的时候,用一个数组先打乱,再按序从中选取

关键代码

  • 除了主函数外只有两个函数

    bool isNUM(string str)//用于判断输入的是否是纯数字

    bool find(int i, int j)//搜索(i,j)可以存储的数字

    几乎把所有功能都堆在了find(i,j)……发现后面的分析等等很不好做,下一次会注意书写的时候把不同功能拆开,模块化处理。

  • Bool型函数,返回true or false,用sign标识简单明白体现是否能放在某个位置

  • 每次都随机打散数组vi,从随机数组vi中循环挑选数字填写,然后三个判断条件:这一行是否有这个数字、这一列是否有这个数字、这一个3x3小矩阵是否有这个数字。如果都符合,就继续find下一个位置能填入的数字。如果1-9全部尝试了都不符合,就退回上一步。

bool find(int i, int j)//搜索(i,j)可以存储的数字
{
int vi[10];
for (int i1 = 1; i1 <= 9; ++i1)
vi[i1] = i1;
random_shuffle(&(vi[1]), &(vi[10]));//vi一维数组打乱1-9 for (int s = 1; s <= 9; s++)//循环数组取数字
{
int k = vi[s];//取k为数组中第一位数
bool sign = true;//sign标记能否将k放在(i,j)处 for (int m = 1; m < i; m++)
if (sudoku[m][j] == k)//检查同一列是否出现过数字k
{
sign = false;
break;
} if (sign == true)
{
for (int n = 1; n < j; n++)
if (sudoku[i][n] == k)//检查同一行是否出现过数字k
{
sign = false;
break;
} } if (sign == true)
{
int imax = (i / 3) * 3 + 3;//(i,j)所在的3x3小方格的最大行数
int jmax = (j / 3) * 3 + 3;//(i,j)所在的3x3小方格的最大列数 if (i % 3 == 0)
imax = i;
if (j % 3 == 0)
jmax = j; for (int p = imax - 2; p <= imax; p++)//检查3x3小方格
{
if (sign == false)
break; for (int q = jmax - 2; q <= jmax; q++)
if (sudoku[p][q] == k)
{
sign = false;
break;
}
}
} if (sign == true)
{
sudoku[i][j] = k;
if (j < 9)
{
if (find(i, j + 1) == true)//搜索本行右边的位置
return true;
}
else
{
if (i < 9)
{
if (find(i + 1, 1) == true)//搜索下一行
return true;
}
else
return true;//i>=9,j>=9,搜索结束 }
sudoku[i][j] = 0;//找不到要清0
}
}
return false;//本位置1-9都不能填,返回上一步
}

测试运行

  • 错误指令/结果

    sudoku.exe -o 1

    Sudoku.exe -c abc

    Sudoku.exe -c 0

    软工实践第二次作业-sudoku

  • 正确结果

    Sudoku.exe -c 3

    软工实践第二次作业-sudoku

    软工实践第二次作业-sudoku

  • (9.10更新)发现还要考虑如果传入的参数不等于3个的情况

    sudoku.exe -c -c 1

    软工实践第二次作业-sudoku

ps:后来发现改成Release的状态下运行速度更快,但是之前测试的版本是Debug的,所以上述的截图上在Debug的文件夹下。


效能分析与改进

  • n=1000000
  • 解决了大部分的奇奇怪怪的输入输出问题,但是1000000的运行时间还是太久,需要15分钟左右,但是没有想到更好更快的改进方法。并且没有进行重复判断,完全是依赖随机性来避免重复。
  • (9.10更新)修改了输出之后,不用ofstream类,用输出重定向,数独缩短了将近一半,现在只需要497s,在十分钟以内。
  • (再更新)一开始没有把编译的版本改为Release,所以跑的非常慢,多达857s,超出十分钟。后来优化了一点点的代码,达到497s。将版本改为release之后,速度达到63s。

    软工实践第二次作业-sudoku

(舍友的电脑左下角会显示函数名但是我的全都是工程的名字……不知道为什么……)

软工实践第二次作业-sudoku

软工实践第二次作业-sudoku

软工实践第二次作业-sudoku

  • 本次作业,自己的代码不够模块化,所有的东西都往一个函数里放,好像这个功能很强大似得。但是其实后面效能分析的时候就比较不容易改进,所以下次码代码的时候,要分块分清楚,更加规范。这次由于在修改输入输出的一些问题花费了很多时间,遂没有去修改函数方面的问题。

    命令行执行EXE参考材料:(http://blog.csdn.net/txl199106/article/details/44703489)

PSP表格

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

遇到的困难及解决方法

- 困难描述

1.遇到的最大的困难就是太久没有接触代码了,一开始的时候,简直无从下手,从书柜里翻出了c语言和c++的书,稍微翻了一下,看了几眼头文件什么的。而且,很久没有打代码,思路很混乱,很难切入这个问题,想到核心,进入状态需要很久。

2.二是不熟悉VS。安装花了很长时间在捣鼓,然后关于新建的东西也比较不熟悉,后来是向同学请教了之后才明白具体如何新建。不然之前一直在报错“找不到EXE文件”,搜遍了百度都没法解决……原来是新建的时候建错了文件。并且,对于测试等等,也是第一次接触,一头雾水。一些名词,比如“代码覆盖率”等等都是第一次听说,感觉高大上了不少……

3.对于命令行运行EXE也是第一次接触,花了很多时间看相关的知识,修改主函数。

4.对于单元覆盖率、单元测试还是不熟悉。比起一些大一就用过Github的同学而且我完全是纯新手……一开始有点茫然

- 做过哪些尝试

1.看其他同学写的博客,有的同学会写教程,感觉很赞,比如VS安装教程等等,虽然可能大部分人都会但是……对于比较菜鸟的我还是挺有用的T T。。

2.还有的同学会把觉得不错的教程链接贴出来,我就进去看看,感觉有的写得简单易懂,能一下子理解很多。

3.感觉现在的自己还处于“拿*造车”的阶段,还有很多东西不是真正属于自己的,还需努力。

- 有何收获

1.熟悉了对于命令行运行exe的主函数写法,文件的输出,输出重定向,最重要的是重新拾起了打代码的思维。

2.本次的习题,我觉得和之前上c++的作业还是有很大区别的,因为c++只需要打一个代码就好了,而本次作业,就更接近真正的程序员要做的事了,包括各种测试等等,完成度更高,更完善了,更像是一个项目而不是一段代码了。

上一篇:Go 标准库 http.FileServer 实现静态文件服务


下一篇:oracle 内存结构具体解释