Kỳ thi học sinh giỏi toàn tỉnh năm học 2006-2007 đề thi và đáp án đề thi môn thi: tin học - ngôn ngữ lập trình

SỞ GIÁO DUC VÀ ĐÀO TẠO TT .HUẾ TRƯỜNG THPT HAI BÀ TRƯNG š› KỲ THI HỌC SINH GIỎI TOÀN TỈNH NĂM HỌC 2006-2007 Đề thi và đáp án đề thi Môn thi: Tin học - Ngôn ngữ lập trình Giáo viên ra đề: Hoang Phước Lộc I. Đề thi: Bài toán 1 : Di chuyển từ Tây sang Đông trên lưới ô vuông. Phát biểu: Cho hình chữ nhật A gồm m x n ô vuông, mỗi ô chứa một số nguyên. Có thể di chuyển từ một ô sang ô thuộc cột bên phải cùng dòng hoặc chênh lệch một dòng. Tìm cách di chuyển từ một ô nào đó thuộc cột 1 đến một ô nào đó thuộc cột n sao cho tổng các số của các ô đi qua là nhỏ nhất. Dữ liệu vào: Có thể cho ở file Input.bt1. Trong đó hàng đầu tiên chứ 2 số m và n, m hàng tiếp theo, mỗi hàng chứa n chữa số của ma trân trọng số. Bài toán 2 : Tìm xâu chung cực đại. Cho 2 xâu bất kỳ, viết chương trình in ra tất cả các xâu chung và cuối cùng thông báo xâu chung cực đại của hai xâu đã cho. Dữ liệu vào: Có thể cho ở file Input.bt2. Trong đó dòng thứ nhất chứa xâu thứ nhất, dòng thứ 2 chứa xâu thứ 2. II. Đáp án: Bài 1: (5 điểm), trong đó: Phân tích bài toán: - Gọi P(r, s) là bài toán di chuyển từ Tây sang Đông, với: r Î N*: Số dòng của hình chử nhật. s Î N*: số cột của hình chử nhật. - Bài toán ban đầu là P(p, n)) - Các giá trị cần tìm: F[r,s]: giá trị Nhỏ nhất của các số trên các ô đi qua của bài toán P(r, s) Giải pháp đệ quy: - Khi s = 1: F[r, 1] = A[r,1] - Khi s > 1: F[r, s] = min { F[r-1,s-1],F[r,s-1],F[r+1,s-1]} +A[r,s] a) Thủ tục đọc dữ liệu: 1điểm Thủ tục lập bảng: 2 điểm Procedure Lapbang; Var i,j,d: byte; Begin For j:=0 to n do A[0,j]:=Maxint; For j:=0 to n do A[m+1,j]:=Maxint; Fillchar(t,siseof(t),0); For j:=2 to n do For i:=1 to m do Begin d:=min(i,j); A[i,j]:=A[d,j-1]+A[i,j]; T[I,j]:=d; End; End; Thủ tục Tổng hợp kết quả: 2 điểm Procedure Ketqua; Var i,j,d: byte; p:integer; Begin p:=maxint; For i:=1 to m do If a[i,n]<p then Begin d:=i; p:=a[i,n] End; i:=n; i:=d; kq[j]:=d; while j>0 do Begin i:= t[i,j]; j:=j-1; kq[j]:=i; End; End; Bài 2: (5 điểm), trong đó: Thủ tục đoc dữ liệu: 1 điểm. Thủ tục tìm xâu chung: 3 điểm. Thủ tục Thông báo kết quả: 1 điểm. program Xau_chung_cuc_dai; uses crt, Strings; var T1, T2, T : string; i, l1, l2 : byte; {-------Chuong trinh con-----------} {---------Thu tuc khoi tao---------} procedure Init(var T1, T2 : String; var l1, l2 : byte); begin Write(' Nhap xau T1 : '); Readln(T1); l1:=length(T1); Writeln; Write(' Nhap xau T2 : '); Readln(T2); l2:=length(T2); end; {---------Thu tuc Hien thi---------} procedure Show_result(T : String); begin Writeln; Writeln(' Xau chung cuc dai la : ', T); end; {-----Ham tra ve xau lon hon trong 2 xau------} function Max(S1, S2 : String) : String; begin if (length(S1) > length(S2)) then Max:=S1 else Max:=S2; end; {----- Ham tim xau chung cuc dai---} function Xau_chung(i : byte) : String; var S : String; k, bg, mem : byte; begin if (i < 1) then Xau_chung:='' else begin {Tim xau chung S cua hai xau T2 va xau con cua T1 bat dau tai vi tri i} S:=''; mem:=1; for k:=i to l1 do begin bg:=mem; while (bg <= l2) do begin if (T1[k] = T2[bg]) then begin S:=S + T2[bg]; mem:=bg+1; break; end; inc(bg); end; end; Writeln(' Xau_chung(',i,') co xau chung la : ',S); Xau_chung:= Max(S,Xau_chung(i-1)); end; end; {----------------------------------} begin clrscr; Init(T1,T2,l1,l2); T:=Xau_chung(l1); Show_result(T); readln; end.