跳馬問題中存在的多種算法思想

鄧立波

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

問題描述：

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

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

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

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

求單路徑的流程圖如下：

參考程序：

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{目標(biāo)點(diǎn)為(mm，nn)}

begin

k:=k+1; {找個(gè)方向}

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.

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

● 用遞歸思想解決問題

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

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

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

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

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

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

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