intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

SKKN: Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn Tin học

Chia sẻ: Trần Thị Ta | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST
Báo xấu
73
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài thực hiện nhằm giúp cho giáo viên cũng như học sinh hệ thống lại các kiến thức về các thao tác trên kiểu dữ liệu xâu từ đó áp dụng cho các bài toán cụ thể. Giới thiệu một số phép toán trên kiểu dữ liệu xâu, đặc biệt phần này có cung cấp thêm một số hàm, thủ tục chưa được giới thiệu trong bài 12 sách giáo khoa tin học 11, đồng thời đưa ra một số ví dụ tương ứng để học sinh dễ dàng sử dụng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: SKKN: Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn Tin học

  1. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học MỤC LỤC TÀI LIỆU THAM KHẢO ...................................................................................................... 2 BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN .................................. 3 1. LỜI GIỚI THIỆU .......................................................................................................... 3 1.1. Lí do chọn đề tài ........................................................................................................ 3 1.2. Mục tiêu nghiên cứu .................................................................................................. 3 1.3. Đối tượng nghiên cứu ................................................................................................ 4 1.4. Phương pháp thực hiện .............................................................................................. 4 2. TÊN SÁNG KIẾN: ......................................................................................................... 4 3. TÁC GIẢ SÁNG KIẾN: ................................................................................................ 4 4. CHỦ ĐẦU TƯ TẠO RA SÁNG KIẾN ......................................................................... 5 5. LĨNH VỰC ÁP DỤNG SÁNG KIẾN ........................................................................... 5 6. NGÀY SÁNG KIẾN ĐƯỢC ÁP DỤNG LẦN ĐẦU.................................................... 5 7. MÔ TẢ BẢN CHẤT CỦA SÁNG KIẾN ...................................................................... 5 CHƯƠNG I: CƠ SỞ LÍ LUẬN CỦA ĐỀ TÀI ............................................................ 5 CHƯƠNG II: THỰC TRẠNG CỦA VẤN ĐỀ NGHIÊN CỨU................................. 6 CHƯƠNG III: NỘI DUNG CỦA ĐỀ TÀI ................................................................... 6 1. Lý thuyết về kiểu xâu .............................................................................................. 6 1.1. Khái niệm .......................................................................................................... 6 1.2. Khai báo ............................................................................................................ 7 1.3. Các thao tác xử lý xâu:...................................................................................... 7 2. Các dạng bài tập kiểu xâu..................................................................................... 10 Dạng 1: Kiểm tra xâu thỏa mãn tính chất nào đó ...................................................... 10 Dạng 2: Đếm số lần xuất hiện của các kí tự trong xâu .............................................. 15 Dạng 3: Mã hóa và giải mã ........................................................................................ 18 Dạng 4: Xóa và thay thế............................................................................................. 21 Dạng 5: Chuyển số sang xâu và ngược lại ................................................................. 23 8. NHỮNG THÔNG TIN CẦN ĐƯỢC BẢO MẬT (NẾU CÓ):.................................. 30 9. CÁC ĐIỀU KIỆN CẦN THIẾT ĐỂ ÁP DỤNG SÁNG KIẾN: ............................... 30 10. ĐÁNH GIÁ LỢI ÍCH THU ĐƯỢC .......................................................................... 30 KẾT LUẬN ............................................................................................................................ 31 11. DANH SÁCH NHỮNG TỔ CHỨC/CÁ NHÂN ĐÃ THAM GIA ÁP DỤNG THỬ HOẶC ÁP DỤNG SÁNG KIẾN LẦN ĐẦU (NẾU CÓ): .............................................. 31 1
  2. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin họ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. Sách bài tập tin học lớp 11 4. Một số đề thi học sinh giỏi tỉnh Vĩnh Phúc 4. Lập trình Pascal Khoa CNTT trường ĐHSPHN 5. Một số sáng kiến kinh nghiệm và ý kiến của đồng nghiệp. 6. Một số trang web trên Internet. 2
  3. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN 1. LỜI GIỚI THIỆU 1.1. Lí do chọn đề tài Môn tin học đặc biệt là nội dung tin học lập trình là một môn học khá là mới lạ đối với học sinh phổ thông nên đa số các em rất bỡ ngỡ khi tiếp cận nội môn học này. Trong thực tiễn dữ liệu vào của các bài toán đều liên quan đến các kiểu dữ liệu khác nhau, để tiện cho việc lập trình và xử lý dữ liệu chúng ta thường đưa dữ liệu đó về các dạng kiểu dữ liệu chuẩn hoặc kiểu dữ liệu có cấu trúc, một trong những kiểu dữ liệu đó là kiểu xâu. Qua quá trình tham gia giảng dạy môn tin học tại trường THPT Đồng Đậu và bồi dưỡng học sinh giỏi tôi nhận thấy dữ liệu kiểu xâu gặp rất nhiều trong các bài toán nhưng để học sinh có thể vận dụng linh hoạt các thao tác xử lý trên kiểu dữ liệu này vào bài toán không phải là dễ. Với mong muốn hệ thống các bài toán dưới dạng một số dạng bài tập thường gặp giúp cho giáo viên và học sinh phần nào nhận dạng và giải một số bài tập liên quan tới kiểu dữ liệu xâu dễ dàng hơn, tôi xin đưa ra “PHƯƠNG PHÁP GIẢI MỘT SỐ DẠNG BÀI TẬP VỀ KIỂU DỮ LIỆU XÂU TRONG ĐỀ THI HỌC SINH GIỎI MÔN TIN HỌC”. 1.2. Mục tiêu nghiên cứu o Đề tài thực hiện nhằm giúp cho giáo viên cũng như học sinh hệ thống lại các kiến thức về các thao tác trên kiểu dữ liệu xâu từ đó áp dụng cho các bài toán cụ thể. o Giới thiệu một số phép toán trên kiểu dữ liệu xâu, đặc biệt phần này có cung cấp thêm một số hàm, thủ tục chưa được giới thiệu trong bài 12 sách giáo khoa 3
  4. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học tin học 11, đồng thời đưa ra một số ví dụ tương ứng để học sinh dễ dàng sử dụng. o Hệ thống các bài toán dưới dạng một số dạng bài tập thường gặp giúp cho giáo viên và học sinh phần nào nhận dạng và giải một số bài tập liên quan. o Giúp học sinh không còn nhàm chán với môn tin học nói chung và kiểu dữ liệu xâu nói riêng. 1.3. Đối tượng nghiên cứu o Học sinh: học sinh học chương trình cơ bản và học sinh đội tuyển học sinh giỏi tin học o Số lượng: 120 học sinh o Số lớp thực hiện: 3 lớp. o Khối lớp: 11 1.4. Phương pháp thực hiện Để hoàn thành SKKN này tôi sử dụng phối kết hợp nhiều phương pháp, trong đó phương pháp chủ yếu là: o Nghiên cứu tài liệu. o Thực nghiệm. o Tham khảo ý kiến của cấp trên và đồng nghiệp. 2. TÊN SÁNG KIẾN: “PHƯƠNG PHÁP GIẢI MỘT SỐ DẠNG BÀI TẬP VỀ KIỂU DỮ LIỆU XÂU TRONG ĐỀ THI HỌC SINH GIỎI MÔN TIN HỌC”. 3. TÁC GIẢ SÁNG KIẾN: o Họ và tên: Bùi Thị Phương o Địa chỉ tác giả sáng kiến: THPT Đồng Đậu o Số điện thoại:0383797818 o E_mail: buithiphuongc3dongdau.vinhphuc.edu.vn 4
  5. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học 4. CHỦ ĐẦU TƯ TẠO RA SÁNG KIẾN 5. LĨNH VỰC ÁP DỤNG SÁNG KIẾN Đề tài được sử dụng để vận dụng giải các bài toán về kiểu dữ liệu xâu trong sách bài tập tin học lớp 11 và trong các đề thi học sinh giỏi tỉnh môn tin học. Khi vận dụng đề tài để giải các bài toán về kiểu dữ liệu xâu giúp: o Học sinh sau khi được giới thiệu một cách hệ thống các dạng bài tập về xâu và quy trình giải quyết từng dạng đã có thể nhận biết yêu cầu của bài toán và cách thức giải quyết chúng một cách hiệu quả. o Hình thành ở HS kỹ năng phân tích, xử lý các vấn đề liên quan đến bài tập kiểu xâu, sử dụng thành thạo vòng lặp biết trước, thủ tục chuẩn vào/ra đơn giản, bước đầu làm quen với 1 số chương trình con dạng thủ tục tạo điều kiện thuận lợi cho việc tiếp thu kiến thức về cách viết chương trình có cấu trúc. o Mở rộng một số bài tập kiểu xâu để học sinh thấy được ứng dụng quan trọng của kiểu dữ liệu xâu trong lập trình. 6. NGÀY SÁNG KIẾN ĐƯỢC ÁP DỤNG LẦN ĐẦU HOẶC ÁP DỤNG THỬ Đề tài được áp dụng vào ngày 20 tháng 02 năm 2019 7. MÔ TẢ BẢN CHẤT CỦA SÁNG KIẾN: NỘI DUNG SÁNG KIẾN CHƯƠNG I: CƠ SỞ LÍ LUẬN CỦA ĐỀ TÀI Trong bối cảnh toàn ngành GD-ĐT đang nỗ lực đổi mới phương pháp dạy học theo hướng phát huy tính tích cực chủ động của học sinh trong hoạt động học tập. Điều 24.2 của Luật giáo dục đã nêu rõ: “Phương pháp giáo dục phổ thông phải phát huy tính tích cực, tự giác, chủ động, sáng tạo của học sinh, phù hợp với đặc điểm của từng lớp học, môn học; bồi dưỡng phương pháp tự học, rèn luyện kỹ năng vận dụng kiến thức vào thực tiễn, tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh ”. Như vậy, chúng ta có thể thấy định hướng đổi mới phương pháp dạy học đã được khẳng 5
  6. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học định, không còn là vấn đề tranh luận. Cốt lõi của việc đổi mới phương pháp dạy học ở trường phổ thông là giúp học sinh hướng tới việc học tập chủ động, chống lại thói quen học tập thụ động. Với một số nội dung trong đề tài này, học sinh có thể tự học, tự rèn luyện thông qua một số bài tập, dạng bài tập cụ thể. CHƯƠNG II: THỰC TRẠNG CỦA VẤN ĐỀ NGHIÊN CỨU Qua thực tế giảng dạy ở trường THPT Đồng Đậu tôi nhận thấy khi học đến chương trình tin học lớp 11 đa số học sinh đều cho rằng đây là môn học khó nhất trong các môn học, nhiều em còn sợ môn học này. Khi học sinh học bài học Bài 12 “Kiểu xâu”, học sinh đã có rất nhiều khó khăn, nhầm lẫn trong việc xử lý dữ liệu vì các em đang quen với các bài toán xử lý dữ liệu kiểu số, các bài toán quen thuộc như tính tổng hoặc tích của 1 dãy số thoả mãn điều kiện nào đó… Khi gặp các bài toán phải sử dụng kiểu dữ liệu lớn nhiều em lúng lúng. Việc giải các bài toán với kiểu dữ liệu lớn thực sự cần thiết cho các em khi làm các bài toán lập trình trong chương trình Tin học phổ thông nói riêng và việc giải quyết các bài toán thực tế nói chung. CHƯƠNG III: NỘI DUNG CỦA ĐỀ TÀI 1. Lý thuyết về kiểu xâu 1.1. Khái niệm o Xâu là một dãy các kí tự trong bộ mã ASCII, mỗi kí tự được gọi là một phần tử của xâu. o Số lượng kí tự trong xâu gọi là độ dài xâu. o Xâu có độ dài bằng 0 gọi là xâu rỗng. o Có thể coi xâu là mảng một chiều, mỗi kí tự trong xâu là một phần tử, được 6
  7. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học đánh chỉ số bắt đầu từ 1. Do vậy, để tham chiếu đến phần tử của xâu ta viết [chỉ số của kí tự]; Ví dụ: s = ‘Tin hoc’ Muốn truy cập đến kí tự ‘i’ thì viết s[2] = ‘i’; 1.2. Khai báo Var : string [ độ dài lớn nhất của xâu ]; Ví dụ: var hoten : string[30]; Chú ý: Độ dài lớn nhất của xâu có thể bỏ qua. Khi đó độ dài lớn nhất của xâu sẽ nhận giá trị ngầm định là 255. Ví dụ var s : string; 1.3. Các thao tác xử lý xâu: 1.3.1. Phép ghép xâu Kí hiệu là dấu (+), được sử dụng để ghép nhiều xâu thành một. Có thể thực hiện phép ghép xâu đối với các hằng và biến xâu. Ví dụ: ‘Tin’ + ‘ Hoc’ = ‘Tin Hoc’; ‘6’ + ‘7’ = ‘67’; 1.3.2. Phép so sánh o Sử dụng phép so sánh = , , , = và có thứ tự ưu tiên thấp hơn phép ghép xâu. o Quy tắc so sánh:  Xâu A là lớn hơn xâu B nếu như kí tự đầu tiên khác nhau giữa chúng kể từ trái sang trong xâu A có mã ASCII lớn hơn. Ví dụ: ‘207’ > ‘2007’; 7
  8. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học  Nếu A và B là các xâu có độ dài khác nhau và A là đoạn đầu của B thì A nhỏ hơn B. Ví dụ: ‘Tin’ < ‘Tin hoc’  Hai xâu được coi là bằng nhau nếu như chúng giống nhau hoàn toàn Ví dụ: ‘Tin hoc’ = ‘Tin hoc’ 1.3.3. Các hàm và thủ tục xử lý xâu  Thủ tục Delete (st, vt, n) Thực hiện xóa n kí tự của biến xâu st bắt đầu từ vị trí vt. Giá trị st Thao tác Kết quả ‘Tin hoc’ Delete(st,5,3); ‘Tin’ ‘Song Hong’ Delete(st,1,5); ‘Hong’  Thủ tục Insert (s1, s2, vt) Chèn xâu s1 vào xâu s2 bắt đầu ở vị trí vt Giá trị s1 Giá trị s2 Thao tác Kết quả ‘ PC ’ ‘IBM486’ insert(s1, s2, 4); ‘IBM PC 486’ ‘1’ ‘Hinh .2’ Insert(s1,s2,6); ‘Hinh 1.2’  Hàm copy (s, vt, n) Tạo xâu gồm n kí tự liên tiếp bắt đầu từ vị trí vt của xâu s Giá trị s Thao tác Kết quả ‘Tin hoc’ copy(s, 1, 3); ‘Tin’ ‘Bai hoc thu 9’ Copy(s,9,5); ‘thu 9’ 8
  9. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học  Hàm length(s) Cho giá trị là độ dài xâu s Giá trị s Thao tác Kết quả ‘Tin hoc’ Length(s); 7 ‘500 ky tu’ Length(s); 9  Hàm pos (s1, s2) Cho vị trí xuất hiện đầu tiên của xâu s1 trong xâu s2 Giá trị s2 Thao tác Kết quả ‘Tin hoc’ Pos(‘oc’,s2); 6 ‘abcdef’ Pos(‘k’,s2); 0  Hàm upcase(ch) Cho chữ cái in hoa ứng với chữ cái trong ch Giá trị ch Thao tác Kết quả ‘a’ Upcase(ch); ‘A’ ‘A’ Upcase(ch); ‘A’  Thủ tục chuyển xâu sang số val (s, v, c) Chuyển xâu s thành giá trị số lưu vào v, c là vị trí gây ra lỗi trong quá trình chuyển đổi, c = 0 thì chuyển đổi thành công Giá trị s Thao tác Kết quả ‘1234’ Val(s,i,c); i = 1234; c=0 ‘12c’ Val(s,i,c); Cho c=3 là vị trí ký tự c không hợp lệ 9
  10. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học  Thủ tục chuyển số sang xâu str(x, s) Chuyển giá trị kiểu số x thành chuỗi biểu diễn nó lưu trong s Giá trị x Thao tác Kết quả 1234 Str(x,s); S=’1234’ 1.1:0:2 Str(x,s); S=’1.10’ 2. Các dạng bài tập kiểu xâu 2.1. Dạng 1: Kiểm tra xâu thỏa mãn tính chất nào đó Phương pháp chung của dạng này là sử dụng các thao tác xử lý xâu vào từng yêu cầu cụ thể, thường vận dụng câu lệnh for..to..do.. để duyệt các phần tử của xâu. Bài 1(sgk): Nhập vào hai xâu họ tên và đưa ra màn hình xâu có độ dài dài hơn. Nếu hai xâu có độ dài bằng nhau thì đưa ra xâu nhập sau. * Ý tưởng: để lấy độ dài xâu sử dụng hàm length(s), So sánh độ dài của hai xâu bằng câu lệnh if. If length(s1) > length(s2) then write(s1) else write(s2); Bài 2(sgk): Kiểm tra xem kí tự đầu tiên của xâu a có trùng với kí tự cuối cùng của xâu b không? * Ý tưởng: Kí tự đầu tiên của xâu a: a[1] kí tự cuối cùng của xâu b: b[length(b)] sử dụng câu lệnh if để so sánh If a[1] = b[length(b)] then write (‘Trung nhau’) else write (‘khong trung’); Bài 3 (sgk): Đưa ra xâu theo thứ tự ngược lại. 10
  11. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học *Ý tưởng: Muốn đưa xâu ra theo thứ tự ngược lại thì phải đi từ cuối xâu đến kí tự liền cuối... => duyệt bằng câu lệnh for...downto....do ....đưa ra từng kí tự của s For i:=length(s) downto 1 do write(s[i]); Bài 4(sgk): Kiểm tra xem xâu có là xâu đối xứng không? Xâu đối xứng là xâu mà đọc từ cuối xâu ngược lên cũng giống đọc từ đầu xâu đến cuối * Cách 1: Tạo 1 xâu đảo ngược từ xâu ban đầu (Cách tạo giống Bài 3) => So sánh hai xâu, nếu bằng nhau thì đối xứng ngược lại thì không đối xứng { Tạo xâu b đảo ngược từ xâu a} b:=’’; for i:= length(a) downto 1 do b:=b+a[i]; if a = b then write(‘Xau doi xung’) else write(‘xau khong doi xung’); * Cách 2: Nhận xét nếu xâu a đối xứng thì: a[1] = a[n] ( Gán n = length(a)); a[2] = a[n-1] a[3] = a[n-2] .... Tổng quát lên a[i] = a[n-i+1] với i chạy từ 1 đên n div 2 Sử dụng biến KT để KT tính đối xứng của a Đoạn chương trình thực hiện kiểm tra đối xứng: KT:= true; for i:= 1 to n div 2 do if a[i] a[n-i+1] then KT:= false; if KT then write(‘Xau doi xung’) else (‘xau khong doi xung’); 11
  12. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học Bài 5 (Bài 4.42 sách bài tập): Xâu N viên đá quý có kích thước giống nhau (5
  13. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học { Thân chương trình xử lý} S:= s1+s1; d:=0; n:= length(s); for i:= n+1 to 2*n do begin s3:= s1 + s[i]; if DX (s3) then d:=d+1; end; Chú ý: với học sinh đại trà chưa học đến chương trình con thì trong phần thân chương trình sẽ kiểm tra tính đối sứng của s3 như trong hàm viết ở trên Bài 6 (Đề thi hsg lớp 10 năm 2010 - 2011) Đưa ra xâu con đối xứng có độ dài dài nhất. Bài này có hai cách để làm là sử dụng quy hoạch động và duyệt bình thường, nhưng xuất phát từ thực tế giảng dạy học sinh trường THPT Đồng Đậu khó hình dung được bằng cách quy hoạch động nên ở đây tôi sử dụng cách duyệt và kiểm tra tính đối xứng thông thường. Để tối ưu lời giải các bạn có thể tìm hiểu thêm cách sử dụng quy hoạch động cho bài toán trên. * Ý tưởng: Tạo các xâu con có độ dài là 2, 3,....đồng thời kiểm tra luôn xâu con đó có đối xứng không? Nếu đối xứng thì so sánh độ dài của xâu con đó với giá trị max trước đó, nếu lớn hơn thì gán lại max. * Đoạn chương trình: n:=length(s); max:=1; for k:=1 to n – 1 do 13
  14. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học for i:=1 to n – k do begin j:= i+1; s1:= copy(s, i, j – i+1); KT:=true; l:=length(s1); for h:=1 to l div 2 do if s1[h] s1[l-h+1] then KT:=false; if (KT) and (max
  15. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học begin if s[i]=’(‘ then inc(d) else dec(d); if d0 then kt:=false; Bài 8( Đề thi hsg lớp 11 năm 2012 – 2013) Cho xâu S độ dài không quá 250 chỉ gồm các kí tự ngoặc đóng và ngoặc mở. Xác định số cặp chỉ số (p, q) sao cho p
  16. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học Bài 1(bài 10 sgk): Viết chương trình nhập vào từ bàn phím một xâu kí tự S có độ dài không quá 100. Hãy cho biết có bao nhiêu chữ số xuất hiện trong xâu S. Thông báo kết quả ra màn hình. * Ý tưởng: Đi từ đầu xâu đến cuối xâu, kiểm tra lần lượt từng kí tự có nằm trong khoảng từ ‘0’ đến ‘9’ không? Nếu nằm thì tăng biến đếm lên 1. * Đoạn chương trình: dem:=0; for i:=1 to length(s) do if (s[i]>=’0’) and (s[i]
  17. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học - Duyệt từ đầu xâu đến cuối xâu, với mỗi ký tự S[i] của N tăng tương ứng phần tử có chỉ số là S[i] trong mang d lên 1 đơn vị . * Đoạn chương trình: var d:array[‘0’..’9’] of byte; c : char; BEGIN for c:=’0’ to ‘9’ do d[c]:=0; for i:=1 to length(s) do inc(d[s[i]]); for c:=’0’ to ‘9’ do writeln(d[c],’ ‘, c); END. Bài 3 (sgk): Thông báo số lần xuất hiện của mỗi chữ cái tiếng anh trong s (không phân biệt chữ hoa hay thường) * Ý tưởng: Tạo ra xâu s2 bằng cách lấy các ký tự là chữ cái trong xâu s1 sau khi đã chuyển thành chữ in hoa. Dùng mảng d để đếm như bài số 2. * Đoạn chương trình: var d:array[‘A’..’Z’] of byte; BEGIN N:=length(s1); s2:=’’; For i:= 1 to n do if (s1[i]>’A’) and (s1[i]
  18. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học inc(d[s2[i]]); for c:=’A’ to ‘Z’ do if d[c] 0 then writeln(‘ki tu ‘,c,’ xuat hien ‘,d[c]); END. Bài 4 ( Bài 4.39 sách bài tập): Viết chương trình nhập vào xâu s chứa các kí tự in thường và các chữ số từ 0 đến 9. Đếm và đưa ra màn hình số kí tự khác nhau trong xâu s. Ví dụ, nếu s = ‘abcabcaab’ thì số kí tự khác nhau là 3 * Ý tưởng: Gộp của hai bài 2 và 3, tức là sử dụng hai mảng đếm chữ số và đếm chữ thường, lúc đưa ra thì nếu đếm khác 0 thì tăng biến tổng lên 1 đơn vị. Dạng 3: Mã hóa và giải mã Ý tưởng chung của dạng bài mã hóa và giải mã: - Sử dụng mảng gán giá trị ban đầu cho các kí tự từ A đến Z là 1 đến 26. - Theo yêu cầu đề bài phải xây dựng được hàm f. - Từ hàm f giải mã ngược trở lại theo quy tắc mã hóa. Bài 1 (Bài 4.27 sách bài tập - Mã Xê Da): Thay mỗi chữ cái bằng chữ cái đứng sau nó k vị trí trong bảng chữ cái. Việc tìm kiếm thay thế được tiến hành vòng tròn. Nếu bảng chữ cái có N chữ thì sau chữ cái N-1 là chữ cái N, sau chữ cái N là chữ cái thứ nhất....Cách mã hóa này gọi là mã Xê da. Nhập từ bàn phím số nguyên K(1< K
  19. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học * Đoạn chương trình: { Khởi tạo mảng d} a:=0; For c:=’A’ to ‘Z’ do begin d[c]:= a+1; a:=d[c]; end; { Tính hàm f} For i:=1 to length(s) do begin For c:=’A’ to ‘Z’ do if s[i]=c then f[i]:=(d[c] + k) mod 26; if s[i] = ‘ ‘ then f[i]=27; { Trường hợp gặp dấu cách} end; {Mã hóa} For i:=1 to length(s) do begin For c:=’A’ to ‘Z’ do if f[i]=d[c] then write (c); if f[i] = 27 then write(‘ ‘); end; Bài 2 (Đề hsg lớp 10 năm 2009 – 2010- Mã hóa caesar): Cho xâu s mã hóa xâu s theo nguyên tắc f[p] = a*p + k; Cho trước a, k. P được xây dựng là p[A]=1, p[B] = 2....p[Z]=26. Cách làm tương tự ví dụ trên. 19
  20. Phương pháp giải một số dạng bài tập về kiểu dữ liệu xâu trong đề thi HSG môn tin học Bài 3 (Đề hsg lớp 11 năm 2010 – 2011- Đi hay ở lại): Cho hai chuỗi in hoa. Hai chuỗi được chuyển thành số theo quy tắc ví dụ ‘USACO’= 21*19*1*3*15=17955 (A có giá trị là 1, B có giá trị là 2,...., Z có giá trị là 26). Nếu số của hai chuỗi mod 47 bằng nhau thì ’GO’ ngược lại thì ‘STAY’. Cách làm hoàn toàn tương tự chỉ khác cách tính hàm f bằng công thức nhân. Không làm phần mã hóa mà kiểm tra điều kiện f1 mod 47 = f2 mod 47 thi GO ngược lại là STAY. Bài 4 (Đề hsg lớp 11 năm 2008 – 2009- Thứ tự từ điển): Cho bảng sắp thứ tự các từ a b.....z aa ab .......az ba bb bc ......bz.........aaa aab ........ aaaa .......abcd 1 2 26 27 28 52 53 54 55 78 703 704 18279 Cho xâu s( nhiều nhất 4 kí tự) Chỉ ra số thứ tự của s trong bảng sắp thứ tự trên Ví dụ, ad ở vị trí 30. * Ý tưởng: - Sử dụng mảng gán giá trị ban đầu cho các kí tự từ A đến Z là 1 đến 26. - Xây dựng hàm tính f trong từng trường hợp n=1, 2, 3, 4( n là độ dài xâu) * Đoạn chương trình: a:=0; for c:=’a’ to ‘z’ do begin f[c]:=a+1; a:= f[c]; end; if n= 1 then tt:= f[c]; if n=2 then tt:= 26 * f[s[1]] +f[s[2]]; if n=3 then tt:= 26* 26* f[s[1]]+26*f[s[2]]+f[s[3]]; if n=4 then tt:= 26* 26*26* f[s[1]]+26*26*f[s[2]]+26*f[s[3]]+f[s[4]]; 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

EXAM.05: Bộ 300+ Đề Thi Thử THPT Quốc Gia 2022
304 tài liệu
926 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2