算法设计中的变量跟踪实验
2017-12-07王爱胜
在算法设计学习中，对于一些经典的算法首先需要的是学习、理解，然后才是应用。原因是，一方面，这些经典的算法比较复杂，不学习基础理论是很难自行设计出代码的，尤其是很多算法都获得过大奖，确非常人所能原创；另一方面，学习经典算法本身就是对计算思维的一种高端认知，是对程序设计语言的一种综合应用体验。由于较为高级的经典算法如递归、搜索等多在高中信息技术课程的选修课程中出现，而目前的信息学奥赛是对开设这类选修课的一种补充，对选修课的课程内涵与教育效应具有较强的放大作用，因此，笔者借鉴基于奥赛水平的经典算法认知过程，探索如何利用变量跟踪算法设计实验认知算法的内涵本质及真实过程。
实验方法与目的
基础实验：以利用变量跟踪认知“广度优先搜索”为例，进行实验指导，并根据数据访问顺序、结果，对应迷宫数阵进行跟踪，最后参照实验数据进行访问过程的推演，以理解广度优先搜索算法的内涵本质。
拓展实验：对上述做法做进一步深化、拓展变量跟踪实验，对深度优先算法进行结点数据的跟踪，依据实验数据进行算法内涵本质的推演。通过对比，对广度优先搜索与深度优先搜索的算法思想、程序代码产生更明确的区分、理解。
实验引言
根据定义，我们可知，广度优先搜索的方法是：从根结点开始，逐步把所有的子结点全部访问之后，再继续访问下一层结点的所有子结点，就像清扫一个个战场，把阵线逐步往前推进。
笔者以C++语言程序的“走迷宫”为例，进行变量跟踪实验。
实验准备
（1）定义方向数组fx[]和走过判断数组string zouguo[]。
string fx[]={"上"，"右"，"下"，"左"}； //显示方向
string zouguo[]={"没走过"，"走过"}； //显示走过与否
（2）准备迷宫数阵等实验原始数据。用纯文本文件migong.in存储如下数阵，第1行表示4行4列矩阵，第2行表示起点坐标，第3行表示终点坐标，以下是迷宫数阵。
4 4
1 1
4 4
0 0 0 1
1 0 1 0
0 0 0 1
1 0 0 0
（3）准备经典算法的源程序（参见下文，不包含跟踪点代码）。
实验过程
根据算法含义，寻找跟踪点，实验中要预先删除以下跟踪点代码指导学生重新编写插入。
//走迷宫：广度搜索
#include
#include
#include
using namespace std；
struct note { //自定义结构体，为访问结点存储坐标、步数
int x； int y； int s； }；
int main（） { //主程序
freopen（"migong.in"，"r"，stdin）； //设置读取文件，获得实验源数据
freopen（"migong.out"，"w"，stdout）； //设置输出文件，存储实验结果
struct note fwd[5000]； //定义存储访问点的数组
int a[100][100]={0}，book[100][100]={0}； //定义存储数阵与访问标记数组
//@跟踪实验设计，以下@说明的代码需要在实验中自行设计、插入、分析
string fx[]={"上"，"右"，"下"，"左"}； //显示方向
string zouguo[]={"没走过"，"走过"}； //显示走过与否
//定义一个用于表示走的方向的数组
int next[4][2]={ {-1，0}，{0，1}， {1，0}，{0，-1} }；
int k，n，m，tx，ty，flag； //定义使用变量
int startx，starty，endx，endy； //定义开始点、结束点变量
cin>>n>>m； //读入矩阵行列数
cin>>startx>>starty； //读入起点坐标
cin>>endx>>endy； //读入终点坐标
for （int i=1；i<=n；i++） //读入迷宫数阵
for（int j=1；j<=m；j++）
cin>>a[i][j]；
//对存储访问结点的队列初始化
int head，tail； //定义对列首尾
head=1； //队列首
tail=1； //队列尾
//往队列存储走迷宫的起点坐标
fwd[tail].x=startx；
fwd[tail].y=starty；
fwd[tail].s=0； //步数开始為0
tail++； //尾后移
book[startx][starty]=1； //起点已访问，作标记
flag=0；//用来标记是否到达目标点，0表示暂时没有到达，1表示到达
while （head //@跟踪点：显示队首及开始搜索的新起点位置、值等。
