1、第二部分,讀程序?qū)懡Y(jié)果 完善程序,閱讀程序現(xiàn)寫結(jié)果方法,一、直接推理,二、由流程圖推斷算法,三、動態(tài)模擬,四、由底向上閱讀分析,基本運(yùn)算題,理解div、mod、and 、or等運(yùn)算符的含義并掌握運(yùn)用 注意它們之間的優(yōu)先級別 算術(shù)運(yùn)算關(guān)系運(yùn)算邏輯運(yùn)算 And or div、mod、優(yōu)先級別相同，按從左至右方向有序運(yùn)算,Var u:array0.3 of integer; I,a,b,c,x,y,z:integer; Begin for i:=0 to 2 do ui:=i*2+1; u3:=u0 or u1 and u2+1; a:=u0 +u1 +u2 +u3-5; b:=u0*(u1-u2

2、div u3+8); c:=u0*u1 div u2*u3; x:=(a+b+2)*3-u(c+3) mod 4; y:=(c*100-13) div a div (ub mod 3*5); if (x+y) mod 2=0) then z:=(a+b+c+x+y) div 2; z:=(a+b+c-x-y)*2; writeln(x+y-z); End.,可關(guān)注遞歸計(jì)算題,如斐波那契數(shù)列,對于一些語句少、結(jié)構(gòu)簡單且可讀性較強(qiáng)的程序，不妨通過分析程序流程，直接尋找其間蘊(yùn)含的計(jì)算模型。,var m,n,I:integer; t:extended; begin readln(n,m); t:=1;

3、 for i:=1 to m do t:=t*(n-i+1)/i; writeln(t:0:0); end. 輸入 10 5 輸出：,直接推理,【分析】由for循環(huán)可以看出 t= ，即 i=1時(shí)，t=n； i=2時(shí)，t=n*(n-1)/2； i=3時(shí)，t=n* (n-1)/2 * (n-2)/3 ； i=m時(shí)，t= c(n,m)=n!/(m!*(n-m)!),顯然，這是求組合數(shù)。當(dāng)輸入n=10、m=5時(shí)，程序應(yīng)輸出252。,對于一些易讀性不十分好的程序，最好的辦法是畫流程圖。其步驟如下 跟著程序畫流程圖，一句一框； 根據(jù)上下文的聯(lián)系合并流程圖。若前幾句計(jì)算值都要代入后一表達(dá)式，則合并為一框。接

4、連合并幾次，使程序成為一個(gè)大功能塊； 由大功能塊推斷算法； 代入輸入值，計(jì)算結(jié)果。,流程圖推斷法,label 10,20,30; var s,p:string; i,k,n,j,m:integer; begin readln(s); n:=length(s); readln(p); m:=length(p); i:=0; 10: i:=i+1; j:=i; k:=1; 20: if sjpk then begin if in-m+1 then goto 10; i:=0; goto 30; end else if km then begin j:=j+1; k:=k+1; goto 20;en

5、d;,30: writeln(i); end. 輸入 asabcdffdin fdi 輸出,這個(gè)程序的功能是計(jì)算s串中與p匹配的子串的首指針。當(dāng)程序輸入 asabcdffdin fdi 程序應(yīng)輸出8，即s8s10=p=fdi。,動態(tài)模擬方法是采用人工模仿機(jī)器執(zhí)行程序的方法計(jì)算結(jié)果值。首先選擇程序中比較重要的變量作為工作現(xiàn)場。人工執(zhí)行程序時(shí)，只要按照時(shí)間先后一步步記錄下現(xiàn)場的變化，就能最后得出程序的運(yùn)算結(jié)果。其具體布置如下： 畫表，畫出程序執(zhí)行時(shí)要用的現(xiàn)場情況表； 基本讀懂各語句的功能 走程序，即動態(tài)模擬程序。主要根據(jù)各語句的功能，按照程序執(zhí)行路徑的先后順序逐項(xiàng)填寫現(xiàn)場情況表，直至得出最后結(jié)果；

6、,動態(tài)模擬方法,var i,j:integer; a:array1.3,1.3of integer; begin for i:=1 to 3 do begin for j:=1 to 3 do begin if i=3 then ai,j:=ai-1,ai-1,j+1 else ai,j:=j; write(ai,j); end; writeln end; readln end. 輸出：,顯然，最后應(yīng)輸出 1 2 3 1 2 3 2 3 4,var a,d:array1.100 of integer; n,i,j,k,x,s:integer; begin n:=5;a1:=1;d1:=1; f

7、or i:=1 to n do begin s:=i+1;x:=0; for j:=1 to n+1-i do begin k:=s+x;x:=x+1;aj+1:=aj+k; write(aj, ); end; writeln(.);di+1:=di+i;a1:=di+1; end; end. 輸出：,最后應(yīng)輸出 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 ,由底向上分析的閱讀分析方法就是在剖析了子程序和模塊資源的基礎(chǔ)上，建立對高層程序結(jié)構(gòu)的理解，從而完成整個(gè)程序的閱讀分析，即從最底層的子目標(biāo)開始分析起，看它們做了哪些事情；然后分析上一層的子目標(biāo)，看這些子目標(biāo)在下一

8、層子目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上實(shí)現(xiàn)了哪些功能。經(jīng)過自底而上的閱讀分析，最后得出計(jì)算模型。,const limit = 3000； type tdata=array0.limitof longint; var ans ,num :tdata; i，j，n：longint; Procedureupdate(var a:tdata); var int I; begin for i：=0 to limit-1 do begin inc(ai+1,ai div 10); ai := ai mod 10; end end；,Procedure mult(var a:tdata;b:integer); var i，

