中學noi初賽練習之四完成程序題新新

1、中學 NOI 初賽練習之四（完成程序題）如何做完成程序題：每年的信息學分區(qū)初賽的最后一部分都是完成程序題，一般是兩道題總分 28。這是最能體現(xiàn)你閱讀理解程序水平的部分。有許多問題可能自己能編寫出程序，但完成程序首先要求你在理解題意的基礎上讀懂給定的算法和數(shù)據(jù)結構，這樣才能填寫出相關內(nèi)容。對于這一類題目，往往要先多讀幾遍題意，理解要實現(xiàn)什么，然后是理程序中的數(shù)據(jù)結構、變量含義，最后才去考慮填什么語句。這類試題常常讓大家填的是：1、初始化(i:=0; j:=0; for i:=1 to n do ai:=0 之類的) 2、一些明顯的動作：（1）（2）（3）結果沒有在需要的地方。累加器沒有做加法輸出

2、3、關鍵動作。在算法描述中出現(xiàn)的比較關鍵的步驟。例如交換排序程序的“交換”操作等很明顯需要完成的操作。分析方法和寫運行結果類似，注意分析變量和程序結構，理解變量和模塊的作用是解題的關鍵。完成程序練習題：1、下面的程序從鍵盤接受任意 6 個數(shù)放入數(shù)組a 中，設這 6 個數(shù)為：8 1 4 2 5 6，則可輸出一個具有如下內(nèi)容的方陣：814256681425568142256814425681142568program ex1;var a:array1.6ofeger;i,j,k: beginfor i:=1 to for i:=1 tobegineger;6 do read(ai);readln;

3、6 doif i=1 then k:= (1) else k:= (2); for j:=1 to (3)dobegin write(ak:2);if k=6 then k:=1 else k:= (4);end;wri endend.n;2.在下列程序中，當輸入一個給定的數(shù) N 后，能輸出所有不超過N 的、其平方由左右對稱的數(shù)字組成的數(shù)。 如：N=23，則輸出：1 2 3 11 22 。它們的平方依次是：1 4 9 121 484，都是左右對稱的數(shù)字組成的數(shù)。program ex2;const max=1000;var m,n,i,j,s:eger;d:array0.max ofeger;

