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
Tags:
DevC