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 4: Các phép lật và chuyển vị

 kết quả về nền nhà đã lát vào mảng 
hai chiều a rồi chuyển qua pha kiểm lỗi. 
 Nếu a[x][y] ≠ 0 ta ghi nhận lỗi 1: đặt sai lỗ thoát nước; 
Với mỗi ô (i,j) trên nền nhà ta gọi thủ tục Loang(i,j,c,d), trong đó c là màu của ô (i,j), c = a[i][j]. 
Thủ tục này đánh dấu và đếm số ô cùng màu c và liên thông cạnh với ô (i,j). Gọi số ô đếm được là s. Ta 
xét: 
 Nếu s > 3 tức là có hơn hai viên gạch chữ L cùng màu và kề cạnh nhau, vì mỗi viên gạch chữ L chỉ được 
phép chiếm tối đa 3 ô cùng màu. Trường hợp này ta ghi lỗi 2: đặt gạch sai. 
 Nếu s = 3 nhưng 3 ô cùng màu đó nằm thẳng hàng thì báo lỗi 2: đặt gạch sai. 
Thủ tục Loang còn đảm nhiệm thêm chức năng tích lũy vào biến d số màu gạch lát khác nhau đã dùng. Nếu 
d ≠ colors ta ghi nhận lỗi 3: số màu thực dùng khác với số màu đã công bố. 
Khi loang ta đánh dấu ô đã xét bằng giá trị đối của nó. 
(* tsquare.pas *) 
uses crt; 
const mn = 100; bl = #32; nl = #13#10; 
 gn = 'square.out'; hn = 'test.out'; 
type mi1 = array[0..mn] of integer; 
 mi2 = array[0..mn] of mi1; 
var 
 a: mi2; 
 n, x, y, colors: integer; 
procedure Loang(i, j, c: integer; var d: integer); 
begin 
 if (a[i][j] c) then exit; 
 a[i][j] := -a[i][j]; inc(d); 
 Loang(i+1,j,c,d); 
 Loang(i-1,j,c,d); 
 Loang(i,j+1,c,d); 
 Loang(i,j-1,c,d); 
end; 
(* 
0: khong co loi 
1: Dat sai lo thoat 
2: Dat sai gach 
3: sai so mau 
*) 
procedure Test; 
 var i, j, c, dc, d: integer; 
 g,h: text; 
 col: mi1; { danh dau so mau da dung } 
begin 
 assign(g,gn); reset(g); 
 read(g,n,x,y,colors); 
 write(nl,' n = ', n, ' x = ', x, ' y = ', y); 
 fillchar(a,sizeof(a),0); fillchar(col,sizeof(col),0); 
 for i := 1 to n do 
 begin 
 writeln; 
 for j := 1 to n do 
 begin 
 read(g,a[i][j]); write(a[i][j],bl); 
 end; 
 end; 
 close(g); 
 writeln; 
 assign(h,hn); rewrite(h); dc := 0; 
 if (a[x][y] 0) then 
 begin writeln(h,1); close(h); exit; end; 
 for i := 1 to n do 
 for j := 1 to n do 
 begin 
 c := a[i][j]; 
 if (c > 0) then 
 begin 
 if (col[c] = 0) then 
 begin col[c] := 1; inc(dc) end; 
 d := 0; Loang(i,j,c,d); 
 if (d 3) then 
 begin writeln(h,2); close(h); exit end; 
 { d = 3: xet 3 phan tu lien tiep } 
 if ( (a[i][j]=a[i][j+1])and(a[i][j]=a[i][j+2]) ) 
 or ( (a[i][j]=a[i+1][j])and(a[i][j]=a[i+2][j]) ) 
 then begin writeln(h,2); close(h); exit end; 
 end; 
 end ; { for } 
 if (d colors) then begin writeln(h,3); close(h); exit end; 
 writeln(h,0); close(h); 
end; 
BEGIN 
 Test; 
 writeln(nl,' Fini'); 
 readln; 
