noip備戰(zhàn)讀程序完善程序

1、第二部分,讀程序?qū)懡Y(jié)果完善程序,閱讀程序現(xiàn)寫結(jié)果方法,一、直接推理,二、由流程圖推斷算法,三、動(dòng)態(tài)模擬,四、由底向上閱讀分析,基本運(yùn)算題,理解div、mod、＊、and 、or等運(yùn)算符的含義并掌握運(yùn)用注意它們之間的優(yōu)先級(jí)別算術(shù)運(yùn)算>關(guān)系運(yùn)算>邏輯運(yùn)算And >or div、mod、＊優(yōu)先級(jí)別相同，按從左至右方向有序運(yùn)算,Varu::array[0..3] of integer;I,a,b,c,x,y,

2、z:integer;Begin for i:=0 to 2 do u[i]:=i*2+1; u[3]:=u[0] or u[1] and u[2]+1; a:=u[0] +u[1] +u[2] +u[3]-5; b:=u[0]*(u[1]-u[2] div u[3]+8); c:=u[0]*u[1] div u[2]*u[3]; x:=(a+b+2)*3-u[(c+3) mod 4]; y:=(c*100-

3、13) div a div (u[b 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ù)列,對(duì)于一些語句少、結(jié)構(gòu)簡單且可讀性較強(qiáng)的程序，不妨通過分析程序流程，直接尋找其間蘊(yùn)含的計(jì)算模型。,varm,n,I:integer;t:extended;be

4、gin readln(n,m); t:=1; 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)

5、=n!/(m!*(n-m)!),顯然，這是求組合數(shù)。當(dāng)輸入n=10、m=5時(shí)，程序應(yīng)輸出252。,對(duì)于一些易讀性不十分好的程序，最好的辦法是畫流程圖。其步驟如下 ⑴跟著程序畫流程圖，一句一框； ⑵根據(jù)上下文的聯(lián)系合并流程圖。若前幾句計(jì)算值都要代入后一表達(dá)式，則合并為一框。接連合并幾次，使程序成為一個(gè)大功能塊； ⑶由大功能塊推斷算法； ⑷代入輸入值，計(jì)算結(jié)果。,流程圖推斷法,label 10,20,30;

6、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 s[j]p[k] then begin if i<n-m+1 then

7、 goto 10; i:=0; goto 30; end else if k<m then begin j:=j+1; k:=k+1; goto 20;end;,30: writeln(i);end.輸入asabcdffdinfdi輸出,,這個(gè)程序的功能是計(jì)算s串中與p匹配的子串的首指針。當(dāng)程序輸入asabcdffdinf

8、di程序應(yīng)輸出8，即s[8]…s[10]=p=‘fdi’。,動(dòng)態(tài)模擬方法是采用人工模仿機(jī)器執(zhí)行程序的方法計(jì)算結(jié)果值。首先選擇程序中比較重要的變量作為工作現(xiàn)場。人工執(zhí)行程序時(shí)，只要按照時(shí)間先后一步步記錄下現(xiàn)場的變化，就能最后得出程序的運(yùn)算結(jié)果。其具體布置如下： ⑴畫表，畫出程序執(zhí)行時(shí)要用的現(xiàn)場情況表； ⑵基本讀懂各語句的功能 ⑶走程序，即動(dòng)態(tài)模擬程序。主要根據(jù)各語句的功能，按照程序執(zhí)行路徑的先后順序逐項(xiàng)填寫現(xiàn)場情

9、況表，直至得出最后結(jié)果；,動(dòng)態(tài)模擬方法,var i,j:integer; a:array[1..3,1..3]of integer;begin for i:=1 to 3 do begin for j:=1 to 3 do begin if i=3 then a[i,j]:=a[i-1,a[i-1,j]]+1 else a[i,j]:=j

10、; write(a[i,j]); end; writeln end; readln end.輸出：,,顯然，最后應(yīng)輸出1 2 31 2 32 3 4,var a,d:array[1..100] of integer; n,i,j,k,x,s:integer;begin n:=5;a[1]:=1;d[1]:=1; for i:=1 to n

11、 do begin s:=i+1;x:=0; for j:=1 to n+1-i dobegin k:=s+x;x:=x+1;a[j+1]:=a[j]+k;write(a[j],' '); end; writeln('...');d[i+1]:=d[i]+i;a[1]:=d[i+1]; end;end.輸出：,最后應(yīng)輸出

