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

阅读程序写结果专题三分析,练习1,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 :array05 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 3 3 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 3 3 7 12 19,K-j表示第j位后面还要填的数字个数；,n-(k-j)表示在n个数中倒数第几大的数,var i,j,s:integer; b :array05 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,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); 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=array1n*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,var a，t：string； i，j：integer； begin a：=morning；j：= 1； for i：=2 to 7 do if (ajai)then j：= i； j：= j-1； for i：=1 to j do write (ai)； end 输出：,mo,练习7,var i,j,k:integer; a: array0100of 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 020 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) 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 :array120of 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 do write(ai);