đề thi HSG tỉnh Nam Định-tin học lớp 9

SỞ GIÁO DỤC – ĐÀO TẠO
NAM ĐỊNH
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 THCS
Năm học 2006-2007
Môn: TIN HỌC
Thời gian làm bài: 150 phút
(không kể thời gian giao đề)


§Ò thi gåm 02 trang

Hä tªn thÝ sinh: . . . . . . . . . . . . . . . . . . . Ch÷ ký cña gi¸m thÞ 1: . . . . . . . . . .
Sè b¸o danh: . . . . . . . . . . . . . . . . . . . . . Ch÷ ký cña gi¸m thÞ 2: . . . . . . . . . .

LËp ch­¬ng tr×nh gi¶i c¸c bµi to¸n sau:
Bµi 1: BiÓu diÔn sè (7 điểm)
D·y sè Fibonaci F1, F2, .., Fn, .. ®­îc ®Þnh nghÜa qui n¹p nh­ sau:
F1 = F2 = 1;
Fn = Fn-1 + Fn-2 víi n>2
Yªu cÇu: Cho sè tù nhiªn S (S< 231), ph©n tÝch sè S thµnh tæng cña c¸c sè thuéc d·y Fibonaci vµ sè l­îng c¸c sè ®­îc dïng lµ Ýt nhÊt.
S = Fi1 + Fi2 + .. + Fik (1< i1< i2< .. < ik)
D÷ liÖu vµo tõ tÖp v¨n b¶n BDFIBO.INP: chøa duy nhÊt mét sè S.
D÷ liÖu ®­a ra tÖp v¨n b¶n BDFIBO.OUT: chøa hai dßng
Dßng 1: Chøa sè K lµ sè l­îng c¸c sè ®­îc dïng Ýt nhÊt t×m ®­îc.
Dßng 2: Chøa K sè theo thø tù t¨ng dÇn thÓ hiÖn chØ sè c¸c sè trong d·y Fibonaci t×m ®­îc (nÕu cã nhiÒu c¸ch th× chØ cÇn ®­a ra 1 c¸ch)
BDFIBO.INP
BDFIBO.OUT

10
2
3 6

VÝ dô vÒ d÷ liÖu vµo vµ d÷ liÖu ra




Bµi 2: ¶nh vÖ tinh (7 điểm)
§Ó kh¶o s¸t mét khu d©n c­ ng­êi ta ph©n tÝch sè liÖu tõ ¶nh chôp do vÖ tinh göi vÒ. Bøc ¶nh chôp cã kÝch th­íc NxM, ®­îc chia thµnh N hµng vµ M cét. Ta coi mçi ng«i nhµ cã d¹ng h×nh ch÷ nhËt. ¤ (i,j) lµ « thuéc dßng i cét j trong bøc ¶nh cã gi¸ trÞ 1 hoÆc 0 t­¬ng øng thuéc hoÆc kh«ng thuéc vµo mét ng«i nhµ. C¸c « trong cïng mét ng«i nhµ ®Òu cã gi¸ trÞ b»ng 1. BiÕt r»ng c¸c ng«i nhµ kh«ng cã phÇn trïng nhau cã nghÜa là 2 « thuéc vµo 2 ng«i nhµ kh¸c nhau kh«ng kÒ c¹nh. Tõ mét bøc ¶nh cho tr­íc, em h·y cho biÕt diÖn tÝch cña ng«i nhµ lín nhÊt trong bøc ¶nh (mçi « lµ mét ®¬n vÞ diÖn tÝch).
D÷ liÖu vµo tõ tÖp v¨n b¶n NHA.INP cã cÊu tróc
Dßng 1 chøa 2 sè N vµ M (N vµ M nguyªn d­¬ng vµ nhá h¬n 100).
Trong N dßng tiÕp theo, mçi dßng chøa M sè 0 hoÆc 1. Sè thø j cña dßng i thÓ hiÖn gi¸ trÞ cña « (i,j).
D÷ liÖu ®­a ra tÖp v¨n b¶n NHA.OUT chøa mét sè duy nhÊt lµ diÖn tÝch ng«i nhµ lín nhÊt t×m ®­îc.
VÝ dô vÒ d÷ liÖu vµo vµ d÷ liÖu ra
NHA.INP
NHA.OUT

3 5
0 1 1 0 1
0 1 1 0 1
0 0 0 1 0
4







