Đề thi học sinh giỏi cấp trường Môn: Tin học 11

 Trường THPT Nguyễn Huệ
	 Năm học 2007 - 2008
Đề thi học sinh giỏi cấp trường
Môn: Tin học 11
Thời gian làm bài: 150 phút
(Vòng 1)
Câu 1. Viết chương trình đọc tệp có tên là SN.Dat chứa 100 số nguyên được chia thành 10 hàng 10 cột mỗi số có giá trị tuyệt đối không vượt quá 1000. Đưa ra màn hình các yêu cầu sau:
Các số nguyên tố (nếu có trong tệp), mối hàng chỉ được phép in 10 số mỗi số cách nhau 3 dấu cách.
Các số hoàn hảo (nếu có trong tệp), mỗi hàng cũng chỉ được phép in 10 số mỗi số cách nhau 3 dấu cách.
Kết quả đưa vào tệp có tên là: KQ.INF dòng đầu là các số nguyên tố dòng thứ 2 là các số hoàn hảo.
 (Biết rằng số hoàn hảo là số mà tổng các ước của nó bằng chính nó VD 6 = 3+2+1 vậy số 6 là số hoàn hảo)
Câu 2. Một tệp có tên là BINARY.DAT có chưa một dãy số nhị phân được viết liền nhau(số nhị phân là số chỉ chứa 0 hoặc 1 và không vượt quá 32 số). Viết chương trình đọc tệp trên và đưa kết quả ra màn hình là số thập phân tương ứng.
VD: BINARY.DAT ghi : 101011111100000011111 Kết quả: 1439775
Câu 3. Trong hệ trục toạ độ Oxy cho N đường tròn bằng nhau có các tâm O1, O2,, ON , bán kính R. Hệ đường tròn trên được gọi là chuẩn nếu nếu các đường tròn trên đôi một không chồng lên nhau(hai đường tròn có thể tiếp xúc nhau) 
Viết chương trình kiểm tra hệ đường tròn có chuẩn hay không?
Dữ liệu: cho trong File INP.DAT
+ Dòng 1: ghi số N là số lượng đường tròn và bán kính R.
+ N dòng tiếp theo mỗi dòng ghi hai số nguyên xi và yi là toạ độ của Oi
Dữ liệu là các số nguyên, các số nghi trên cùng một dòng cách nhau ít nhất 1 dấu cách.
- INP.DAT 	 Kết quả:
 5 3 Hệ đường tròn chuẩn:
 0 0 
 0 6
 10 20
 -8 3
 -2 -10
Ví dụ:
- INP.DAT Kết quả:
4 10 Hệ không chuẩn
0 0 
1 1
10 10
-9 7
======================= Hết ======================
Học sinh làm bài trên máy tính, mỗi câu một chương trình riêng, sao chép vào đĩa mềm nộp cho giám thị.
 Trường THPT Nguyễn Huệ
	 Năm học 2007 - 2008
Đề thi học sinh giỏi cấp trường
Môn: Tin học 11
Thời gian làm bài: 150 phút
(Vòng 2)
Câu 1. Xâu S chỉ bao gồm các kí tự ngoặc mở ‘(‘ và ngoặc đóng ‘)’ xâu S xác định một các đặt ngoặc đúng, nếu thoả mãn một trong các điều kiện sau:
Số ngoặc mở bằng số ngoặc đóng 
Nếu duyệt từ trái sang phải, số lượng ngoặc mở luôn lớn hơn hoặc bằng số lượng ngoặc đóng.
Ví dụ : xâu S= ‘( ( ( ) ( ( ) ) ) )’ xác định là cách đặt ngoặc là đúng. Còn xâu 
S= ‘( ( ) ( ) ) ) ( ( ) )’ xác định là cách đặt ngoặc là sai ở ví trí thứ 7.
Hãy viết đoạn chương trình kiểm tra xâu S có được đặt ngoặc đúng hay không nếu không đúng thì đưa ra ví trị sai trong xâu.
Xâu S nhập từ bàn phím./
Câu 2. Người ta xâu N viên đá quý kích thước giống nhâu thành một vòng đeo cổ, mỗi viên có một màu trong số các màu được đánh số từ 1 đến 9. Để tăng tính độc đáo cho vòng trang sức quý này, người ta định lắp khoá đeo vào vị trí sao cho khi mở vòng ta được một dây đá quý có tính chất: không phụ thuộc vào việc cầm đầu dây nào bên tay phải và đầu kia bên tay trái, ta đều được một chuỗi hạt giống nhau, tức là viên đá thứ i từ trái sang luôn có màu j không phụ thuộc vào cách cầm.
Xâu S: 2 2 2 2 2 2 3 3 5 5 3 3 
2
2
2
2
2
2
3
3
5
5
3
3
2
2
2
3
3
2
2
2
2
2
2
2
2
2
3
3
5
3
3
5
5
5
3
3
Cách đặt khoá thứ 1:
Cách đặt khoá thứ 2:
Câu 3. Viết chương trình đưa ra tất cả các hoán vị của N số 1, 2, 3, , N với N (N10) nhập từ bàn phím.
 VD: Với N=3 ta có: 
