《软件工程第四章软件设计》课件.ppt

NS 盒图 由Nassi和Shneiderman提出，因此而得名。 PAD 问题分析图 由Nassi和Shneiderman提出。 PDL 程序设计语言 PDL是一种用于描述功能模块的算法设计和加工细节的语言，也称伪码(pseudo code)。 外层语法：符合一般程序设计语言常用语句的较严格的关键字语法规则，用于定义控制结构和数据结构。 内层语法：可以用英语中一些简单的句子、短语和通用的数学符号，来描述程序应执行的功能。 IF- THEN- ELSE- ENDIF DO-WHILE- ENDDO REPEAT-UNTIL- ENDREP CASE-OF- WHEN-CONDITION-SELECT- ENDCASE DECLARE …AS STRING ARG … …AS ARRAY ARG 例 某系统主控模块的处理流程用PDL描述如下： PROCEDURE MAIN( ) 清屏； 显示xx系统用户界面； 接收用户输入口令； IF 输入口令系统保存的口令 提示警告信息； 退出系统； ENDIF WHILE (.T.) 显示系统主菜单； ABC=接收用户选择； IF ABC = ‘退出’ 退出本循环; ENDIF 调用相应的下层模块完成用户选择的功能; ENDWHILE 清屏； RETURN END 例 某系统主控模块的处理流程用FC描述如下： 例 模块binary(x,v,n,p)完成判断一个特定值x是否出现在已经按递增顺序排好序的数组v中。如果存在则返回相应下标mid ，否则返回值-1。 low=0 low=high mid=(low+high)/2 xv[mid] high=mid-1 low=mid+1 xv[mid] return(mid) high=L return(-1) Y 例 逐步求精方法示例：骑士周游问题。给出一块有n2个格子的棋盘。一位骑士放在初始坐标为（x0,y0）的格子里，然后按照国际象棋的规则移动。问题是找到一种可以走遍整个棋盘的方案（如果这种方案存在），即计算一个n2-1次移动的周游，使得棋盘上每一个格子恰好被走过（访问过）一次。 (1)数据结构设计： 棋盘：用一个二维整型数组h[i,j],I=1..n,j=1..n 马的移动位置：有8个可走位置。马的初始位置为(x,y),下一个移动位置(x+a[k],y+b[k])，其中k=1..8。 3 2 4 1 5 8 6 7 i a[i] B[i] 1 2 1 2 1 2 3 -1 2 4 -2 1 5 -2 -1 6 -1 -2 7 1 -2 8 2 -1 X 0 棋盘格子h[ x,y]是否被访问过，可以用下面的方式记录： 0表示格子[ x,y]未被访问过 i 表示格子[ x,y]在第i次移动中被访问过,1=i=n2 h[ x,y] = (2)算法设计：试探+回溯 步1：初始化； 步2：对给定的马的当前位置 调用“试探下步移动”； 步3：if 下步移动成功 then 步3.1： 打印移动结果； else 步3.2： 打印无解 endif 步1的“初始化”工作可以细化为： 1.1马的8个可移动位置的差值分别按照前面表格中的值预先放在a、b数组中； 1.2 棋盘在马未访问过时应该都预先放入0； 1.3 马的最初位置可以是（1 ,1）；此时该位置所确定的棋盘格子认为被访问过,因此应有h[ 1,1] =1。 (2)算法设计：试探+回溯 步1：初始化； 步2：对给定的马的当前位置 调用“试探下步移动”； 步3：if 下步移动成功 then 步3.1： 打印移动结果； else 步3.2： 打印无解。 endif 对于马的当前位置的下步移动应该有8个候选位置用K计数，候选次序是前面图示中的逆时针方向进行。一旦进入下一步即一个新的位置，同样又要“试探下步移动”。如果本步移动成功，那么返回“真”，否则返回“假”。因此是一个递归过程try(i,x,y,q) 。 “试探下步移动”可设为try(i,x,y,q) ： 2.0 做候选准备； 2.1 repeat 2