Đề thi lập trình khối b (trung học cơ sở) thời gian làm bài: 120 phút (không tính thời gian giao đề)

HỘI THI TIN HỌC TRẺ THÀNH PHỐ ĐÀ NẴNG 
LẦN THỨ XII - NĂM 2009
 Đề Thi Lập Trình Khối B (Trung học Cơ sở)
(Đề thi gồm có 2 trang)
 Thời gian làm bài: 120 phút
 (Không tính thời gian giao đề)
ĐỀ CHÍNH THỨC : 
Tổng quan đề thi
Bài 1
Bài 2
Bài 3
Bài 4Bài 2
Tên bài làm
BL1.PAS
BL2.PAS
BL3.PAS
BL4.PASXAU.PAS
Dữ ử liệu vào
Nhập từ bàn phím
Nhập từ bàn phím
RECT.INP
FIBO.INPXAU.INP
Dữ Dử liệu ra
In ra màn hình
In ra màn hình
RECT.OUT
FIBO.OUTXAU.OUT
Giới hạn
1 giây
1 giây
2 giây
2 giây1 giây
Tổng quan đề thi
Tên bài làm
BL1.PAS
BL2.PAS
BL3.PAS
Dữ liệu vào
Nhập từ bàn phím
Dữ liệu ra
In ra màn hình
Giới hạn
1 giây
1 giây
1 giây
Bài 1:(2,5 điểm) 
 Viết chương trình nhập vào từ bàn phím một số N nguyên dương 
(1<=N<327673276765535). In ra màn hình các thông tin sau:
a) Số cCác ước số nguyên dương của số N.
b) Tổng số các ước số nguyên dương của N.
Ví dụ: Nhập từ bàn phím N = 10
 In ra màn hình:
 	Co tat ca 4 uoc so 
 	Tong cac uoc la 18
Bài 2:( 2,52 điểm)
 Nhập từ bàn phím Cho một xâu kí ý tự S và một kýí tự tự K. 
 Hãy in ra màn hình số lượng kí tự K có trong xâu kí tự Sho biết trong xâu ký tự S có bao nhiêu ký tự K và các vị trí xuất hiện của kí tự K trong xâu Schúng . Nếu không có kí tự K trong xâu S thì in ra màn hình dòng thông báo: 
Khong co 
Dữ liệu vào : Cho trong file văn bản XAU.INP có cấu trúc như sau :
Dòng đầu tiên ghi chuỗi ký tự S.
Dòng thứ 2 ghi ký tự K.
Dữ liệu ra : Ghi vào file văn bản XAU.OUT gồm 2 dòng:
Dòng đầu tiên ghi 1 số là số ký tự K trong xâu ký tự S.
Dòng thứ 2 ghi các số là vị trí ký tự K trong xâu S.
Ví dụ:
Xâu kí tự S và kí tự K nhập từ bàn phímAU.INP
XAU.OUTIn ra màn hình 
KITHITINHOCTRETHANHPHOKITHITINHOCTRETHANHPHO
T
4
3 6 12 15
SOGIAODUC
M
Khong co
Bài 3:RECTANGLE RECTANGLE (27,5 điểm)
 Trên giấy kẻ ô khổ N x N có vẽ một số hình chữ nhật. Mỗi hình chữ nhật được tạo ra từ các ô nguyên vẹn, các hình chữ nhật khác nhau không chồng lên nhau và không tiếp xúc nhau (Ví dụ : Hình vẽ dưới đây có 4 hình chữ nhật).
Cho mảng A có kích thước N x N, trong đó A[i,j]=1 nếu ô [i,j] thuộc một hình chữ nhật nào đó, còn A[i,j] =0 trong trường hợp ngược lại.
Hãy viết chương trình xác định số các hình chữ nhật có trong bảng.
Dữ liệu vào: Từ File văn bản RECT.INP có cấu trúc như sau:
- Dòng đầu tiên ghi số nguyên dương N (N<=250).
- N dòng tiếp theo mỗi dòng ghi N số 0 hoặc 1 là các phần tử của mảng, mỗi số viết cách nhau ít nhất một dấu cáchkhoảng.trắng .
Dữ liệu ra: Ghi ra File văn bản RECT.OUT gồm duy nhất một số là số hình chữ nhật tìm được.
Ví dụ:
RECT.INP
RECT.OUT
4
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
0
7
1 0 0 0 0 0 0 
0 0 1 1 1 0 0 
1 0 1 1 1 0 0 
1 0 1 1 1 0 0 
0 0 0 0 0 0 0 
0 0 0 0 1 1 1 
0 0 0 0 1 1 1 
4
Bài 4:(3đ) FIBONACCI (7,5 điểm)
Dãy số Fibonacci được định nghĩa như sau:
U1 = U2 = 1; Un+1 = Un + Un-1 (với mọi số nguyên dương n, n > 1).
Như vậy, dãy số Fibonacci có dạng sau: 1, 1, 2, 3, 5, 8, 13, 21, 34,
	Với một số tự nhiên x bất kỳ khác 0 ta có thể phân tích thành tổng các số Fibonacci khác nhau (số số hạng của tổng có thể là từ 1 trở lên). Chẳng hạn x = 9, khi đó, ta có: 