HV1: 1 2 3
HV2 : 2 1 3
HV3 : 1 3 2
HV4: 3 1 2
HV5 : 3 2 1
HV6 : 2 3 1 
-------------------------Hết -------------------------
Học sinh làm bài trên máy tính, mỗi câu một chương trình riêng, sao chép vào đĩa mềm nộp cho giám thị.
Trường THPT Nguyễn Huệ
Năm học 2007 - 2008
Đề thi chọn học sinh giỏi cấp trường
 Môn: Tin học 11
Thời gian làm bài: 150 phút
Câu 1. Viết chương trình đọc tệp có tên là SN.Dat chứa 100 số nguyên được chia thành 10 hàng 10 cột mỗi số có giá trị tuyệt đối không vượt quá 1000. Đưa ra màn hình các yêu cầu sau:
Các số nguyên tố (nếu có trong tệp), mối hàng chỉ được phép in 10 số mỗi số cách nhau 3 dấu cách.
Các số hoàn hảo (nếu có trong tệp), mỗi hàng cũng chỉ được phép in 10 số mỗi số cách nhau 3 dấu cách.
Kết quả đưa vào tệp NT.DAT nếu là các số nguyên tố, đưa vào tệp HH.DAT nếu là số hoàn hảo. Trên các tệp này mỗi dòng ghi 10 số.
 (Biết rằng số hoàn hảo là số mà tổng các ước của nó bằng chính nó VD 6 = 3+2+1 vậy số 6 là số hoàn hảo)
Câu 2. Người ta xâu N viên đá quý kích thước giống nhâu thành một vòng đeo cổ, mỗi viên có một màu trong số các màu được đánh số từ 1 đến 9. Để tăng tính độc đáo cho vòng trang sức quý này, người ta định lắp khoá đeo vào vị trí sao cho khi mở vòng ta được một dây đá quý có tính chất: không phụ thuộc vào việc cầm đầu dây nào bên tay phải và đầu kia bên tay trái, ta đều được một chuỗi hạt giống nhau, tức là viên đá thứ i từ trái sang luôn có màu j không phụ thuộc vào cách cầm.
Xâu S: 2 2 2 2 2 2 3 3 5 5 3 3 
2
2
2
2
2
2
3
3
5
5
3
3
2
2
2
3
3
2
2
2
2
2
2
2
2
2
3
3
5
3
3
5
5
5
3
3
Cách đặt khoá thứ 1:
Cách đặt khoá thứ 2:
Yêu cầu: 
Nhập dữ liệu vào từ bàn phím số lượng hạt kim cương thứ tự các hạt để xâu vào chuỗi hạt.
Tìm vị trí có thể để đặt khoá thoả mãn yêu cầu trên.
Câu 3. Trong hệ trục toạ độ Oxy cho N đường tròn bằng nhau có các tâm O1, O2,, ON , bán kính R. Hệ đường tròn trên được gọi là chuẩn nếu nếu các đường tròn trên đôi một không chồng lên nhau(hai đường tròn có thể tiếp xúc nhau) 
Viết chương trình kiểm tra hệ đường tròn có chuẩn hay không?
Dữ liệu: cho trong File INP.DAT
+ Dòng 1: ghi số N là số lượng đường tròn và bán kính R.
+ N dòng tiếp theo mỗi dòng ghi hai số nguyên xi và yi là toạ độ của Oi
Dữ liệu là các số nguyên, các số nghi trên cùng một dòng cách nhau ít nhất 1 dấu cách.
- INP.DAT 	 Kết quả:
 5 3 Hệ đường tròn chuẩn:
 0 0 
 0 6
 10 20
 -8 3
 -2 -10
Ví dụ:
- INP.DAT Kết quả:
4 10 Hệ không chuẩn
0 0 
1 1
10 10
-9 7
--------------------------------------- Hết ------------------------------------
Giám thị không giải thích gì thêm
Học sinh làm trên máy tính mỗi câu một chương trình và lưu vào đĩa mền.
Đề thi chọn học sinh giỏi trường
Năm học 2007 – 2008
---------------------------------
Đáp án và biểu điểm
Câu 1. 6đ
Khai báo các biến hợp lệ, tổ chức đọc dữ liệu từ tệp đúng, song kết quả còn sai : 1đ
Đọc tệp SN.DAT đưa ra các số nguyên tố trên màn hình và ghi vào tệp NT.DAT : 2,5đ
Đọc tệp SN.DAT đưa ra các số hoàn hảo trên màn hình và ghi vào tệp HH.DAT : 2,5đ
Câu 2. 7đ
 Khai báo các biến hợp lệ, nhập được dữ liệu từ bàn phím, song kết quả còn sai : 2đ
