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

實驗方法與目的

基礎(chǔ)實驗：以利用變量跟蹤認(rèn)知“廣度優(yōu)先搜索”為例，進行實驗指導(dǎo)，并根據(jù)數(shù)據(jù)訪問順序、結(jié)果，對應(yīng)迷宮數(shù)陣進行跟蹤，最后參照實驗數(shù)據(jù)進行訪問過程的推演，以理解廣度優(yōu)先搜索算法的內(nèi)涵本質(zhì)。

拓展實驗：對上述做法做進一步深化、拓展變量跟蹤實驗，對深度優(yōu)先算法進行結(jié)點數(shù)據(jù)的跟蹤，依據(jù)實驗數(shù)據(jù)進行算法內(nèi)涵本質(zhì)的推演。通過對比，對廣度優(yōu)先搜索與深度優(yōu)先搜索的算法思想、程序代碼產(chǎn)生更明確的區(qū)分、理解。

實驗引言

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

筆者以C++語言程序的“走迷宮”為例，進行變量跟蹤實驗。

實驗準(zhǔn)備

（1）定義方向數(shù)組fx[]和走過判斷數(shù)組string zouguo[]。

string fx[]={"上"，"右"，"下"，"左"}； //顯示方向

string zouguo[]={"沒走過"，"走過"}； //顯示走過與否

（2）準(zhǔn)備迷宮數(shù)陣等實驗原始數(shù)據(jù)。用純文本文件migong.in存儲如下數(shù)陣，第1行表示4行4列矩陣，第2行表示起點坐標(biāo)，第3行表示終點坐標(biāo)，以下是迷宮數(shù)陣。

4 4

1 1

4 4

0 0 0 1

1 0 1 0

0 0 0 1

1 0 0 0

（3）準(zhǔn)備經(jīng)典算法的源程序（參見下文，不包含跟蹤點代碼）。

實驗過程

根據(jù)算法含義，尋找跟蹤點，實驗中要預(yù)先刪除以下跟蹤點代碼指導(dǎo)學(xué)生重新編寫插入。

//走迷宮：廣度搜索

#include

#include

#include

using namespace std；

struct note { //自定義結(jié)構(gòu)體，為訪問結(jié)點存儲坐標(biāo)、步數(shù)

int x； int y； int s； }；

int main（） { //主程序

freopen（"migong.in"，"r"，stdin）； //設(shè)置讀取文件，獲得實驗源數(shù)據(jù)

freopen（"migong.out"，"w"，stdout）； //設(shè)置輸出文件，存儲實驗結(jié)果

struct note fwd[5000]； //定義存儲訪問點的數(shù)組

int a[100][100]={0}，book[100][100]={0}； //定義存儲數(shù)陣與訪問標(biāo)記數(shù)組

//@跟蹤實驗設(shè)計，以下@說明的代碼需要在實驗中自行設(shè)計、插入、分析

string fx[]={"上"，"右"，"下"，"左"}； //顯示方向

string zouguo[]={"沒走過"，"走過"}； //顯示走過與否

//定義一個用于表示走的方向的數(shù)組

int next[4][2]={ {-1，0}，{0，1}， {1，0}，{0，-1} }；

int k，n，m，tx，ty，flag； //定義使用變量

int startx，starty，endx，endy； //定義開始點、結(jié)束點變量

cin>>n>>m； //讀入矩陣行列數(shù)

cin>>startx>>starty； //讀入起點坐標(biāo)

cin>>endx>>endy； //讀入終點坐標(biāo)

for （int i=1；i<=n；i++） //讀入迷宮數(shù)陣

for（int j=1；j<=m；j++）

cin>>a[i][j]；

//對存儲訪問結(jié)點的隊列初始化

int head，tail； //定義對列首尾

head=1； //隊列首

tail=1； //隊列尾

//往隊列存儲走迷宮的起點坐標(biāo)

fwd[tail].x=startx；

fwd[tail].y=starty；

fwd[tail].s=0； //步數(shù)開始為0

tail++； //尾后移

book[startx][starty]=1； //起點已訪問，作標(biāo)記

flag=0；//用來標(biāo)記是否到達目標(biāo)點，0表示暫時沒有到達，1表示到達

while （head

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

cout<

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