算法設(shè)計(jì)中的變量跟蹤實(shí)驗(yàn)

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

實(shí)驗(yàn)方法與目的

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

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

實(shí)驗(yàn)引言

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

筆者以C++語(yǔ)言程序的“走迷宮”為例，進(jìn)行變量跟蹤實(shí)驗(yàn)。

實(shí)驗(yàn)準(zhǔn)備

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

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

string zouguo[]={"沒(méi)走過(guò)"，"走過(guò)"}； //顯示走過(guò)與否

（2）準(zhǔn)備迷宮數(shù)陣等實(shí)驗(yàn)原始數(shù)據(jù)。用純文本文件migong.in存儲(chǔ)如下數(shù)陣，第1行表示4行4列矩陣，第2行表示起點(diǎn)坐標(biāo)，第3行表示終點(diǎn)坐標(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)典算法的源程序（參見下文，不包含跟蹤點(diǎn)代碼）。

實(shí)驗(yàn)過(guò)程

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

//走迷宮：廣度搜索

#include

#include

#include

using namespace std；

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

int x； int y； int s； }；

int main（） { //主程序

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

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

struct note fwd[5000]； //定義存儲(chǔ)訪問(wèn)點(diǎn)的數(shù)組

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

//@跟蹤實(shí)驗(yàn)設(shè)計(jì)，以下@說(shuō)明的代碼需要在實(shí)驗(yàn)中自行設(shè)計(jì)、插入、分析

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

string zouguo[]={"沒(méi)走過(guò)"，"走過(guò)"}； //顯示走過(guò)與否

//定義一個(gè)用于表示走的方向的數(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； //定義開始點(diǎn)、結(jié)束點(diǎn)變量

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

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

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

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

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

cin>>a[i][j]；

//對(duì)存儲(chǔ)訪問(wèn)結(jié)點(diǎn)的隊(duì)列初始化

int head，tail； //定義對(duì)列首尾

head=1； //隊(duì)列首

tail=1； //隊(duì)列尾

//往隊(duì)列存儲(chǔ)走迷宮的起點(diǎn)坐標(biāo)

fwd[tail].x=startx；

fwd[tail].y=starty；

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

tail++； //尾后移

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

flag=0；//用來(lái)標(biāo)記是否到達(dá)目標(biāo)點(diǎn)，0表示暫時(shí)沒(méi)有到達(dá)，1表示到達(dá)

while （head

//@跟蹤點(diǎn)：顯示隊(duì)首及開始搜索的新起點(diǎn)位置、值等。

cout<

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