Tài liệu Skkn những bài tập xử lí mảng một chiều và xử lí xâu

SỞ GD - ĐT BẠC LIÊU TRƯỜNG THPT VÕ VĂN KIỆT TỔ: TIN - KTCN CHUYÊN ĐỀ: “NHỮNG BÀI TẬP XỬ LÍ MẢNG MỘT CHIỀU VÀ XỬ LÍ XÂU” (TÀI LIỆU BỒI DƯỠNG HSG) Giáo viên: NGUYỄN VĂN DƯỢC Lĩnh vực nghiên cứu: Phương pháp dạy học Năm học 2014 - 2015 SƠ LƯỢC LÝ LỊCH KHOA HỌC I. THÔNG TIN CHUNG VỀ CÁ NHÂN: 1. Họ và tên: Nguyễn Văn Dược 2. Ngày tháng năm sinh: 1985 3. Quê quán: Ấp Long Đức, thị trấn Phước Long, Phước Long, Bạc Liêu 4. Nơi cư trú: Ấp Long Đức, thị trấn Phước Long, Phước Long, Bạc Liêu 5. Điện thoại cá nhân: 0919653311 6. Chức vụ: giáo viên II. TRÌNH ĐỘ ĐÀO TẠO: - Trình độ chuyên môn, nghiệp vụ: Đại học - Năm nhận bằng: 2007 - Chuyên ngành đào tạo: Sư phạm Toán – Tin học III. KINH NGHIỆM KHOA HỌC: - Lĩnh vực chuyên môn có kinh nghiệm: giảng dạy - Số năm kinh nghiệm: 8 Phần 1: ĐẶT VẤN ĐỀ - Trong cấu trúc đề thi học sinh giỏi cấp tỉnh môn tin học lớp 10, 11, 12 nhiều năm qua luôn có những dạng bài tập xử lí mảng một chiều và xử lí xâu, ở bộ môn này nội dung chủ yếu sử dụng để thi học sinh giỏi vòng tỉnh chỉ có ở lớp 11. Tuy nhiên với mức độ kiến thức trong sách giáo khoa cơ bản chưa đủ kiến thức để sử dụng trong việc bồi dưỡng học sinh giỏi. - Tôi viết đề tài NHỮNG BÀI TẬP XỬ LÍ MẢNG MỘT CHIỀU VÀ XỬ LÍ XÂU nhằm hệ thống hóa toàn bộ kiến thức về mảng một chiều và xâu với mức độ nâng cao để giáo viên và học sinh sử dụng trong khi luyện học sinh giỏi. - Trong thời gian hiện tại, chưa có đề tài hay sáng kiến kinh nghiệm nào công bố về nội dung này trong các phương tiện thông tin, tạp chí khoa học. Thông qua đề tài này tôi muốn giới thiệu với các thầy cô, học sinh hệ thống kiến thức và bài tập về xử lí mảng và xử lí xâu. Vận dụng đề tài này sẽ giúp cho quá trình bồi dưỡng học sinh giỏi môn tin học được nhiều thuận lợi và hiệu quả. Phần 2: NỘI DUNG A. THỰC TRẠNG  Qua các năm tham gia bồi dưỡng học sinh giỏi, tôi nhận thấy: - Số lượng học sinh viết được chương trình ở phần mảng và phần xâu chưa nhiều - Khả năng nhận dạng, phân tích đề của học sinh chưa chắc chắn, đặc biệt ở phần sử dụng câu lệnh còn lúng túng, sai những kiến thức cơ bản về cú pháp lẫn ngữ nghĩa  Nguyên nhân: - Bản chất viết chương trình là một môn học khó, trừu tượng, học sinh khó nắm kiến thức. Học sinh muốn nắm được kiến thức phải nắm vững những kiến thức cơ bản của môn học, phải có kiến thức của môn toán và phải có sự đam mê - Sách giáo khoa viết nội dung về xử lí mảng và xử lí xâu còn cơ bản chưa đủ kiến thức để các em làm bài tốt khi thi học sinh giỏi. Do đó giáo viên dạy bồi dưỡng phải có chương trình bồi dưỡng thường xuyên, tập hợp kiến thức, biên soạn tư liệu để học sinh tham khảo. - Tài liệu ôn học sinh giỏi tại các trường phổ thông chưa nhiều, đa số mang tính chấp nối các tài liệu tham khảo. Đa số kiến thức thi học sinh giỏi là những kiến thức ở các sách tham khảo, vì thế giáo viên dạy bồi dưỡng phải chắc lọc sao cho phù hợp với đối tượng học sinh nhưng cũng đảm bảo mức độ của một đề thi học sinh giỏi. - Học sinh còn kiểu học máy móc chỉ nhớ từng mảng bài cụ thể mà giáo viên đã dạy nên khó làm tốt các bài tập khi tham gia thi học sinh giỏi.  Biện pháp: - Nhận thức được tầm quan trọng của xử lí mảng và xử lí xâu trong quá trình viết chương trình, tôi biên soạn những bài tập liên quan đến 2 nội dung này nhằm cung cấp các kiến thức nền tảng và nâng cao để phục vụ trong việc bồi dưỡng học sinh giỏi. - Tôi tập hợp, sàn lọc kiến thức lí thuyết phù hợp, sưu tầm, biên soạn bài tập và đưa ra một số phương pháp làm bài tập để học sinh có thể học tập, vận dụng khi làm các bài tập về nội dung này. B. NỘI DUNG CHÍNH CỦA ĐỀ TÀI I. CÁC DẠNG BÀI TẬP XỬ LÍ MẢNG MỘT CHIỀU * Dạng bài tập sắp xếp Bài 1: Viết chương trình nhập vào số nguyên dương N và dãy A gồm N số nguyên A1, A2,... AN. Hãy sắp xếp dãy số trên sao cho các số chẵn chia hết cho 3 lên đầu dãy, các số lẻ chia hết cho 3 xuống cuối dãy, các số còn lại ở giữa dãy vẫn giữ được thứ tự trước khi nhập vào. In ra màn hình dãy trước và sau khi sắp xếp mỗi phần tử cách nhau một khoảng trắng. Ví dụ: Input: 1 6 5 9 12 3 4 15 7 Output: Dãy trước khi sắp xếp: 1 6 5 9 12 3 4 15 7 Dãy sau khi sắp xếp: 6 12 1 5 4 7 9 3 15 Hướng dẫn viết chương trình: Program bai1; Uses crt; Var A: array[1..250] of integer; i, N: integer; Begin Clrscr; Write(‘nhap so luong phan tu N= ‘); readln(N); For i:= 1 to N do Begin Write(‘A[‘,I,‘] = ‘);readln(A[i]); End; Writeln(‘Day truoc khi sap xep‘); For i:= 1 to N do write(A[i], ‘ ‘); Writeln; Writeln(‘Day sao khi sap xep‘); For i:=1 to N do If (A[i] mod 2=0) and (A[i] mod 3=0) write(A[i], ‘ ‘); For i:=1 to N do If ((A[i] mod 2=0) and (A[i] mod 3<>0)) or ((A[i] mod 2<>0) and (A[i] mod 3<>0)) write(A[i], ‘ ‘); For i:=1 to N do If (A[i] mod 2<>0) and (A[i] mod 3=0) write(A[i], ‘ ‘); Readln; End. Bài 2: Cho một dãy số nguyên A1, A2,... AN (N<=100). Yêu cầu: sắp xếp dãy số sao cho những số nhỏ nhất lên đầu dãy, tiếp theo là những số lớn nhất, rồi đến các số còn lại như khi nhập vào. In ra màn hình dãy trước và sau khi sắp xếp mỗi phần tử cách nhau một khoảng trắng. + Dữ liệu vào: Đọc từ tệp INP.TXT gồm 2 dòng - Dòng đầu tiên ghi số N - Các dòng tiếp theo chứa các số nguyên A[i] (mỗi số cách nhau 1 khoảng trắng) + Dữ liệu ra: Ghi ra tệp OUT.TXT theo yêu cầu Ví dụ: INP.TXT OUT.TXT 14 11199564772383 51641977123893 Hướng dẫn viết chương trình: Program bai2; Var A: array[1..100] of integer; i, N, max, min: integer; fi, fo: text; Begin Assign(fi, ‘INP.TXT‘);reset(fi); Assign(fo, ‘OUT.TXT‘);rewrite(fo); Readln(fi,N); For i:=1 to N do read(fi, A[i]); Max:=a[1]; min:=A[1]; For i:=2 to N do Begin If (A[i]< min) then min:= A[i]; If (A[i]> max) then max:= A[i]; End; For i:=1 to N do If (A[i] = min) then write(fo, A[i], ‘ ‘); For i:=1 to N do If (A[i] = max) then write(fo, A[i], ‘ ‘); For i:=1 to N do If (A[i] <> min) and (A[i] <> min) then write(fo, A[i], ‘ ‘); Close(fi); close(fo); End. * Dạng bài tập xử lí các phần tử trong mảng theo yêu cầu của đề bài Bài 3: Cho dãy N số nguyên A1, A2,... AN (0A[j]) do inc(j); if i = j then write(A[i], ‘ ‘); inc(i); end; readln; end. Bài 5: Cho một dãy số nguyên A1, A2,... AN (N<=100). Hãy lập trình + Dữ liệu vào: Đọc từ tệp SUBSEQ.INP gồm 2 dòng - Dòng đầu tiên chứa hai số nguyên N, k≠1 - Các dòng tiếp theo chứa các số nguyên A[i] (mỗi số cách nhau 1 khoảng trắng) + Tìm đoạn dài nhất các phần tử liên tiếp cùng chia hết cho 1 số nguyên k. Đưa ra tệp văn bản SUBSEQ.OUT 1 số nguyên xác định độ dài lớn nhất tìm được Ví dụ: SUBSEQ.INP SUBSEQ.OUT 10 5 4 6 10 15 7 9 15 20 25 30 11 Hướng dẫn viết chương trình: Program bai5; Var A: array[1..100] of integer; i, N, max, k, s: integer; fi, fo: text; ok: boolean; Begin Assign(fi, ‘SUBSEQ.INP‘);reset(fi); Assign(fo, ‘SUBSEQ.OUT‘);reset(fo); Readln(fi,N,k); Ok := false; s:=0; max:=0; For i:=1 to N do begin read(fi, A[i]); if (A[i] mod k=0) then if ok then inc(s) else begin ok:=true;s:=1; end else if ok then begin ok:=false; if s>max then max:=s; s:=0; end; if s>max then max:=s; end; Close(fi); Writeln(fo, max); close(fo); End. Bài 6: Dãy con tăng dần A1, A2,... AN được gọi là tăng nếu A1 ≤ A2 ≤ AN Cho 1 dãy số nguyên tối đa N số (1≤ N ≤ 100). Viết chương trình tìm đò dài dãy con liên tiếp tăng dần dài nhất trong dãy nói trên + Dữ liệu vào: Đọc từ tệp DAYSO.INP gồm 2 dòng - Dòng đầu tiên chứa số nguyên N - Dòng tiếp theo gồm n số nguyên dương cách nhau 1 khoảng trắng + Dữ liệu ra: Ghi vào tệp DAYCON.OUT gồm 1 số duy nhất là độ dài của dãy con liên tiếp dài nhất tìm được Ví dụ: DAYSO.INP DAYCON.OUT 11 4 1 4 10 8 3 4 3 1 1 2 5 Hướng dẫn viết chương trình: Program bai6; Var A: array[1..100] of integer; i, j, N, t, max: integer; fi, fo: text; Begin Assign(fi, ‘DAYSO.INP‘);reset(fi); Assign(fo, ‘DAYCON.OUT‘);reset(fo); Readln(fi,N); For i:=1 to N do read(fi, A[i]); Max:=0; For i:=1 to N-1 do If A[i] <= A[i+1] then Begin T:=1; j:=i While (A[j]<=A[j+1]) and (j<=n) do Begin Inc(t);inc(j); End; If t>max then max:=t; End; Write(fo, max); Close(fi); close(fo); End. II. CÁC DẠNG BÀI TẬP XỬ LÍ XÂU Bài 1: Viết chương trình nhập vào một xâu từ bàn phím không vượt qua 255 kí tự. Thông báo ra màn hình các yêu cầu sau: - Xóa các khoảng trắng thừa của xâu vừa nhập - Đếm số lượng từ trong xâu - Từ có độ dài lớn nhất trong xâu (nếu có nhiều từ có đồ dài lớn nhất bằng nhau thì in từ dài nhất đầu tiên) - Xâu theo chiều đảo ngược các từ của xâu đã nhập Ví dụ: Xâu nhập vào là: ‘ Truong THPT Vo Van Kiet ‘ Xuất ra màn hình: - Xâu sau khi xóa khoảng trắng thừa là: ‘Truong THPT Vo Van Kiet‘ - Số lượng từ trong xâu là: 5 - Từ có độ dài lớn nhất là: Truong - Xâu đảo ngược các từ là: ‘Kiet Van Vo THPT Truong‘ Hướng dẫn viết chương trình: Program bai1; Uses crt; Var s, a, b, t: string; i, dem: byte; Begin Clrscr; Write(‘nhap xau s: ‘); readln(s); While s[1]=#32 do delete(s,1,1); While s[length(s)]=#32 do delete(s,length(s),1); While pos(#32#32,s)<>0 do delete(s,pos(#32#32,s),1); //----------------------------// S:= s+ ‘ ‘; For i:= 1 to length(s) do If (s[i]<>#32) and (s[i+1]=#32) then inc(dem); //----------------------------// a:= ‘‘; b:= ‘‘ for i:= 1 to length(s) do if s[i]<>#32 then b:=b+s[i] else begin if length(a)0 do begin t:=copy(s,1,pos(#32))+t; delete(s,1,pos(#32,s); end; t:= s + ‘ ‘ + t; //------------------------------// Writeln(‘xau sau khi xoa khoang trang thua: ‘,s); Writeln(‘so luong tu trong xau s la: ‘,dem); Writeln(‘tu dai nhat trong xau s la: ‘,a); Writeln(‘xau viet theo chieu dao nguoc cac tu cua xau s la: ‘,t); Readln; End. Bài 2: Cho 2 xâu P, Q nhập từ bàn phím. Tìm xem xâu P có phải là xâu con xâu Q không? Nếu P là con xâu Q, hãy cho biết vị trí và số lần xuất hiện của P trong Q. Hướng dẫn viết chương trình: Program bai2; Uses crt; Var P, Q: string; dem: byte; Begin Clrscr; Write(‘nhap xau P: ‘);readln(P); Write(‘nhap xau Q: ‘);readln(Q); dem:=0; While pos(P,Q) > 0 do Begin Writeln(‘Xau P o vi tri: ‘,dem*length(P) + pos(P,Q)); dem := dem+1; Delete(Q, pos(P,Q), length(P)); End; If dem = 0 then write(‘P khong phai la xau con cua Q‘) Else write(‘co ‘,dem,‘ vi tri cua xau P trong Q‘); Readln; End. Bài 3: Viết chương trình nhập vào 1 xâu. Đưa ra màn hình sau khi xoá các kí tự trùng nhau. Hướng dẫn viết chương trình: Program bai3; Uses crt; Var s:string; i, j: byte; begin clrscr; write(‘nhap xau s: ‘);readln(s); write(s[1]); i:=2; while i<= length(s) do begin j:=1; while (js[j]) do inc(j); if i=j then write(s[i]); inc(i); end; readln; end. Bài 4: Cho xâu kí tự s. Viết chương trình tính xem trong s có bao nhiêu loại kí tự khác nhau (phân biệt chữ in hoa và in thường). ví dụ với s là ‘Pascal‘ ta có đáp số là 5. Program bai4; Var s: string; i, j, dem: integer; t: boolean; begin write(‘nhap mot xau ki tu s: ‘);readln(s); dem:=0; for i:=1 to length(s) do begin t:=false; for j:=1 to i-1 do if (s[j]=s[i]) then t:=true; if not t then inc(dem); end; write(‘so ki tu khac nhau cua xau s la: ‘,dem); readln; end. Phần 3: KẾT LUẬN - Qua đề tài này tôi đã hệ thống được kiến thức về kiểu mảng và kiểu xâu. Sưu tầm, biên soạn 10 bài tập với mức độ thi HSG lớp 10, 11 cấp tỉnh. Trong phần bài tập này, đã được phân dạng, có hướng dẫn rõ ràng. - Áp dụng vào chương trình bồi dưỡng học sinh giỏi lớp 10 và lớp 11 - Kết quả vận dụng chuyên đề khi ôn luyện học sinh giỏi năm: Kết quả năm 2013- 2014: + 01 giải khuyến khích HSG vòng tỉnh lớp 11 (em Thái Minh Tân). * Những kết luận trong quá trình nghiên cứu: - Quá trình bồi dưỡng học sinh giỏi và dạy các lớp chọn điểm sáng ở năm học vừa qua, tôi nhận thấy: + Kiến thức của học sinh ngày càng được củng cố và phát triển sau khi hiểu nắm vững được bản chất của các chương trình + Niềm hứng thú, say mê trong học tập của học sinh càng được phát huy khi có tài liệu chuyên sâu để học sinh nghiên cứu. Đặc biệt, việc phân dạng bài tập sẽ giúp học sinh có điều kiện khai thác triệt để nội dung kiến thức từng dạng. - Tuy đã có nhiều cố gắng nhưng không thể tránh khỏi những thiếu sót nhất định. Rất mong quí thầy cô và các bạn đóng góp ý kiến để bài viết sau được tốt hơn. Xin chân thành cám ơn! Phước Long, ngày 23 tháng 02 năm 2015 Người viết Nguyễn Văn Dược TÀI LIỆU THAM KHẢO 1. Sách giáo khoa tin học 11 Hồ Sĩ Đàm chủ biên 2. Sách giáo viên tin học 11 Hồ Sĩ Đàm chủ biên 3. Bài tập thực hành Pascal Nguyễn Quang Vịnh 4. Một số sáng kiến kinh nghiệm và ý kiến của đồng nghiệp …