鄧立波

在信息量飛速增長的現(xiàn)代社會中，如何有效地獲取和處理信息已成了信息技術教師面對的課題之一。如何有條理地分析各種問題中的有用數(shù)據(jù)，發(fā)現(xiàn)數(shù)據(jù)的變化規(guī)律，制訂相應的處理方法，構建解決整個問題的流程，也成了教師們的日常工作之一。眾所周知，計算機的特征是運算速度快、精度高，在精確的控制之下，一切都會按部就班地執(zhí)行，從而提高效率。如果我們能很好地利用計算機這個工具，那么我們就只需做個規(guī)劃者，而繁瑣的處理過程就可以留給計算機來執(zhí)行。下面我就以對一個問題的分析來說明流程控制中的多樣性。

問題描述：

設一個m*n的棋盤，在棋盤上左下角的A點（0，0）有一個中國象棋的馬，并約定馬走的規(guī)則是：①馬走日字；②馬只能向右走。任務：編程讀入m,n，請打印出一條從A（0，0）到B（m，n）的路徑。

跳馬問題也稱為騎士遍歷問題，是一道非常古老的題目了，好多人在講回溯算法時都喜歡用到這個例子，因為這是適合用回溯法解決的一個經典例子，它僅用一張平面表格就把階段、狀態(tài)、決策等因素直觀而又抽象地展現(xiàn)在人們面前。但我們不希望僅以一道或幾道經典題目，讓學生掌握一種算法，而是從不同的角度、方向來分析當前這種變化規(guī)則，找到適合的方法來處理目前這種變化，從而提高學生的解題適應能力。

● 回溯法適用于解決多階段決策問題中求單路徑、全路徑等

用回溯法解決跳馬問題的基本思想是從起點開始每一步先作出選擇，再判斷，再跨出到下一步，重復上述過程，每一步的跨出都會離目的地越來越近，但當?shù)讲涣四康牡貢r，回退一步，如果可以作出新的選擇，則重新跨出，否則再退，以此類推。上述過程可以借助于圖形進行模擬，讓學生先清楚整個過程。接下來便是每一步驟的語言描述及控制。其中每一步所做出的選擇必須記錄，否則回退時不能做出新的選擇。

求單路徑的流程圖如下：

參考程序：

program knight1;

const dx:array[1..4] of integer=(1,2,2,1);

dy:array[1..4] of integer=(-2,-1,1,2);

max=1000;

var x,y,m,k,i,mm,nn:integer;

b:array[0..max] of integer;

begin

write('input m,n:');

readln(mm,nn);

x:=0;y:=0;

m:=0;

k:=0;

for i:=0 to max do b[i]:=0;

while (x<>mm) or (y<>nn) do{目標點為(mm，nn)}

begin

k:=k+1; {找個方向}

if k>4 then begin k:=b[m]; {沒有方向可跳，則回溯}

m:=m-1;

x:=x-dx[k];

y:=y-dy[k];

end

else

if (x+dx[k]<=mm) or (y+dy[k]>=0) or (y+dy[k]<=nn) then

begin {繼續(xù)往下跳}

m:=m+1;

b[m]:=k;

k:=0;

end;

end;

for i:=1 to m do write(b[i]:9);{輸出每步的方向}

writeln;

x:=0;y:=0; {輸出路徑}

write('(0,0)--->');

for i:=1 to m do

begin

x:=x+dx[b[i]];

y:=y+dy[b[i]];

if i<>m then write('(',x,',',y,')','--->')

else writeln('(',x,',',y,')');

end;

readln;

end.

以上是求從起點到終點的一條路徑，這是一種能深入先深入，否則回退，換條路走的思維方式，即深度優(yōu)先搜索。但能否把所有路徑都打印出來呢？引導學生繼續(xù)思考。也就是一條路徑找到后，不能結束，要繼續(xù)找下一條路徑，因此結束條件要更改。觀察B數(shù)組的變化規(guī)則，只能當所有路徑找全后，也就是數(shù)組B的每一位都為最大值，才能讓程序結束，這是一種記數(shù)現(xiàn)象，但要判斷每一位是否達到最大值較繁瑣，我們再加一，也就是第一位的前一位發(fā)生變化，因此采用0位做標記位，初始化為0，當為1時結束。但調試程序后發(fā)現(xiàn)有201錯誤，也就是數(shù)組超界情況。仔細觀察發(fā)現(xiàn)當回退到B數(shù)組的0位時，K的值為0，也就是會發(fā)生dx[0]，dy[0]的現(xiàn)象，根據(jù)現(xiàn)象采用兩種不同的控制方式：①加判斷語句，當K為0時不做x:=x-dx[k]，y:=y-dy[k]；②當K為0時，用BREAK結束程序。

● 用遞歸思想解決問題

在用回溯法分析這個問題之后，學生對跳馬問題的解題思路已經有了一定的了解，那我們還可以讓學生用遞歸的思想來分析這個問題。也就是從問題的規(guī)模出發(fā)，不同規(guī)模的問題解決方案是否一致，能否找到大規(guī)模問題與小規(guī)模問題（子問題）間的關系，并建立遞歸模型。本題在每一步上存在四種選擇，如果選擇合適（不超界），則離終點近了一步，問題規(guī)模變小，但解決子問題的方法與原問題一致。

參考程序：

program ex(input,output);

const dx:array [1..4] of integer=(1,2,2,1);

dy:array [1..4] of integer=(-2,-1,1,2);

var

m,n,c:integer;

procedure cs(x,y:integer);

var

i:integer;

begin

if (x=m) and (y=n) then c:=c+1

else for i:=1 to 4 do

if (x+dx[i]<=m) and (y+dy[i]<=n) and (y+dy[i]>=0) then

cs(x+dx[i],y+dy[i]);

end;

begin

c:=0;

read(m,n);

cs(0,0);

writeln(c);

end.

以上是從起點出發(fā)編寫的遞歸程序。如何從終點開始尋找遞歸關系、編寫程序，大家可自行嘗試。

而如果要求到終點的所有路徑是多少，是否一定要用上述方法求出所有路徑，然后統(tǒng)計呢？仔細觀察，可以發(fā)現(xiàn)本問題步驟性強，馬跳的方向很明顯，前后結果有著必然的聯(lián)系。用遞歸思想很容易找到總數(shù)量與子問題之間的關系，即如果能把到達終點前各點的方案數(shù)計算清楚，則終點的方案數(shù)為馬從終點回退一步能到的點的方案數(shù)之和。得出遞歸關系式：

邊界條件為f(1,1)=1

注意：m為寬，n為高，它們的值不能超出棋盤范圍，可把第一列初始化為0，然后采用記憶方式求解。

找到遞歸關系，用遞推很容易地求出了起點到終點的總方案數(shù)。那么在此基礎上能否找到起點到終點的路徑呢？可再引導學生思考。此時如果從終點回退，而回退到的點有具體數(shù)值，也就是說，馬能從起點跳到剛才那一點，記載那一點的坐標。以此類推，把馬從終點退到起點的坐標都記載下來，就形成了一條通路。從這里可以看到，遞推也可以用到尋找路徑。

根據(jù)一個問題的本質進行多方面、多角度思考，一方面可以更加清晰地認識到問題的本質，另一方面也可以鍛煉思維能力。一題多解，從多種方案中總結出較好的方法，這種思維方式，不管是對問題的全局還是局部，都可以提高對問題的理解和解決，從而方便對過程的控制。