NOIP備戰(zhàn)讀程序完善程序課件

第二部分讀程序?qū)懡Y(jié)果完善程序1第二部分讀程序?qū)懡Y(jié)果1閱讀程序現(xiàn)寫結(jié)果方法

一、直接推理二、由流程圖推斷算法三、動(dòng)態(tài)模擬

四、由底向上閱讀分析

2閱讀程序現(xiàn)寫結(jié)果方法一、直接推理二、由流程圖推斷算法三、動(dòng)基本運(yùn)算題理解div、mod、＊、and、or等運(yùn)算符的含義并掌握運(yùn)用注意它們之間的優(yōu)先級(jí)別算術(shù)運(yùn)算>關(guān)系運(yùn)算>邏輯運(yùn)算And>ordiv、mod、＊優(yōu)先級(jí)別相同，按從左至右方向有序運(yùn)算3基本運(yùn)算題理解div、mod、＊、and、or等運(yùn)算符的含Varu::array[0..3]ofinteger;I,a,b,c,x,y,z:integer;Beginfori:=0to2dou[i]:=i*2+1;u[3]:=u[0]oru[1]andu[2]+1;a:=u[0]+u[1]+u[2]+u[3]-5;b:=u[0]*(u[1]-u[2]divu[3]+8);c:=u[0]*u[1]divu[2]*u[3];x:=(a+b+2)*3-u[(c+3)mod4];y:=(c*100-13)divadiv(u[bmod3]*5);if((x+y)mod2=0)thenz:=(a+b+c+x+y)div2;z:=(a+b+c-x-y)*2;writeln(x+y-z);End.4Var4可關(guān)注遞歸計(jì)算題,如

斐波那契數(shù)列5可關(guān)注遞歸計(jì)算題,如

斐波那契數(shù)列5對(duì)于一些語(yǔ)句少、結(jié)構(gòu)簡(jiǎn)單且可讀性較強(qiáng)的程序，不妨通過(guò)分析程序流程，直接尋找其間蘊(yùn)含的計(jì)算模型。varm,n,I:integer;t:extended;beginreadln(n,m);t:=1;fori:=1tomdot:=t*(n-i+1)/i;writeln(t:0:0);end.輸入105輸出：

直接推理6對(duì)于一些語(yǔ)句少、結(jié)構(gòu)簡(jiǎn)單且可讀性較強(qiáng)的程序，不妨通過(guò)分析程序【分析】由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。7【分析】由for循環(huán)可以看出

顯然，這是求組合數(shù)。當(dāng)輸入n=對(duì)于一些易讀性不十分好的程序，最好的辦法是畫流程圖。其步驟如下

⑴跟著程序畫流程圖，一句一框；

⑵根據(jù)上下文的聯(lián)系合并流程圖。若前幾句計(jì)算值都要代入后一表達(dá)式，則合并為一框。接連合并幾次，使程序成為一個(gè)大功能塊；

⑶由大功能塊推斷算法；

