算法設計中的變量跟蹤實驗

在算法設計學習中，對于一些經典的算法首先需要的是學習、理解，然后才是應用。原因是，一方面，這些經典的算法比較復雜，不學習基礎理論是很難自行設計出代碼的，尤其是很多算法都獲得過大獎，確非常人所能原創；另一方面，學習經典算法本身就是對計算思維的一種高端認知，是對程序設計語言的一種綜合應用體驗。由于較為高級的經典算法如遞歸、搜索等多在高中信息技術課程的選修課程中出現，而目前的信息學奧賽是對開設這類選修課的一種補充，對選修課的課程內涵與教育效應具有較強的放大作用，因此，筆者借鑒基于奧賽水平的經典算法認知過程，探索如何利用變量跟蹤算法設計實驗認知算法的內涵本質及真實過程。

實驗方法與目的

基礎實驗：以利用變量跟蹤認知“廣度優先搜索”為例，進行實驗指導，并根據數據訪問順序、結果，對應迷宮數陣進行跟蹤，最后參照實驗數據進行訪問過程的推演，以理解廣度優先搜索算法的內涵本質。

拓展實驗：對上述做法做進一步深化、拓展變量跟蹤實驗，對深度優先算法進行結點數據的跟蹤，依據實驗數據進行算法內涵本質的推演。通過對比，對廣度優先搜索與深度優先搜索的算法思想、程序代碼產生更明確的區分、理解。

實驗引言

根據定義，我們可知，廣度優先搜索的方法是：從根結點開始，逐步把所有的子結點全部訪問之后，再繼續訪問下一層結點的所有子結點，就像清掃一個個戰場，把陣線逐步往前推進。

筆者以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

//@跟蹤點：顯示隊首及開始搜索的新起點位置、值等。

cout<

cout<<"head位置："< 1 [2] 存入我的閱覽室