从需求分析到系统设计.pdfVIP

讲座：从需求分析到系统设计 董祖明, 2005 年5 月20 日 一、八皇后问题 先以八皇后为例，说明从原始需求的描述、到需求的分析、再到系统的设计的逻辑抽象 的过程，说明从需求分析的What 到系统设计的How 。 1、原始需求描述 八皇后问题：把八个皇后放在棋盘上，使任何皇后都不能吃到其他皇后 2、需求分析： 这个需求隐含了国际象棋的规则（业务规则）： 国际象棋的棋盘：8 行8 列的64 个方格，棋子放在方格上 皇后的走法：可以走直线、横线、斜线，任意格数 因为皇后可以走任意步数的直线、横线和斜线的米字形棋步，所以八个皇后互相不能 吃到其他皇后可以转化表述为同一条直线、横线和斜线上不能有两个或以上的皇后。 由于明显每行只能有一个皇后，可把问题简化为每条横线、上斜线、下斜线上最多只 能摆一个皇后。 用数据的方法抽象地表示“同线”的业务逻辑，同一直线上的皇后，横坐标相同；同 一横线上的皇后，纵坐标相同；斜线分为上行斜线和下行斜线，下行斜线的横纵坐标之和相 等；上行斜线的横纵坐标之差相等。 一共有8 条横线、8 条直线、15 条上斜线、15 条下斜线。 3、系统设计： 8x8 的棋盘共有8 条直线、8 条横线、15 条上行斜线和15 条下行斜线，可以表示如下： 数据结构： int a[8]; /* 1 表示第i 行上无皇后 1 到8 */ int b[15]; /* 1 表示第i 条上行斜线上无皇后 2 到15 */ int c[15]; /* 1 表示第i 条下行斜线上无皇后 -7 到+7*/ int x[8]; /* 记录第i 列上皇后的位置 1 到8 */ 操作设计： 置放皇后：x[i]=j; a[j]=0; b[i+j]=0; c[i-j+7]=0; /* 0=false */ 移去皇后：a[j]=1; b[i+j]=1; c[i-j+7]=1; /* 1=true */ 判断安全：a[j] b[i+j] c[i-j+7] /* true 表示三条线上都无其他皇后 */ 这里下标的计算方法决定了数组的边界, 本例是为因为C 语言的数组只能从0 开始 算法设计： 使用尝试-纠错和回溯方法，递归算法。先找第 i 行的安全位置放一个皇后，然后 尝试在第i+1 行的安全位置放下一个皇后，如果第i+1 个皇后无处可放，则退回到第i 个皇 后重新选择另一个安全位置，直到放完8 个皇后。 算法概要： test(i) { for k=1 to m { 选择第k 个候选者 if 可接受 then { 记录它 if in then test(i+1) else 打印解 删除记录 } } } 这是在算法与数据结构的教科书中讲过的一个非常基础的通过试错- 回溯来寻找所有解 的解题思路。当然也可以转化为等价的8 层循环的算法，递归算法表达得更简练。 4、程序设计 #include stdio.h int a[8]; /* 1 表示第i 行上无皇后 1 到8 */ int b[15]; /* 1 表示第i 条上行斜线上无皇后 2 到15 */ int c[15]; /* 1 表示第i 条下行斜线上无皇后 -7 到+7*/ int x[8]; /* 表示第i 列上皇后的位置 1 到8 */ /* 打印一个解 */ void print() { int k; for (k=0; k8; k++) printf(%d ,x[k]); printf(\n); } /* 递归算法 */ void test(int i) { int j; for (j=0; j8; j++) /* 选择第j 个候选者 */ if (a[j] b[i+j] c[i-j+7