ĐỀ THI ĐÁP ÁN HSG MÔN TIN 2010-2011

SỞ GIÁO DỤC VÀ ĐÀO TẠO
HÀ TĨNH


ĐÁP ÁN ĐỀ THI CHỌN HỌC SINH GIỎI TỈNH
LỚP 11 THPT - NĂM HỌC 2010 - 2011

Môn thi: Tin học



Bài 1: Dãy con lớn nhất
Ý tưởng thuật toán:
Duyệt hết tất cả các dãy con và tìm tổng của chúng. Đưa ra dãy con có tổng lớn nhất.
Thuật toán:
Đọc N và dãy số A[1],A[2],...,A[N] từ tệp dữ liệu vào.
mmax:=0;
For i:=1 to N do
For j:=1 to N do
Begin
s:=0; {s là tổng của dãy con đang xét, có kiểu dữ liệu là Longint}
For k:=i to j do
s:=s+A[k];
If s>mmax then
Begin
mmax:=s; {mmax là tổng lớn nhất của các dãy con đã xét. Nếu s > mmax }
imax:=i; {thì cập nhật giá trị mmax mới là s và ghi nhận chỉ số đầu và cuối của}
jmax:=j; {dãy lớn nhất hiện tại phục vụ cho việc truy xuất kết quả}
End;
End;
End;
Bài 2: Robot công nghiệp
Ý tưởng thuật toán:
Thực chất của bài toán là kiểm tra xem với 1 xâu S cho trước gồm N (N chẵn và N≤24) các ký tự in hoa có phải là xâu đối xứng và có khác nhau theo từng cặp đối xứng hay không?
Thuật toán:
- Đọc N và xâu S từ tệp dữ liệu vào.
- Kiểm tra nữa đầu xâu S xem các ký tự có khác nhau hay không? Nếu nữa đầu xâu mà các ký tự không khác nhau từng đôi một thì đưa ra kết luận xâu S không phải là lệnh của Robot và dừng thuật toán.
For i:=1 to (N div 2)-1 do
Begin
dem:=0;
For j:=i+1 to N div 2 do
If S[i]=S[j] then
Begin
Inc(dem);
If dem<>0 then
Begin
Write(f,`KHONG`);
Close(f);
Halt;
End;
End;
End;
- Nếu nữa đầu xâu S có các ký tự khác nhau từng đội một thì ta kiểm tra tính đối xứng của xâu S (việc kiểm tra tính đối xứng của xâu S bao gồm cả việc kiểm tra các ký tự có khác nhau từng đôi một của nữa sau của xâu S: Bởi vì nếu nữa sau của xâu S không khác nhau từng đôi một thì sẽ không đảm bảo tính đối xứng của xâu S).
Để kiểm tra tính đối xứng của xâu S, ta kiểm tra xem với mọi giá trị của i từ 1 tới N thì S[i] có bằng S[N-i+1] hay không? Nếu có thì kết luận xâu S là lệnh của Robot, nếu không thì kết luận xâu S không phải là lệnh của Robot.
dem:=0;
For i:=1 to N do
If S[i]=S[N-i+1] then Inc(dem);
If dem=N then Writeln(f,`CO`)
else Write(f,`KHONG`);

Bài 3: Tạo sơn tổng hợp
Ý tưởng thuật toán:
Thực chất của bài toán là liệt kê tất cả các tổ hợp chập M của N phần tử.
Thuật toán:
Sử dụng thuật toán đệ quy quay lui.
Procedure Tao_tu(i:Integer);
Var j:Integer;
Begin
For j:=1 to N do
If B[j] then {Nếu số j chưa được chọn thì ...}
Begin
B[j]:=False; {Nếu số j đã được chọn thì B[j]:=False}
C[i]:=j;
If i=M then
Begin
viet; {Ghi ra tệp SON.OUT các giá trị của C[k] với k=1..M}
Inc(dem);
End
Else tao_tu(i+1);
B[j]:=True; {Trả lại trạng thái ban đầu của j – Quay lui}
End;
End;
Trong chương trình chính thực hiện:
Nhập N, M từ bàn phím.
Khởi tạo B[j]=True với mọi j=1..N.
Gọi thủ tục Tao_tu(1).