当前位置:首页 >> 学科竞赛 >> 全国青少年信息学奥林匹克联赛

全国青少年信息学奥林匹克联赛


阅读程序写结果专题三分析

练习1

var i, s, max: integer;
a :array [1..10] of integer; begin for i:=1 to 10 do read (a[i]);

max:=a[1] ;s:=a[1];
for i:=2 to 10 do b

egin if s<0 then s:=0; s:= s+a[i]; if s>max 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;

组合数定义 s1:=10*9/2 :从n个不同元素中取出r(r≤n)个元素的 co(2) S1=45 所有组合的个数。

co(3) co(4)

s1:=10*9/2 *8/3

S1=120 S1=210

begin

S1:= 2*3*4*5 s1:=n; 5! =10 for j1:= (n-1) downto (n-i1+1) do 2!*(5-2)! 10*9*8*7*6*5 co(6) S1:= 2*3*4*5*6 s1:= s1*j1 div (n-j1+1);
co(5)
co:=s1 end;

s1:=10*9/2 *8/3 *7/4 例: 从A、B、C、D、E五个球中任取2个有多少种方案? 10*9*8*7*6 S1=252 S1=210

co(7) co(8) co(9)

S1:= S1:= S1:=

10*9*8*7*6*5*4 2*3*4*5*6*7

S1=120
S1=45 S1=10 S1=1

begin s:=n+1; for i:= 2 to n do s:=s + co(i); writeln(‘s=’,s);

10*9*8*7*6*5*4*3 2*3*4*5*6*7*8 10*9*8*7*6*5*4*3*2 2*3*4*5*6*7*8*9

end.

co(10) S1:= 10*9*8*7*6*5*4*3*2*1 2*3*4*5*6*7*8*9*10

1024 输出:_____________

练习3

var i,j,s:integer; 6 7 b :array[0..5] of integer; 0 1 2 begin s:=1; 0 1 2 for i:=1 to 5 do b[i]:=i; j:=1; 1 2 while j>0 do begin j:=5; 6 7 while (j>0) and (b[j]=10+j-5) do j:=j-1; if j>0 then begin s:=s+1; b[j]:=b[j]+1; for i:=j+1 to 5 do b[i]:=b[j]+i-j end; end; writeln('s=',s); end. 252 输出:___________

8

9

10

3 3 3

4 4 5 4

5 10 5 10 9 8 7 6 5

8

9

10

第二种枚举(利用while循环产生排列串)
最大值 4-(3-j) 1
a[0]

2
a[1]

3
a[2]

4
a[3]

1 0

1 2

3 2

4 3

j

j

j

j

for i:=0 to k do a[i]:=i;

while

a[0]

do

begin j:=k; while a[j]=n-(k-j) do j:=j-1; a[j]:=a[j]+1; for i:=j+1 to k do a[i]:=a[i-1]+1;

end;

例6.选数(NOIP2002初中组复赛第二题)

问题描述:
已知n(1<=n<=20)个整数x1,x2,…,xn(1<=xi<=5000000),以及一个整数k (k<n)。从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 输出:一个整数(满足条件的组合个数) 样例

输入:
43 3 7 12 19 输出:

1

分析:本题可分解成以下两部分:
① 从n个数中任取k个数的组合 因为n<=20,所以可以用穷举实现。用数组a[1],a[2],…,a[k]记录每种组合中

各数的下标,a[0]是循环开关,初始时a[0]=0,当a[0]=1时穷举结束。当选用前
面的输入样例,n=4,k=3时,a[0]~a[3]的变化如下表所示: a[0] a[1] 1 1 1 2 2 a[2] 2 2 3 3 3 a[3] 3 4 4 4 4 生成的组合 3 7 12 3 7 19 3 12 19 7 12 19 循环结束

输入: 43 3 7 12 19

0 0 0 0 1

结合上表仔细分析,我们可以总结出a[j]的变化范围是: j~n-(k-j)
K-j表示第j位后面还要填的数字个数; n-(k-j)表示在n个数中倒数第几大的数