END. 
// DevC++: tsquare.cpp 
#include 
#include 
#include 
using namespace std; 
// D A T A A N D V A R I A B L E 
const int mn = 101; 
const char * gn = "square.out"; 
const char * hn = "test.out"; 
const char bl = ' '; 
int a[mn][mn]; 
int n, x, y, colors; 
// P R O T O T Y P E S 
void Test(); 
void Loang(int, int, int, int& ); 
// I M P L E M E N T A T I O N 
int main() { 
 Test(); 
 cout << endl << " Fini" << endl; 
 cin.get(); 
 return 0; 
} 
/* 
0: khong co loi 
1: Dat sai lo thoat 
2: Dat sai gach 
3: sai so mau 
*/ 
void Test() { 
 ifstream g(gn); 
 g >> n >> x >> y >> colors; 
 cout << endl << " n = " << n << ", x = " << x << ", y = " << y 
 << ", colors = " << colors << endl; 
 int i, j, c, dc, d; // dc dem so mau 
 int col[100]; // danh dau mau da dung 
 memset(a,0,sizeof(a)); memset(col,0,sizeof(col)); 
 for (i = 1; i <= n; ++i) { 
 cout << endl; 
 for (j = 1; j <= n; ++j) { 
 g >> a[i][j]; cout << a[i][j] << bl; 
 } 
 } 
 g.close(); 
 cout << endl; 
 ofstream h(hn); dc = 0; 
 if (a[x][y] != 0) { h << 1; h.close(); return; } 
 for (i = 1; i <= n; ++i) 
 for (j = 1; j <= n; ++j) { 
 c = a[i][j]; 
 if (c > 0) { 
 if (col[c] == 0) {col[c] = 1; ++dc; } // them mau moi 
 d = 0; Loang(i,j,c,d); 
 if (d != 3) { h << 2; h.close(); return; } 
 // d = 3: xet 3 phan tu lien tiep 
 if ( ( (a[i][j]==a[i][j+1])&&(a[i][j]==a[i][j+2]) ) 
 || ( (a[i][j]==a[i+1][j])&&(a[i][j]==a[i+2][j]) ) ) 
 { h << 2; h.close(); return; } 
 }// if c > 0 
 }// for j 
 if (d != colors) { h << 3; h.close(); return; } 
 h << 0; 
 h.close(); 
} 
void Loang(int i, int j, int c, int &d) { 
 if (a[i][j] != c) return; 
 a[i][j] = -a[i][j]; ++d; 
 Loang(i+1,j,c,d); 
 Loang(i-1,j,c,d); 
 Loang(i,j+1,c,d); 
 Loang(i,j-1,c,d); 
} 
4.9 Giải mã 
Cho mã nhị phân của n chữ cái đầu bảng chữ tiếng Anh A, B, C,.... Biết rằng không có mã nào là khúc đầu 
của mã khác và chiều dài tối đa của mỗi mã là 10. Lập chương trình giải mã một văn bản cho trước. 
Input text file: code.inp 
Dòng đầu tiên: số n; 1  n  26. 
Tiếp đến là n dòng, mỗi dòng chứa mã nhị phân của một chữ cái theo trật tự A, B, C,... 
Cuối cùng là dòng chứa mã cần giải. 
Output file: code.out chứa văn bản đã giải. 
code.inp code.out 
5 
0000 
0001 
0010 
0011 
110 
0000000100010000 
ABBA 
Thí dụ trên cho mã của n = 5 kí tự đầu trong bảng chữ cái tiếng Anh là A = 0000, B = 0001, C = 
0010, D = 0011 và E = 110. Đoạn mã văn bản cần giải là s = 0000000100010000. Sau khi giải 
mã ta phải thu được kết quả: ABBA. 
Thuật toán 
Trước hết ta xây dựng cây nhị phân h với các nhánh trái ứng với giá trị 0 của mỗi mã, nhánh phải ứng với 
giá trị 1. Tại các lá của cây ta ghi kí tự tương ứng của mã đó. Như vậy, dãy nhãn trên mỗi đường đi từ gốc 
cây h đến lá của h sẽ lập thành mã của kí tự trên lá. Thí dụ, đường đi 0011 sẽ kết thúc tại lá D, do đó 0011 
là mã nhị phân của D. 
Sau đó dựa vào dãy bit 0/1 của mã văn bản s ta giải mã thông qua phép duyệt cây h như sau: 
Ta có thể cài đặt nhanh bằng cách sử dụng heap (chùm, đống) thay cho cây. Trong bài này ta hiểu heap h là 
một cây nhị phân đầy đủ (gọi là cây cân bằng hoàn toàn). Nếu gọi đỉnh đầu tiên của h là 1 thì hai đỉnh kề 
của nó sẽ nhận mã số là 2 và 3..., tổng quát, hai đỉnh kề của đỉnh i sẽ có mã số 2i và 2i+1, trong đó ta qui 
định nhánh i  2i sẽ là nhánh trái, do đó nhận nhãn 0; nhánh i  2i+1 là nhánh phải, do đó nhận nhãn 1. 
Nếu độ dài tối đa của mã là k thì heap sẽ có 2k+11 phần tử. Thật vậy, do heap có k nhánh tính từ gốc đến lá 
nên sẽ có k+1 mức với số lượng đỉnh theo từng mức lần lượt là 1, 2, 4,…, 2i,…, 2k. Tổng số đỉnh của heap 
khi đó là 
1 + 2 + 2
2
 + …+ 2k = 2k+1 – 1 
Áp dụng công thức trên cho độ dài max của mã k = 10 ta tính được số phần tử của heap sẽ là 2111 = 2047. 
Như vậy ta có thể sử dụng một mảng h để chứa các đỉnh của cây. Thủ tục tạo cây trên heap khi đó sẽ khá 
đơn giản. 
Tạo cây h như một cây con của heap 
 Duyệt cây h để giải mã văn bản 
