Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 3 - Chương 1: Các thuật toán trên String

; 
 for (int i = 0; i > w[i]; 
 f >> s; lens = strlen(s); 
 f.close(); 
} 
void Xem() { 
 cout << endl << n << " " << s; 
 for (int i = 0; i < n; ++i) cout << endl << w[i]; 
} 
// Nhung tu w vao tien to s:i 
int Nhung(char *w, int i) { 
 int j = strlen(w)-1; 
 if (i < j) return -1; 
 if (w[j] != s[i]) return -1; 
 for (; i >= 0; --i) 
 if (w[j] == s[i]) { 
 --j; 
 if (j < 0) return i; 
 } 
 return -1; 
} 
int XuLi() { 
 for (int i = 0; i < lens; ++i) Tinhd(i); 
 return d[lens-1]; 
} 
void Tinhd(int i) { 
 int j, k, v; 
 d[i] = (i == 0) ? 1 : (d[i-1]+1); 
 for (j = 0; j < n; ++j) 
 if ((v = Nhung(w[j],i)) >= 0) { 
 k = (v == 0) ? 0 : d[v-1]; 
 d[i] = Min(d[i], k+i-v+1-strlen(w[j])); 
 } 
} 
Độ phức tạp. Cỡ p.n.m, trong đó p = len(s), n là số từ trong từ điển T, m là chiều dài của từ dài nhất trong 
T. 
Chú thích Bạn có thể cải tiến chương trình như sau. Khi đọc dữ liệu và tổ chức từ điển T bạn có thể loại 
trước khỏi T những từ w nào mà kí tự đầu tiên w[1] hoặc kí tự cuối cùng w[m] không xuất hiện trong s vì 
khi đó chắc chắn là hàm Nhung sẽ cho giá trị 1. Tốt hơn cả là bạn cho w trượt trong s để xác định xem w 
đặt lọt tại các chỉ số nào trong s. 
1.8 TEFI 
TEFI.INP TEFI.OUT Trong text file tên TEFI.INP gồm n dòng và m cột 
 người ta dùng dấu chấm '.' tạo thành một bảng 
nền. Trên bảng nền đó người ta dùng dấu sao '*' 
để viết các chữ IN HOA T, E, F và I theo các qui 
tắc sau: 
- chân phương, không có chân 
- đơn nét 
- các nét song song không dính nhau 
- các nét của hai chữ không dính nhau mà cách 
nhau ít nhất một dấu chấm 
Hãy đếm số chữ cái mỗi loại. 
Thí dụ bên cho biết có 3 chữ T, 2 chữ E, 2 chữ F 
và 3 chữ I. 
15 27 
...........***............. 
***.........*.....****..... 
*...........*.....*........ 
***...............***...... 
*....***********..*........ 
*........*........*..*****. 
***..*...*...***.....*..... 
.....*...*....*..*...*..... 
.....*...*....*..*...****.. 
.........*....*..*...*..... 
..****...*.......*...*..... 
..*......*..*....*...****.. 
..***....*..*.............. 
..*.........*.............. 
..*.........*.............. 
3 2 2 3 
Thuật toán 
Ta xét hai dòng x và y liên tiếp nhau trong bảng nền và thử phát hiện đặc trưng của các chữ cái dựa trên 2 
dòng này. Ta thấy, chữ T có đặc trưng duy nhất (không lẫn với các chữ cái khác) là đầu trên gồm 1 vach 
ngang (–) và 1 sổ đứng (|) dính nhau. Chữ I có đặc trưng duy nhất là một sổ đứng (|). Trong chữ E có 2 nét 
ngang trên và 2 nét ngang dưới, chữ F có 2 nét ngang trên và 1 nét ngang dưới. 
 i i i i 
x * * . . * * . * dnt = số nét ngang trên. 
dnd = số nét ngang dưới. 
dx = đếm số chữ X; 
X = {T,E,F,I}. 
Mỗi chữ E có 2 nét ngang trên và 
2 nét ngang dưới. Mỗi chữ F có 2 
nét ngang trên và 1 nét ngang 
dưới. 
de+df = dnt / 2; de = dnd – dnt/2. 
df = dnt/2 – de. 
y * . * . . * . * * 
 Đầu trên 
chữ T 
 Đầu trên 
chữ I 
 Nét ngang 
trên và 
giữa của 
chữ E và F 
 Nét ngang 
