Đề thi chọn HSG

HỘI THI TIN HỌC TRẺ TỈNH VĨNH LONG LẦN THỨ 13 NĂM 2011
ĐỀ THI THỰC HÀNH KHỐI TRUNG HỌC CƠ SỞ
Thời gian làm bài: 90 phút (không kể phát đề)

(Qui ước lưu bài thi: các bài làm của thí sinh khi lưu vào đĩa đặt tên theo dạng B1_xxx.pas, B2_xxx.pas, B3_xxx.pas. Trong đó B1, B2, B3 lần lượt là Bài 1, Bài 2, Bài 3; còn xxx là số báo danh. Ví dụ: B1_025.pas, B2_025.pas, B3_025.pas).

(Đề thi có 2 trang, gồm 3 bài)

Bài 1: Dãy số Fibonacci (3 điểm)
Dãy Fibonacci là dãy số F0, F1, F2, …, Fn, … có tính chất:
F0 = 1;
F1 = 1;
Fk = Fk-1 + Fk-2 (với mọi k ≥ 2)
Ví dụ: Với n = 5, ta có dãy 1, 1, 2, 3, 5, 8
Yêu cầu: Cho trước số n, hãy lập trình tính số hạng Fn của dãy Fibonacci.
Dữ liệu: Vào từ bàn phím là số n (0 ≤ n ≤ 45). Nếu nhập số n ngoài phạm vi cho phép có thông báo nhắc nhở và cho nhập lại.
Kết quả: In lên màn hình một số duy nhất là số hạng Fn tìm được.
Ví dụ:
Dữ liệu vào
Kết quả

N = 3
3

N = 50
Nhap so n khong hop le! Xin nhap lai

N = 5
8


Bài 2: Xâu con (3 điểm)
Cho hai xâu X và Y. Ta định nghĩa xâu con như sau: Xâu Y được gọi là xâu con của xâu X nếu trong xâu X ta xóa đi một số kí tự thì sẽ thu được xâu Y (số kí tự xóa có thể bằng 0).
Ví dụ: Cho xâu X = ‘1A2B3CD4EF5G’ và xâu Y = ‘12345’, ta nói Y là một xâu con của xâu X vì trong xâu X nếu xóa các kí tự ở những vị trí 2, 4, 6, 7, 9, 10, 12 thì sẽ thu được xâu Y.
Yêu cầu: Cho trước hai xâu X và Y, hãy kiểm tra xem xâu Y có là xâu con của xâu X không? Nếu có, thì chỉ ra những vị trí nào trong xâu X cần xóa kí tự để thu được xâu Y.
Dữ liệu: Vào từ tập tin văn bản XAUCON.INP gồm hai dòng:
Dòng thứ nhất là xâu X (không quá 200 kí tự);
Dòng thứ hai là xâu Y (không quá 200 kí tự).
Kết quả: Ghi ra tập tin văn bản XAUCON.OUT gồm:
Dòng dầu ghi ‘CO’ nếu xâu Y là xâu con của xâu X, ngược lại ghi ‘KHONG’;
Nếu dòng đầu là ‘CO’ thì các dòng tiếp theo ghi danh sách các vị trí trong xâu X cần xóa kí tự để thu được xâu Y hoặc ghi 0 nếu không cần xóa bất kì kí tự nào trong xâu X.
Ví dụ:
XAUCON.INP
XAUCON.OUT

HTOIINTHHIOLCATTRHUE13
TINHOCTRE
CO
1
3
5
7
9
10
12
14
16
18
19
21
22

HOITHITINHOCTRE
THCS
KHONG


ABCD
ABCD
CO
0


Bài 3: Vòng số nguyên tố (4 điểm)
Một vòng tròn chứa 2*n vòng tròn nhỏ (xem hình vẽ). Các vòng tròn nhỏ được đánh số từ 1 đến 2*n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến 2*n vào 2*n vòng tròn nhỏ, mỗi số điền vào một vòng tròn nhỏ, sao cho tổng của hai số trong hai vòng tròn nhỏ liên tiếp nhau là sô nguyên tố. Vòng tròn thứ nhất luôn luôn điền số 1.















Yêu cầu: Cho trước số n, hỏi có bao nhiêu cách điền số thỏa yêu cầu nêu trên?
Ví dụ cho trước n = 3, ta có 2 cách điền là:
1 6 5 2 3 4
1 4 3 2 5 6
Dữ liệu: Vào từ bàn phím là số n (1 < n < 10).
Kết quả: In ra màn hình một số duy nhất là số lượng các cách điền số tìm được.
Ví dụ:
Dữ liệu vào
Kết quả

2
2

3
2

4
4



HẾT

Thí sinh không sử dụng tài liệu;
Giám thị không giải thích gì thêm.