S GIO DC O TO
NAM NH
THI CHN HC SINH GII LP 9 THCS
Nm hc 2006-2007
Mụn: TIN HC
Thi gian lm bi: 150 phỳt
(khụng k thi 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 im)
Dãy số Fibonaci F
1
, F
2
, .., F
n
, .. đợc định nghĩa qui nạp nh sau:
F
1
= F
2
= 1;
F
n
= F
n-1
+ F
n-2
với n>2

10 2
3 6
CHNH THC
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
Bài 3: Dãy tăng dần (6 im)
Ta gọi dãy số X
1
, X
2
, . . . X
k
là dãy tăng dần nếu với mọi giá trị của i
(0<i<k ) đều thoả mãn X
i
X
i+1
.
Cho 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.

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à lu 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 để lu 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