BÀI TOÁN XÂU KÝ TỰ
1. Khái niệm.
v Khái niệm
§ Kiểu char chỉ chứa được một ký tự. Để lưu trữ một chuỗi (nhiều ký tự) ta sử dụng mảng (một chiều) các ký tự.
§ Chuỗi ký tự kết thúc bằng ký tự ‘\0’ (null)
=> Độ dài chuỗi = kích thước mảng – 1
Ví dụ.
char hoten[30]; // Dài 29 ký tự
char ngaysinh[9]; // Dài 8 ký tự
2. Khởi tạo.
v Khởi tạo như mảng thông thường
§ Độ dài cụ thể
char s[10] = {‘T’, ‘H’, ‘C’, ‘S’, ‘A’, ‘ ’, ‘\0’};
char s[10] = “THCS A”; // Tự động thêm ‘\0’
§ Tự xác định độ dài
char s[] = {‘T’, ‘H’, ‘C’, ‘S’, ‘ ’, ‘A’, ‘\0’};
char s[] = “THCS A”; // Tự động thêm ‘\0’
3. Các thao tác trên chuỗi ký tự.
3.1. Xuất chuỗi.
v Sử dụng hàm printf với đặc tả “%s”
char monhoc[50] = “Tin hoc co so A”;
printf(“%s”, monhoc); // Không xuống dòng
v Sử dụng hàm puts
char monhoc[50] = “Tin hoc co so A”;
puts(monhoc); // Tự động xuống dòng
ó printf(“%s\n”, monhoc);
3.2. Nhập chuỗi.
v Sử dụng hàm scanf với đặc tả “%s”
§ Chỉ nhận các ký tự từ bàn phím đến khi gặp ký tự khoảng trắng hoặc ký tự xuống dòng.
§ Chuỗi nhận được không bao gồm ký tự khoảng trắng và xuống dòng.
char monhoc[50];
printf(“Nhap mot chuoi: “);
scanf(“%s”, monhoc);
printf(“Chuoi nhan duoc la: %s”, monhoc);
v Sử dụng hàm gets
§ Nhận các ký tự từ bàn phím đến khi gặp ký tự xuống dòng.
§ Chuỗi nhận được là những gì người dùng nhập (trừ ký tự xuống dòng).
char monhoc[50];
printf(“Nhap mot chuoi: “);
gets(monhoc);
printf(“Chuoi nhan duoc la: %s”, monhoc);
v Một số hàm thao tác trên chuỗi:
§ Thuộc thư viện <string.h>
• strcpy
• strdup
• strlwr/strupr
• strrev
• strcmp/stricmp
• strcat
• strlen
• strstr
§ Hàm sao chép chuỗi
char *strcpy(char dest[], const char src[])
• Sao chép chuỗi src sang chuỗi dest, dừng khi ký tự kết thúc chuỗi ‘\0’ vừa được chép.! dest phải đủ lớn để chứa src
• Trả về địa chỉ chuỗi dest
char s[100];
s = “Tin hoc co so A”; // sai
strcpy(s, “Tin hoc co so A”); // đúng
§ Hàm tạo bản sao
char *strdup(const char s[])
• Tạo bản sao của một chuỗi s cho trước. Hàm sẽ tự tạo vùng nhớ đủ chứa chuỗi s.
• Trả về: nếu thành công: Địa chỉ chuỗi kết quả, nếu thất bài: null
char *s;
s = strdup(“Tin hoc co so A”);
§ Hàm chuyển chuỗi thành chữ thường
char *strlwr(char *s)
• Chuyển chuỗi s thành chuỗi thường (‘A’ thành ‘a’, ‘B’ thành ‘b’, …, ‘Z’ thành ‘z’)
• Trả về: Địa chỉ chuỗi s
char s[] = “Tin hoc co so A!!!”;
strlwr(s);
puts(s); // tin hoc co so a!!!
§ Hàm chuyển chuỗi thành chữ IN
char *strupr(char *s)
• Chuyển chuỗi s thành chuỗi in (‘a’ thành ‘A’, ‘b’ thành ‘B’, …, ‘z’ thành ‘Z’)
• Trả về: Địa chỉ chuỗi s
char s[] = “Tin hoc co so A!!!”;
strupr(s);
puts(s); // TIN HOC CO SO A!!!
§ Hàm đảo ngược chuỗi
char *strrev(char *s)
• Đảo ngược thứ tự các ký tự trong chuỗi (trừ ký tự kết thúc chuỗi)
• Trả về: Địa chỉ chuỗi kết quả
char s[] = “Tin hoc co so A!!!”;
strrev(s);
puts(s); // !!!A os oc coh niT
§ Hàm so sánh hai chuỗi
int strcmp(const char *s1, const char *s2)
• So sánh hai chuỗi s1 và s2 (phân biệt hoa thường)
• Trả về:
o < 0 nếu s1 < s2
o == 0 nếu s1 == s2
o >0 nếu s1 > s2
char s1[] = “tin hoc co so A!!!”;
char s2[] = “hoc tin co so A!!!”;
int kq = strcmp(s1, s2); // => kq > 0
§ Hàm so sánh hai chuỗi
int stricmp(const char *s1, const char *s2)
• So sánh hai chuỗi s1 và s2 (không phân biệt hoa thường)
• Trả về:
o < 0 nếu s1 < s2
o == 0 nếu s1 == s2
o >0 nếu s1 > s2
char s1[] = “tin hoc co so A!!!”;
char s2[] = “TIN HOC CO SO A!!!”;
int kq = stricmp(s1, s2); // => kq == 0
§ Hàm nối hai chuỗi
char* strcat(char *dest, const char *src)
• Nối chuỗi src vào sau chuỗi dest. ! Chuỗi dest phải đủ chứa kết quả
• Trả về: Địa chỉ của chuỗi được nối
char s1[100] = “Tin hoc”;
char s2[] = “co so A!!!”;
strcat(s1, “ ”); // => “Tin hoc ”
strcat(s1, s2); // => “Tin hoc co so A!!!”
§ Hàm tính độ dài chuỗi
size_t* strlen(const char *s)
• Tính độ dài chuỗi s,size_t thay cho unsigned (trong <stddef.h>) dùng để đo các đại lượng không dấu.
• Trả về: Độ dài chuỗi s
char s[] = “Tin hoc co so A!!!”;
int len = strlen(s); // => 18
§ Hàm tìm chuỗi trong chuỗi
char* strstr(const char *s1, const char *s2)
• Tìm vị trí xuất hiện đầu tiên của s2 trong s1
• Trả về:
o Thành công: trả về con trỏ đến vị trí xuất hiện đầu tiên của s2 trong s1.
o Thất bại: trả về null
char s1[] = “Tin hoc co so A!!!”;
char s2[] = “hoc”;
if (strstr(s1, s2) != null)
printf(“Tim thay!”);
4. Một số dạng bài cơ bản
a) Xử lý một xâu ký tự
* Bài toán:
- Dữ liệu: nhập một xâu ký tự S
- Yêu cầu: xử lý xâu ký tự S.
* Một số yêu cầu thường gặp:
- Loại bỏ các ký tự không hợp lệ: Loại bỏ các ký tự không phải ký tự chữ và khoảng trắng, loại bỏ các khoảng trắng ở đầu và cuối xâu ký tự, nếu có nhiều khoảng trắng liền nhau thì chỉ giữ lại một khoảng trắng.
- Chuyển kiểu: đưa xâu S về dạng chữ HOA, chữ thường, ...
- Đếm từ: từ là một số ký tự liên tiếp và khác khoảng trắng.
- Kiểm tra tính chất xâu lặp, xâu đối xứng
- ...
b) Xử lý hai xâu ký tự
* Bài toán:
- Dữ liệu: nhập hai xâu ký tự S1, S2
- Yêu cầu: xử lý hai xâu ký tự S1, S2
* Một số yêu cầu thường gặp:
- Kiểm tra S1 có phải là xâu lặp, hoán vị, ... của S2.
- Tìm số lần xuất hiện của S1 trong S2.
- Tìm xâu con chung liên tiếp dài nhất của S1 và S2.
- ...
c) Xử lý số lớn
* Bài toán:
- Dữ liệu: nhập một số nguyên N lớn (N vượt quá phạm vi biểu diễn của kiểu số nguyên lớn nhất (ví dụ Qword, 8 byte, không dấu).
- Yêu cầu: xử lý số nguyên N
* Một số yêu cầu thường gặp:
- Thực hiện các phép toán số học (nhân, chia, cộng, trừ) với N.
- ...
5. Bài tập minh họa
5.1. Bài tập 1
a) Bài toán
o Dữ liệu: từ tập tin xaulap.inp xâu ký tự S chỉ chứa các ký tự chữ cái và có không quá 250 ký tự.
o Yêu cầu: kiểm tra xem có hay không 1 xâu X sao cho S là lặp lại k lần của X, (k > 1)?
o Kết quả: xuất ra tập tin xaulap.out giá trị 0 nếu S không phải xâu lặp, ngược lại kết quả là xâu X có độ dài lớn nhất tìm được.
Ví dụ:
Xaulap.inp | Xaulap.out |
ABCABCABCABC | ABCABC |
b) Chương trình
* Nhận xét:
- Do S là lặp lại k lần của X và k > 1 nên độ dài tối đa của X là bằng 1/2 độ dài của S.
- Nếu S là xâu lặp k lần của xâu X thì độ dài của X phải là ước số của độ dài của S.
5.2. Bài tập 2
a) Bài toán
o Dữ liệu: từ tập tin demtu.inp xâu ký tự S có không quá 1000 ký tự.
o Yêu cầu: Do có lỗi trong quá trình soạn thảo nên xâu ký tự S bị một số lỗi như sau: có một số ký tự lạ (không phải ký tự chữ và khoảng trắng), thừa một số khoảng trắng (ở đầu, cuối và nhiều khoảng trắng giữa các từ trong xâu). Biết rằng: từ là một nhóm các ký tự liên tiếp khác khoảng trắng. Hãy chuẩn hóa xâu S bằng cách loại bỏ các ký tự không hợp lệ và đếm số từ có trong xâu S.
o Kết quả: xuất ra tập tin xaulap.out gồm 2 dòng: dòng 1 chứa xâu S sau khi đã chuẩn hóa, dòng 2 chứa số từ trong xâu S.
Ví dụ:
Demtu.inp | Demtu.out |
K1hoa C2ong Nghe3 Thong 4 Tin @ | Khoa Cong Nghe Thong Tin 5 |
b) Chương trình
* Nhận xét:
- Do xâu S có không quá 1000 ký tự nên phải sử dụng kiểu xâu ký tự dài (AnsiString).
- Bài toán đếm từ của một xâu ký tự chính là bài toán đếm số dãy con của một dãy cho trước, trong đó mỗi dãy con là một từ!
* Ý tưởng:
o B1: Loại bỏ các ký tự không hợp lệ
o B2: Loại bỏ các khoảng trắng ở đầu
o B3: Loại bỏ các khoảng trắng ở cuối
o B4: Loại bỏ các khoảng trắng thừa giữa 2 từ, chỉ giữ lại đúng 1 khoảng trắng
o B5: Đếm từ
5.3. Bài tập 3
a) Bài toán
o Dữ liệu: từ tập tin chia3.inp số nguyên dương N có không quá 100 chữ số.
o Yêu cầu: Tìm số dư R khi chia N cho 3.
o Kết quả: xuất ra tập tin chia3.out giá trị của R.
Ví dụ:
Chia3.inp | Chia3.out |
12345678900 | 0 |
b) Chương trình
* Nhận xét:
- Do số N có không quá 100 chữ số nên không thể sử dụng các kiểu dữ liệu số để biểu diễn N mà phải sử dụng kiểu xâu ký tự (String).
- Dấu hiệu chia hết của 3 của một số nguyên dương N là tổng các chữ số của N chia hết cho 3.
* Ý tưởng 1:
o B1: Chuyển đổi các ký tự của N thành chữ số và tính tổng
o B2: Tìm số dư khi chia N cho 3
* Ý tưởng 2:
o B1: Chia các ký tự của N thành các nhóm đồng dư theo mô đun 3 (0, 3 6, 9), (1, 4, 7) và (2, 5, 8). Tính tổng các số dư.
o B2: Tìm số dư khi chia N cho 3
.PNG)
Không có nhận xét nào:
Đăng nhận xét