Ky thi chon hoc sinh gioi câp tinh lơp 9 THCS môn Tin học

SỞ GIÁO DỤC ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS BÌNH ĐỊNH KHÓA NGÀY: 18-3-2015

ĐỀ CHÍNH THỨC Môn thi: TIN HỌC Thời gian: 150 phút (không kể thời gian phát đề) Ngày thi: 18/3/2015

Tổng quan bài thi:

Bài Tên bài Tên tệp chương trình

Tên tệp dữ liệu vào

Tên tệp dữ liệu ra

1 Liên phân số LIENPS.PAS Nhập từ bàn phím

Xuất trên màn hình 2 Số nguyên tố cùng nhau NTCN.PAS NTCN.INP NTCN.OUT 3 Tìm đường hái quả HAIQUA.PAS HAIQUA.INP HAIQUA.OUT

Bài 1: Liên phân số (7,0 điểm):

Số hữu tỉ dương a/b luôn được biểu diễn dưới dạng một liên phân số hữu hạn:

n q

q q q b a

1 ...

1 1 1

2

1

0

    

Liên phân số này ký hiệu là [q0,q1,q2,...,qn], trong đó q00; q1,q2,...,qn là những số nguyên dương; qn>1; n gọi là độ dài của liên phân số.

Hãy viết chương trình biến đổi một phân số a/b thành liên phân số hữu hạn. Dữ liệu vào là hai số nguyên dương a, b nhập từ bàn phím để biểu diễn phân số a/b. Dữ liệu ra là một dòng gồm các số q0,q1,q2,...,qn biểu diễn dạng liên phân số của phân số a/b. Các số viết cách nhau ít nhất một khoảng cách.

Ví dụ:

Input Output a=7 b=5

1 2 2

Bài 2: Số nguyên tố cùng nhau: (7,0 điểm):

Hai số nguyên dương được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1.

Cho N số nguyên dương A1,A2,...,AN. Gọi M là giá trị lớn nhất trong các số A1,A2,...,AN. Viết chương trình tìm số nguyên dương X lớn nhất không vượt quá M mà X nguyên tố cùng nhau với tất cả các số A1,A2,...,AN.

Dữ liệu vào là tệp NTCN.Inp có cấu trúc như sau: - Dòng đầu là số nguyên dương N (N100). - N dòng tiếp theo, mỗi dòng chứa một giá trị tương ứng A1,A2,...,AN (Ai1000;i=1,2,...,N). Dữ liệu ra là tệp NTCN.Out chứa số nguyên X tìm được thỏa mãn điều kiện của bài toán. Ví dụ:

NTCN.Inp NTCN.Out 3 4 12 15

13

ThuVienDeThi.com

Bài 3: Tìm đường hái quả (6,0 điểm):

Một khu vườn hình chữ nhật kích thước MxN được chia thành các ô vuông đơn vị để trồng một loại cây ăn quả. Trên mỗi ô thì số quả tương ứng có thể hái được là A[i,j] (1iM; 1jN). Một người khách dạo qua vườn và hái tất cả các quả trên những ô đi qua. Vị trí xuất phát từ ô [1,1] và kết thúc tại ô [M,N] với hành trình là sang ô chung cạnh theo hướng tăng của i hoặc j (sang phải hoặc đi xuống – như hình vẽ). Hãy viết chương trình tìm lộ trình đi của người đó để hái được nhiều quả nhất.

1 3 5 7 2

7 9 4 2 2

2 3 1 6 7

7 4 6 2 5

Dữ liệu vào là tệp HAIQUA.INP có cấu trúc như sau: - Dòng đầu tiên là hai số M, N nguyên dương cách nhau một khoảng cách (0<M,N<100). - M dòng tiếp theo, mỗi dòng gồm N số tương ứng là số quả có thể hái được ở các ô theo thứ tự tại hàng thứ i. Mỗi số cách nhau một khoảng cách. Dữ liệu ra là tệp HAIQUA.OUT cso cấu trúc như sau: - Dòng đầu là số quả lớn nhất có thể hái được theo một lộ trình thỏa mãn yêu cầu. - Dòng tiếp theo gồm M+N-1 số tương ứng là số quả hái ở từng ô theo đường đi để được số quả nhiều nhất. Mỗi số cách nhau ít nhất một khoảng cách. Ví dụ:

HAIQUA.INP HAIQUA.OUT 4 5 1 3 5 7 2 7 9 4 2 2 2 3 1 6 7 7 4 6 2 5

41 1 7 9 4 2 6 7 5

ThuVienDeThi.com