【文章內(nèi)容簡介】 。從圖中可以看出，從城市 A到城市 H要經(jīng)過若干個城市。求出一 條經(jīng)過城市最少的一條路線。 12 圖 8 看到圖 8 很容易想到用鄰接距陣來表示， 0 表示能走， 1 表示不能走。如圖 9： 圖 9 用隊(duì)來解題，我們可以 a 記錄搜索過程， 記錄經(jīng)過的城市， 記錄前趨元素，這樣就可以倒推出最短線路。具體過程如下 將城市 A入隊(duì)，隊(duì)首、隊(duì)尾都為 1。 將隊(duì)首所指的城市所有可直通的城 市入隊(duì)（如果這個城市在隊(duì)中出現(xiàn)過就不入隊(duì)，可用一個集合來判斷），將入隊(duì)城市的 pre指向隊(duì)首的位置。然后將隊(duì)首加 1，得到新的隊(duì)首城市。重復(fù)以上步驟，直到城市 H 入隊(duì)為止。當(dāng)搜到城市 H 時，搜索結(jié)束。利用 pre 可倒推出最少城市線路。 PASCAL 源程序： const ju:array[1..8,1..8] of 0..1=( (1,0,0,0,1,0,1,1),(0,1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,1,1,0), (1,1,1,1,0,0,0,1))。 type r=record {記錄定義 } city:array[1..100] of char。 pre:array[1..100] of integer。 end。 var h,d,i:integer。a:r。s:set of 39。A39。..39。H39。 procedure out。 {輸出過程 } begin write([d])。 repeat d:=[d]。 write(39。39。,[d])。 until [d]=0。 13 writeln。 halt。 end。 procedure doit。 begin h:=0。 d:=1。 [1]:=39。A39。 [1]:=0。 s:=[39。A39。]。 repeat {步驟 2} inc(h)。 {隊(duì)首加一，出隊(duì) } for i:=1 to 8 do {搜索可直通的城市 } if （ ju[ord([h])64,i]=0） and （ not（ chr（ i+64） in s）） then {判斷城市是否走過 } begin inc(d)。 {隊(duì)尾加一，入隊(duì) } [d]:=chr(64+i)。 [d]:=h。 s:=s+[[d]]。 if [d]=39。H39。 then out。 end。 until h=d。 end。 begin {主程序 } doit。 end. 輸出： HF—A 通過數(shù)學(xué)方式重新審題 有些問題有很多精妙的數(shù)學(xué)解法，選手可以從數(shù)據(jù)角度（多角度）審題，如能歸納出數(shù)學(xué)公式解題，效率和準(zhǔn)確性會有很大的提高。 例如前文提到的一題： 計算從 1開始的前 100個自然數(shù)的和”的算法。 運(yùn)用圖 4 所列出的公式（ S 的值來源于等差數(shù)列，用求等差級數(shù)前 N 項(xiàng)和的公式），可以輕松求解。這種方法只需做一次加法和二次乘法，所以數(shù)學(xué)公式算法比其它算法運(yùn)算量小，效率高。 再如：“?！币活}（問題略，可參見 2020 年普及組復(fù)賽試題三） 此題可以用動態(tài)規(guī)劃求解，但在審題中，我們分析出：若設(shè) 入棧為 1，出棧為 0（不入棧為 10），對于任意一種方案，與 2n 位的 01 序列一一對應(yīng)（在前任意位， 1的個數(shù)總是大于等于 0的個數(shù)）。可以證明，在 2 的 0 任意排列中，不符合要求的個數(shù)為： ，則可產(chǎn)生出的序列數(shù)： ，即為 n 的 Catalan 數(shù)。 14 選手寫階乘的程序比較容易， PASCAL 程序如下： program stacks。 var n,m:longint。 function jc(n:integer):longint。 var i,s:longint。 begin s:=1。 for i:=1 to n do s:=s*i。 jc:=s。 end。 function jm(n,m:integer):real。 begin jm:=jc(n)/(jc(m)*jc(nm))。 end。 begin write(39。input n:39。)。 readln(n)。 writeln(jm(2*n,n)/(n+1))。 readln end. （二）建模 運(yùn)用已經(jīng)掌握的知識，快速與命題建立聯(lián)系 窮舉法是常用的算法， 窮舉是窮舉出所有可 能滿足題意的情形，并從中找出符合要求的解，是最直觀的循環(huán)算法。 在講解 LOGO、 BASIC、 PASCAL 語言中都要講到，這個基礎(chǔ)算法可以被選手熟練掌握，當(dāng)遇到類似問題時，就會很容易產(chǎn)生聯(lián)系，便于建立模型。 如窮舉法的經(jīng)典例題，百雞百錢問題：用 100錢買 100只雞。其中母雞 5 錢一只，公雞 3 錢一只，小雞 1 錢三只，試編程求可買母雞、公雞、小雞各多少只？ LOGO 語言源程序： TO B FOR X 0 20[FOR Y 0 33[FOR Z 0 100 [ IF AND :X+:Y+:Z=100 5*:X+3*:Y+:Z/3=100 THEN (PR :X :Y :Z)]] ] END 這個模型在此不再贅述，當(dāng)選手在遇到類似的結(jié)構(gòu)描述時，就會很快建立解題的模型，如： 找出 n個自然數(shù) (1,2,3,? ,n)中 r個數(shù)的組合。例如，當(dāng) n=５ ,r=3時，所有組合為 ： ５ ４ ３ ５ ４ ２ ５ ４ １ ５ ３ ２ ５ ３ １ ５ ２ １ ４ ３ ２ ４ ３ １ 15 ４ ２ １ ３ ２ １ total=10 {組合的總數(shù) } 此題中， n 個數(shù)中 r 的組合，其中每 r 個數(shù)中，數(shù)不能相同。另外，任何兩組組合的數(shù)，所包含的數(shù)也不應(yīng)相同。例如，５、４、３與３、４、５。為此，約定前一個數(shù)應(yīng)大于后一個數(shù)。 將上述兩 條不允許為條件，當(dāng) r=3時，因?yàn)橛星懊?百雞百錢的知識，選手比較容易建立模型，即 三重循環(huán)進(jìn)行窮舉： PASCAL 程序： program qje。 const n=5。 var i,j,k,t:integer。 begin t:=0。 for i:=n downto 1 do for j:=n downto 1 do for k:=n downto 1 do if (ij)and(ik)and(ij)and(jk) then begin t:=t+1。writeln(i:3,j:3,k:3)。end。 writeln(39。total=39。,t)。 end. 所以，對于經(jīng)典例題的模型的輔導(dǎo)是比較重要的，是學(xué)生建模的知識積累。 根據(jù)運(yùn)算量及數(shù)據(jù)范圍，確定存儲結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu) PASCAL 語言解題的過程之前一定要進(jìn)行數(shù)據(jù)的存儲，良好的存儲結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)是建模的基礎(chǔ)，好的數(shù) 據(jù)結(jié)構(gòu)是成功求解的關(guān)鍵。 如回溯算法是所有搜索算法中最為基本的一種算法，其采用了一種“走不通就掉頭”思想作為其控制結(jié)構(gòu)， 其相當(dāng)于采用了先根遍歷的方法來構(gòu)造解答樹，可用于找解或所有解以及最優(yōu)解。具體的算法描述如下： 非遞歸算法： Type Node(節(jié)點(diǎn)類型 )＝ Record Situtation:TSituation（當(dāng)前節(jié)點(diǎn)狀態(tài)） 。 WayNO:Integer（已使用過的擴(kuò)展規(guī)則的數(shù)目） 。 End Var List(回溯表 ):Array[1..Max(最大深 度 )] of Node。 pos(當(dāng)前擴(kuò)展節(jié)點(diǎn)編號 ):Integer。 Init List0。 pos1。 List[1].Situation初始狀態(tài) 。 Main Program While (pos0(有路可走 )) and ([未達(dá)到目標(biāo) ]) do Begin If pos=Max then (數(shù)據(jù)溢出 ,跳出主程序 )。 List[pos].WayNO:=List[pos].WayNo+1。 If (List[pos].WayNO=TotalExpendMethod) then (如果還有沒用過的擴(kuò)展規(guī)則 ) Begin 16 If (可以使用當(dāng)前擴(kuò)展規(guī)則 ) then Begin (用第 way 條規(guī)則擴(kuò)展當(dāng)前節(jié)點(diǎn) ) List[pos+1].Situation:=ExpendNode(List[pos].Situation, List[pos].WayNO)。 List[pos+1].WayNO:=0。 pos:=pos+1。 EndIf。 EndIf Else Begin pos:=pos1。 EndElse EndWhile。 遞歸算法： Procedure BackTrack(Situation:TSituation。deepth:Integer)。 Var I :Integer。 Begin If deepthMax then (空間達(dá)到極限 ,跳出本過程 )。 If Situation=Target then (找到目標(biāo) )。 For I:=1 to TotalExpendMethod do Begin BackTrack(ExpendNode(Situation,I),deepth+1)。 EndFor。 End。 回溯算法對空間的消耗較少，當(dāng)其與分枝定界法一起使用時，對于所求解在解答樹中層次較深的問題有較好的效果。如八皇后問題： 問題描述： 求出在一個 nn的棋盤上，放置 n個不能互相捕捉的 “皇后 ”的所有布局。 算法分析 ： 這是來源于國際象棋的一個問題。皇后可以前、后、左、右和沿著對角線方向相互捕捉。 一個合適的解應(yīng)是在每列、每行確實(shí)有一個皇后，且在一條對角線上最多只有一個皇后。 在寫程序之前，設(shè)定表示棋盤的數(shù)據(jù)結(jié)構(gòu)是一個 n n 數(shù)組。每一個位置代表棋盤上的一個方格。然而考慮到一個合理的解中每列、每行只能放置一個皇后，棋盤也可用一個一維數(shù)組來表示。數(shù)組的每一個元素代表棋盤的一列，該元素的值是皇后在該列上的行位置。 為找到一個解，必須從空布局開始，每放置一個皇后要檢查布局是否合理。在合理的情況下，試探找下一個皇后的位置；如果布局不合理，就改變布局。重復(fù)檢查、試探或檢查、改變位置，直到找到最后一個皇后的合理位置 ，這時就找到一個合理的布局。重復(fù)以上過程直到無法再改變皇后位置為止，就可找到所有合理的布局。 PASCAL 的源程序?yàn)椋? program j。 const n=8。 var x:array [1..100] of integer。 cont:integer。 17 procedure print。 var i:integer。 begin cont:=cont+1。 for i:=1 to n do write(x[i])。 writeln(39。S:39。,cont)。 end。 function try(i,k:integer):boolean。 var j:integer。 begin j:=1。 while jk do begin if(x[j]=i)or(abs(x[j]i)=abs(jk)) then begin try:=false。 exit end。 j:=j+1。 end。 try:=true。 end。 procedure place(k:integer)。 var i:integer。 begin if kn then print else for i:=1 to n do if try(i,k) then begin x[k]:=i。place(k+1)。 end