var i,j,s:integer; 6 7 8 9 10 b :array[0..5] of integer; 0 1 2 3 4 5 begin s:=1; 10 0 1 2 3 4 5 5 10 9 8 7 6 for i:=1 to 5 do b[i]:=i j:=1; 1 2 3 4 5 while j>0 do begin j:=5; 6 7 8 9 10 while (j>0) and (b[j]=10+j-5) do j:=j-1; if j>0 then begin 从10个不同的球中任取 s:=s+1; b[j]:=b[j]+1; 5个有多少种方案? for i:=j+1 to 5 do b[i]:=b[j]+i-j end; 10! =252 end; 5!*(10-5)! writeln('s=',s); end. 252 输出:___________

练习4

var i,j,n:longint;

procedure m(s:longint);
var i:longint; begin
1 2
m(1) j=1 m(2) j=3 m(3) j=5 m(4) j=9 m(1) j=2 m(1) j=4 m(1) m(1)j=6 m(1)j=7

for i:=1 to s div 2 do m(i);
j:=j+1; end;
m(8)

3
4

begin
readln(n); m(n); end. 输入:8 输出:___________ writeln(j);
j=10

m(2)
j=8

练习5

const n=4; type se=array[1..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(a[i]); readln; s:=0; t:=0; for i:=1 to n*2 do if a[i]='1' then s:=s+1 else if a[i]='0' then t:=t+1; if (s<>n) or (t<>n) then writeln('error') else begin … end; end. 输入:10101100

输出:___________

s1:=0; for i:=1 to 2*n-1 do for i:=1 to 2*n-1 do for j:=i+1 to 2*n do if a[i]<>a[j] then begin temp:=a[i];a[i]:=a[j] ;a[j]:=temp; s:=0; if a[i]<>a[i+1] then s1:=s1+1;

输入:10101100 jamp=5 10101010

writeln('jamp=',s1); swap:=0;

maxswap=2 i=6 j=7

for l:=1 to 2*n-1 do
if a[l]<>a[l+1] then s:=s+1; if s>swap then begin swap:=s; i1:=i; j1:=j; temp:=a[i]; a[i]:=a[j]; a[j]:=temp end; if swap>0 then end;

writeln('maxswap=',swap-s1,' i=',i1,' j=',j1)

练习6

var
begin

a,t:string;

i,j:integer;

a:=`morning`;j:= 1;

for i:=2 to 7 do
j:= j-1; for i:=1 to j do end. 输出: mo
1

if (a[j]<a[i])then
write (a[i]);

j:= i;

2

3

4

5

6

7

m j

o j i

r j i

n i

i i

n

g

i

i

练习7

var

i,j,k:integer; a: array[0..100]of integer; begin for i:=0 to 100 do a[i]:=i; 1 2 3 4 5 6 7 8 9 10 for k:=5 downto 2 do begin 11 12 13 14 15 16 17 18 19 20 for i:=1 to 100 do 21 22 23 24 25 26 27 28 29 30 if ( i mod k)=0 then a[i]:=0; 31 32 33 34 35 36 37 38 39 40 for i:=1 to 99 do for j:=1 to 100-i do 41 42 43 44 45 46 47 48 49 50 if a[j]>a[j+1]then begin 51 52 53 54 55 56 57 58 59 60 a[j]:=a[j]+a[j+1]; 61 62 63 64 65 66 67 68 69 70 a[j+1]:=a[j]-a[j+1]; a[j]:=a[j]-a[j+1]; 71 72 73 74 75 76 77 78 79 80 end; 81 82 83 84 85 86 87 88 89 90 end; 91 92 93 94 95 96 97 98 99100 j:=1; while (a[j]=0)and (j<100)do j:=j+1; for i:=j to 100 do a[0]=a[0]+a[i]; writeln(a[0]); end. 本题的运行结果是: 970

练习8

var i,j,k,n,,l0,l1,lk:integer; 0 1 2 3 4 a :array [0..20] of integer; 1 2 9 10 1 3 4 5 7 8 begin readln(n,k); for i:=0 to n-1 do a[i]:=i+1; a[n]:=a[n-1]; l0:=n-1; lk:=n-1; for i:=1 to n-1 do begin l1:=l0-k; if (l1<0) then l1:=l1+n; if (l1=lk) then begin a[l0]:=a[n]; lk:=lk-1; a[n]:=a[lk]; l0:=lk end; else begin a[l0]:=a[l1];l0:=l1; end; end; a[l0]:=a[n]; for i:=0 to n-1 do write(a[i]:4); writeln; end.
输入:10 4 输出:________________

5

6

7

8

9

10

6 2

7 3

4 8

9 5

6 9 10 10

n=10 k=4

i 1 2

l0 9 5 1 7 3 8 4 0 6 2

lk 9 9 9 9 9 8 8 8 8

l1 0 5 1 7 3 9 4 0 6 2

3
4 5 6 7

8 9

8

练习9

Var I,j,p,n,q,s:integer;
a :array[1..20]of integer; begin … 16 17 3 18 0 19 5 20 1

readln(p,n,q); j :=21;
while (n>0)do begin j:=j-1; a[j]:=n mod 10; n:=n div 10; end; s:=0; for i:=j t0 20 do s:=s*p+a[i];

writeln(s); j :=21;
while (s>0)do begin j:=j-1; a[j]:=s mod q; s:=s div q;end;

for i:=j to 20 do write(a[i]);readln;
end.

1065 输入:7 3051 8 输出:2051

练习10

var a,x,y,ok1,ok2:integer; begin a:=100; x:=10; y:=20; ok1:=5; ok2:=0; if ((x>y) or ((y<>20) and (ok1=0)) and (ok2<>0)) then a:=1 else if ((ok1<>0) and (ok2=0)) then

a:=-1
else a:=0; writeln(a); end.


更多相关文档:

1995-2012历年全国青少年信息学奥林匹克联赛初赛试题(包括答案)。

第七届全国青少年信息学(计算机)奥林匹克分区联赛试题(普及组参考答案) 一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题 1.5 分,多选无分,共 30...

全国青少年信息学奥林匹克联赛大纲

全国青少年信息学奥林匹克联赛大纲发布日期: 2006-02-10 访问总次数: 954 一、总则由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛(National Olympiad in ...

全国青少年信息学奥林匹克联赛初赛讲义

全国青少年信息学奥林匹克联赛初赛讲义_学科竞赛_高中教育_教育专区。全国青少年信息学奥林匹克联赛初赛讲义全国青少年信息学奥林匹克联赛初赛复习讲义 2011-09-14 12:04...

NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及组试题及答案)

NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及组试题及答案)_学科竞赛_高中教育_教育专区。NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及...

