《算法分析及设计大作业》由会员分享，可在线阅读，更多相关《算法分析及设计大作业（11页珍藏版）》请在金锄头文库上搜索。
1、问题描述在本次算法分析的课堂演示中，我做的是一个关于“裁切悖论消失的正方形的 PPT”，但是由于代码的问题，现在借鉴了同学的实验，写了一个关于数独算法的小题目。如下图所示，有一个 9*9 的正方形，而正方形又分成了九个小正方形，现在已经在图示的正方形中给出了一些方格中的数字，要求将正方形中所有小方格的数字填充完，并且每个小正方形以及每行、每列，只能出现一次 19 这九个数字。6 8 79 5 7 64 83 24 6 94 1 2 35 3 1 78 9 21 7 6 3解决方案我们先假设填入的数字为 08 共 9 个数字。将整个图分成 9 个 3*3 的方块，从左到右，从上到下，依次编号 0
2、 8。填每个格子的时候,我们可以选择.08。对于选择的数字，有 3 种限制，我们通过这三种限制来对回溯过程进行剪枝。1.行不重复 r992.列不重复 c993.块不重复 b99对使用 3 个 99 的数组来描述这三种限制。对于行 n 来说，所有之前填过的数字 nums，都有 rnnums = 1。同理，对与列与块来说，之前每个填过的数字都相应标记为1。当尝试向一个格子rowcol (块序号为 bi)填充数据i（0#include #define MMAX 9char MMMAXMMAX = 0;int count = 0;int getblockid(int row, int col)retu
3、rn row/3 * 3 + col/3;void getnext(int *row, int *col, int* nrow, int* ncol)if(*col =8)*ncol = 0;*nrow = (*row)+1;Else*nrow = *row;*ncol = (*col) +1;void outputmatrix(char mtrMMAXMMAX )int i, j;for(i=0;iMMAX;i+)for(j = 0; jMMAX;j+)printf(%d , mtrij);printf ( n );void fill(int row, int col, char matri
4、xMMAXMMAX, char rowdMMAX, char coldMMAX, char blodMMAX)count +;if(matrixrowcol != 0)if(row = 8 & col = 8)outputmatrix(matrix);return;int nr, nc;getnext(fill(nr,nc,matrix,rowd,cold,blod);return;int i = 1;char mtrMMAXMMAX;memcpy(mtr, matrix, MMAX*MMAX*sizeof(char);for(;i= 9;i+)/duplicate all dataint b
5、lockid = getblockid(row, col);if(blodblockidi-1!= (char)1 &rowdrowi-1!=(char)1 &coldcoli-1!=(char)1 )/fill the cell/ printf ( fill %d %d with %dn,row, col, i );matrixrowcol = i;if(row = 8 & col = 8)outputmatrix(matrix);return;/set the restrictionblodblockidi-1 = 1;rowdrowi-1 = 1;coldcoli-1 = 1;int n
6、row,ncol;getnext(fill(nrow,ncol,matrix,rowd,cold,blod);/restore statusblodblockidi-1 = 0;rowdrowi-1 = 0;coldcoli-1 = 0; matrixrowcol = 0;void trackfixedcell(char fixmtrMMAXMMAX, char rMMAXMMAX,char cMMAXMMAX,char bMMAXMMAX)int row,col;for(row = 0; rowMMAX; row+)for(col= 0; colMMAX; col+)if(fixmtrrow
7、col!= 0)rrow(int)fixmtrrowcol-1 = 1;ccol(int)fixmtrrowcol-1 = 1;bgetblockid(row,col)(int)fixmtrrowcol-1 = 1;void readfixed(char mtrMMAXMMAX, char* input)int i = 0;for(;iMMAX*MMAX;i+)int row = i/MMAX;int col = i%MMAX;if(inputi != 0)mtrrowcol = inputi-48;/* = FUNCTION =* Name: main* Description:* =*/i
8、ntmain ( int argc, char *argv )char * fixed = 600087000000905706040000080030002000004000690000410023500030170080090200001076300;char rMMAXMMAX = 0;char cMMAXMMAX = 0;char bMMAXMMAX = 0;readfixed(M,fixed);trackfixedcell(M,r,c,b);fill(0,0,M,r,c,b);printf ( count = %dn, count );return EXIT_SUCCESS; /*
9、- end of function main - */实现图总结在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性与时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编辑系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法分析与设计是计算机科学与技术的一个核心问题。
