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

1、第二部分,讀程序?qū)懡Y(jié)果完善程序,閱讀程序現(xiàn)寫結(jié)果方法,一、直接推理,二、由流程圖推斷算法,三、動態(tài)模擬,四、由底向上閱讀分析,基本運算題,理解div、mod、＊、and 、or等運算符的含義并掌握運用注意它們之間的優(yōu)先級別算術(shù)運算>關(guān)系運算>邏輯運算And >or div、mod、＊優(yōu)先級別相同，按從左至右方向有序運算,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)注遞歸計算題,如斐波那契數(shù)列,對于一些語句少、結(jié)構(gòu)簡單且可讀性較強的程序，不妨通過分析程序流程，直接尋找其間蘊含的計算模型。,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時，t=n；i=2時，t=n*(n-1)/2；i=3時，t=n* (n-1)/2 * (n-2)/3 ；………i=m時，t= c(n,m)

5、=n!/(m!*(n-m)!),顯然，這是求組合數(shù)。當(dāng)輸入n=10、m=5時，程序應(yīng)輸出252。,對于一些易讀性不十分好的程序，最好的辦法是畫流程圖。其步驟如下 ⑴跟著程序畫流程圖，一句一框； ⑵根據(jù)上下文的聯(lián)系合并流程圖。若前幾句計算值都要代入后一表達式，則合并為一框。接連合并幾次，使程序成為一個大功能塊； ⑶由大功能塊推斷算法； ⑷代入輸入值，計算結(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輸出,,這個程序的功能是計算s串中與p匹配的子串的首指針。當(dāng)程序輸入asabcdffdinf

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

9、況表，直至得出最后結(jié)果；,動態(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ǔ)上，建立對高層程序結(jié)構(gòu)的理解，從而完成整個程序的閱讀分析，即從最底層的子目標(biāo)開始分析起，看它們做了哪些事情；然后分析上一層的子目標(biāo)，看這些子目標(biāo)在下一

13、層子目標(biāo)實現(xiàn)的基礎(chǔ)上實現(xiàn)了哪些功能……。經(jīng)過自底而上的閱讀分析，最后得出計算模型。,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ī)整為高精度的十進制數(shù)組mult(var a

19、，b)是將高精度的十進制數(shù)組a乘以整數(shù)b，積存儲在a中。 add(x， ob)計算因子表，ob=1,num←num*x；ob=-1，num←num/x。其中num[i]為因子i的個數(shù) 主程序計算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、出方面的填空 填空方法： 按照自頂向下的思維方法閱讀程序——從主程序開始，沿控制層次向下閱讀。在查到某一個子程序(子模塊)時，比照題目給出的說明和調(diào)用它的“父程序(父模塊)”，弄清該子程序(子模塊)究竟要達到什么樣的子目標(biāo)，然后查程序，看它是如何實現(xiàn)這個子目標(biāo)的。如果該子程序(子模塊)有空格，則按照算法的邏輯進行填空。依次類推，直至最底層的子程序（子模塊）中的空格全部填完為止。,指導(dǎo)思想假定－>填寫－>

21、;驗證－>調(diào)整－>驗證,1、背包問題：設(shè)有不同價值、不同重量的物品n件，求從這n件物品中選取部分物品的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。 [算法說明]：設(shè)n件物品的重量分別為w1,w2,…,wn；，物品的價值分別為v1,v2,…,vn。采用遞歸尋找物品的選擇方案。設(shè)前面已有了多種選擇的方案，并保留了其中總價值最大的方案于數(shù)組result中，該方案的總價值存于變量maxv。當(dāng)前正在考察某

22、一新的方案，其物品選擇情況保存于數(shù)組option中。假定當(dāng)前方案已考慮了前i-1件物品，現(xiàn)在要考慮第i件物品；當(dāng)前方案已包含的物品的重量之和為tw；至此，若其余物品都選擇是可能的話，本方案能達到的總價值的期望值設(shè)為tv。算法引入tv是當(dāng)一旦當(dāng)前方案的總價值的期望值也小于前面方案的總價值maxv時，繼續(xù)考察當(dāng)前方案變成無意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個方案。因為當(dāng)方案的總價值不比maxv大時，該方案不會再被考察。這同時保證后面

23、找到的方案一定會比前面的方案更好。,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('輸入各物品的重量和價值:');   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('總價值為:',maxv) end.,2、一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細胞,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞,求給定矩形陣列的細胞個數(shù)。如:陣列0234

28、500067103456050020456006710000000089有4個細胞。,[算法說明]：1． 從文件中讀入m*n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入bz數(shù)組中；2． 沿bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個細胞；3． 將細胞的位置入隊h，并沿其上、下、左、右四個方向上的細胞位置入隊，入隊后的位置bz數(shù)組置為FLASE；4． 將h隊的隊頭出隊，沿其上、下、左、右四個方向上的細胞位置入隊，入隊后的

29、位置bz數(shù)組置為FLASE；5． 重復(fù)4，直至h隊空為止，則此時找出了一個細胞；6． 重復(fù)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..

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