【文章內(nèi)容簡(jiǎn)介】 有的人全部出列為止。設(shè)ｎ個(gè)人的編號(hào)分別為 1， 2，?， n，打印出出列的順序。 分析：本題我們可以用數(shù)組建立標(biāo)志位等方法求解，但如果用上數(shù)據(jù)結(jié)構(gòu)中循環(huán)鏈的思想，則更貼切題意，解題效率更高。ｎ人圍成一圈，把一人看成一個(gè)結(jié)點(diǎn)，ｎ人之間的關(guān)系采用鏈接方式，即每一結(jié)點(diǎn)有一個(gè)前繼結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)有一個(gè) 指針指向下一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)指針指向第一個(gè)結(jié)點(diǎn)。這就是單循環(huán)鏈的數(shù)據(jù)結(jié)構(gòu)。當(dāng)ｍ人出列時(shí)，將ｍ結(jié)點(diǎn)的前繼結(jié)點(diǎn)指針指向ｍ結(jié)點(diǎn)的后繼結(jié)點(diǎn)指針，即把ｍ結(jié)點(diǎn)驅(qū)出循環(huán)鏈。 建立循環(huán)鏈表。 當(dāng)用數(shù)組實(shí)現(xiàn)本題鏈?zhǔn)浇Y(jié)構(gòu)時(shí)，數(shù)組 a[i]作為 指針 變量來(lái)使用， a[i]存放下一個(gè)結(jié)點(diǎn)的位置。設(shè)立指針 j 指向當(dāng)前結(jié)點(diǎn)，則移動(dòng)結(jié)點(diǎn)過(guò)程為 j:=a[j]，當(dāng)數(shù)到 m時(shí)， m結(jié)點(diǎn)出鏈，則 a[j]:=a[a[j]]。 當(dāng)直接用鏈來(lái)實(shí)現(xiàn)時(shí)，則比較直觀，每個(gè)結(jié)點(diǎn)有兩個(gè)域：一個(gè)數(shù)值域，一個(gè)指針域，當(dāng)數(shù)到 m 時(shí)， m 出鏈，將 m 結(jié)點(diǎn)的前繼結(jié)點(diǎn)指針指向 其后繼結(jié)點(diǎn)； 設(shè)立指針，指向當(dāng)前結(jié)點(diǎn)，設(shè)立計(jì)數(shù)器，計(jì)數(shù)數(shù)到多少人； 沿鏈移動(dòng)指針，每移動(dòng)一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器值加１，當(dāng)計(jì)數(shù)器值為ｍ時(shí)，則ｍ結(jié)點(diǎn)出鏈。計(jì)數(shù)器值置為１； 重復(fù)３、直到 n 個(gè)結(jié)點(diǎn)均出鏈為止。 源程序一： 用數(shù)組實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu) program ex116a。 const n=14。m=4。{設(shè)有 10 個(gè)人 ,報(bào)到 4 的人出列 } var a:array[1..n] of integer。 i,j,k,p:integer。 begin for i:=1 to n1 do a[i]:=i+1。{建立鏈表 } a[n]:=1。j:=n。k:=1。p:=0。{第 n 人指向第 1 人 ,并置初始 } repeat j:=a[j]。k:=k+1。{報(bào)數(shù) ,計(jì)數(shù)器加 1} if k=m then {數(shù)到 m,m人出隊(duì) ,計(jì)數(shù)器置 1} begin write(a[j]:4)。p:=p+1。a[j]:=a[a[j]]。k:=1。 end until p=n。{直到 n 個(gè)人均出隊(duì)為止 } end. 源程序二： 單鏈環(huán)實(shí)現(xiàn) program ex116b。 type pointer=^node。 node=record val:integer。 link:pointer end。 var ptr,ptb:pointer。 i,j,n,m:integer。 begin readln(n,m)。 new(ptb)。ptb^.val:=1。ptr:=ptb。{申請(qǐng)第 1 個(gè)結(jié)點(diǎn) } for i:=2 to n do begin new(ptr^.link)。ptr:=ptr^.link。 {申請(qǐng)第 2 到 n 結(jié)點(diǎn) } ptr^.val:=i。 end。 ptr^.link:=ptb。j:=0。{第 n 結(jié)點(diǎn)指針指向第 1 個(gè)結(jié)點(diǎn) } repeat i:=1。 repeat {報(bào)數(shù) ,報(bào)到 m人出列 } ptr:=ptb。ptb:=ptb^.link。i:=i+1。 until i=m。 write(ptb^.val:2)。 ptb:=ptb^.link。ptr^.link:=ptb。j:=j+1。{將 m結(jié)點(diǎn)驅(qū)出鏈表 } until j=n1。{直到 n 個(gè)人均出隊(duì)為止 } writeln(ptb^.val:4) end. 例 一矩形陣列由數(shù)字 0 到 9組成 ,數(shù)字 1 到 9代表細(xì)胞 ,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞 ,求給定矩形陣列的細(xì)胞個(gè)數(shù)。如 :陣列 0234500067 1034560500 2045600671 0000000089 有 4 個(gè)細(xì)胞。 算法步驟： 1． 從文件中讀入 m*n 矩陣陣列，將其轉(zhuǎn)換為 boolean 矩陣存入 bz數(shù)組中； 2． 沿 bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個(gè)細(xì)胞； 3． 將細(xì)胞的位置入隊(duì) h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置 bz數(shù)組置為 FLASE； 4． 將 h 隊(duì)的隊(duì)頭出隊(duì)，沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置 bz數(shù)組置為 FLASE； 5． 重復(fù) 4，直至 h 隊(duì)空為止，則此時(shí)找出了一個(gè)細(xì)胞； 6． 重復(fù) 2，直至矩陣找不到細(xì)胞； 7． 輸出找到的細(xì)胞數(shù)。 program xibao。 const dx:array[1..4] of 1..1=(1,0,1,0)。 dy:array[1..4] of 1..1=(0,1,0,1)。 var int:text。 name,s:string。 pic:array[1..50,1..79] of byte。 bz:array[1..50,1..79] of boolean。 m,n,i,j,num:integer。 h:array[1..4000,1..2] of byte。 procedure doing(p,q:integer)。 var i,t,w,x,y:integer。 begin inc(num)。bz[p,q]:=false。 t:=1。w:=1。h[1,1]:=p。h[1,2]:=q。{遇到的第一個(gè)細(xì)胞入隊(duì) } repeat for i:=1 to 4 do{沿細(xì)胞的上下左右四個(gè)方向搜索細(xì)胞 } begin x:=h[t,1]+dx[i]。y:=h[t,2]+dy[i]。 if (x0) and (x=m) and (y0) and (y=n) and bz[x,y] then begin inc(w)。h[w,1]:=x。h[w,2]:=y。bz[x,y]:=false。end。{為細(xì)胞的入隊(duì) } end。 inc(t)。{隊(duì)頭指針加 1} until tw。{直至隊(duì)空為止 } end。 begin fillchar(bz,sizeof(bz),true)。num:=0。 write(39。input file:39。)。readln(name)。 assign(int,name)。reset(int)。 readln(int,m,n)。 for i:=1 to m do begin readln(int,s)。 for j:=1 to n do begin pic[i,j]:=ord(s[j])ord(39。039。)。 if pic[i,j]=0 then bz[i,j]:=false。 end。 end。 close(int)。 for i:=1 to m do for j:=1 to n do if bz[i,j] then doing(i,j)。{在矩陣中尋找細(xì)胞 } writeln(39。NUMBER of cells=39。,num)。readln。 end. （四）――迭代與遞推 本次我們想與大家共同探討一下迭代與遞推。在計(jì)算機(jī)數(shù)值程序設(shè)計(jì)中，迭代與遞推是兩個(gè) 重要的基礎(chǔ)算法。 一、迭代 許多的實(shí)際問題都能轉(zhuǎn)化為解方程 F(x)=0 的實(shí)數(shù)解的問題。求根可以直接從方程出發(fā)，逐步縮小根的存在區(qū)間，把根的近似值逐步精確到要以滿足具體實(shí)際問題的需要為止，該算法稱為迭代。迭代的一般原則可以用一個(gè)數(shù)學(xué)模型來(lái)描述，現(xiàn)要求出方程F(x)=0 的解：先設(shè) F(x)=G(x)x，則方程 F(x)=0 可化為 x=G(x)， 這就產(chǎn)生了一個(gè)迭代算法的數(shù)學(xué)模型： Ｘ n+1=Ｇ（Ｘ n） 從某一個(gè)數(shù)Ｘ 0 出發(fā)，按此迭代模型，求出一個(gè)序列： ｛Ｘ 0，Ｘ 1，Ｘ 2，Ｘ 3，??，Ｘ n2，Ｘ n1，Ｘ n｝ 當(dāng)Ｘ n－Ｘ n1 小于一個(gè)特定值（誤差許可值）時(shí)，Ｘ≈Ｘ n1≈Ｘ n，這時(shí)可認(rèn)定x=G(x)。也就是說(shuō)，求出的Ｘ n 已經(jīng)可以作為原方程 f(x)=0 根的近似值了。 設(shè)誤差許可值為 A，則迭代算法的 NS 圖如圖 1。 圖 1 迭代算法 NS 框圖 迭代算法的關(guān)鍵在于確定迭代函數(shù) G(x)。確定 G(x)時(shí)需保證產(chǎn)生的迭代序列｛Ｘ n ｝是否能使兩個(gè)相鄰的數(shù)之間的差距越來(lái)越?。磧蓴?shù)的差值越靠近誤差值，我們稱這樣的序列為收斂序列），因?yàn)橹挥羞@樣才能使根的存在范圍越來(lái)越小，從而為根的取得創(chuàng)造條件。 例 1 求 2 的算術(shù)平方根（不使用內(nèi)部函數(shù)）。 :使用迭代算法來(lái)解決這個(gè)問題，使用迭代法可以先設(shè) X=SQRT(2)1，則求 2 的算術(shù)平方根的近似值就可以轉(zhuǎn)化為求 X(X+2)=1 的正根。列出等 價(jià)方程 X=1/(X+2)， 以 1/(X+2)為迭代函數(shù)，以 0 為初始近似值Ｘ 0，誤差值設(shè)定為 ， 則程序可寫成： program ex11_7。 const a=。 var x0,x1,X:real。 begin x0:=0。x1:=1/(x0+2)。 while abs(x1x0)a do begin x0:=x1。x1:=1/(x0+2)。 end。 x:=x1+1。 {將 X1 的值轉(zhuǎn)為 2 的算術(shù)平方根 } writeln(39。sqrt(2)=39。,x)。 end. 程序的輸出結(jié)果如下： SQRT(2)=+00 開始時(shí)，迭代函數(shù)的根的近似值設(shè)定在 [0,]之間， 由于區(qū)間寬度大于給定誤差許可值，于是再進(jìn)行迭代運(yùn)算，產(chǎn)生下一個(gè)區(qū)間 [,]； 其寬度仍然大于誤差許可值，再產(chǎn)生下一個(gè)區(qū)間；??；如此反復(fù)，直到區(qū)間的寬度小于誤差給定值時(shí)，則表明在該區(qū)間中，任意選擇一個(gè)數(shù)都可以滿足根的近似值要求了。為方便起見，取下該區(qū)間的邊界置作為近似值。這就是迭代算法的一般原則的體現(xiàn)了。 二、 .遞推 對(duì)于一個(gè)的序列來(lái)說(shuō)，如果 已知它的通項(xiàng)公式（即表達(dá)位置與位置上的數(shù)據(jù)的關(guān)系的公式），那么，要求出數(shù)列中某項(xiàng)之值是十分容易的。但是，在許多情況下，要得到數(shù)列的通項(xiàng)公式是很困難的，甚至無(wú)法得到。然而，一個(gè)有規(guī)律的數(shù)列的相鄰位置上的數(shù)項(xiàng)之間通常存在著一定的關(guān)系，我們可以借助已知的項(xiàng)，利用特定的關(guān)系逐項(xiàng)推算出它的后繼項(xiàng)的值，??，如此反復(fù)，直到找到所需的那一項(xiàng)為止，這樣的方法稱為遞推算法。 遞推算法的首要問題是得到相鄰的數(shù)據(jù)項(xiàng)間的關(guān)系（即遞推關(guān)系）。遞推算法避開了求通項(xiàng)公項(xiàng)的麻煩，把一個(gè)復(fù)雜的問題的求解，分解成了連續(xù)的若干步簡(jiǎn)單運(yùn)算。一般說(shuō)來(lái)，可以將遞推算法看成是一種特殊的迭代算法。 例 2 著名的菲波納葜 (Fibonacci)數(shù)列，其第一項(xiàng)為 0，第二項(xiàng)為 1， 從第三項(xiàng)開始，其每一項(xiàng)都是前兩項(xiàng)的和。編程求出該數(shù)列第 N 項(xiàng)數(shù)據(jù)。 分析：按菲波納葜?jǐn)?shù)列的原則，數(shù)列為： 0 1 1 2 3 5 8 13 21 34 55…… 無(wú)疑地，尋找其項(xiàng)數(shù)位置與項(xiàng)值的關(guān)系（即通項(xiàng)公式）是非常困難的。而根椐該數(shù)列的形成規(guī)則，其有一個(gè)的公式即 Ｕ n＝Ｕ n1＋Ｕ n2 表明了相鄰的數(shù)據(jù)項(xiàng)之間的明顯關(guān)系。因此，可以其作為遞推公式，以已知項(xiàng) 0 與 1為起點(diǎn)，逐項(xiàng)產(chǎn)生第 3 項(xiàng)、第 4 項(xiàng)、??，直到取得需要的第 N 項(xiàng)為止。 在其遞推算法的語(yǔ)言實(shí)現(xiàn)上，可取 J、 K、 P 三個(gè)變量，分別表示前二項(xiàng)、前一項(xiàng)與當(dāng)前項(xiàng)， J、 K分別取初值 0 與 1。第一次通過(guò)遞推公式 P=J+K得到第三項(xiàng)，并進(jìn)行移位，即 J 取 K 值、 K 取 P 值， 為下次遞推作準(zhǔn)備；??；如此反復(fù)，經(jīng)過(guò) N2 次的遞推， P 就是第 N 項(xiàng)的值（第 1次產(chǎn)生的是 3 項(xiàng)的值）。 源程序如下 : program ex11_8。 var n,i,j,k,p:longint。 begin write(39。N=39。)。readln(n)。 i:=2。j:=0。k:=1。 repeat inc(i)。p:=j+k。j:=k。k:=p。 until i=n。 writeln(39。F(39。,n,39。)=39。,p)。 end. 菲波納葜?jǐn)?shù)列的遞推明確地體現(xiàn)了遞推算法程序設(shè)計(jì)的一般原則，即遞推公式取得。 例 3 數(shù)字三角形。如下所示為一個(gè)數(shù)字三角形。請(qǐng)編一個(gè)程序計(jì)算從頂?shù)降椎哪程幍囊粭l 路徑，使該路徑所經(jīng)過(guò)的數(shù)字總和最大。只要求輸出總和。 一步可沿左斜線向下或右斜線向下走； 角形行數(shù)小于等于 100； 三角形中的數(shù)字為 0， 1， ?， 99； 測(cè)試數(shù)據(jù)通過(guò)鍵盤逐行輸入，如上例數(shù)據(jù)應(yīng)以如下所示格式輸入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 分析：此題解法有多種，從遞推的思想出發(fā)，可以設(shè)想，當(dāng)從頂層沿某條路徑走到第 I 層向第 I+1 層前進(jìn)時(shí)，我們的選擇一定是沿其下兩條可行路徑中最大數(shù)字的方向前進(jìn)，為此，我們可以采用倒推的手法，設(shè) a[i， j]存放從 i， j 出發(fā)到達(dá)