时间戳

首页 > 技术文章 > 软件工程实践第二次作业——个人项目实战(数独)

软件工程实践第二次作业——个人项目实战(数独)

cjqcjq 2017-09-12 16:29 原文

作业链接

1）Github项目地址

2）在开始实现程序之前，在下述PSP表格记录下你估计将在程序的各个模块的开发上耗费的时间
见 8）。
3）解题思路描述

拿到题目后，阅读了项目需求，得知这次作业要求我们利用程序随机构造出N个已解答的数独棋盘。项目的关键就是一要构建出9 * 9且符合要求的数独棋盘。由于自己并未写过有关构建数独的算法，于是就去上网搜了相关资料,我选择了比较容易理解的置换法。置换法的思路是：数独棋盘的9宫从左至右，从上至下标记为M1,M2,...,M8,M9(方便理解和阐述)，先构建3 * 3的初始棋盘将其放在M5的位置上，将M5进行行变换生成M4,M6,将M5进行列变换生成M2,M8。现在再分别以M2,M8，进行行变换，分别得到M1,M3和M7,M9。构建好之后，将数独棋盘输出至txt，采用了ofstream方法。

4）设计实现过程

理清了思路，接着就要设计实现了。代码包含了generator类，在generator类中声明了以下函数

  • int get_random_number(); //获取随机数1~9
  • void generate_sudoku(); //构建数独
  • void generate_txt(int num,string str); //将数独棋盘写入文件

5）代码说明

以下是构造数独棋盘的代码：

int begin_board[3][3];  //数独棋盘中心3*3棋盘(基点棋盘)

int sudoku_board[10][10];
//数独棋盘中心9*9棋盘(9*9棋盘分成9个3*3棋盘填充，从左往右，从上到下记为M1,M2, ... ,M8，M9棋盘)

int flag[10]; //判断随机数是否重复


void generator::generate_sudoku() //构建数独
{

memset(begin_board, 0, sizeof(begin_board));
memset(flag, 0, sizeof(flag));
memset(sudoku_board, 0, sizeof(sudoku_board));

/*
 生成基点3*3棋盘
*/

int count = 0;

for (int i = 0; i < 3; i++)
	for (int j = 0; ; j++)
	{
		int temp = get_random_number();
		//cout << temp << endl;
		if (flag[temp] == 0)
		{
			begin_board[i][count] = temp;
			flag[temp] = 1;
			count++;
			if (count == 3)
			{
				count = 0;
				break;
			}
		}
	}



for (int i = 0; i < 3; i++)
	for (int j = 0; j < 3; j++)
	{
		sudoku_board[i + 3][j + 3] = begin_board[i][j];  // 生成9*9棋盘的中心的3*3棋盘(M5)

		/*
		 以基点棋盘进行行变换，向左，右扩展，生成M4,M6
		*/

		switch (i)
		{
		case 0:
			sudoku_board[i + 4][j] = begin_board[i][j];  // 填充9*9棋盘的[4][0~2]位置
			sudoku_board[i + 5][j + 6] = begin_board[i][j];  // 填充9*9棋盘的[5][6~8]位置
			break;

		case 1:
			sudoku_board[i + 4][j] = begin_board[i][j];  // 填充9*9棋盘的[5][0~2]位置
			sudoku_board[i + 2][j + 6] = begin_board[i][j];  // 填充9*9棋盘的[3][6~8]位置
			break;

		case 2:
			sudoku_board[i + 1][j] = begin_board[i][j];  // 填充9*9棋盘的[3][0~2]位置
			sudoku_board[i + 2][j + 6] = begin_board[i][j];  // 填充9*9棋盘的[4][6~8]位置
			break;
		}

		/*
		  以基点棋盘进行列变换，向上，向下扩展，生成M2，M8
		*/

		switch (j)
		{
		case 0:
			sudoku_board[i][j + 4] = begin_board[i][j];  // 填充9*9棋盘的[0~2][4]位置
			sudoku_board[i + 6][j + 5] = begin_board[i][j];  // 填充9*9棋盘的[6~8][5]位置
			break;

		case 1:
			sudoku_board[i][j + 4] = begin_board[i][j];  // 填充9*9棋盘的[0~2][5]位置
			sudoku_board[i + 6][j + 2] = begin_board[i][j];  // 填充9*9棋盘的[6~8][3]位置
			break;

		case 2:
			sudoku_board[i][j + 1] = begin_board[i][j];  // 填充9*9棋盘的[0~2][3]位置
			sudoku_board[i + 6][j + 2] = begin_board[i][j];  // 填充9*9棋盘的[6~8][4]位置
			break;
		}
	}

/*
	   以M2作为基点棋盘进行行变换，向左，向右扩展，生成M1，M3
*/

for (int i = 0; i <= 2; i++)
	for (int j = 3; j <= 5; j++)
	{
		switch (i)
		{
		case 0:
			sudoku_board[i + 1][j - 3] = sudoku_board[i][j];  // 填充9*9棋盘的[1][0~2]位置
			sudoku_board[i + 2][j + 3] = sudoku_board[i][j];  // 填充9*9棋盘的[2][6~8]位置
			break;

		case 1:
			sudoku_board[i + 1][j - 3] = sudoku_board[i][j];  // 填充9*9棋盘的[2][0~2]位置
			sudoku_board[i - 1][j + 3] = sudoku_board[i][j];  // 填充9*9棋盘的[0][6~8]位置
			break;

		case 2:
			sudoku_board[i - 2][j - 3] = sudoku_board[i][j];  // 填充9*9棋盘的[0][0~2]位置
			sudoku_board[i - 1][j + 3] = sudoku_board[i][j];  // 填充9*9棋盘的[1][6~8]位置
			break;
		}
	}


/*
以M8作为基点棋盘进行行变换，向左，向右扩展，生成M7，M9
*/

for (int i = 6; i <= 8; i++)
	for (int j = 3; j <= 5; j++)
	{
		switch (i)
		{
		case 6:
			sudoku_board[i + 1][j - 3] = sudoku_board[i][j];  // 填充9*9棋盘的[7][0~2]位置
			sudoku_board[i + 2][j + 3] = sudoku_board[i][j];  // 填充9*9棋盘的[9][6~8]位置
			break;

		case 7:
			sudoku_board[i + 1][j - 3] = sudoku_board[i][j];  // 填充9*9棋盘的[8][0~2]位置
			sudoku_board[i - 1][j + 3] = sudoku_board[i][j];  // 填充9*9棋盘的[6][6~8]位置
			break;

		case 8:
			sudoku_board[i - 2][j - 3] = sudoku_board[i][j];  // 填充9*9棋盘的[6][0~2]位置
			sudoku_board[i - 1][j + 3] = sudoku_board[i][j];  // 填充9*9棋盘的[9][6~8]位置
			break;
		}
	}

}