⑷代入輸入值，計(jì)算結(jié)果。流程圖推斷法8對(duì)于一些易讀性不十分好的程序，最好的辦法是畫流程圖。其步驟如label10,20,30;vars,p:string;i,k,n,j,m:integer;beginreadln(s);n:=length(s);readln(p);m:=length(p);i:=0;10:i:=i+1;j:=i;k:=1;20:ifs[j]<>p[k]thenbeginifi<n-m+1thengoto10;i:=0;goto30;endelseifk<mthenbeginj:=j+1;k:=k+1;goto20;end;30:writeln(i);end.輸入asabcdffdinfdi輸出9label10,20,30;30:writeln(i1010這個(gè)程序的功能是計(jì)算s串中與p匹配的子串的首指針。當(dāng)程序輸入asabcdffdinfdi程序應(yīng)輸出8，即s[8]…s[10]=p=‘fdi’。11這個(gè)程序的功能是計(jì)算s串中與p匹配的子串的首指針。當(dāng)程序輸入

動(dòng)態(tài)模擬方法是采用人工模仿機(jī)器執(zhí)行程序的方法計(jì)算結(jié)果值。首先選擇程序中比較重要的變量作為工作現(xiàn)場(chǎng)。人工執(zhí)行程序時(shí)，只要按照時(shí)間先后一步步記錄下現(xiàn)場(chǎng)的變化，就能最后得出程序的運(yùn)算結(jié)果。其具體布置如下：

⑴畫表，畫出程序執(zhí)行時(shí)要用的現(xiàn)場(chǎng)情況表；

⑵基本讀懂各語(yǔ)句的功能

⑶走程序，即動(dòng)態(tài)模擬程序。主要根據(jù)各語(yǔ)句的功能，按照程序執(zhí)行路徑的先后順序逐項(xiàng)填寫現(xiàn)場(chǎng)情況表，直至得出最后結(jié)果；動(dòng)態(tài)模擬方法12

動(dòng)態(tài)模擬方法是采用人工模仿機(jī)器執(zhí)行程序的方法計(jì)算結(jié)果值。首vari,j:integer;a:array[1..3,1..3]ofinteger;beginfori:=1to3dobeginforj:=1to3dobeginifi=3thena[i,j]:=a[i-1,a[i-1,j]]+1elsea[i,j]:=j;write(a[i,j]);end;writelnend;readlnend.輸出：

13var13ji123112321233234顯然，最后應(yīng)輸出12312323414j123112321233234顯然，最后應(yīng)輸出14vara,d:array[1..100]ofinteger;n,i,j,k,x,s:integer;beginn:=5;a[1]:=1;d[1]:=1;fori:=1tondobegins:=i+1;x:=0;forj:=1ton+1-idobegink:=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.輸出：

外循環(huán)內(nèi)循環(huán)i=S=d[i+1]a[1]=k=x=a[j+1]=輸出a[j]1222213123263343106454151056521152344315224295353149464201434774184252138363191345111151127262181256

611711最后應(yīng)輸出1361015…25914…4813…712…11…15var外循環(huán)內(nèi)循環(huán)i=S=d[i+1]a[1]=k=x=a[由底向上分析的閱讀分析方法就是在剖析了子程序和模塊資源的基礎(chǔ)上，建立對(duì)高層程序結(jié)構(gòu)的理解，從而完成整個(gè)程序的閱讀分析，即從最底層的子目標(biāo)開(kāi)始分析起，看它們做了哪些事情；然后分析上一層的子目標(biāo)，看這些子目標(biāo)在下一層子目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上實(shí)現(xiàn)了哪些功能……。經(jīng)過(guò)自底而上的閱讀分析，最后得出計(jì)算模型。16由底向上分析的閱讀分析方法就是在剖析了子程序和模塊資源的基礎(chǔ)constlimit=3000；typetdata=array[0..limit]oflongint;varans,num:tdata;i，j，n：longint;Procedureupdate(vara:tdata);

varintI;beginfori：=0tolimit-1dobegininc(a[i+1],a[i]div10);

a[i]:=a[i]mod10;endend；Proceduremult(vara:tdata;b:integer);

vari，j：integer；beginfori:=0tolimitdoa[i]:=a[i]*b;update(a);end；

procedureadd(x，ob：longint)；

vari：longint；beginfori：=2toxdowhile(xmodi=0)dobegininc(num[i]，ob);x：=xdivi’;end；End;17constProceduremult(vara:tdaBeginread(n)；

fillchar(num，sizeof(num)，0)；fori：=0tondobeginadd(i+1，-1)；add(n+n-i，1)；end；{for}add(n+1，-1);fillchar(ans，sizeof(ans)，0);ans[0]:=1；

fori：=2tolimitdoforj:=1tonum[i]domult(ans，i)；

fori：=limitdownto0doif(ans[i]>0)thenbeginforj:=idownto0dowrite(ans[j])；writeln；break；end；{then}End.輸入輸出52018Begin18update(vara)是將數(shù)組a規(guī)整為高精度的十進(jìn)制數(shù)組mult(vara，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))19update(vara)是將數(shù)組a規(guī)整為高精度的十進(jìn)制數(shù)組完善程序

填空內(nèi)容：1、變量方面的填空2、循環(huán)方面的填空

3、分支轉(zhuǎn)移方面的填空

4、主程序和子程序關(guān)系方面的填空

5、輸入輸出方面的填空

填空方法：

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

假定－>填寫－>驗(yàn)證－>調(diào)整－>驗(yàn)證21指導(dǎo)思想

假定－>填寫－>驗(yàn)證－>調(diào)整－>驗(yàn)證211、背包問(wèn)題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取部分物品的方案，使選中物品的總重量不超過(guò)指定的限制重量，但選中物品的價(jià)值之和最大。[算法說(shuō)明]：設(shè)n件物品的重量分別為w1,w2,…,wn；，物品的價(jià)值分別為v1,v2,…,vn。采用遞歸尋找物品的選擇方案。設(shè)前面已有了多種選擇的方案，并保留了其中總價(jià)值最大的方案于數(shù)組result中，該方案的總價(jià)值存于變量maxv。當(dāng)前正在考察某一新的方案，其物品選擇情況保存于數(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)前方案變成無(wú)意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個(gè)方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會(huì)再被考察。這同時(shí)保證后面找到的方案一定會(huì)比前面的方案更好。221、背包問(wèn)題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物programex01;

constmaxn=20;

vari,n,limitw,maxv,totalv:longint;

w,v:array[1..maxn]oflongint;

result,option:array[1..maxn]ofboolean;23programex01;

constmaxn=20;proceduretry(i,tw,tv:longint);

vark:longint;

begin

iftw+w[i]<=limitwthen

begin

option[i]:=true;

ifi<nthen______(1)_____

elsebegin

fork:=1tondoresult[k]:=option[k];

maxv:=tv

end;

______(2)_______;

end;

iftv-v[i]>maxvthen

ifi<nthen_____(3)_____

elsebegin

fork:=1tondoresult[k]:=option[k];

maxv:=tv-v[i]

end

end;24proceduretry(i,tw,tv:longint)begin

write('輸入物品種數(shù)n:');readln(n);

writeln('輸入各物品的重量和價(jià)值:');

totalv:=0;

fori:=1tondobegin

write('Inputw[',i,'],v[',i,']:');

readln(w[i],v[i]);

___(4)___;

end;

write('輸入限制重量limitw:');readln(limitw);

maxv:=0;

fori:=1tondooption[i]:=false;

try(1,0,totalv);

write('選擇方案為:');

fori:=1tondoif___(5)___thenwrite(i,'');

writeln;

writeln('總價(jià)值為:',maxv)

end.25begin

write('輸入物品種數(shù)n:');re2、一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。

如:陣列

0234500067

1034560500

2045600671

0000000089

有4個(gè)細(xì)胞。262、一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定[算法說(shuō)明]：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ù)27[算法說(shuō)明]：27programxibao;

constdx:array[1..4]of-1..1=(-1,0,1,0);

dy:array[1..4]of-1..1=(0,1,0,-1);

varint:text;name,s:string;

pic:array[1..50,1..79]ofbyte;

bz:array[1..50,1..79]ofboolean;

m,n,i,j,num:integer;

h:array[1..4000,1..2]ofbyte;28programxibao;

constdx:arrayproceduredoing(p,q:integer);

vari,t,w,x,y:integer;

begin

inc(num);

______(1)______;

t:=1;w:=1;

h[1,1]:=_____(2)_____;

h[1,2]:=_____(3)_____;

repeat

fori:=1to4do

begin

x:=h[t,1]+dx[i];y:=h[t,2]+dy[i];

if(x>0)and(x<=m)and(y>0)and(y<=n)andbz[x,y]

thenbegininc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;

end;

inc(t);

until______(4)________;

end;29proceduredoing(p,q:integer);

begin

fillchar(bz,sizeof(bz),true);num:=0;

write('inputfile:');readln(name);

assign(int,name);

reset(int);

readln(int,m,n);

fori:=1tomdo

beginreadln(int,s);

forj:=1tondo

beginpic[i,j]:=ord(s[j])-ord('0');

if_____(5)____thenbz[i,j]:=false;

end;

end;

close(int);

fori:=1tomdo

forj:=1tondoifbz[i,j]thendoing(i,j);

writeln('NUMBERofcells=',num);readln;

end.30begin

fillchar(bz,sizeof(bz)3131第二部分讀程序?qū)懡Y(jié)果完善程序32第二部分讀程序?qū)懡Y(jié)果1閱讀程序現(xiàn)寫結(jié)果方法