4、beginreadln(n);for m:=1 to n do begin(1); j:=0;while s0 dobeginj:=j+1;end;i:=1;dj:=s mod 10;(2);while (3)do begini:=i+1;j:=j-1;end;if i=j then wri endend.n( (4);3.下面過程實現(xiàn)將數(shù)組 a 賦予如下的值：1111141111341112341112341procedure fuzhe;var a:array1.5,1.5 ofeger;i,j,k:begineger;forfor ifi:=1 toj:=1 to (i-j=4)5 do

5、5 door ( (1) then ai,j:=1else begink:=(2); case k of1:ai,j:=4;2:ai,j:=(3);3:ai,j:=(4); end;end;end;4、驗證回文數(shù)猜想：一個數(shù)的倒置數(shù)還是它自己，這個數(shù)就是回文數(shù)。任一個數(shù)（196 除外），如果它不是回文數(shù)，把它和它的倒置數(shù)相加，得到一個新數(shù)，如果是回文數(shù)即結束，如果不是重復上過程，總能得到一個回文數(shù)。program hws; typear=array1.100 of var c,i,j,n,len,time:s,p:ar; st:string;function check(s:ar;l: beg

6、incheck:=false;for i:=1 to l div 2 end;byte;eger;eger):;f (1)thencheck:=true;function change(num:word;var s:ar):byte;var len:begineger; st:string;str(num,st);len:=length(st); for i:=1 to len dobeginsi:=num mod 10;num:=num div 10; end;change:=(2); end;begin readln(n); c:=0;time:=0;len:=change(n,s); w

7、hile check(s,len) do beginp:=s;c:=0;inc(time);write(time:3,:);for i:=len downto 1 do write(si); write(+);for i:=1 to len do write(si);write(=); for i:=1 to len dobeginsi:=(3); c:=si div 10;si:=si mod 10; end;if c0 then begin len:=len+1;slen:=(4);for i:=len downto 1 do write(si);end;wri end;end.n;5.從

8、鍵盤讀入一個算術表達式（中綴表示法），把它轉為后綴表示法并輸出。所謂后綴表達式就是把運算符號放在兩個運算元素的后面，如 a+b 寫作 ab+。又如輸入：A/BC+D*(E-F)*G program hz;var expstr,newexp:string;輸出：ABC/DEF-*G*+s:array 1.255 of char; opcode:array1.255 of 0.3; p,len:byte;ch:char; letters:A.Z;procedure init; beginp:=0;newexp:=; end;procedure trans_exp;vari:byte;procedu

9、re acs_oprator;var fg:byte;flag: begincase ch of +,-:fg:=1;*,/:fg:=2;:fg:3; end; flag:=false; repeatif (1)then beginp:=p+1; sp:=ch; endelse;opcodep:=fg;flag:=true;while (p0) and (opcodep=fg) do begin(2); p:=p-1; end;until flagend;procedure acbegins_left;p:=p+1;sp:= (3) ; end;procedure acs_right;begi

10、nopcodep:=0;if p=0 then begin wriwhile sp( don(error);halt(1)end;begin newexp:=newexp+sp;p:=p-1 end;p:=p-1;end; beginfor i:=1 to len do begincase ch of:A.Z,a.z:newexp:=newexp+ch;+,-,*,/,:acs_oprator;(:ac):ac end;end;while p0s_left;s_right;dobegin (4);(5) end;end;end;procedure prbegin;wrin(newexp,new

11、exp); end;main begininit; repeatreadln(expstr); len:=length(expstr);until len0;trans_exp;prend.;6.在 n 個不同元素中找出第 K 個最小元素。program search_k;var i,j,k:eger;a:array1.100 of procedure search(b,e: var i,m,t:eger;begineger;eger);if b=e then begin j:=b;exit end; i:=b;j:=e;m:=ak;repeatwhile (1)nc(i); while (2

12、)do dec(j);if(3)then beg until i=j;if i=k then exit;:=ai;ai:=aj;aj:=t;end;if ik then (4)else (5);end;procedure pr(n:eger);var i:begineger;for wri wri end;begini:=1 to n do write(ai, ); n;n(a,k,=,ak);write(n=);readln(n);write(a1.,n,=);for k:=1 to n do read(ak); readln; write(k=);readln(k); search(1,n

13、);pr(n);end.7.郵票問題：郵局一套票面有 4 種不同值的郵票，如果限制每封信貼的郵票過 3 枚。存在整數(shù) r，使得用不超過 3 枚的郵票可以貼出以下序列的整數(shù)值：1，2，3，,r編程求出可以得到盡可能大的r 的郵票面值。progarm st4;var s1,s2,s3,s4,r,r0,r1,r2,r3,r4:eger;st:set of 1.100;function work(s1,s2,s3,s4:eger): begin(1); for n1:=0 to 3 dofor n2:=0 to 3-n1 dofor n3:=0 to 3-n1-n2 do for n4:=0 to 3

14、-n1-n2-n3 doif n1+n2+n3+n4=3 thenbegineger;f:=n1*s1+n2*s2+n3*s3+n4*s4;st:=(2); end;f:=1;while f in st work:=f-1; end;begins1:=1;r0:=0;do (3);for s2:=s1+1 to 3*s1+1 do for s3:=s2+1 to 3*s2+1 dofor s4:=s3+1 to s*s3+1 dobegin r:=work(s1,s2,s3,s4); if(4)thenbegin r0:=r;r1:=s1;r2:=s2;r3:=s3;r4:=s4; end e

15、nd;n(r1:5,r2:5,r3:5,r4:5);n(r0=,r0);wri wriend.8.設計一個程序，把一個真分數(shù)表示為埃及分數(shù)之和的形式。所謂埃及分數(shù)，是指分子為 1 的形式。古代埃及有一個非常奇怪的，他們喜歡把一個分數(shù)表示為若干個分子為7/8=1/2+1/3+1/24。1的分數(shù)之和的形式。如，下面是一種貪心算法，由數(shù)學家（1）設某個真分數(shù)的分子為 A，分母為B；，基本是：把 B 除以 A 的商的整數(shù)部分加 1 后的值作為埃及分數(shù)的某一個分母c；將 A 乘以 C 減去 B 作為新的 A；將B 乘以 C 作為新的 B；如果 A 大于 1 且能整除 B，則最后一個分母為 B/A否則 如

16、果 A1，則最后一個分母為 B，否則轉步驟（2）。 program Egp_num;var a,b,c: beginrepeateger;write(a,b=);readln(a, b); until a 1 dobegin(1) ;a := a * c - b; b: = b * c; write(1/, c);IF (2)THEN write(+1/, b / a); IF (3)THEN write(+);end;(4);wriend.n9翻硬幣 （2003 高中組第一題，初中組第二題）題目描述：一摞硬幣共有 m 枚，每一枚都是正面朝上。取下最上面的一枚硬幣，將它翻面后放回原處。然后取下

17、最上面的 2 枚硬幣，將他們一起翻面后放回原處。在取 3 枚，取 4 枚直至 m 枚。然后在從這摞硬幣最上面的一枚開始，重復剛才的做法。這樣一直做下去，直到這摞硬幣中每一枚又是正面朝上為止。例如，m 為 1時，翻兩次即可。輸入：僅有的一個數(shù)字是這摞硬幣的枚數(shù) m ，0 m 1000。輸出：為了使這摞硬幣中的每一枚都是朝正面朝上所必須翻的次數(shù)。輸入樣例：30 程序：progrrogram1;輸出樣例：899varm:eger;function solve(m:eger):eger;var i,t,d:flag: begineger;if (m = 1) thensolve :=(1)else b

18、egind := 2*m+1; repeatif (t = 1) thenbegint := 2;i := 1;flag := False;solve := (2); endelse if (3) thenbeginflag := True;solve := i*m-1;endflag := True;elset :=(4); i:=i+1;until flag;endend; beginread(m); if (5) and (m=0) then beginnth:=nth-m1,k,s;if (yh) then(2) ;picy,x:=UP;y:=y+1;x:=x+1;draw(3); e

19、ndelse begin y:=y - 1; picy,x:=DN; x:=x+1; draw(k-1,s-1,nth); end;end;begininit;read(nth); for e:=0 to SZ-1 dofor f:=0 to SZ-1 dopice,f:= ;x:=0;y:=0;h:=0;i:=0;while (nth-m0,2*i,0)=0) dobeginnth:= nth-m0,2*i,0;(4);end;draw ( (5); for i:=h downto x-1 dobeginfor e:=0 to x-1 dowritend.ci,e);wrin( );end;

20、11降序組合給定兩個自然數(shù) n，r(nr)，輸出從數(shù) 1有如下組合：到 n 中按降序順序取 r 個自然數(shù)的所有組合。例如，n=5、r=3 時，5 4 35 4 25 43 24 3 14 2 13 2 1程序：program tk11; varn,r,i,j :eger;a : array1.20 of beginwrite(n,r=);repeat readln(n,r); i:=1; a1:=n; wri repeatif ir thenif ar-i then begin(1);endeger;until nr;n(result:);i:=i+1;else begin(2);a:=a-1

21、 end elsebeginfor j:=1 to r do write(aj:3); wrin;if ar=1 thenbegini:=i-1; a:=a-1; end end;until a1=r-1;end.else (3)12高速公路現(xiàn)在計劃在某個區(qū)域內(nèi)的的城市間架設高速公路，以使任意兩個城市間能夠直接或間接到達，怎樣修路，費用最小。輸入：第一行一個整數(shù) n(n=100)表示城市數(shù)目。第二行至第 n+1 行每行兩個數(shù) xi,yi(0=xi,yi=100)表示第 i 個城市的坐標(:千米)；輸出：最小費用(每千米一個程序：program tk12; const maxn=100;價格)。type tcity=recordx,y:real end;var c : array1.maxn of tcity;d : array1.maxn,1.maxn of real;p : array1.maxn of n , I , j , k :eger; a, min : real;beginreadln(n);eger;for i:=1 to n do readln(c.x,c.y); for i:=1 to n dofor j:=1 to n dodi,j:=sqrt(sqr(c.x-cj.x)+sqr