算法與數(shù)據(jù)結構綜合應用典型競賽試題分析長安教

算法與數(shù)據(jù)結構綜合應用——典型競賽試題分析一、數(shù)值計算問題：1、 打印所有的“水仙花數(shù)”，所謂“水仙花數(shù)”是指一個三位數(shù)，其各位數(shù)字立方和等于該數(shù)字本身，例2、一個數(shù)如果恰好等于它的因子之和，這個數(shù)就稱為"完數(shù)”。例如：6的因子為1、2、3,而6=1+2+3,因此6是''完數(shù)”。編程序找出1000以內(nèi)的所有完數(shù)。3、 有一分數(shù)序列：求出這個數(shù)列的前20項的和。(32.660259)4、 求之值，其中a是一個數(shù)字。例如：(當n=5時，n由鍵盤輸入。5、 已知四位數(shù)3025有一個待殊性質：它的前兩位數(shù)字30和后兩位數(shù)字25的和是55,而55的平方剛好等于該數(shù)(552=3025)。試編一程序打印具有這種性質的所有四位數(shù)。分析：從32至99之間的數(shù)的平方是四位數(shù)，滿足題目條件的數(shù)必須在這些四位數(shù)之內(nèi)選擇。分別把它們按前兩位數(shù)后兩位數(shù)進行分離，驗證分離后的兩個兩位數(shù)之和的平方是否等于分離前的那個四位數(shù)，若等 于即打印輸出，否則放棄。6、 求兩個自然數(shù)，其和是667,最小公倍數(shù)與最大公約數(shù)之比是 120：lo(例如：115,552)迭代法例題：用二分法求方程在區(qū)間(0,3)之間的一個解。算法提示：二分法是用計算機求解多項式方程的一中常用方法?；舅枷胧牵海绻偷姆栂喾?，那么在(xl,x2)之間一定存在一個數(shù)使f(x)=0即方程的一個解。取xl,x2的中點r,如果f(r)與f(xl)異號，解肯定在(xl.r)之間，否則解在(r,x2)之間，重復直到|f(r)|〈eO,e0是一個很小的數(shù),通過這種方法能夠求出，方程f(x)=O的一個近似解r,誤差在e0內(nèi)。窮舉搜索法窮舉法也叫枚舉法，它的基本思想是依題目的部分條件確定答案的大致范圍，在此范圍內(nèi)對所有可能的情 況逐一驗證，直到全部情況驗證完。若某個情況經(jīng)驗證符合題目的全部條件，則為本題的一個答案。若全部 情況經(jīng)驗證后都不符合題目的全部條件，則本題無答案。用窮舉法解題時，答案所在的范圍總是要求是有限的，怎樣才能使我們不重復的、一個不漏、一個不增的 逐個列舉答案所在范圍的所有情況，就是本節(jié)所講的“列舉方法”。列舉方法按答案的數(shù)據(jù)類型，常用的有下面三種。順序列舉：順序列舉是指答案范圍內(nèi)的各種情況很容易與自然數(shù)對應甚至就是自然數(shù)，可以按自然數(shù)的變化順序去列舉。排列列舉：有時答案的數(shù)據(jù)形式是一組數(shù)的排列,列舉出所有答案所在范圍內(nèi)的排列，稱為排列列舉。組合列舉：(參考組合數(shù)學知識)當答案的數(shù)據(jù)形式為一些元素的組合時，往往需要用組合列舉。從幾個不同的元素中任取m(mn)個元素組成的一組，就叫做從 n個元素取m個元素的一個組合。組合是無序的， 女口：123,132,321,312,213,231 是同一個組合(但是6個不同的排列)。例題：【問題提出】找出n個自然數(shù)(1,2,3,4,...n) 屮r個數(shù)的組合。例如n=3,r=2,所有的組合為：12,13,23；n=5,r=3,所有的情況為：123,124,125,134,135,145,234,235,245,345 ?！舅惴ā慨攔=3時用3重循環(huán)實現(xiàn)。for1=5tolforj=5tolfork=5to1ifIOjANDI!=kANDjOKANDI>jANDj>kprintI,j,k練習：1、求出具有下列兩個性質的最小自然數(shù) n：、n是個6位數(shù)、若將n的各位數(shù)移到其余各位之前，所得的新數(shù)是 n的4倍。遞推法：例題：運動會連續(xù)開了n天，一共發(fā)了m枚獎章，第一天發(fā)1枚并剩下(m-1)枚的1/7,第二天發(fā)2枚并剩下的1/7,以后每天按規(guī)律發(fā)放獎章，在最后一天即第n天發(fā)剩下的n枚獎章。問運動會一共開了多少天？一共發(fā)了幾枚獎章？貪心算法一、算法思想貪心法的基本思路：—從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某算法中的某 一步不能再繼續(xù)前進時，算法停止。該算法存在問題：不能保證求得的最后解是最佳的；不能用來求最大或最小解問題；只能求滿足某些約束條件的可行解的范圍。實現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while能朝給定總13標前進一步do求出可行解的一個解元素；由所有解元素組合成問題的一個可行解；二、 例題分析1、［背包問題］有一個背包，背包容量是 M=150o有7個物品，物品可以分割成任意大小。 要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。物品：ABCDEFG重量：35306050401025價值：10403050354030分析：目標函數(shù)：工pi最大約束條件是裝入的物品總重量不超過背包容量：Swi<=M(M=150)(1)根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優(yōu)(2)每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？每次選取單位容量價值最大的物品，成為解本題的策略。簡單背包問題解.[問題描述]背包是一個簡單的遞歸問題，要求是從n件物品中抽取幾件,使之質量一定?該程序只求一組輸入：[KEYBOARD]輸岀:解.1012345678912951234545234NOANSWER![問題分析]使用遞歸算法完成.每件物品只有放入，不放入兩種情況 .programknapProg;constm二5;varitem:array[1..m]ofinteger;w:integer;functionknap(a,b:integer):boolean;beginifitem[a]=bthenbeginknap:=true;write(item[a]:8);exit;end;if((item[a]>b)and(a=m))thenbeginknap:=false;exit;end;ifknap(a+1,b-item[a])thenbeginknap:=true;write(item[a]:8);exit;end;ifnotknap(a+1,b)thenknap: 二false;end;beginwriteln('Pleaseinputitemweights:');fori:二1tomdoread(item[i]);writeln('Totalweight:');readln(w);writeln;ifnotknap(1,w)thenwritein CNOANSWER!!');readln;end.2、 [單源最短路徑]一個有向圖G,它的每條邊都有一個非負的權值c[i,j],"路徑長度"就是所經(jīng)過的所有邊的權值之和。對于源點需要找出從源點出發(fā)到達其他所有結點的最短路徑。E.Dijkstra發(fā)明的貪婪算法可以解決最短路徑問題。算法的主要思想是：分步求出最短路徑，每一步產(chǎn)生一個到達新目的頂點的最短路徑。下一步所能達到的目的頂點通過如下貪婪準則選?。涸谖串a(chǎn)生最短路徑的頂點中，選擇路徑最短的目的頂點。設置頂點集合S并不斷作貪心選擇來擴充這個集合。當且僅當頂點到該頂點的最短路徑已知時該頂點屬于集合S。初始時S中只含源。設u為G中一頂點，我們把從源點到 u且中間僅經(jīng)過集合S中的頂點的路稱為從源到u特殊路徑，并把這個特TOC\o"1-5"\h\z殊路徑記錄下來(例如程序中的dist[i,j]) 。每次從V-S選出具有最短特殊路徑長度的頂點u,將u添加到S中，同時對特殊路徑長度進行必要的修改。一旦V=S,就得到從源到其他所有頂點的最短路徑，也就得到問題的解。3、[機器調(diào)度]現(xiàn)有N項任務和無限多臺機器。任務可以在機器上處理。每件任務開始時間和完成時間有 下表：任務_a_b_c_d_e_f_g開始(si)-O-3-4-9-7-1-6完成(fi)-2-7-7-ll-10-5-8在可行分配屮每臺機器在任何時刻最多處理一個任務。最優(yōu)分配是指使用的機器最少的可行分配方 案。請就本題給出的條件，求出最優(yōu)分配。三、練習題：已知5個城市之間有班機傳遞郵件，目的是為了尋找一條耗油量較少的飛行路線。 5個城市的聯(lián)系網(wǎng)絡如 圖所從城市i示。圖中編號的結點表示城市，兩個城市之間的連線上的值表示班機沿該航線已行的耗油量，并假定到j和城市j到i從城市i運用貪心思想：在每一步前進的選擇上，選取相對當前城市耗油量最小的航線；圖解：若從1出發(fā)，有圖：總耗油量=141-2-5-3-4T但若路線改為:1-5-3-4-2-1,則總耗油量=13所以，這樣的貪心法并不能得出最佳解。改善方案：從所有城市出發(fā)的信心過程，求最優(yōu)的。編程：1.數(shù)據(jù)結構：城市聯(lián)系網(wǎng)絡圖的描述(圖的鄰接矩陣的描述)：constc=array[1..5,1..5]ofinteger=((0,1,2,7,5),(1,0,4,4,3),(2,4,0,1,2),(7,4,1,0,3));貪心過程：begin初始化所有城市的算途徑標志；設置出發(fā)城市V；fori:=1ton-1do{nT 個城市}begins:=UV至所有未曾到過的城市的邊集中耗油量最少的那個城市；累加耗油量；V:=s；設V城市的訪問標志；end;最后一個城市返回第一個城市，累加耗油量；end;主過程：實現(xiàn)改善方案beginfori:=ltondobegincostl:=maxint; {初始化調(diào)用貪心過程，返回本次搜索耗油量cost；ifcost<costlthen 替換；end;輸出；end.例：設計一個程序，把一個真分數(shù)表示為埃及分數(shù)之和的形式。問題分析：個分所謂埃及分數(shù)，是指分子為1的形式。古代埃及有一個非常奇怪的習慣，他們喜歡把一個分數(shù)表示為若干子為1的分數(shù)之和的形式。如，7/8=1/2+1/3+1/24。個分下面介紹其中一種算法一一貪心算法。貪心算法是由數(shù)學家菲波那契提出的，基本思想是：設某個真分數(shù)的分子為A,分母為B；把B除以A的商的整數(shù)部分加1后的值作為埃及分數(shù)的某一個分母；將A乘以C減去B作為新的A；將B乘以C作為新的B；如果A大于1且能整除B,則最后一個分母為B/A；如果A=l,則最后一個分母為B；否則轉步驟（2）。如：7/8=1/2+1/3+1/24解題步驟：變量A表示分子，變量B表示分母；C=B\A+1A=A*C-B,B=B*C打印1/C若A〉1且B/A=B\A,則C=B/A若A=l,則。=3,打印1/C轉步驟（2）。QBASIC程序清單：CLSDOINPUT"a,X";a,bLOOPUNTILa<bPRINTa;7";b;DOa=a*c—b:b二b*cPRINT〃l/〃；c;IFb/a=b\aTHENPRINT〃+l/〃；b/a:ENDIFa>1THENPRINT 〃+〃；LOOPWHILEa>1PRINT〃+l〃；bEND數(shù)的劃分的研究問題描述求把一個整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。分析我們其實可以將這題轉化一下?因為我們知道我們在劃分時只要按不下降排列就不會有重復并且每 一份都不為0.我們可以形象的把n的k-自然數(shù)剖分看作把n塊積木堆成k列，且每列的積木個數(shù)依次遞增，也就是這n塊積木被從左到右積木被堆成了 "樓梯狀比如，下圖是 10的幾種4-剖分。現(xiàn)在，我們不妨把這三個圖順時針旋轉90度，成為：對于這道題我們很容易可以想到一種狀態(tài)表示方法，即用F(I,J,K)來表示把J無序劃分成I份其中最人為K的劃分方案數(shù).那么，它就等于把 J-K無序劃分成1-1份，其中最大不超過 K的劃分方案數(shù)，狀態(tài)轉 移方程就是對應的pascal程序如下：proceduredp;vari,j,k,1:integer;beginassign(output,outputfile);rewrite(output);f：0,0,0]:=1;fori:=ltomdoforj:=itondofork:=ltojdofor1:=0tokdoinc(f[i,j,k],f[i-1,j-k,1]);fori:=1tondoinc(count,f[m,n,i]);writeln(courrt);close(output);end;但是如果我們再把上圖逆時針翻轉90度，那么其實也就等于先在最下一行各擺上一塊積木接下來也就 是把I-J塊積木放上去，并要保持樓梯狀.我們可以發(fā)現(xiàn)其實上就是把I-J無序拆分成1?K份。那么我們可以得到如下動態(tài)轉移方程proceduredp;vari,j,k:integer;beginf[0,0]:=l;fori:=1tondoforj:=1tomdoifj〈二ithenfork:二0tojdoinc(f[i,j],f[i-j,k]);assign(output,outputfile);rewrite(output);writeln(f[n,m]);close(output);end;我們還可以把上述式子繼續(xù)簡化,因為我們發(fā)現(xiàn)，其實F[I-1,J-l]=那么我們在計算F[I,J]的時候就可以只做F[I,J]=F[I-1,J-1]+F[I-J,J]—次簡單的加法運算就可以了，這樣可以大大減少時間.proceduredp;vari,j,k:integer;beginf[0,0]:=l;fori:=1tondoforj:=1tomdoifi>=jthenf[i,j]:=f[i-j,j]+f[iT,j-1];assign(output,outputfile);rewrite(output);writeIn(f[n,m]);close(output);end;其實對于這題我們還可以繼續(xù)優(yōu)化，例如用滾動數(shù)組的方法使存處空間減少，這里就不再累贅了.這里還想介紹一種更容易的做法.若用F(I,J)表示把I無序劃分成J份的方案數(shù)，則F(5,2)=({1,4},{2,3});F(6,3)=({1,1,4},{1,2,3},{2,2,2})你一定會發(fā)現(xiàn)如果把I無序劃分為J份，那么它的前幾個劃分一定等于把1-1無序劃分成J-1份每份前面加1的方案數(shù).那么后面那一部拆分方案又會等于什么呢 ?我們不妨將后面每一份中的每一個數(shù)減 1,我們會發(fā)現(xiàn)它與F(I-J,J)是一一對應的.證明如下我們將一個自然數(shù) I劃分為K份，為了避免重復，習慣于從小到大地劃分。我們將數(shù) I分為K份的方法數(shù)記作F(I,K),可知:F(I,K)=F(I-K,K)+F(IT,K-l)證明：設集合{A2為I的所有劃分方案的第一項， 0<A〈=(IDIVK), 設每一種劃分方案的以后 K-1個數(shù)為A+Dl,A+D2,A+D3—A+Dk-1,DiWDi+1,于是:D的不下降排列數(shù)即I的首項是A的不同劃分數(shù)。同理，設⑻為I-K的劃分方案的首項集合，以后的K-1個數(shù)是B+CI,B+C2-B+Ck-1,所以，

