Kỳ thi chọn học sinh giỏi cấp tỉnh 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:
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
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
Bài giải tham khảo:
Câu 1: LienPS.Pas:
Uses 	Crt;
Var 	q:Array[1..100] of Word;
 	a,b,i,k:Word;
Function Uc(x,y:Word):Word;
Var r:Word;
Begin
 	While y0 do Begin	r:=x mod y;	x:=y;y:=r;End;
Uc:=x;
End;
Procedure Psrg;
Var m:Word;
Begin
m:=Uc(a,b);
a:=a div m;
b:=b div m;
End;
Procedure Xuli;
Begin
k:=0;
Repeat
If a>b then Begin q[k]:= a div b; a:= a mod b; End
 Else Begin q[k]:= b div a; b:= b mod a;End;
inc(k);
Until (a=1) or (b=1);
If a1 then q[k]:=a Else q[k]:=b;
 For i:=0 to k do Write(q[i],' ');
 End;
Begin
Clrscr;
Repeat
Write('Nhap a: '); Readln(a); Write('Nhap b: '); Readln(b);
Until (a>0) and (b>0);
Psrg;
If a<=b then Write(0,' ',b) Else Xuli;
Readln
End.
Câu 2: NTCN.Pas:
Uses	Crt;
Type 	mmc=Array[1..100] of Word;
Const 	fi='D:\Ntcn.Inp'; 
 	fo='D:\Ntcn.Out';
Var	i,n,m:Byte;
a:mmc;
f,g:Text;
Function	Uc(x,y:Word):Boolean;
Var r:Word;
Begin
While y0 do Begin r:=x mod y; x:=y; y:=r; End;
 If x=1 then Uc:=True Else Uc:=False;
End;
Function mUc(c:mmc;k:Byte;m:Word):Boolean;
Var	i:Byte;
kt:Boolean;
Begin
Kt:=True;
For i:=1 to k do Kt:=(Uc(m,c[i]) and Kt);
mUc:=Kt;
End;
Function	Max(c:mmc;k:Byte):Word;
Var 	i:Byte;
m:Word;
Begin
m:=a[1];
For i:=2 to k do If m<a[i] then m:=a[i];
 Max:=m;
End;
Begin
 	Assign(f,fi);
Reset(f);
Readln(f,n);
For i:=1 to n do
Readln(f,a[i]);
Close(f);
 	m:=Max(a,n)-1;
Assign(g,fo);
Rewrite(g);
Repeat
If mUc(a,n,m) then Begin Write(g,m); Close(g); Exit; End Else dec(m);
Until m=0;
End.
Câu 3: Haiqua.Pas:
Uses	Crt;
Const	fi='D:\Haiqua.Inp';
fo='D:\Haiqua.Out';
Type m2c=Array[1..100,1..100] of Word;
mmc=Array[1..100] of Word;
Var	i,j,k,m,n,max:Byte;
a:m2c;
b:mmc;
f,g:Text;
Begin
Assign(f,fi); Reset(f); Readln(f,m,n);
For i:=1 to m do
Begin
For j:=1 to n do Read(f,a[i,j]);
Readln(f);
 End;
Close(f);
 	max:=a[1,1];
k:=1;	i:=1;	j:=1;
fillchar(b,sizeof(b),0);
b[1]:=max;
 	While (i<=m) and (j<=n) do
Begin
inc(k);
If a[i+1,j]>a[i,j+1] then Begin inc(i); max:=max+a[i,j]; b[k]:=a[i,j]; End
Else
Begin
 If a[i+2,j]>a[i,j+2] then Begin inc(i); max:=max+a[i,j]; b[k]:=a[i,j]; End
 Else inc(j); 
 max:=max+a[i,j]; b[k]:=a[i,j];
End;
End;
 	Dec(k);
Assign(g,fo);
Rewrite(g);
 	Writeln(g,max);
For i:=1 to k do Write(g,b[i],' ');
Close(g);
End.
{ Lưu ý: 
1. Chưa Test đủ các trường hợp:	a[i+h,j] và a[i,j+k] (1<h<M-1;1<k<N-1);
1
3
5
7
2
7
9
4
2
2
2
3
9
6
7
7
4
6
2
5
	2. Trường hợp đầu bài chưa chặt chẽ: Giới hạn số quả tại mỗi A[i,j].
1
3
99
7
2
7
9
4
2
2
2
3
1
6
7
7
99
6
2
5