12、 1 3 6 10 15 … 2 5 9 14 … 4 8 13 … 7 12 … 11 …,由底向上分析的閱讀分析方法就是在剖析了子程序和模塊資源的基礎(chǔ)上，建立對(duì)高層程序結(jié)構(gòu)的理解，從而完成整個(gè)程序的閱讀分析，即從最底層的子目標(biāo)開始分析起，看它們做了哪些事情；然后分析上一層的子目標(biāo)，看這些子目標(biāo)在下一

13、層子目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上實(shí)現(xiàn)了哪些功能……。經(jīng)過自底而上的閱讀分析，最后得出計(jì)算模型。,const limit = 3000；type tdata=array[0..limit]of longint;varans ,num :tdata;i，j，n：longint;Procedureupdate(var a:tdata); var int I; begin for i：=0

14、to limit-1 do begin inc(a[i+1],a[i] div 10); a[i] := a[i] mod 10;end end；,Procedure mult(var a:tdata;b:integer); vari， j：integer；begin for i:=0 to limit do a[i]:= a[i] * b; up

15、date(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(num[i]， ob); x ：= x div i’;end；End;,Beginread(n)；

16、 fillchar(num， sizeof(num)，0)； for i：= 0 to n do begin add(i+1，-1)； add(n+n-i，1)； end；{for}add(n+1， -1);fillchar(ans，sizeof(ans)，0);ans[0] := 1；

17、 for i：=2 to limit do for j:=1 to num[i] do mult(ans，i)； for i：=limit downto 0 do if

18、 (ans[i] > 0) then begin for j:=i downto 0 do write(ans[j])； writeln；break； end；{then}End.輸入 輸出 5 20,update(var a)是將數(shù)組a規(guī)整為高精度的十進(jìn)制數(shù)組mult(var a

19、，b)是將高精度的十進(jìn)制數(shù)組a乘以整數(shù)b，積存儲(chǔ)在a中。 add(x， ob)計(jì)算因子表，ob=1,num←num*x；ob=-1，num←num/x。其中num[i]為因子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、輸入輸

20、出方面的填空 填空方法： 按照自頂向下的思維方法閱讀程序——從主程序開始，沿控制層次向下閱讀。在查到某一個(gè)子程序(子模塊)時(shí)，比照題目給出的說明和調(diào)用它的“父程序(父模塊)”，弄清該子程序(子模塊)究竟要達(dá)到什么樣的子目標(biāo)，然后查程序，看它是如何實(shí)現(xiàn)這個(gè)子目標(biāo)的。如果該子程序(子模塊)有空格，則按照算法的邏輯進(jìn)行填空。依次類推，直至最底層的子程序（子模塊）中的空格全部填完為止。,指導(dǎo)思想假定－>填寫－>

21、;驗(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)前正在考察某

22、一新的方案，其物品選擇情況保存于數(shù)組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í)，該方案不會(huì)再被考察。這同時(shí)保證后面

23、找到的方案一定會(huì)比前面的方案更好。,program ex01; const maxn=20; var i,n,limitw,maxv,totalv:longint;   w,v:array[1..maxn] of longint;   result,option:array[1..maxn] of boolean;,procedure try(i,tw,tv:longint); var k:longint;

24、 begin   if tw+w[i]maxv then     if i<n then _____(3)_____ else begin for k:=1 to n do result[k]:=option[k]; maxv:=tv-v[i] end end;,,begin   write('輸入物

25、品種數(shù)n:'); readln(n);   writeln('輸入各物品的重量和價(jià)值:');   totalv:=0;   for i:=1 to n do begin       write('Input w[',i,'],v[',i,']:');       r

26、eadln(w[i],v[i]);       ___(4)___;   end;   write('輸入限制重量limitw:'); readln(limitw);   maxv:=0;   for i:=1 to n do option[i]:=false;   try(1,0,totalv);   write(&

27、#39;選擇方案為:');   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ì)胞個(gè)數(shù)。如:陣列0234

28、500067103456050020456006710000000089有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ì)后的

29、位置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..

30、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); ______(1)______;

31、 t:=1;w:=1; h[1,1]:=_____(2)_____; h[1,2]:=_____(3)_____;　 repeat　　for i:=1 to 4 do　　 begin　　　 x:=h[t,1]+dx[i];y:=h[t,2]+dy[i];　　　 if (x>0) and (x0) and (y<=n) and bz[x,y]　then begin inc(w);h

32、[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;　　 end;　 inc(t);　until ______ (4)________;end;,begin　　fillchar(bz,sizeof(bz),true); num:=0;　　write('input file:'); readln(name);　　assign(int,name);   reset(int

33、);　　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('0');　　　　　if _____(5)____then bz[i,j]:=false;　　　　end;　　　end;　　close(int);　　for i:=1 to m