又因為：可知當A-1=B時，方案數(shù)相同，其中 A能從2取到(Idivk),而BG[1,(l-k)divk]即Be[1,(Idivk)-1], 所以，當Ae[2,Idivk] 時，方案總數(shù)是F(I-K,K)。又因為當A=1時，是F(1-1,K-l),所以：F(I,K)=F(I-K,K)+F(1-1,K-l) 成立。由此我們也可以推出與上面第三個程序一樣的狀態(tài)轉移方程 .分治策略一、算法思想任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。問題規(guī)模越小，解題所需的計算時間也越少，從而也越容易計算。想解決一個較大的問題，有時是相當困難的。分治法的思想就是，將一接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題同。找出各部分的解，然后把各部分的解組合成整個問題的解。1、解決算法實現(xiàn)的同時，需要估算算法實現(xiàn)所需時間。分治算法時間是這樣確定的：解決子問題所需總量(由子問題的個數(shù)、解決每個子問題的工作量決定)合并所有子問題所需的工作量2、 分治法是把任意大小問題盡可能地等分成兩個子問題的遞歸算法3、 分治的具體過程：begin｛開始2if問題不可分then返回問題解elsebegin從原問題中劃出含一半運算對象的子問題1;遞歸調(diào)用分治法過程，求出解 1;從原問題中劃出含另一半運算對象的子問題2；遞歸調(diào)用分治法過程，求出解 2；將解1、解2組合成整修問題的解；end;end;｛結束2二、例題分析1、[金塊問題]老板有一袋金塊(共n塊，n是2的幕(n〉=2)),將有兩名最優(yōu)秀的雇員每人得到其中的一排名第一的得到最重的那塊，排名第二的雇員得到袋子中最輕的金塊。假設有一臺比較重量的儀器，用最少的比較次數(shù)找出最重的金塊。分析：問題可以簡化為：在含 n(n是2的幕(n>=2))個元素的集合中尋找極大元和極小元。明顯的方法是逐個的進行比較查找。(一次冒泡排序)m:=a[l];fori:=2tondo案數(shù)往往個難以直相的工作塊，案數(shù)往往個難以直相的工作塊，我們希望(或者一次選擇排序)fori:=2tondoifa[p]<a[i]thenp:=i;m:=a[p];需要n-1次比較得到max,而再經(jīng)過n-2次比較得到min,共進行2*n-3次比較可以找出極大元和極小元。用分治法可以較少比較次數(shù)地解決上述問題：如果集合中只有1個元素，則它既是最大值也是最小值；如果有2個元素，則一次maxnum(i,j)一次minnum(i,j)就可以得到最大值和最小值；如果把集合分成兩個子集合，遞歸的應用這個算法分別求出兩個子集合的最大值和最小值，最后讓子集合1的最大值跟子集合2的最大值比較得到整個集合的最大值；讓子集合1的最小值跟子集合2的最小值比較得到整個集合的最小值?？傻媒忸}思想：{maxmin}if問題不可分：n二2問題的解求得(兩個元素時)：對兩元素進行比較；return;fori:=1tondiv2dob[i]:=a[i]maxmin(ndiv2,b,maxi,mini), 其中maxi和mini為解1fori:=1tondiv2dob[i]:=a[i+ndiv2]maxmin(ndiv2,b,max2,min2), 其中max2和min2為解2max:=maxnum(maxi,max2);min:=minnum(mini,min2);{maxmin}其中對函數(shù)maxnum的求精：functionmaxnum(a,b:integer):integer;beginifa>bthenmaxnum:=aelsemaxnum:=b;end;分析比較次數(shù)： 比較運算均在函數(shù) maxnum和minnum中進行，當n二2時,比較次數(shù)T(n)=l當n>2時，比較次數(shù)T(n)=2T(n/2)+2n 是2的k次幕。設n二272、 快速排序快速排序是基于分治策略的一個排序算法。按照分治法的思想分析快速排序：分解(Divide)以元素a[p]為基準元素將a[p：q-1]劃分為三段a[p：q-1],a[q]和a[q+l：r],使得a[p：q-1]中任何一個元素都小于a[q],a[q+l：r]中任何一個元素大于等于a[q],下標q在劃分中確定。遞歸求解(Conquer)通過遞歸調(diào)用快速排序算法分別對a[p:qT]和a[q+l:r]進行排序。合并(Merge)由于a[p:q-l]和a[q+l:r]的排序都是在原位置進行的，所以不必進行任何合并操作 就已經(jīng)排好序了快速排在上面三個步驟中，第一步：分解是關鍵。一次快速排序確定劃分元素的位置，具體參見排序算法序快速排3、 歸并排序歸并排序也是基于分治策略的另一個算法。歸并的思路是把兩個已經(jīng)排好序的數(shù)組合并為一個。(源程序)2—路歸并排序示例：初始值EYUKSLB一趟歸并排序TOC\o"1-5"\h\zE YKUL SB兩趟歸并排序E K U YB L S三趟歸并排序B E K L SUY習題:對數(shù)字49384097761327進行歸并排序proceduremergesort(vorr,rl:listtype;seger);{r,rl：均為鏈表，存儲排序數(shù)據(jù)；過程mergesort(r,rl,s,t)完成把鏈表i?中的關鍵字進行歸并排序、并存放到鏈表門中，其中s是下界t是上界}{過程merge(r2,s,m,t,rl) 把鏈表r2中排好序的子鏈r2[s..m]和子鏈r2[m+l..t]合并到rl中if問題不可分then求解else分出問題的一個子問題1,并求解子問題1分出問題的一個子問題 2,求解子問題2合并子問題1和子問題2ifs二tthenrl[s]:=r[s]elsemergesort(r,r2,s,(s+t)div2);mergesort(r,r2,(s+t)div2,t);merge(r2,s,(s+t)div2,t,rl);4、［循環(huán)賽問題］（1999年廣東省青少年信息學奧林匹克競賽第三題：棒球聯(lián)賽 ）問題描述：廣州市體委將舉行一次由N支隊伍（隊伍編號為1..N）參加的少年棒球聯(lián)賽。聯(lián)賽總共不能多于N輪（同一時間內(nèi)若干支隊進行一次比賽為一輪），并且每兩支隊之間必須而且僅必須進行一次比賽。 請編程為這次比賽設計一個賽程表。循環(huán)賽問題可以用分治法解決。下面是先假定 n二2飛proceduretable(k:integer;a:array[1..ul,1..u2]ofinteger);varn,i,j,m,s,t:integer;beginn:二1;fortkdn:=n*2;for1onoa[l,i:=1ooi]:=i;m:二1;fortkds:=1 .oobeginn:/)=nfort: 二1tondofori:=m+lto2*mdoforj:=m+1to2*mdobegina[i,j+(tT)*m*2]:=a[i-m,j+(t-l)*m*2-m];a[i,j+(tT)*m*2-m]:=a[i-m,j+(tT)*m*2];end;m:二m*2;end;{fors}end;三、練習題[二分檢索]假定在A[l..9] 中順序存放這九個數(shù)：-7,-2,0,5,16,43,57,102,291 要求檢索291,16,101是否在數(shù)組屮。給定已排好序的 n個元素Al,A2,A3,...,An, 找岀元素x是否在A屮，如果x在A屮，指岀它在A屮的位置。模擬隨機函數(shù)及其應用：解決有些問題需要有一個產(chǎn)生隨機數(shù)的函數(shù)。如果你使用的機器的 Pascal未提供產(chǎn)生隨機數(shù)的標準函數(shù)， 這里就向你介紹一個實現(xiàn)這個要求的函數(shù)，并舉若干應用例子。假定問題要在整區(qū)間： a--b］集合中隨機的選取一個整數(shù) r。如［1--2］士表示擲一枚硬幣的正面或反面的結果；］1--6］士表示投一粒骰子的面值等。連續(xù)擲幣，或連續(xù)投骰子得到的結果序列： rl,r2,...稱為隨機序列。程序不能嚴格地產(chǎn)生： a--b］士的隨機序列，但能用數(shù)學方法產(chǎn)生滿足應用上所要求的近 似隨機randomint就序列的隨機數(shù)，通常稱為偽隨機數(shù)。程序產(chǎn)生偽隨機數(shù)的最通常的方法是線性同余法。下面函數(shù)是這一方法編制的產(chǎn)生［a??brandomint就FUNCTIONrandomint(a,b:integer):integer;{產(chǎn)生區(qū)間［a??b］±的一個整數(shù)，使用并改變整體變量seed}CONSTmaxseed=65536;{=216}multiplier=25173;adder=13849;BEGINseed:=(multiplier*seed+adder)MODmaxseed;randomint:二a+seed*(b~a+1)DIVmaxseedEND;函數(shù)randomint通過保留一個整體變量seed而產(chǎn)生偽隨機數(shù)。變量seed由主程序提供初值。為了產(chǎn)生一個偽隨機數(shù)，應用線性同余法改變seed的值。seed的取值范圍0??maxseed被分成(b-a+1)等分，每個等分內(nèi)的值代表］a??b］上的一個數(shù)。函數(shù)randomint不滿足前面建議的〃函數(shù)不應改變整體量值〃這一規(guī)則。但是，為了滿足每次調(diào)用 randomint能得到一個不同的值，這又是必需的。例1：利用函數(shù) randomint編制的一個20以內(nèi)整數(shù)加法教學程序。計算機隨機產(chǎn)生兩個整數(shù)，讓學生回答。簡單的算法分析：產(chǎn)生第一個隨機數(shù)x,x:=randomint(1,19)以保證兩個數(shù)相加不超過20。產(chǎn)生第二個隨機數(shù)y,y:=randomint(1,20-x) 以保證兩個數(shù)相加不超過20?！驹闯绦?xoi00_13.pas】PROGRAMsimpledrill(input,output);VARseed,i:integer;x,y,answer:integer;FUNCTIONrandomint(a,b:integer):integer;{產(chǎn)生區(qū)間［a??b］±的一個整數(shù)，使用并改變整體變量seed}CONSTmaxseed=65536;multiplier=25173;adder=13849;beginseed:=(multiplier*seed+adder)MODmaxseed;randomint:二a+seed*(b-a+l)DIVmaxseedend;{randomint}beginwriteln('Hello,Iamacomputer.');writeln('Todaywearegoingtodoadditionproblem.*);seed:=l;fori:=lto10dobeginx:=randomint(1,19); ｛產(chǎn)生一個1-19的隨機整數(shù)x｝y:=randomint(l,20-x); ｛產(chǎn)生另一個隨機整數(shù) y,并確保它與x之和小于等于20｝writeln(JPleasetellme,howmuchis',x:2,',y:2,' 二?')；write('Typetheanswer:');read(answer);ifx+y=answerthen ｛判斷答案是否正確writeln(JCorrect.')elsewriteln('That''snotright.Theansweris',x+y:2)endend.除了整隨機數(shù)外，有時也需要(a?區(qū)間上的實隨機數(shù)。產(chǎn)生實偽隨機數(shù)函數(shù)randomreal與函數(shù)randomint原理基本相同。FUNCTIONrandomreal(a,b:real):real;｛產(chǎn)生(a??b)內(nèi)的一個實數(shù)，使用并改變整體變量 seed的值2CONSTmaxseed=65536;multiplier=25173;BEGINseed plier*seedMODmaxseed;randomreal:二a+seed*(b-&)/maxseedEND;例2：計算橢圓的面積。設橢圓方程為x2/32+y2/22=1①算法思想：為了求一個不規(guī)則平面圖S的面積，選取一個長方形C圍住S。產(chǎn)生足夠多的C中的隨機點，則這些隨機 點同時落在S中的概率是SA/CA,其中SA,CA分別是S和C的面積。如果有一個簡單的標準能確定一個 點是否在S內(nèi)，就可通過產(chǎn)生隨機點，計算落在 S中的點數(shù)，估計S的面積。因為所給橢圓關于 x軸和y軸對稱，總面積是第一象限部分面積的四倍。選取長方形 C為0WxW3,OWyW2，長方形C內(nèi)的點(x,y) 落在橢圓內(nèi)的判別標準是x2/32+y2/22W1[xoi00_14.pas]PROGRAMarea(input,output);VARtotal,inside,seed:integer;x,y:real;i:integer;FUNCTIONrandomreal(a,b:real):real;{產(chǎn)生區(qū)間［a??b］上的一個實數(shù)，使用并改變實型變量 seed}CONSTmaxseed=65536;multiplier=25173;beginseed:=muItiplier*seedMODmaxseed;randomreal:二a+seed*(b~a)/maxseedend;{randomreal}beginread(total); {讀入要產(chǎn)生的隨機點的數(shù)目2inside:=O;seed:=l;fori:=ltototaldobeginx:=randomreal(0,3);y:=randomreal(0,2);if(x*x/9+y*y/4)〈二1then俘!I斷產(chǎn)生的隨機點是否落在橢圓內(nèi)2inside:=inside+lend;writeln('Estimatedarea =,6*4*inside/total)end.例3：模擬百貨商店的付款情況，假定這個商店一天營業(yè) 10個小時，中午12點到1點及下午5點到6點是高峰時間，而中午12點到1點的顧客是一般情形的兩倍，下午5點到6點是平時的三倍。【源程序：xoi00_12.pas,演示程序：DEM0014.exe】①算法思想：當模擬開始后，第一個隨機函數(shù)產(chǎn)生顧客的到來，第二個隨機函數(shù)決定此顧客要用多少時間付款，第三個 隨機函數(shù)決定顧客要到哪一個付款處去付款。此模擬的主要目的是要幫助管理者找出最適當?shù)母犊钐帞?shù) 目，滿足百貨商店的要求，使顧客排隊付款的時間在十分鐘以內(nèi)，但是不要讓收款員空閑在哪兒沒有人付 款。這種方式的模擬，主要在于建立多重的處理，雖然TruboPascal并沒有提供多重處理的功能，但是你可以讓主程序內(nèi)的各個函數(shù)，輪流使用然后循環(huán)，本質上就是使用時間分段式函數(shù)達到多重處理的效果。 例如，模擬付款的函數(shù)每次被調(diào)用時，只能計算每個對列的一部分，此種方式下，主程序的每個函數(shù)都輪 流執(zhí)行。下面是控制整個模擬的主要循環(huán)：repeatAddCust;AddQueue;DisplayCheck;Displayif(time>30)and(time<50)thenAddCust;if(time>70)and(time<80)thenbeginAddCust;AddCustend;time:二time+1;untiltime>100;在每次被調(diào)用時，函數(shù)AddCust就用Rani或Random來產(chǎn)生到達付款處的顧客數(shù)目。 AddQueue是依照Ran2的結果用來把顧客放到有服務的付款處排隊，而且當每個付款處都客滿時，它會再開放另一個付款處。Display會顯示模擬的情形。 Check使用Ran2去設定每個顧客一個付款的次序，而且每次調(diào)用時，都會使 計數(shù)器減一，直到計數(shù)器為0時，此顧客就離開了付款處了。變量time會改變產(chǎn)生顧客的速度，使得可以滿足商店高峰時間的要求，循環(huán)每做完一次就表示過了一個 小時的十分之一。你可以直接控制程序中的一些變量。首先，你可以更改顧客到達的方式和顧客到達的數(shù)目，你也能在快接 近高峰時段或高峰時段快結束時，漸漸地增加或減少AddCust返回的顧客人數(shù)。此程序是假定顧客會隨機 的選擇付款處，雖然有些人是這種情形，但是大部分人都會選擇人較少的付款處，所以你可以把各付款處 的人數(shù)記下來，然后更改AddQueue函數(shù)，改成有時把顧客放到人最少的付款處，而有時是隨機的選擇付 款處。這個程序沒有考慮到一些突發(fā)狀況。例如有人把醬油弄翻了，或是付款處有位叼鉆的顧客，這兩種 情形都會使付款工作稍微停頓。關鍵路徑：【源程序：xoi00_16.pas,演示程序：DEM00_07.zip]問題描述下圖是一個工程的AOE(ActivityOnEdge)網(wǎng)。圖中N1至N10表示該工程由十項子工程組成。有向邊al至al4表示各子工程的活動情況，其權代表各項子工程持續(xù)的時間。對于AOE網(wǎng)，研究的問題是：完成整個工程至少需要多少時間；哪些活動是影響