思路的话，前面已经叙述过了，就不再赘述了。

6）测试运行。
输入N=10，在控制台得出以下结果:

以下是命令行测试截图：

7）记录在改进程序性能上所花费的时间，描述你改进的思路，并展示一张性能分析图，并展示你程序中消耗最大的函数

第一次使用性能分析工具，用的不是很得心应手...

以N=1000测试得到以下的性能分析图：

从性能分析图可得出程序中消耗最大的函数是: void generate_txt(int num,string str); //将数独棋盘写入文件

改进前代码：

void generator::generate_txt(string str) //将数独棋盘写入文件
{
    string str1 = str + "/sudoku.txt";
    //cout << str1 << endl;

    ofstream txt(str1, ios::out);
    //txt.open(str1);

    for (int i = 0; i < 9; i++)
	    for (int j = 0; j < 9; j++)
	    {
		    txt << sudoku_board[i][j] << " ";

		    if (j == 8) txt << endl;
	    }

    txt << endl;
    txt << endl;
    txt.close();
}

通过在主函数调用写入txt函数，每写入一次就得打开一次文件，比较耗时

改进方法:只打开一次文件，直至写入文件完成后关闭文件

改进后代码:

void generator::generate_txt(int num, string str) //将数独棋盘写入文件
{
generator gene;

string path = str + "/sudoku.txt";

//cout << path << endl;

ofstream  txt(path, ios::out);

for (int k = 0; k < num; k++)
{
	gene.generate_sudoku();

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
		{
			txt << sudoku_board[i][j] << " ";

			if (j == 8) txt << endl;
		}

	txt << endl;
	txt << endl;
}

txt.close();
}

改进后得到以下的性能分析图：

好像只快了3秒钟额...虽然提升的不是很多，但自己也挺满足的。

在网上查了一些资料，了解到c++里的文件流fstream输出效率在批量较大的时候远不如c里的freopen，因此再一次改进输出函数

void generator::generate_txt(int num, char * str) //将数独棋盘写入文件
 {
generator gene;

freopen(str, "w", stdout);

for (int k = 0; k < num; k++)
{
	int len = 0;
	gene.generate_sudoku();

	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
		{
			res[len++] = sudoku_board[i][j] + '0' ;
			res[len++]=' ';

			if (j == 8) res[len++] =' \n';
		}

	puts(res);
}

fclose(stdout);
 }

改进后得到以下的性能分析图：

由性能分析图可知，输出写入txt的效率大大提高了。

8）PSP 2.1表格

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

9）遇到的困难与收获

对于确保生成的棋盘文件 sudoku.txt 与可执行文件在同一目录下，生成文件时请使用相对路径这一要求，自己思考了挺久的。
解决方法：我的想法是去获取.exe的路径，然后在该路径下将数独棋盘写入 sudoku.txt，题目要求我们使用相对路径，然而自己完全没有这个概念，于是就去了解了绝对路径和相对路径的区别；对于获取.exe的路径，运用了GetModuleFileName函数（参考资料1,参考资料2）
收获的话，学习了一些新的知识，如获取.exe的路径...也复习了一些知识，如通过命令行调用.exe...除此之外，通过填写PSP表格，让自己估算完成每一步骤的所时间，督促自己提高效率，在实践的过程中更有目标性。因此在之后的项目实践中要好好利用PSP这一利器。
至于附加题，想法是用MFC开发GUI界面，自己尝试着去学习，发现并不能很快的学会，因此就先放着...

积跬步，至千里，未来可期。

推荐阅读