dưới của 
chữ E và F 
Để tiện xử lý ta thêm vào đầu và cuối mỗi xâu một dấu chấm '.'. Các trường hợp cần xét được mô tả chi tiết 
dưới dạng bảng quyết định. 
Bảng quyết định cho bài toán TEFI 
Bảng quyết định gồm 2 phần: phần điều kiện và 
phần quyết định.Các điều kiện được liệt kê độc 
lập nhau. 
Giá trị 1 ứng với điều kiện đúng (true), 0 ứng với 
điều kiện sai (false), dấu – cho biết điều kiện này 
không cần xét. 
Bảng được đọc theo cột: nếu các điều kiện trong 
cột thuộc phần điều kiện được thỏa thì quyết định 
tại cột đó được chọn. 
x  dòng trên; y  dòng dưới. 
Điều kiện 
x[i] = '*' 1 0 1 1 
x[i–1] = '*' 1 - 0 0 
x[i+1] = '*' - - 1 - 
y[i] = '*' 1 1 1 1 
y[i–1] = '*' - 0 0 0 
y[i+1] = '*' - 0 - 1 
Quyết 
định 
T (chữ T) 1 
 (nét ngang trên) 1 
L (nét ngang dưới) 1 
I (chữ I) 1 
Dựa vào bảng quyết định ta duyệt đồng thời dòng trên x và dòng dưới y để đếm các giá trị sau: 
dt là số lượng chữ T, di là số lượng chữ i, dnt là số lượng nét ngang trên  và dnd là số lượng nét ngang 
dưới L. Từ các giá trị dnt và dnd ta dễ dàng tính được số lượng chữ E và số lượng chữ F. Vì mỗi chữ E và 
mỗi chữ F đều có cùng 2 nét ngang trên nên de + df = dnt/2 (1). Mỗi chữ E có 2 nét ngang dưới, mỗi chữ F 
có 1 nét ngang dưới nên 2.de + df = dnd (2). Trừ từng vế của (2) cho (1) ta thu được de = dnd – dnt/2. Từ 
(1) ta suy ra df = dnt/2 – de. 
Độ phức tạp. cỡ m.n = dung lượng input file. 
(* TEFI.PAS *) 
uses crt; 
const fn = 'tefi.inp'; gn = 'tefi.out'; 
bl = #32; nl = #13#10; ss = '*'; cc = '.'; 
var x, y: string; 
dt, de, df, di: integer; 
n, m: integer; 
dnt, dnd: integer; 
f,g: text; 
procedure EF(i: integer); 
begin 
 if (x[i+1] = ss) then inc(dnt) 
 else if (y[i+1] = ss) then inc(dnd) 
end; 
procedure TEF(i: integer); 
begin 
 if (y[i] = cc) then exit; 
 if (x[i-1] = cc) then EF(i) 
 else inc(dt); 
end; 
procedure II(i: integer); { x[i] = cc } 
begin 
 if (y[i] = ss) and (y[i-1] = cc) and (y[i+1] = cc) then inc(di); 
end; 
procedure TEFI; 
var i,j: integer; 
begin 
 dt := 0; di := 0; dnt := 0; dnd := 0; 
 fillchar(x,sizeof(x),cc); 
 assign(f,fn); reset(f); readln(f,n,m); 
 for j := 1 to n do 
 begin 
 readln(f,y); y := cc + y + cc; 
 for i := 2 to m do 
 begin 
 if (x[i] = ss) then TEF(i) else II(i); 
 end; 
 x := y; 
 end; 
 close(f); 
 i := dnt div 2; { de + df } de := dnd - i; df := i - de; 
end; 
BEGIN 
 TEFI; 
 writeln('T = ',dt,' E = ',de,' F = ',df, ' I = ', di); 
 readln; 