一、直接推理二、由流程圖推斷算法三、動(dòng)態(tài)模擬

四、由底向上閱讀分析

33閱讀程序現(xiàn)寫結(jié)果方法一、直接推理二、由流程圖推斷算法三、動(dòng)基本運(yùn)算題理解div、mod、＊、and、or等運(yùn)算符的含義并掌握運(yùn)用注意它們之間的優(yōu)先級(jí)別算術(shù)運(yùn)算>關(guān)系運(yùn)算>邏輯運(yùn)算And>ordiv、mod、＊優(yōu)先級(jí)別相同，按從左至右方向有序運(yùn)算34基本運(yùn)算題理解div、mod、＊、and、or等運(yùn)算符的含Varu::array[0..3]ofinteger;I,a,b,c,x,y,z:integer;Beginfori:=0to2dou[i]:=i*2+1;u[3]:=u[0]oru[1]andu[2]+1;a:=u[0]+u[1]+u[2]+u[3]-5;b:=u[0]*(u[1]-u[2]divu[3]+8);c:=u[0]*u[1]divu[2]*u[3];x:=(a+b+2)*3-u[(c+3)mod4];y:=(c*100-13)divadiv(u[bmod3]*5);if((x+y)mod2=0)thenz:=(a+b+c+x+y)div2;z:=(a+b+c-x-y)*2;writeln(x+y-z);End.35Var4可關(guān)注遞歸計(jì)算題,如

