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

1、阅读程序写结果专题三分析,练习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

2、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 *

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,组合数定义 ：从

4、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.

5、输出：_,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）。

6、从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 3 3 7 12 19 输出： 1,分析：本题可分解成以下两部分： 从n个数中任取k个数的组合 因为n=20，所以可以用穷举实现。用数组a1,a2,ak记录每种组合中各数的下标，a

7、0是循环开关，初始时a0=0，当a0=1时穷举结束。当选用前面的输入样例，n=4，k=3时，a0a3的变化如下表所示,结合上表仔细分析，我们可以总结出aj的变化范围是: jn-(k-j,输入： 4 3 3 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

8、 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,var i,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; begin readln(n); m(n); writeln(j)

9、; 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

10、:=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 d

11、o 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：=

12、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

13、; 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

14、 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; begin readln(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 do begin l1:=l0-k; if (l10) then l1:=l1+n; if (l1=lk

15、) 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; begin readln(p,n,q); j :=21; while (n0)do begin j:=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)do begin j:=j-1; aj:=s mod q; s:=s div q;end; for i:=j to 20 d