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