END. 
// DevC++: TEFI.CPP 
#include 
#include 
#include 
#include 
using namespace std; 
const char * fn = "tefi.inp"; 
const char * gn = "tefi.out"; 
string x, y; 
char ss = '*', cc = '.'; 
int n, m; 
int dt, de, df, di, dnt, dnd; 
// P R O T O T Y P E S 
void TEFI(); 
void TEF(int); 
void EF(int); 
void II(int); 
// I M P L E M E N T A T I O N 
int main(){ 
 TEFI(); 
 cout << endl << " T: " << dt << " E: " << de; 
 cout << " F: " << df << " I: " << di; 
 cout << endl << endl << " Fini "; // 3 
 cin.get(); 
 return 0; 
} 
void TEF(int i) { 
 if (y[i] == cc) return; 
 if (x[i-1] == cc) EF(i); 
 else ++dt; 
} 
void EF(int i){ 
 if (x[i+1] == ss) ++dnt; 
 else if (y[i+1] == ss) ++dnd; 
} 
void II(int i) { 
 if (y[i] == ss && y[i-1] == cc && y[i+1] == cc) ++di; 
} 
void TEFI() { 
 int i, j; 
 dt = di = dnt = dnd = 0; 
 ifstream f(fn); 
 f >> n >> m; f.get(); 
 x = cc; 
 for (i = 0; i < 8; ++i) x = x + x; 
 for (j = 0 ; j < n; ++j) { 
 f >> y; y = cc + y + cc; 
 for (i = 1; i <= m; ++i) 
 if (x[i] == ss) TEF(i); 
 else II(i); 
 x = y; 
 } 
 f.close(); 
 i = dnt / 2; // i = de + df 
 de = dnd - i; df = i - de; 
} 
1.9 E xiếc 
EXIEC.INP EXIEC.OUT Trong text file tên EXIEC.INP gồm n dòng và m 
cột người ta dùng dấu chấm '.' tạo thành một 
bảng nền. Trên bảng nền đó người ta dùng dấu 
sao '*' để viết các chữ IN HOA E với nét ngang 
giữa hướng về phía Đông, Tây, Nam và Bắc. 
Qui tắc viết giống như trong bài TEFI. Hãy đếm 
số chữ cái mỗi loại. 
Thí dụ bên cho biết có 2 chữ E (nét ngang 
hướng về phía Đông), 2 chữ  (nét ngang 
hướng về phía Tây). 1 chữ E úp (nét ngang 
hướng về phía Nam), và 2 chữ E ngửa (nét 
ngang hướng về phía Bắc). 
15 27 
........................... 
***...............****..... 
*.................*........ 
***...............***...... 
*....***********..*........ 
*....*...*.....*..****..... 
***..*.*.*.*.*.*........... 
.....*.*.*.*.*.*..****..... 
.......*...*.*.......*..... 
.......*******....****..... 
..****...............*..... 
.....*............****..... 
..****..*...*....*......... 
.....*..*...*....*......... 
..****..**********......... 
2 2 1 2 
Thuật toán 
x * * * * * * Hai E Nam và E Bắc được đặc trưng duy 
nhất qua hướng của nét ngang giữa 
giống chữ T (E Nam) và  (E Bắc). Mỗi 
E Đông có 2 nét dạng L và mỗi E Tây có 
2 nét dạng  . Ngoài ra, mỗi chữ E Bắc 
còn có 1 nét L và 1 nét . Ta có 
Số chữ E Đông = (dd – db)/2, 
Số chữ E Tây = (dtdb)/2, 
Số chữ E Nam = dn, 
Số chữ E Bắc = db. 
y * * * * * * * * 
 Đông 
dd L 
 Tây 
dt  
 Nam 
dn T 
 Bắc 
db  
Đặc trưng của các chữ E xiếc. Các biến dd, dt, dn, 
db dùng để đếm số lần xuất hiện của các đặc trưng. 
Độ phức tạp. cỡ m.n = dung lượng input file. 
(* EXIEC.PAS *) 
uses crt; 
const fn = 'Exiec.inp'; gn = 'Exiec.out'; 
bl = #32; nl = #13#10; ss = '*'; cc = '.'; 
var x, y: string; 
dd, dt, dn , db: integer; 
n, m: integer; 
f,g: text; 
procedure TayNam(i: integer); 
begin 
 if (y[i-1] = ss) then inc(dft) 
 else if (x[i-1] = ss) and (x[i+1] = ss) then inc(dn) 
end; 
procedure DongBac(i: integer); 
begin 
 if (y[i-1] = ss) then inc(db) 
 else inc(dd); 
end; 
procedure DongTayNamBac(i: integer); 
begin 
 if (y[i+1] = ss) then DongBac(i) else TayNam(i); 
end; 
procedure EXIEC; 
var i,j: integer; 
begin 
 dd := 0; dt := 0; dn := 0; db := 0; 
 assign(f,fn); reset(f); readln(f,n,m); 
 fillchar(x,sizeof(x),cc); 
 for j := 1 to n do 
 begin 
 readln(f,y); y := cc + y + cc; 
 for i := 2 to m do 
 if (x[i] = ss) and (y[i] = ss) then DongTayNamBac(i); 
 x := y; 
 end; 
 close(f); 
 dd := (dd-db) div 2; dt := (dt-db) div 2; 
end; 
BEGIN 
 EXIEC; 
 writeln(dd,' ',dt, ' ', dn, ' ', db); readln; 
END. 
// DevC++: EXIEC.CPP 
#include 
#include 
#include 
#include 
using namespace std; 
const char * fn = "exiec.inp"; 
const char * gn = "exiec.out"; 
string x, y; 
char ss = '*', cc = '.'; 
int n, m; 
int dd, dt, dn, db; // huong tro cua vach giua: Dong Tay Nam Bac 
// P R O T O T Y P E S 
void EXIEC(); 
void DongTayNamBac(int); 
void DongBac(int); 
void TayNam(int); 
// I M P L E M E N T A T I O N 
int main(){ 
 EXIEC(); 
 cout << endl << dd << " " << dt; 
 cout << " " << dn << " " << db;