第二十届全国青少年信息学奥林匹克联赛初赛

第二十届全国青少年信息学奥林匹克联赛初赛_电脑基础知识_IT/计算机_专业资料。2014第二十届全国青少年信息学奥林匹克联赛初赛普及组Pascal语言试题 ...

18届全国青少年信息学奥林匹克联赛初赛(详解)(普及组)

第十八届全国青少年信息学奥林匹克联赛初赛 (普及组 Pascal 语言试题) 竞赛时间:2012 年 10 月 13 日 14:30~16:30 选手注意 · 试题纸共有 10 页,答题纸...

全国青少年信息学奥林匹克联赛初赛试题2009-2015

第十五届全国青少年信息学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一. 单项...

全国青少年信息学奥林匹克联赛

全国青少年信息学奥林匹克联赛_学科竞赛_高中教育_教育专区。全国青少年信息学奥林匹克联赛 noip 即 全国青少年信息学奥林匹克联赛全国青少年信息学奥林匹克联赛(Nat...

全国青少年信息学奥林匹克联赛大纲

全国青少年信息学奥林匹克联赛大纲(节选)NOIP 大纲 一、 总则 由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛(NOIP)是全国信息学奥林匹克竞赛 (NOI)整个...

第二十一届(2015)全国青少年信息学奥林匹克联赛初赛试题(含答案)

第二十一届(2015)全国青少年信息学奥林匹克联赛初赛试题(含答案)_学科竞赛_高中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言...
更多相关标签:
全国青少年普法网 | 信息学奥林匹克联赛 | 信息学奥林匹克竞赛 | 信息学奥赛培训 | 信息学奥赛辅导 | 国际信息学奥林匹克 | 青少年信息学奥林匹克 | 国际奥林匹克数学竞赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com