全国青少年信息学奥林匹克联赛阅读程序训练及答案.ppt

阅读程序写结果专题三分析,练习1,var i,s,max:integer;a：array 1.10 of integer;begin for i:=1 to 10 do read(ai);max:=a1；s:=a1;for i：=2 to 10 do begin if smax then max：=s end;writeln(max=,MAX)end.输入：8 9-1 24 6 5 11 15-28 9输出：max=,77,输入：2 3-6-1 1 2 3-9 4 6输出：max=,10,本质是求一个n长的整数数列的连续子序列的和最大！,练习2,const n=10;var s,i:integer;function co(i1:integer):integer;var j1,s1:integer;begin s1:=n;for j1:=(n-1)downto(n-i1+1)do s1:=s1*j1 div(n-j1+1);co:=s1 end;begin s:=n+1;for i:=2 to n do s:=s+co(i);writeln(s=,s);end.输出：_,1024,co(2),s1:=10*9/2,co(3),s1:=10*9/2*8/3,co(4),s1:=10*9/2*8/3*7/4,S1=45,S1=120,S1=210,co(5),S1:=,10*9*8*7*6,2*3*4*5,S1=252,co(6),S1:=,10*9*8*7*6*5,2*3*4*5*6,S1=210,co(7),S1:=,10*9*8*7*6*5*4,2*3*4*5*6*7,S1=120,co(8),S1:=,10*9*8*7*6*5*4*3,2*3*4*5*6*7*8,S1=45,co(9),S1:=,10*9*8*7*6*5*4*3*2,2*3*4*5*6*7*8*9,S1=10,co(10),S1:=,10*9*8*7*6*5*4*3*2*1,2*3*4*5*6*7*8*9*10,S1=1,组合数定义：从n个不同元素中取出r(rn)个元素的所有组合的个数。,例：从A、B、C、D、E五个球中任取2个有多少种方案？,练习3,var i,j,s:integer;b:array0.5 of integer;begin s:=1;for i:=1 to 5 do bi:=i;j:=1;while j0 do begin j:=5;while(j0)and(bj=10+j-5)do j:=j-1;if j0 then begin s:=s+1;bj:=bj+1;for i:=j+1 to 5 do bi:=bj+i-j end;end;writeln(s=,s);end.输出：_,252,10,9,8,7,6,6,7,8,9,10,5,6,7,8,9,10,for i:=0 to k do ai:=i;while a0 do begin j:=k;while aj=n-(k-j)do j:=j-1；aj:=aj+1;for i:=j+1 to k do ai:=ai-1+1;end;,最大值 4-(3-j)1 2 3 4,3,2,1,3,4,0,1,2,第二种枚举(利用while循环产生排列串),例6选数（NOIP2002初中组复赛第二题）问题描述：已知n（1=n=20）个整数x1,x2,xn（1=xi=5000000），以及一个整数k（kn）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k=3，4个整数分别为3，7，12，19时，可得到的全部组合及它们的和为3+7+12=22,3+7+19=29,7+12+19=38,3+12+19=34。现在，要求你计算出和为素数的组合共有多少种。如上例中，只有一种组合的和为素数：3+7+19=29。输入：n,k x1，x2，xn输出：一个整数(满足条件的组合个数)样例输入：4 33 7 12 19输出：1,分析：本题可分解成以下两部分：从n个数中任取k个数的组合因为n=20，所以可以用穷举实现。用数组a1,a2,ak记录每种组合中各数的下标，a0是循环开关，初始时a0=0，当a0=1时穷举结束。当选用前面的输入样例，n=4，k=3时，a0a3的变化如下表所示：,结合上表仔细分析，我们可以总结出aj的变化范围是:jn-(k-j),输入：4 33 7 12 19,K-j表示第j位后面还要填的数字个数；,n-(k-j)表示在n个数中倒数第几大的数,var i,j,s:integer;b:array0.5 of integer;begin s:=1;for i:=1 to 5 do bi:=i j:=1;while j0 do begin j:=5;while(j0)and(bj=10+j-5)do j:=j-1;if j0 then begin s:=s+1;bj:=bj+1;for i:=j+1 to 5 do bi:=bj+i-j end;end;writeln(s=,s);end.输出：_,252,10,9,8,7,6,6,7,8,9,10,5,6,7,8,9,10,从10个不同的球中任取5个有多少种方案？,练习4,vari,j,n:longint;procedure m(s:longint);var i:longint;begin for i:=1 to s div 2 do m(i);j:=j+1;end;beginreadln(n);m(n);writeln(j);end.输入：8输出：_,m(8),1,2,3,4,m(1)j=1,m(2),m(1)j=2,j=3,m(3),m(1)j=4,j=5,m(4),m(1),m(1)j=6,m(2),m(1)j=7,j=8,j=9,j=10,练习5,const n=4;type se=array1.n*2 of char;var i,j,i1,j1,k,s,t,s1,l,swap:integer;temp:char;a:se;begin for i:=1 to n*2 do read(ai);readln;s:=0;t:=0;for i:=1 to n*2 do if ai=1 then s:=s+1 else if ai=0 then t:=t+1;if(sn)or(tn)then writeln(error)else begin end;end.输入：10101100 输出：_,s1:=0;for i:=1 to 2*n-1 do if aiai+1 then s1:=s1+1;writeln(jamp=,s1);swap:=0;for i:=1 to 2*n-1 do for j:=i+1 to 2*n do if aiaj then begin temp:=ai;ai:=aj;aj:=temp;s:=0;for l:=1 to 2*n-1 do if alal+1 then s:=s+1;if sswap then begin swap:=s;i1:=i;j1:=j;end;temp:=ai;ai:=aj;aj:=temp end;if swap0 then writeln(maxswap=,swap-s1,i=,i1,j=,j1),输入：10101100,jamp=5,10101010,maxswap=2 i=6 j=7,练习6,vara，t：string；i，j：integer；begina：=morning；j：=1；for i：=2 to 7 do if(ajai)thenj：=i；j：=j-1；for i：=1 to j do write(ai)；end 输出：,mo,练习7,var i,j,k:integer;a:array0.100of integer;begin for i:=0 to 100 do ai:=i;for k:=5 downto 2 do begin for i:=1 to 100 do if(i mod k)=0 then ai:=0;for i:=1 to 99 do for j:=1 to 100-i do if ajaj+1then begin aj:=aj+aj+1;aj+1:=aj-aj+1;aj:=aj-aj+1;end;end;j:=1;while(aj=0)and(j100)do j:=j+1;for i:=j to 100 do a0=a0+ai;writeln(a0);end.本题的运行结果是:,970,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99100,练习8,var i,j,k,n,l0,l1,lk:integer;a:array 0.20 of integer;beginreadln(n,k);for i:=0 to n-1 do ai:=i+1;an:=an-1;l0:=n-1;lk:=n-1;for i:=1 to n-1 dobegin l1:=l0-k;if(l10)then l1:=l1+n;if(l1=lk)then begin al0:=an;lk:=lk-1;an:=alk;l0:=lk end;else begin al0:=al1;l0:=l1;end;end;al0:=an;for i:=0 to n-1 do write(ai:4);writeln;end.输入:10 4 输出:_,9,9,0,n=10 k=4,5,6,5,9,1,2,1,9,7,8,7,9,3,4,3,9,9,10,8,8,9,4,5,4,8,0,1,0,8,6,7,6,8,2,3,2,8,9,练习9,Var I,j,p,n,q,s:integer;a:array1.20of integer;beginreadln(p,n,q);j:=21;while(n0)do beginj:=j-1;aj:=n mod 10;n:=n div 10;end;s:=0;for i:=j t0 20 do s:=s*p+ai;writeln(s);j:=21;while(s0)dobegin j:=j-1;aj:=s mod q;s:=s div q;end;for i:=j to 20 do write(ai);readln;end.输入:7 3051 8 输出:,1065,2051,1,5,0,3,练习10,var a,x,y,ok1,ok2:integer;begin a:=100;x:=10;y:=20;ok1:=5;ok2:=0;if(xy)or(y20)and(ok1=0)and(ok20)then a:=1 else if(ok10)and(ok2=0)then a:=-1 else a:=0;writeln(a);end.,