中学noi初赛练习之四完成程序题新新

1、中学 NOI 初赛练习之四（完成程序题）如何做完成程序题：每年的信息学分区初赛的最后一部分都是完成程序题，一般是两道题总分 28。这是最能体现你阅读理解程序水平的部分。有许多问题可能自己能编写出程序，但完成程序首先要求你在理解题意的基础上读懂给定的算法和数据结构，这样才能填写出相关内容。对于这一类题目，往往要先多读几遍题意，理解要实现什么，然后是理程序中的数据结构、变量含义，最后才去考虑填什么语句。这类试题常常让大家填的是：1、初始化(i:=0; j:=0; for i:=1 to n do ai:=0 之类的) 2、一些明显的动作：（1）（2）（3）结果没有在需要的地方。累加器没有做加法输出

2、3、关键动作。在算法描述中出现的比较关键的步骤。例如交换排序程序的“交换”操作等很明显需要完成的操作。分析方法和写运行结果类似，注意分析变量和程序结构，理解变量和模块的作用是解题的关键。完成程序练习题：1、下面的程序从键盘接受任意 6 个数放入数组a 中，设这 6 个数为：8 1 4 2 5 6，则可输出一个具有如下内容的方阵：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.在下列程序中，当输入一个给定的数 N 后，能输出所有不超过N 的、其平方由左右对称的数字组成的数。 如：N=23，则输出：1 2 3 11 22 。它们的平方依次是：1 4 9 121 484，都是左右对称的数字组成的数。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.下面过程实现将数组 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、验证回文数猜想：一个数的倒置数还是它自己，这个数就是回文数。任一个数（196 除外），如果它不是回文数，把它和它的倒置数相加，得到一个新数，如果是回文数即结束，如果不是重复上过程，总能得到一个回文数。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 枚。存在整数 r，使得用不超过 3 枚的邮票可以贴出以下序列的整数值：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.设计一个程序，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为 1 的形式。古代埃及有一个非常奇怪的，他们喜欢把一个分数表示为若干个分子为7/8=1/2+1/3+1/24。1的分数之和的形式。如，下面是一种贪心算法，由数学家（1）设某个真分数的分子为 A，分母为B；，基本是：把 B 除以 A 的商的整数部分加 1 后的值作为埃及分数的某一个分母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时，翻两次即可。输入：仅有的一个数字是这摞硬币的枚数 m ，0 m 1000。输出：为了使这摞硬币中的每一枚都是朝正面朝上所必须翻的次数。输入样例：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降序组合给定两个自然数 n，r(nr)，输出从数 1有如下组合：到 n 中按降序顺序取 r 个自然数的所有组合。例如，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高速公路现在计划在某个区域内的的城市间架设高速公路，以使任意两个城市间能够直接或间接到达，怎样修路，费用最小。输入：第一行一个整数 n(n=100)表示城市数目。第二行至第 n+1 行每行两个数 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