9 = 1 + 8 hoặc 9 = 1 + 3 + 5
Trong hai cách phân tích trên thì cách thứ hai có số số hạng nhiều nhất (3 số hạng).
Yêu cầu: Cho trước một số nguyên dương x (x <= 10000). Hãy cho biết, nếu biểu diễn x thành tổng của các số Fibonacci khác nhau thì số số hạng nhiều nhất của một tổng là bao nhiêu?
Dữ liệu vào: Cho trong file văn bản FIBO.INP chỉ ghi một số nguyên dương x (x<=10000).
Dữ liệu ra: Ghi ra file văn bản FIBO.OUT gồm một số nguyên dương n duy nhất là số số hạng của tổng có số số hạng nhiều nhất trong các tổng.
Ví dụ:
FIBO.INP
FIBO.OUT
9
3
Chú ý: Đề thi gồm có 2 trang - Giám thị coi thi không được giải thích gì thêm
ĐÁP ÁN áP áNPHẦN LẬP TRÌNH
Bài 1:( 5 điểm) (Có 5 Test ứng với 5 giá trị của N, đúng mỗi Test cho 1 điểm. Không yêu cầu chính xác các từ trong câu trả lời , chủ yếu đúng số ước và tổng số các ước) 
Nhập N vào từ bàn phím :
Stt
N
Kết quả trên màn hình
1
510
Co tat ca 4 uoc so 
Tong cac uoc la 18-10 2
 10 3
2
507
Co tat ca 6 uoc so 
Tong cac uoc la 93 -2 3
 1 7
3
7079
Co tat ca 4 uoc so 
Tong cac uoc la Không có số âm lớn nhất
 6 2816 
4
500511
Co tat ca 16 uoc so 
Tong cac uoc la -3 6
 4 3 8064
5
32766
Co tat ca 16 uoc so 
Tong cac uoc la 67584
Bài 2:( 5 điểm) 
Có 2 5 bộ TEST chạy đúng mỗi bộ cho 12 điểm
Stt
Xâu kí tự S và kí tự K
In ra màn hình 
1
KITHITINHOCTRETHANHPHO
T
4
3 6 12 15
2
SOGIAODUC
M
Khong co
3
NGONGUPASCAL
A
2
8 11
4
BANADANANG
N
3
3 7 9
5
HOIANMYSON
O
2
2 9
Bài 3:( 7,5 điểm) 
Có 6 bộ TEST : 3 Test đầu chạy đúng mỗi bộ cho 1,5 điểm,3 Test cuối chạy đúng mỗi bộ cho 1 điểm
Stt
RECT.INP
RECT.OUT
1
3
 1 0 0 
 0 0 0 
 1 1 1
2
2
4
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
0
3
7
1 0 0 0 0 0 0 
0 0 1 1 1 0 0 
1 0 1 1 1 0 0 
1 0 1 1 1 0 0 
0 0 0 0 0 0 0 
0 0 0 0 1 1 1 
0 0 0 0 1 1 1 
4
4
15
1 1 1 0 0 0 0 0 0 0 0 0 0 1 1
1 1 1 0 0 0 0 0 0 0 0 0 0 1 1
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 1 1 1 1 1
6
5
Nội dung như File RECT5.INP
20
6
Nội dung như File RECT6.INP
125
Bài 4:( 7,5 điểm) 
Có 5 bộ TEST: Chạy đúng mỗi bộ cho 1,5 điểm.
Stt
FIBO.INP
FIBO.OUT
1
9
3
2
50
6
3
100
7
4
6763
17
5
9989
13
Stt
ANALYSE.INP
ANALYSE.OUT
1
5
8
50
818
10899
300425
1
2
1
0
6
2
5
900421
7000425
89800016
1500500692
2000000000
4
3
1
6
5
Bài 3:
Có 6 bộ TEST chạy đúng mỗi bộ cho 5 điểm
Stt
AREA.INP
AREA.OUT
1
0 4 16 4 16 0 0 0 4 4 8 0 15 4 10 0
24.00 26.00 14.00
2
0 4 16 4 16 0 0 0 4 4 10 0 15 4 8 0
27.38 18.62 0.62 17.38
3
-1 5 5 5 5 0 -1 0 0 5 0 0 1 5 3 0
5.00 10.00 15.00
4
-2 2 6 2 6 -3 -2 -3 -1 2 5 -3 1 2 3 -3
17.50 2.50 2.50 17.50
5
-3 4 2 4 2 -2 -3 -2 -1 4 -2 -2 0 4 1 -2
9.00 12.00 9.00
6
-3 4 2 4 2 -2 -3 -2 -1 4 1 -2 0 4 -2 -2
11.25 0.75 6.75 11.25