Bµi 3: D·y t¨ng dÇn (6 điểm)
Ta gäi d·y sè X1, X2, . . . Xk lµ d·y t¨ng dÇn nÕu víi mäi gi¸ trÞ cña i (0Cho mét d·y sè tù nhiªn. H·y xo¸ khái d·y ®· cho mét sè phÇn tö vµ gi÷ nguyªn thø tù cña c¸c phÇn tö cßn l¹i ®Ó ®­îc mét d·y t¨ng dÇn cã sè phÇn tö lín nhÊt.
D÷ liÖu vµo tõ tÖp v¨n b¶n TANGDAN.INP cã cÊu tróc
Dßng 1 chøa sè N lµ sè phÇn tö cña d·y sè ban ®Çu (0Dßng 2 chøa N sè tù nhiªn cña d·y ban ®Çu theo ®óng thø tù (c¸c sè ®Òu nhá h¬n 200).
D÷ liÖu ®­a ra tÖp v¨n b¶n TANGDAN.OUT chøa mét sè duy nhÊt lµ sè c¸c phÇn tö ®­îc gi÷ l¹i mµ ®¶m b¶o d·y t¨ng dÇn cã sè phÇn tö lín nhÊt.
VÝ dô vÒ d÷ liÖu vµo vµ d÷ liÖu ra
TANGDAN.INP
TANGDAN.OUT

6
3 8 5 7 9 12
5
(chØ bá sè 8)





Chú ý: File chương trình của bài 1 đặt tên là BDFIBO.PAS.
của bài 2 đặt tên là NHA.PAS.
của bài 3 đặt tên là TANGDAN.PAS.

HÕt

 SỞ GIÁO DỤC – ĐÀO TẠO ĐÁP ÁN VÀ HƯỚNG DẪN CHẤM
NAM ĐỊNH ĐỀ THI CHỌN HỌC SINH GIỎI
-------- Năm học 2006-2007
Môn : TIN HỌC Lớp 9
ChÊm bµi b»ng c¸c test, ch­¬ng tr×nh kh«ng ch¹y hoÆc d÷ liÖu vµo ra kh«ng phï hîp sÏ kh«ng ®­îc ®iÓm. Tr­êng hîp sai tªn tÖp ch­¬ng tr×nh hoÆc tÖp d÷ liÖu vµo ra th× söa l¹i cho ®óng, chÊm b×nh th­êng, trõ 2 ®iÓm mçi bµi.
Bµi 1: BiÓu diÔn sè 7 ®iÓm
- T¹o K sè Fibonaci vµ l­u vµo m¶ng F, sè thø K lµ sè lín nhÊt mµ kh«ng lín h¬n S.
- M¶ng X cã N phÇn tö, chøa chØ sè cña c¸c sè Fibonaci xuÊt hiÖn trong c¸ch biÓu diÔn theo thø tù gi¶m dÇn.
i:=0;
While S>0 do
Begin i:=i+1; while F[k] > S do k:=k-1; X[i]:=k; S:=S-F[k]; End
- In gi¸ trÞ cña m¶ng X theo thø tù ng­îc l¹i.
ChØ chó ý khi xö lý sè lín, sè Fibo thø 47 lµ v­ît qua ph¹m vi longint
(dïng m¶ng sè thùc ®Ó l­u lµ tèt nhÊt) vµ kh«ng dïng F[1]
Bµi 2: ¶nh vÖ tinh 7 ®iÓm
NhËp d÷ liÖu vµo m¶ng X. Phñ thªm c¸c gi¸ trÞ 0 ra bªn ngoµi.
For i:=1 to N do
For j:=1 to M do
If X[i,j]=1 then
Begin d:=i; c:=j;
Whlie X[d,j]=1 do d:=d+1;
Whlie X[i,c]=1 do c:=c+1;
For a:=i to d do for b:=j to c do X[a,b]:=0;
If Max<(d-i)*(c-j) then Max:=(d-i)*(c-j);
End
Bµi 3: D·y t¨ng dÇn 6 ®iÓm
Dïng ph­¬ng ph¸p quy ho¹ch ®éng
-NhËp d÷ liÖu vµo m¶ng X (kiÓu byte)
- Dïng m¶ng F ®Ó tÝnh theo quy ho¹ch (kiÓu integer)
F[1]:=1;
For i:=2 to N do
Begin Max:=0;
For j:=1 to i-1 do
If X[j]<=X[i] Then If Max F[i]:=Max+1;
End;
KQ:=1;
For i:=2 to N do If KQ