Báo cáo Biện pháp Vận dụng kiến thức về kiểu dữ liệu xâu trong việc lập trình giải các bài toán bằng ngôn ngữ C++

Nội dung tài liệu: Báo cáo Biện pháp Vận dụng kiến thức về kiểu dữ liệu xâu trong việc lập trình giải các bài toán bằng ngôn ngữ C++

1. II. NỘI DUNG BIỆN PHÁP 1. KHÁI NIỆM: - Xâu là một dãy kí tự trong bảng mã ASCII. Mỗi kí tự được gọi là một phần tử của xâu. - Số lượng kí tự trong xâu được gọi là độ dài xâu. - Xâu có độ dài bằng 0 gọi là xâu rỗng. (Lưu ý: Ta có thể xem xâu như là mảng một chiều mà mỗi phần tử kiểu kí t - Tham chiếu đến một phần tử của xâu: S[Chỉ số] Ví dụ: Với xâu S = “Le_Thanh_Huy”. Ta có: S[3] là ‘T’, S[0] = ‘L’ * Khai báo: string ; Ví dụ: string s; - Các kí tự trong xâu được đánh chỉ số bắt đầu từ 0. 2. CÁC THAO TÁC LÀM VIỆC VỚI BIẾN XÂU: * So sánh hai xâu: Quy tắc: - Hai xâu bằng nhau nếu chúng giống nhau hoàn toàn: (Phân biệt hoa thường) Ví dụ: “Hona” = “Hona” Nhưng “hona” ≠ “HONA” - Hai xâu khác nhau: Ta sẽ kiểm tra kí tự khác nhau đầu tiên của hai xâu tính từ bên trái sang, nếu kí tự nào có mã ASCII lớn hơn thì xâu đó lớn hơn Giải thích: Kí tự khác nhau đầu tiên tính từ bên trái sang là n và Ví dụ: “Anh” < “Amh” m. Mà m có mã ASCII lớn hơn nên xâu “Amh” lớn hơn. Chú ý: - ‘A’ có mã ASCII là 65, ‘B’ là 66 - ‘a’ có mã ASCII là 97 * Ghép xâu: Sử dụng toán tử += hoặc + Ví dụ: s = "Chao"; s +=" ban"; * Các hàm và thủ tục xử lý xâu: - Lấy độ dài xâu: Hàm length() hoặc size() s = “chao”;
2. cout <<s.size(); Kết quả: 4 - Xóa phần tử trong xâu: Hàm erase(từ vị trí , số kí tự cần xoá); s = “chao ban”; s.erase(0, 5); Kết quả: s = “ban”; - Chèn thêm vào xâu: Hàm insert s = “Chao ban”; s.insert(0, “Xin ”); Kết quả: s = “Xin chao ban”; S = “Chao ban”; R = “ Huy”; S.insert(8, R); Kết quả: S = “Chao ban Huy”; S = “Chao ban”; R = “ Huy”; S.insert(8, R, 2, 2); Kết quả: S = “Chao ban uy”; - Sao chép xâu: Hàm substr S = “Chao ban”; R = S.substr(1, 3); Kết quả: R = “hao” - Tìm kiếm: Hàm find sẽ trả về vị trí đầu tiên xuất hiện, nếu không tìm thấy sẽ trả về vị trí string::npos s = "Chao ban"; if(s.find("ban") != string::npos) cout <<"YES"; Đáp án: in ra YES Tương tự có: rfind tìm kiếm vị trí xuất hiện cuối cùng - Thay thế: Hàm replace(pos, len, str2); s = "Chao ban"; s.repalce(1,4,’hu’); Thay thế len kí tự từ kí tự pos bằng str2 - Chuyển từ xâu sang số: x = stoi(s); (Tương tự có: stof, stol, stoll, stoull) y = stoll(s+r); (Đáp án y là tổng của hai xâu số)
3. - Chuyển từ số sang xâu: Số x - Qua xâu: (Cách chuẩn hiện tại, nên dạy khi bồi dưỡng HSG) ostringstream ss; ss << num; string s = ss.str(); - in hoa một xâu: for(int i=0; i<s.size(); i++) s[i] = toupper(s[i]); //in hoa - in thường xâu s: for(int i=0; i<s.size(); i++) s[i] = tolower(s[i]); //in thuong 3. BÀI TẬP CHỦ ĐỀ XỬ LÝ XÂU Bài 1: Tìm kiếm và thay thế: Trong khi soạn thảo văn bản một số người thường có thói quen gõ tắt cho nhanh nhưng với văn bản hành chính các từ này là không hợp lệ, một số khác lại thường xuyên gõ lỗi 1 số từ nào đó. Để sửa những lỗi này các phần mềm soạn thảo đều có chức năng tìm kiếm và thay thế. Vậy em hãy viết chương trình nhập vào từ bàn phím xâu ký tự s, tìm và thay thế tất cả các cụm ký tự s1 thành s2. Ví dụ: Xâu gốc: s = “HS lop 12 thi HS gioi” s1= “HS”; s2= “Hoc sinh”; Xâu kết quả: S = “Hoc sinh lop 12 thi Hoc sinh gioi” Hướng dẫn: Cách 1: Dùng hàm tìm kiếm s.find(s1) để xác định vị trí xuất hiện xâu s1 trong xâu s:vt = s.find(s1) Nếu vt != -1 tức là có xâu s1 trong xâu s thì thay thế xâu s1 bởi xâu s2 bằng hàm s.replace(vt,l1,s2); hoặc thay thế bằng lệnh xóa và chèn: s.erase(vt,l1); s.insert(vt,s2); Lưu ý: Trong xâu có thể có rất nhiều cụm từ cần thay thế nên ta phải sử dụng lệnh while để thay thế hết: trong khi s.find(s1) != -1 thì tiếp tục thay thế Cách 2: Để duyệt hết tất cả các khả năng cần thay thế ta sử dụng lệnh for kết hợp lệnh s.substr() để sao chép từng đoạn con có độ dài bằng độ dài xâu s1 rồi so sánh với s1. Nếu kết quả bằng s1 thì ta tiến hành thay thế bằng các câu lệnh tương tự cách 1. Chương trình:
4. Cách 1 Cách 2 #include #include using namespace std; using namespace std; int main() int main() { { string s,s1,s2; string s,s1,s2; getline(cin,s); getline(cin,s); getline(cin,s1); getline(cin,s1); getline(cin,s2); getline(cin,s2); int k=s1.size(); int k=s1.size(); while(s.find(s1)!=-1){ for(int i=0;i<s.size()-k;i++){ int vt=s.find(s1); if(s.substr(i,k)==s1){ s.replace(vt,k,s2); s.replace(i,k,s2); } } cout<<s; } return 0; cout<<s; } return 0; } Bài 2: Chuyển đổi phông chữ: Khi soạn thảo và trình bày văn bản, việc chuyển đổi đoạn văn chữ hoa sang thường hay chữ thường sang chữ hoa là một nhu cầu rất phổ biến. Trong hệ soạn thảo văn bản Word, nếu ta dùng bảng mã TCVN3 thì việc chuyển đổi rất đơn giản, chỉ cần chọn lại phông chữ tương ứng còn khi dùng bảng mã Unicode thì ta phải sử dụng công cụ chuyển đổi của phần mềm hỗ trợ gõ chữ việt. Em hãy viết chương trình nhập vào 1 xâu ký tự s, tạo xâu s1 chứa các từ trong xâu s nhưng ở dạng chữ hoa, tạo xâu s2 chứa các tự trong xâu s nhưng ở dạng chữ thường. Xuất kết quả xâu s1, s2 ra màn hình. Hướng dẫn: Cách 1: Dùng hàm toupper(), tolower() để chuyển đồi từng ký tự. Duyệt từng ký tự của xâu s, với mỗi ký tự đó ta dùng hàm toupper() chuyển sang ký tự hoa rồi nối vào xâu s1, dùng hàm tolower() chuyển sang chữ thường rồi nối vào xâu s
5. Hoặc gán s1 = s; s2 =s; sau đó duyệt từng ký tự của xâu s1 dùng hàm toupper() chuyển sang ký tự hoa, duyệt từng ký tự của xâu s2 dùng hàm tolower() đê chuyển sang ký tự thường Cách 2: Dùng hàm transform() để chuyển đồi tất cả các ký tự. - transform(s1.begin(), s1.end(),s1.begin(), ::toupper); chuyển tất cả các ký tự trong xâu s1 thành chữ hoa. - transform(s2.begin(), s2.end(),s2.begin(), ::tolower); chuyển tất cả các ký tự trong xâu s2 thành chữ thường. Chương trình: Cách 1 Cách 2 #include #include using namespace std; using namespace std; int main() int main() { { string s,s1,s2; string s,s1,s2; getline(cin,s); getline(cin,s); s1=""; s1=s; s2=""; s2=s; char c; transform(s1.begin(),s1.end(),s1.begin(),::toupper); for(int i=0;i<s.size();i++){ transform(s2.begin(),s2.end(),s2.begin(),::towlower); c=toupper(s[i]); cout<<s1<<"\n"; s1=s1+c; cout<<s2; c=towlower(s[i]); return 0; s2=s2+c; } } cout<<s1<<"\n"; cout<<s2; return 0; } Bài 3: Công tác quản lý thi: Trong công tác tổ chức các kỳ thi, để đảm bảo tính khách quan, công bằng cho các thí sinh, một công đoạn hết sức quan trọng là lập danh sách dự thi và đánh số báo danh. Để đánh số báo danh, danh sách phải được sắp xếp với tên theo bảng chữ cái.
6. Em hãy viết chương trình giúp cán bộ làm công tác thi, nhập vào số nguyên n là số lượng thí sinh, sau đó đưa vào họ và tên của n thí sinh, đưa ra danh sách thí sinh đó nhưng đã được sắp xếp với tên theo bảng chữ cái. Hướng dẫn: - Dùng mảng hoten để lưu danh sách thí sinh: hoten[i] ghi họ và tên thí sinh i. - Với mỗi thí sinh i, tách lấy phần tên lưu vào mảng: ten[i] - Sắp xếp mảng tên theo thứ tự tăng dần, với mỗi lượt tráo đổi 2 phần tử trong mảng tên thì tráo đổi luôn 2 phần tử tương ứng trong mảng hoten. Xuất ra kết quả là danh sách thí sinh trong mảng hoten Chương trình tham khảo #include using namespace std; struct thisinh{ string hoten; string ten; }; bool comp(thisinh a, thisinh b){ return a.ten<b.ten; } int main() { int n; cin>>n; cin.ignore(32767,'\n'); thisinh s[n]; int l; int j; for(int i=0;i<n;i++){ getline(cin,s[i].hoten); l=s[i].hoten.size(); j=l-1; while(s[i].hoten[j]!=' '){
7. j--; } s[i].ten=s[i].hoten.substr(j+1,l-j); } sort(s,s+n,comp); for(int i=0;i<n;i++){ cout<<s[i].hoten; cout<<"\n"; } return 0; } Bài 4: Đếm số lần xuất hiện mỗi loại ký tự. Cho xâu s (có độ dài không vượt quá 103) chỉ gồm các ký tự từ 'A' đến 'Z'. Cho biết có bao nhiêu loại ký tự xuất hiện trong s và đưa ra một ký tự xuất hiện nhiều nhất trong s cùng với số lần xuất hiện của ký tự đó Hướng dẫn: Các ký tự từ 'A' đến 'Z' có mã ASCII tương ứng từ 65 đến 90. Nên ta sử dụng mảng T gồm 91 phần tử với kiểu chỉ số từ 0 đến 90, kiểu giá trị int để lưu số lần xuất hiện: T[65] T[90] tương ứng số lần xuất hiện ký tự ‘A’ ‘Z’. Lần theo các giá trị của mảng T trên đoạn từ 65 đến 90 ta được số lượng các ký tự khác nhau (tức số lượng phần tử có giá trị khác 0 trong mảng T) và tìm giá trị lớn nhất của mảng T ta sẽ tìm được ký tự xuất hiện nhiều lần nhất. Về nguyên tắc, ta chỉ cần sử dụng mảng với 26 phần tử kiểu int với chỉ số từ 0 đến 25, khi đó với mỗi ký tự ta chuyển sang mã ASCII rồi dịch chuyển chỉ số 65 đơn vị để lưu vào đầu mảng. Chương trình #include using namespace std; int main() { string s; getline(cin,s);
8. int t[91]; for(int i=65;i<=90;i++){ t[i]=0; } for(int i=1;i<s.size();i++){ t[s[i]]++; } int dem=0; int max=65; for(int i=65;i<=90;i++){ if(t[i]!=0){ dem++; if(t[max]<t[i]){ max=i; } } } cout<<dem<<"\n"; cout<<char(max)<<" "<<t[max]; return 0; } Bài 5: Mã hóa Xê Da (sách bài tập tin học 11) Để giữ bí mật người ta phải mã hóa các thông tin trước khi truyền đi hoặc lưu trữ. Một trong những cách mã hóa sớm nhất được sử dụng rộng rãi thời cổ đại là cách mã hóa do Xê Da đề xuất: trong thông điệp, người ta thay đổ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 theo bảng chữ cái. Nếu bảng chữ cái có N chữ, thì sau chữ cái thứ 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. Các kí tự ngoài bảng chữ cái vẫn được giữ nguyên. Ví dụ, bảng chữ cái tiếng Anh có 26 chữ cái. Nếu K = 2 thì có nghĩa là a được thay thế bằng c, b được thay thế bằng d, . . ., y được thay thế bằng a, z được thay thế
9. bằng b. Các chữ cái in hoa sẽ được thay thế bằng chữ cái in hoa tương ứng. Trong trường hợp này, từ ‘TIN HOC’ sẽ được mã hóa thành ‘VKP JQE’ . Hãy lập trình: Nhập vào từ bàn phím số nguyên K (1<K<=26) và xâu S không quá 255 kí tự. Mã hóa theo quy tắc mã Xê Da và đưa kết quả ra màn hình. Hướng dẫn: Để dễ xử lý hơn khi dịch k ký tự theo vòng tròn, ta dùng thêm 2 biến phụ S1 để lưu 2 lần bảng chữ cái in hoa. S2 lưu 2 lần bảng chữ cái in thường. Duyệt từng ký tự trong xâu s, tìm vị trí xuất hiện của nó trong xâu s1, s2. Nếu tìm thấy thì ta lấy ký tự cách nó k ký tự trên mảng tương ứng. Chương trình tham khảo #include using namespace std; int main() { int n; cin>>n; string s; cin.ignore(32767,'\n'); getline(cin,s); string s1=""; string s2=""; for(int i=65;i<=90;i++){ s1=s1+char(i); s2=s2+char(i+32); } s1=s1+s1+s2+s2; string ans=""; for(int i=0;i<s.size();i++){ int vt=s1.find(s[i]); if(vt==-1){ ans=ans+s[i]; }
10. else{ ans=ans+s1[vt+n]; } } cout<<ans; return 0; } Bài 6: Xâu con dài nhất Cho xâu S, tìm xâu con liên tục dài nhất của xâu S mà không chứa chữ số nào. Kết quả đưa ra vị trí đầu và xâu con đó. Nếu có nhiều xâu con dài nhất thì đưa ra xâu đầu tiên. Hướng dẫn: Có rất nhiều giải thuật để duyệt tìm xâu con dài nhất thỏa mãn một điều kiện nào đó. Cách 1: Duyệt vét cạn thử với mọi xâu con để tìm xâu con dài nhất. Sử dụng hai vòng for lồng nhau duyệt từ đầu đến hết xâu với mỗi cặp chỉ số đầu i và chỉ số j. Ta kiểm tra có thỏa mãn điều kiện hay không, rồi so sánh tìm xâu con thỏa mãn dài nhất. Cách 2: Duyệt theo các xâu con với độ dài từ lớn đến bé. Ta duyệt các xâu con với độ dài từ độ dài xâu mẹ giảm dần. Khi gặp xâu con đầu tiên thỏa mãn điều kiện thì đây chính là xâu cần tìm và ta kết thúc việc duyệt bằng lệnh break; Cách 3: Duyệt phát triển xâu con: Lần lượt duyệt lần lượt các ký tự trong xâu, dùng biến lmax để lưu độ dài xâu lớn nhất đã tìm được, nếu gặp ký tự thỏa mãn (không phải số) ta tăng dần độ dài xâu con. Khi gặp ký tự không thỏa mãn (ký tự số) thì ta thu được một xâu con thỏa mãn điều kiện, đem độ dài xâu này so sánh với lmax đã lưu để cập nhật lại lmax mới. Với bài toán này ta sử dụng cách 3 duyệt theo phát triển xâu con với độ phức tạp o(n). Chương trình tham khảo #include using namespace std;
11. int main() { string s; getline(cin,s); int lmax=0; int l=0; int c; for(int i=0;i<s.size();i++){ if(isdigit(s[i])==false){ l++; } else{ if(lmax<l){ c=i; lmax=l; } l=0; } } string k=s.substr(c-lmax,lmax); cout<<lmax<<" "<<k; return 0; } Bài 7: Đếm xâu con (có chồng lấn và không chồng lấn lên nhau) Viết chương trình nhập vào 2 xâu ký tự s1, s2. Hãy cho biết số lần xuất hiện xâu s2 trong xâu s1 không chồng lấn và số lần xuất hiện xâu s2 trong s1 có chồng lấn. Ví dụ: s1= “ababababaab” S2= “aba” Kết quả: Số lần xuất hiện không chồng lấn là: 2 Số lần xuất hiện có chồng lấn là: 4 Hướng dẫn: Cách 1: Sử dụng hàm tìm kiếm sự xuất hiện xâu s2 trong xâu s1. Khi tìm thấy s2 trong s1, ta xóa (hoặc thay thế bởi xâu “”) toàn phần tìm thấy hoặc 1 ký tự tại vị trí tìm thấy rồi tìm tiếp. Nếu dung câu lệnh find() có tham số vị trí bắt đầu thì không cần xóa. Cách 2: Ta có thể dùng lệnh while duyệt sao chép đoạn con của s1 có độ dài bằng l2 (độ dài xâu s2) để so sánh với s2, trong yêu cầu 1 nếu tìm thầy thì ta nhảy qua l2 vị trí tiếp theo.