1. Xuất phát từ gốc h. 
2. Duyệt lần lượt mỗi bit si. xét 2 tình huống: 
2.1 Nếu si = 0: rẽ trái; 
 Nếu si = 1: rẽ phải. 
2.2 Nếu gặp lá thì: 
- Ghi kí tự trên lá vào kết quả; 
- Quay lại gốc h. 
3. end. 
1 
1 
0 
0 
1 
A B C D 
0 0 
0 0 1 1 E 
h 
1. Khởi trị mọi phần tử của mảng h bằng 0 với ý nghĩa 
 h[i] = 0: đỉnh i là đỉnh trung gian hoặc không thuộc 
cây; 
 h[i] = C: đỉnh i là lá và đường đi từ gốc đến đỉnh i sẽ 
là mã của kí tự C. 
2. Với mỗi mã (u1, u2,…,um) của kí tự C ta xét 
 2.1 Gọi v là số hiệu của đỉnh trong cây h. 
 Khởi trị v := 1; 
2.2 Với mỗi bit ui xét. 
Nếu ui = 0: tính v := 2*v; 
Nếu ui = 1: tính v := 2*v + 1; 
3.2 Gán h[v] := C. 
3. end. 
 Và thủ tục giải mã trên heap h khi đó sẽ là: 
Giải mã s trên heap h 
. Xuất phát từ gốc h với v := 1. 
2. Với mỗi bit si của mã văn bản s xét: 
2.1 Nếu si = 0: tính v := 2*v ; 
 Nếu si = 1: tính v := 2*v + 1. 
2.2 Nếu h[v] ≠ 0 tức là đã gặp lá thì: 
- Ghi kí tự trên lá vào kết quả; 
- Quay lại gốc h: đặt v := 1. 
3. end. 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
0 0 0 0 0 0 0 0 0 0 0 0 0 E 0 A B C D 
 Heap h thu được sau khi đọc dữ liệu 
Độ phức tạp 
Có n mã cho n kí tự, mỗi mã được duyệt 1 lần để tạo heap. Gọi chiều dài tối đa của mã là k. Vậy để tạo 
heap ta cần n.k thao tác. Để giải mã ta duyệt mỗi bit trong bản mã 1 lần trên cây nhị phân. Vậy khi giải mã 
ta cần m = len(s) thao tác trên cây nhị phân. Thao tác trên cây nhị phân v đỉnh cần log2(v) = k phép so sánh. 
Tổng hợp lại, tính theo chiều dài m của mã văn bản ta cần mk phép so sánh. 
Chương trình 
(* code.pas *) 
uses crt; 
const fn = 'code.inp'; gn = 'code.out'; 
 mn = 2050; bl = #32; nl = #13#10; 
var h: array[0..mn] of char; 
procedure Decode; 
var i, j, v, n: integer; 
 ch: char; 
 f,g: text; 
 x: string; 
begin 
 ch := 'A'; 
 assign(f,fn); reset(f); 
 assign(g,gn); rewrite(g); 
 readln(f,n); writeln(n,nl,nl); 
 fillchar(h,sizeof(h),0); 
 {Tao heap h } 
 for i := 1 to n do 
 begin 
 readln(f,x); writeln(x); 
 v := 1; 
 for j := 1 to length(x) do 
 if x[j] = '0' then v := v*2 else v := v*2 + 1; 
 h[v] := ch; inc(ch); 
 end; 
 writeln(nl); 
 for i := 1 to mn do 
 if (h[i] #0) then writeln(i,bl,h[i]); 
 v := 1; { Giai ma } 
 while not eof(f) do 
 begin 
 read(f,ch); 
 if (ch = '0') or (ch = '1') then 
 begin 
 v := 2*v; 
 if ch = '1' then v := v+1; 
 if (h[v] #0) then 
 begin 
 write(g,h[v]); 
 v := 1; 
 end; 
 end; 
 end; 
 close(f); close(g); 
end; 
BEGIN 
 Decode; 
 writeln(nl, ' Fini '); 
 readln; 
END. 
// DevC++: code.cpp 
#include 
#include 
using namespace std; 
const char * fn = "code.inp"; 
const char * gn = "code.out"; 
const int mn = 2050;char h[mn]; // heap 
int main(); 
void Decode(); 
int main() { 
 Decode(); 
 cout << endl << " Fini "; 
 cin.get(); 
 return 0; 
} 
void Decode() { 
 int i, j, v, n; 
 char x[15]; // doan ma 
 char ch = 'A'; 
 ifstream f(fn); f >> n; cout << endl << n; 
 f.getline(x,mn,'\n'); 
 ofstream g(gn); 
 memset(h,0,sizeof(h)); 
 cout << endl << endl; 
 // Tạo heap h 
 for (i = 0; i < n; ++i) { 
 f.getline(x,mn,'\n'); cout << endl << x; 
 v = 1; 
 for (j = 0; x[j]; ++j)