9、j：integer； begin for i:=0 to limit do ai:= ai * b; update(a); end； procedure add(x， ob：longint)； var i：longint； begin for i：=2 to x do while (x mod i =0) do begin inc(numi， ob); x ：= x div i; end； End;,Begin read(n)； fillchar(num， sizeof(num)，0)； for i：= 0 to n do begin add(i+1，-1)； add(n+n-i，1)； en

10、d；for add(n+1， -1);fillchar(ans，sizeof(ans)，0);ans0 := 1； for i：=2 to limit do for j:=1 to numi do mult(ans，i)； for i：=limit downto 0 do if (ansi 0) then begin for j:=i downto 0 do write(ansj)； writeln；break； end；then End. 輸入 輸出 5 20,update(var a)是將數(shù)組a規(guī)整為高精度的十進(jìn)制數(shù)組mult(var a，b)是將高精度的十進(jìn)制數(shù)組a乘以整數(shù)b，積存儲在a

11、中。 add(x， ob)計(jì)算因子表，ob=1,numnum*x；ob=-1，numnum/x。其中numi為因子i的個(gè)數(shù) 主程序計(jì)算catalan數(shù)1/（n+1）*c(2*n,n) 。顯然n=5，則程序輸出42(1/6*c(10,5),完善程序,填空內(nèi)容： 1、變量方面的填空 2、循環(huán)方面的填空 3、分支轉(zhuǎn)移方面的填空 4、主程序和子程序關(guān)系方面的填空 5、輸入輸出方面的填空 填空方法： 按照自頂向下的思維方法閱讀程序從主程序開始，沿控制層次向下閱讀。在查到某一個(gè)子程序(子模塊)時(shí)，比照題目給出的說明和調(diào)用它的“父程序(父模塊)”，弄清該子程序(子模塊)究竟要達(dá)到什么樣的子目標(biāo)，然后查程序，

12、看它是如何實(shí)現(xiàn)這個(gè)子目標(biāo)的。如果該子程序(子模塊)有空格，則按照算法的邏輯進(jìn)行填空。依次類推，直至最底層的子程序（子模塊）中的空格全部填完為止。,指導(dǎo)思想假定填寫驗(yàn)證調(diào)整驗(yàn)證,1、背包問題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取部分物品的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價(jià)值之和最大。 算法說明：設(shè)n件物品的重量分別為w1,w2,wn；，物品的價(jià)值分別為v1,v2,vn。采用遞歸尋找物品的選擇方案。設(shè)前面已有了多種選擇的方案，并保留了其中總價(jià)值最大的方案于數(shù)組result中，該方案的總價(jià)值存于變量maxv。當(dāng)前正在考察某一新的方案，其物品選擇情況保存于數(shù)

13、組option中。假定當(dāng)前方案已考慮了前i-1件物品，現(xiàn)在要考慮第i件物品；當(dāng)前方案已包含的物品的重量之和為tw；至此，若其余物品都選擇是可能的話，本方案能達(dá)到的總價(jià)值的期望值設(shè)為tv。算法引入tv是當(dāng)一旦當(dāng)前方案的總價(jià)值的期望值也小于前面方案的總價(jià)值maxv時(shí)，繼續(xù)考察當(dāng)前方案變成無意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個(gè)方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會再被考察。這同時(shí)保證后面找到的方案一定會比前面的方案更好。,program ex01; const maxn=20; var i,n,limitw,maxv,totalv:longint; w,v:array1.max

14、n of longint; result,option:array1.maxn of boolean;,procedure try(i,tw,tv:longint); var k:longint; begin if tw+wimaxv then if in then _(3)_ else begin for k:=1 to n do resultk:=optionk; maxv:=tv-vi end end;,begin write(輸入物品種數(shù)n:); readln(n); writeln(輸入各物品的重量和價(jià)值:); totalv:=0; for i:=1 to n do begin wr

15、ite(Input w,i,v,i,:); readln(wi,vi); _(4)_; end; write(輸入限制重量limitw:); readln(limitw); maxv:=0; for i:=1 to n do optioni:=false; try(1,0,totalv); write(選擇方案為:); for i:=1 to n do if _(5)_then write(i, ); writeln; writeln(總價(jià)值為:,maxv) end.,2、一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)

16、胞個(gè)數(shù)。如:陣列0234500067103456050020456006710000000089有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 x

17、ibao;const dx:array1.4 of -1.1=(-1,0,1,0);dy:array1.4 of -1.1=(0,1,0,-1);var int: text; name ,s: string;pic: array1.50,1.79 of byte;bz:array1.50,1.79 of boolean;m,n,i,j,num : integer;h: array1.4000,1.2 of byte;,procedure doing(p,q:integer);var i,t,w,x,y:integer;begin inc(num); _(1)_; t:=1;w:=1; h1,1:=_(2)_; h1,2:=_(3)_; repeatfor i:=1 to 4 do begin x:=ht,1+dxi;y:=ht,2+dyi; if (x0) and (x0) and (y=n) and bzx,ythen begin inc(w);hw,1:=x;hw,2:=y;bzx,y:=false;end; end; inc(t);until _ (4)_;end;,beginfillchar(bz,sizeof(bz),true); num:=0;write(input file:); re