Chỉ ra được các vị trí đặt khoá : 5đ
Câu 3. 7 đ
Khai báo các biến hợp lệ, tổ chức đọc dữ liệu từ tệp đúng, song kết quả còn sai : 2đ
Thuật toán bằng NNLT Pascal thể hiện thuật toán cho kết quả đúng : 5 đ
Lời giả cụ thể cho các bài toán như sau:
(Các bài toán được viêt trên NNLT Pascal)
Bài 1: 
Program bai1;
Uses Crt;
Var A,b,c: Array[1..100] of integer;
 N,i,j ,M,t,tong,k,l : Integer;
 f1,f,f2: text;
 	Begin clrscr;
 Assign(f,'C:\sn.dat');
reset(f);
Readln(f,N,M);
i:=0;
{$I+};
if IOresult 0 then halt;
for i:=1 to N do
 Begin
 for j:=1 to M do
 read(f,a[(i-1)*N+j]);
 readln(f);
 End;
 close(f);
 Assign(f1,'C:\HH.dat');
 rewrite(f1);
 t:=0;
 WRITELN('KET QUA DOC TEP:');
 For i:=1 to N do
 Begin
 for j:=1 to M do
 Begin tong:=0;
 write(A[(i-1)*N+j]:3);
 for k:=1 to A[(i-1)*N+j]-1 do
 if A[(i-1)*N+j] mod k =0 then tong:=tong+k;
 if tong=A[(i-1)*N+j] then
 begin
 t:=t+1;
 c[t]:=A[(i-1)*N+j] ;
 write(f1,c[t]:5);
 if t mod 10 =0 then writeln(f1);
 end;
 end;
 writeln;
 End;
 Writeln('CAC SO HOAN HAO LA');
 Assign(f2,'C:\NT.dat');
 rewrite(f2);
 for i:=1 to t do
 begin
 Write(c[i]:3);
 if i mod 10 = 0 then writeln;
 end; l:=0;
 For i:=1 to N do
 Begin
 for j:=1 to M do
 if abs(A[(i-1)*N+j])>1 then
 Begin
 t:=2;
 k:= TRUNc(SQRT(A[(i-1)*N+j]));
 While (A[(i-1)*N+j] mod t0)and (t<=k) do
 t:=t+1;
 if t>k then
 begin
 l:=l+1;
 B[l]:=A[(i-1)*N+j] ;
 write(f2,B[l]:2);
 if l mod 10 =0 then writeln(f2);
 end;
 end;
 End;
 Writeln('CAC SO NGUYEN TO LA:');
 for i:=1 to L do
 begin
 write(b[i]:3);
 if i mod 10 = 0 then writeln;
 end;
 close(f1);
 close(f2);
Readln
End.
Bài 2.
Program cau2;
Uses crt;
Var A:array[1..50] of string;
 ct:array[1..9]of byte;
 i,j,n:byte; s,p:string[120]; h:string[240];
Begin
 clrscr;
 write('So vien da quy: '); readln(n);
 write('So chi thi mau: '); readln(s);
 h:=s+s;
 for i:=1 to 2*n do
 begin a[i]:=copy(h,i,n);
 h:=s+s; end;
 writeln('cac vi tri co then lap:');
 for j:=1 to 2*n do
 begin p:='';
 for i:=n downto 1 do p:=p+a[j][i];
 if p=a[j] then writeln('giua ',j-1,' va ',j);
 end;
 readln
end.
Bài 3.
Program bai_3;
Uses Crt;
Var 	n: Byte;
	R,i,j : Integer;
	C: Array[1..2,1..100] of integer;
Procedure nhap;
Var 	f: text;
Begin 
 	Assign(f, ‘INP.Dat’);
	Reset(f);
	Readln(f,n,R);
	Fillchar(C,sizeOf(C),0);
	For i:=1 to N do 
Readln(f, C[1,i], C[2,i]);
Close(f);
End;
Funtion Kiemtra: Boolean;
Begin
	Clrscr;
	Kiemtra:=false;
	If sqr(C[1,i] – C[2,i]) + sqr(C[1,i] – C[2,j])<4*R*R then exit;
	Kiemtra:=true;
End;
Begin
	Nhap;
	IF kiemtra then Writeln(‘He duong tron chuan’)
	Else Writeln(‘He duong tron khong chuan’);
	Readln;
End.
-------------------------------------------------------------------------------------------------------------------