斐波那契數(shù)列36可關(guān)注遞歸計(jì)算題,如

斐波那契數(shù)列5對(duì)于一些語(yǔ)句少、結(jié)構(gòu)簡(jiǎn)單且可讀性較強(qiáng)的程序，不妨通過(guò)分析程序流程，直接尋找其間蘊(yùn)含的計(jì)算模型。varm,n,I:integer;t:extended;beginreadln(n,m);t:=1;fori:=1tomdot:=t*(n-i+1)/i;writeln(t:0:0);end.輸入105輸出：

直接推理37對(duì)于一些語(yǔ)句少、結(jié)構(gòu)簡(jiǎn)單且可讀性較強(qiáng)的程序，不妨通過(guò)分析程序【分析】由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。38【分析】由for循環(huán)可以看出

顯然，這是求組合數(shù)。當(dāng)輸入n=對(duì)于一些易讀性不十分好的程序，最好的辦法是畫流程圖。其步驟如下

⑴跟著程序畫流程圖，一句一框；

⑵根據(jù)上下文的聯(lián)系合并流程圖。若前幾句計(jì)算值都要代入后一表達(dá)式，則合并為一框。接連合并幾次，使程序成為一個(gè)大功能塊；

⑶由大功能塊推斷算法；

⑷代入輸入值，計(jì)算結(jié)果。流程圖推斷法39對(duì)于一些易讀性不十分好的程序，最好的辦法是畫流程圖。其步驟如label10,20,30;vars,p:string;i,k,n,j,m:integer;beginreadln(s);n:=length(s);readln(p);m:=length(p);i:=0;10:i:=i+1;j:=i;k:=1;20:ifs[j]<>p[k]thenbeginifi<n-m+1thengoto10;i:=0;goto30;endelseifk<mthenbeginj:=j+1;k:=k+1;goto20;end;30:writeln(i);end.輸入asabcdffdinfdi輸出40label10,20,30;30:writeln(i4110這個(gè)程序的功能是計(jì)算s串中與p匹配的子串的首指針。當(dāng)程序輸入asabcdffdinfdi程序應(yīng)輸出8，即s[8]…s[10]=p=‘fdi’。42這個(gè)程序的功能是計(jì)算s串中與p匹配的子串的首指針。當(dāng)程序輸入

動(dòng)態(tài)模擬方法是采用人工模仿機(jī)器執(zhí)行程序的方法計(jì)算結(jié)果值。首先選擇程序中比較重要的變量作為工作現(xiàn)場(chǎng)。人工執(zhí)行程序時(shí)，只要按照時(shí)間先后一步步記錄下現(xiàn)場(chǎng)的變化，就能最后得出程序的運(yùn)算結(jié)果。其具體布置如下：

⑴畫表，畫出程序執(zhí)行時(shí)要用的現(xiàn)場(chǎng)情況表；

⑵基本讀懂各語(yǔ)句的功能

⑶走程序，即動(dòng)態(tài)模擬程序。主要根據(jù)各語(yǔ)句的功能，按照程序執(zhí)行路徑的先后順序逐項(xiàng)填寫現(xiàn)場(chǎng)情況表，直至得出最后結(jié)果；動(dòng)態(tài)模擬方法43

動(dòng)態(tài)模擬方法是采用人工模仿機(jī)器執(zhí)行程序的方法計(jì)算結(jié)果值。首vari,j:integer;a:array[1..3,1..3]ofinteger;beginfori:=1to3dobeginforj:=1to3dobeginifi=3thena[i,j]:=a[i-1,a[i-1,j]]+1elsea[i,j]:=j;write(a[i,j]);end;writelnend;readlnend.輸出：

44var13ji123112321233234顯然，最后應(yīng)輸出12312323445j123112321233234顯然，最后應(yīng)輸出14vara,d:array[1..100]ofinteger;n,i,j,k,x,s:integer;beginn:=5;a[1]:=1;d[1]:=1;fori:=1tondobegins:=i+1;x:=0;forj:=1ton+1-idobegink:=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.輸出：

外循環(huán)內(nèi)循環(huán)i=S=d[i+1]a[1]=k=x=a[j+1]=輸出a[j]1222213123263343106454151056521152344315224295353149464201434774184252138363191345111151127262181256

611711最后應(yīng)輸出1361015…25914…4813…712…11…46var外循環(huán)內(nèi)循環(huán)i=S=d[i+1]a[1]=k=x=a[由底向上分析的閱讀分析方法就是在剖析了子程序和模塊資源的基礎(chǔ)上，建立對(duì)高層程序結(jié)構(gòu)的理解，從而完成整個(gè)程序的閱讀分析，即從最底層的子目標(biāo)開(kāi)始分析起，看它們做了哪些事情；然后分析上一層的子目標(biāo)，看這些子目標(biāo)在下一層子目標(biāo)實(shí)現(xiàn)的基礎(chǔ)上實(shí)現(xiàn)了哪些功能……。經(jīng)過(guò)自底而上的閱讀分析，最后得出計(jì)算模型。47由底向上分析的閱讀分析方法就是在剖析了子程序和模塊資源的基礎(chǔ)constlimit=3000；typetdata=array[0..limit]oflongint;varans,num:tdata;i，j，n：longint;Procedureupdate(vara:tdata);

varintI;beginfori：=0tolimit-1dobegininc(a[i+1],a[i]div10);

a[i]:=a[i]mod10;endend；Proceduremult(vara:tdata;b:integer);

vari，j：integer；beginfori:=0tolimitdoa[i]:=a[i]*b;update(a);end；

procedureadd(x，ob：longint)；

vari：longint；beginfori：=2toxdowhile(xmodi=0)dobegininc(num[i]，ob);x：=xdivi’;end；End;48constProceduremult(vara:tdaBeginread(n)；

fillchar(num，sizeof(num)，0)；fori：=0tondobeginadd(i+1，-1)；add(n+n-i，1)；end；{for}add(n+1，-1);fillchar(ans，sizeof(ans)，0);ans[0]:=1；

fori：=2tolimitdoforj:=1tonum[i]domult(ans，i)；

fori：=limitdownto0doif(ans[i]>0)thenbeginforj:=idownto0dowrite(ans[j])；writeln；break；end；{then}End.輸入輸出52049Begin18update(vara)是將數(shù)組a規(guī)整為高精度的十進(jìn)制數(shù)組mult(vara，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))50update(vara)是將數(shù)組a規(guī)整為高精度的十進(jìn)制數(shù)組完善程序

填空內(nèi)容：1、變量方面的填空2、循環(huán)方面的填空

3、分支轉(zhuǎn)移方面的填空

4、主程序和子程序關(guān)系方面的填空

5、輸入輸出方面的填空

填空方法：

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

假定－>填寫－>驗(yàn)證－>調(diào)整－>驗(yàn)證52指導(dǎo)思想

假定－>填寫－>驗(yàn)證－>調(diào)整－>驗(yàn)證211、背包問(wèn)題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取部分物品的方案，使選中物品的總重量不超過(guò)指定的限制重量，但選中物品的價(jià)值之和最大。[算法說(shuō)明]：設(shè)n件物品的重量分別為w1,w2,…,wn；，物品的價(jià)值分別為v1,v2,…,vn。采用遞歸尋找物品的選擇方案。設(shè)前面已有了多種選擇的方案，并保留了其中總價(jià)值最大的方案于數(shù)組result中，該方案的總價(jià)值存于變量maxv。當(dāng)前正在考察某一新的方案，其物品選擇情況保存于數(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)前方案變成無(wú)意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個(gè)方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會(huì)再被考察。這同時(shí)保證后面找到的方案一定會(huì)比前面的方案更好。531、背包問(wèn)題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物programex01;

constmaxn=20;

vari,n,limitw,maxv,totalv:longint;

w,v:array[1..maxn]oflongint;

result,option:array[1..maxn]ofboolean;54programex01;

constmaxn=20;proceduretry(i,tw,tv:longint);

vark:longint;

begin

iftw+w[i]<=limitwthen

begin

option[i]:=true;

ifi<nthen______(1)_____

elsebegin

fork:=1tondoresult[k]:=option[k];

maxv:=tv

end;

______(2)_______;

end;

iftv-v[i]>maxvthen

ifi<nthen_____(3)_____

elsebegin

fork:=1tondoresult[k]:=option[k];

maxv:=tv-v[i]

end

end;55proceduretry(i,tw,tv:longint)begin

write('輸入物品種數(shù)n:');readln(n);

writeln('輸入各物品的重量和價(jià)值:');

totalv:=0;

fori:=1tondobegin

write('Inputw[',i,'],v[',i,']:');

readln(w[i],v[i]);

___(4)___;

end;

write('輸入限制重量limitw:');readln(limitw);

maxv:=0;

fori:=1tondooption[i]:=false;

try(1,0,totalv);

write('選擇方案為:');

fori:=1tondoif___(5)___thenwrite(i,'');

writeln;

writeln('總價(jià)值為:',maxv)

end.56begin

write('輸入物品種數(shù)n:'