TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH



tải về 2.51 Mb.
trang12/21
Chuyển đổi dữ liệu24.07.2016
Kích2.51 Mb.
#3874
1   ...   8   9   10   11   12   13   14   15   ...   21

4.7 Lát nền 2

Người ta cần lát kín một nền nhà hình vuông cạnh dài n = 2t, (t là một số tự nhiên trong khoảng 1..6) khuyết một ô thoát nước tại vị trí (x,y) bằng những viên gạch màu hình thước thợ (chữ L) tạo bởi 3 ô vuông đơn vị như trong hình 4.7.1(b). Hai viên gạch kề cạnh nhau, dù chỉ 1 đơn vị dài, phải có màu khác nhau. Hãy cho biết một cách lát với số màu ít nhất.



Nền nhà kích thước 88

(t = 3). Lỗ thoát nước tại dòng 5 cột 6


Hình 4.7.1


Dữ liệu vào: tệp văn bản SQUARE.INP:
Dòng đầu tiên: số tự nhiên n;
Dòng thứ hai: hai số tự nhiên x y cách nhau qua dấu cách, trong đó x là tọa độ dòng, y là tọa độ cột của lỗ thoát nước.
Nền nhà kích thước n được mã số dòng 1, 2, …, n tính từ trên xuống và mã số cột 1, 2, …, n tính từ trái qua phải.
Dữ liệu ra: tệp văn bản SQUARE.OUT:
Hai dòng đầu tiên ghi lại các dữ liệu của input file;
Dòng thứ ba: số màu cần dùng cho việc lát nền.

Tiếp đến là một phương án lát nền tìm được, trong đó mỗi viên gạch lát được tạo bởi ba chữ số giống nhau thể hiện màu của viên gạch đó. Các số trên mỗi dòng cách nhau qua dấu cách. Ô thoát nước được ghi số 0.


NEN.INP

NEN.OUT

8

5 6

8

5 6

3

1 1 3 3 1 1 3 3

1 2 2 3 1 2 2 3

3 2 1 1 3 3 2 1

3 3 1 2 2 3 1 1

1 1 3 2 1 0 3 3

1 2 3 3 1 1 2 3

3 2 2 1 3 2 2 1

3 3 1 1 3 3 1 1
Thí dụ, với n = 8 và ô thóat nước tại vị trí x = 5, y = 6 ta có một cách lát nền như hình vẽ.

Thuật toán


1

1

3

3

1

1

3

3

1

2

2

3

1

2

2

3

3

2

1

1

3

3

2

1

3

3

1

2

2

3

1

1

1

1

3

2

1

0

3

3

1

2

3

3

1

1

2

3

3

2

2

1

3

2

2

1

3

3

1

1

3

3

1

1

Hình 4.7.2 Nền nhà với n = 8

(t = 3)

Về số màu, với n = 2 thì chỉ cần 1 viên gạch màu 1. Với mọi n lớn hơn 2 ta sẽ trình bày một thuật toán cần tối đa ba màu. Ta sẽ giải bài toán qua hai pha. Trước hết ta lát nền nhà để chừa một ô trống tại góc cuối cùng (n,n) của nền nhà. Sau đó ta sẽ tìm cách dịch chuyển ô trống này đến vị trí (x,y) cần thiết.



Phần lát nền đã trình bày chi tiết ở tập 1. Thủ tục này có tên là Fill và hoạt động như sau. Đầu tiên ta khởi trị với hình vuông cạnh k = 2 nằm ở góc trên trái của nền nhà được biểu diễn dưới dạng một mảng hai chiều a: ba ô trong hình vuông 2  2 sẽ được điền giá trị 1, ô nằm ở góc dưới phải được điền giá trị 2 (phần tô đậm). Như vậy, sau khi khởi trị ta coi như đã lát xong nền nhà cạnh n = 2 bằng 1 viên gạch màu 1, lỗ thoát nước nằm ở góc dưới-phải (ô (1,1)). Gọi hình được khởi trị là A. Mỗi bước tiếp theo ta thực hiện ba thao tác biến hình sau đây:

  • Tịnh tiến A đi xuống theo đường chéo để thu được hình B (xem thủ tục Copy).

  • Lật A sang phải (tức là lấy đối xứng gương qua trục tung) để thu được hình C (xem thủ tục Right).

  • Lật A xuống dưới (tức là lấy đối xứng gương qua trục hoành) để thu được hình D (xem thủ tục Down).

Chú ý rằng khi lật ta cần thực hiện thêm phép hoán đổi trị 1 và 3 cho nhau.

1

1






















1

1

3

3
















1

1

3

3

1

1

3

3

1

2






















1

2

2

3
















1

2

2

3

1

2

2

3




























3

2

1

1
















3

2

1

1

3

3

2

1




























3

3

1

2
















3

3

1

2

2

3

1

1








































1

1

1

1




1

1

3

2

1

1

3

3























































1

2

3

3

1

2

2

3







1

1

1

1

1

1































3

2

2

1

3

2

1

1























































3

3

1

1

3

3

1

0

Hình 4.7.3

Mỗi lần lặp như vậy ta sẽ thu được hình vuông có cạnh tăng gấp đôi hình trước. Khi k = n ta thu được nền nhà được lát bằng các viên gạnh chữ L với tối đa 3 màu 1, 2 và 3 cho trường hợp n > 2. Riêng ô (n,n) mang giá trị 2 sẽ được sửa thành 0.



Bây gìơ ta chuyển qua pha thứ hai: Dịch chuyển ô trống tại (n,n) đến vị trí (x,y). Ta sẽ sử dụng thao tác cơ bản sau đây: dịch chuyển ô (d,c) tại góc một hình vuông cạnh k tới tâm của hình vuông cụ thể là tới một trong 4 ô nằm tại tâm của hình vuông này.


Ô trống (8,8) được dịch chuyển đến tâm, tới ô (4,4). Hướng dịch chuyển dx = 1 (theo dòng) và dy = 1 (theo cột).

A

C




0

1

D

B




2

3





1

1

3

3

1

1

3

3



1

1

3

3

1

1

3

3



1

2

2

3

1

2

2

3



1

2

2

3

1

2

2

3



3

2

1

1

3

3

2

1



3

2

1

1

3

3

2

1



3

3

1

0

2

3

1

1



3

3

1

0

2

3

1

1



1

1

3

2

1

1

3

3



1

1

3

2

2

1

3

3



1

2

3

3

1

2

2

3



1

2

3

3

1

1

2

3



3

2

2

1

3

2

1

1



3

2

2

1

3

2

2

1



3

3

1

1

3

3

1

0



3

3

1

1

3

3

1

1

Hình 4.7.4

Thủ tục này có tên là ToCenter(k). Độ dịch chuyển theo dòng và cột phụ thuộc vào hướng dịch chuyển. Ta gọi dx là độ dịch chuyển (mỗi bước 1 ô) theo dòng và dy là độ dịch chuyển theo cột. Khi cần dịch ô trống về tâm theo hướng B  A ta đặt dx = dy = 1; theo hướng D  C ta đặt dx = 1, dy = 1; theo hướng C  D ta đặt dx = 1, dy = 1.

Muốn đưa ô trống (d,c) về vị trí (x,y) trước hết ta xác định xem hai ô này rơi vào mảnh nào trong các mảnh phần tư của hình vuông cạnh k. Ta dùng 2 bit để biểu diễn mệnh đề số hiệu dòng và cột lớn hơn hay nhỏ hơn k/2. Như vậy giá trị 01 ứng với mệnh đề: tọa độ dòng của ô (x,y) đang xét x  k/2 và tọa độ cột của ô đó y > k/2. Vậy ô (x,y) đang xét nằm trong mảnh phần tư 1. Theo cách mã hóa nhị phân này, mỗi mảnh sẽ được mã số như sau: A = 0 = 002, B = 3 = 112, C = 1 = 012 và D = 2 = 10. Sau khi đưa được ô (c,d) về tâm ta còn phải thực hiện một bước nhỏ nữa là chuyển tiếp ô này trong phạm vi 4 ô ở tâm để ô (c,d) rơi vào cùng mảnh với ô (x,y). Thủ tục này có tên là Equalize.

Với mỗi hình vuông cạnh k ta chia làm 4 phần A, B, C và D rồi gọi thủ tục Equalize để đưa hai ô (c,d) và (x,y) về cùng một mảnh phần tư. Sau một số lần lặp ta thu được k = 2. Khi đó trong hình vuông 4 ô chứa hai ô (c,d) và (x,y), trong đó (c,d) là ô trống, 3 ô còn lại cùng màu, ta chỉ làm phép đổi chỗ hai ô (c,d) và (x,y) là thu được kết quả.

Độ phức tạp

Thủ tục lát nền duyệt mỗi ô 1 lần nên đòi hỏi n2 phép gán.

Giả sử n = 2t. Thủ tục chuyển ô (c,d) tại góc dưới phải của nền nhà, tức là từ vị trí (n,n) về vị trí lỗ thoát nước (x,y) đòi hỏi t lần lặp, mỗi lần lặp ta phải dịch chuyển tối đa v/2 lần, trong đó v là chiều dài cạnh của mảnh nền nhà hình vuông đang xét. Mỗi lần dịch chuyển ta đổi chỗ 2 ô, do đó cần 3 phép gán. Tổng cộng thủ tục này đòi hỏi cỡ 3t(n/2+n/22+…+n/2t) = 3tn(1/2+1/22+…+1/2t) =3tn(11/2t+1) /(11/2) = 6tn(1/2t+1). Vì n = 2t nên đại lượng trên được rút gọn thành 6tn(1/2n) = 3t với t = log2(n).

Tổng hợp lại, độ phức tạp của bài toán vào cỡ n2.



Chương trình

(* square.pas *)

uses crt;

const fn = 'square.inp'; gn = 'square.out';

bl = ' '; nl = #13#10; mn = 101;

type mi1 = array[0..mn] of integer;

mi2 = array[0..mn] of mi1;

var

a: mi2;

n: integer; { chieu dai nen nha }

x,y : integer; { Vi tri lo thoat nuoc }

colors: integer; { so mau gach lat }

sx, sy: integer; { goc tren trai cua manh dang xet }

d, c: integer; { dong (d) va cot (c) chua o trong }

qdc, qxy: integer;

{ qdc: manh chua o trong d c; qxy: manh chua o x y }

dx, dy: integer; { huong dich chuyen o trong }

procedure ReadData;

var f: text;

begin

assign(f,fn); reset(f);

readln(f,n,x,y);

close(f);

writeln(nl, n, bl, x, bl, y);

end;

procedure Down(k: integer); { Lat xuống }

var i, j, ii, k2: integer;

begin

ii := k; k2 := 2*k;

for i := k+1 to k2 do

begin

for j := 1 to k2 do

a[i][j] := 4-a[ii][j];

dec(ii);

end;

end;

procedure Right(k: integer); { Lật phải }

var i, j, jj, k2: integer;

begin

jj := k; k2 := 2*k;

for j := k+1 to k2 do

begin

for i := 1 to k2 do

a[i][j] := 4-a[i][jj];

dec(jj);

end;

end;

procedure Copy(k: integer); { Tịnh tiến theo đường chéo }

var i, j: integer;

begin

for i := 1 to k do

for j := 1 to k do

a[i+k][j+k] := a[i][j];

end;

procedure Fill; { Lát nền nn }

var k: integer;

begin

a[1][1] := 1; a[1][2] := 1;

a[2][1] := 1; a[2][2] := 2;

k := 2;

while (k > n) do

begin

Down(k); Right(k); Copy(k);

k := k*2;

end;

a[n][n] := 0;

end;

procedure ToCenter(k: integer); { Dịch ô trống (c,d) về tâm }

var nd, nc, i: integer;

begin

nd := d + sx; nc := c + sy; k := k div 2;

for i := 1 to k do

begin

a[nd][nc] := a[nd+dx][nc+dy];

nd := nd + dx; nc := nc + dy;

a[nd][nc] := 0;

end;

d := d + k*dx; c := c + k*dy; { Chỉnh lại tọa độ (c,d) }

end;

{ Manh chua (x,y) trong hinh [1..n,1..n].

0 1

2 3 }

function Quater(n, x, y: integer): integer;

var q, n2: integer;

begin

q := 0; n := n div 2;

if (x > n) then q := q + 2;

if (y > n) then q := q + 1;

Quater := q;

end;

procedure NewPos(n: integer); { tọa độ mới của (x,y) và (c,d) }

begin

if (x > n) then x := x - n;

if (y > n) then y := y - n;

if (d > n) then d := d - n;

if (c > n) then c := c - n;

case qxy of

1: sy := sx + n;

2: sx := sy + n;

3: begin sx := sx + n; sy := sy + n; end;

end;

end;

{ doi cho a[x][y] va a[u][v] }

procedure ISwap(x, y, u, v: integer);

var t: integer;

begin

t := a[sx+x][sy+y]; a[sx+x][sy+y] := a[sx+u][sy+v];

a[sx+u][sy+v] := t;

end;

procedure Equalize(k: integer); { Đưa (c,d) về cùng mảnh với (x,y) }

var k2: integer;

begin

k2 := k div 2;

if d = k then dx := -1 else dx := 1;

if c = k then dy := -1 else dy := 1;

ToCenter(k); { d, c den vi tri moi; a[d][c] = 0 }

case qdc of

0: if (qxy = 1) then

begin

ISwap(d,c,k2,k2+1);

d := k2; c := k2+1;

end else if (qxy = 2) then

begin

ISwap(d,c,k2+1,k2);

d := k2+1; c := k2;

end;

1: if (qxy = 0) then

begin

ISwap(d,c,k2,k2);

d := k2; c := k2;

end else if (qxy = 3) then

begin

ISwap(d,c,k2+1,k2+1);

d := k2+1; c := d;

end;

2: if (qxy = 0) then

begin

ISwap(d,c,k2,k2);

d := k2; c := d;

end else if (qxy = 3) then

begin

ISwap(d,c,k2+1,k2+1);

d := k2+1; c := d;

end;

3: if (qxy = 1) then

begin

ISwap(d,c,k2,k2+1);

d := k2; c := k2+1;

end else if (qxy = 2) then

begin

ISwap(d,c,k2+1,k2);

d := k2+1; c := k2;

end;

end { case };

qdc := qxy;

end;

procedure Move;

var k: integer;

begin

k := n; d := n; c := n;

sx := 0; sy := 0;

while (k > 2) do

begin

if (x = d) and (y = c) then exit;

qdc := Quater(k,d,c); { manh chua (d,c) }

qxy := Quater(k,x,y); { manh chua (x,y) }

if (qdc <> qxy) then

{ chinh dong d va cot c cho cung manh voi (x,y) }

Equalize(k);

k := k div 2; NewPos(k);

end;

{ k = 2. Final }

ISwap(d,c,x,y);

end;

procedure WriteResult;

var i, j: integer;

g: text;

begin

ReadData;

assign(g,gn); rewrite(g);

writeln(g,n); writeln(g, x, bl, y); writeln(g, colors);

for i := 1 to n do

begin

writeln(g);

for j := 1 to n do write(g,a[i][j],bl);

end;

close(g);

end;

procedure Run;

begin

ReadData;

Fill; Move;

if (n = 2) then colors := 1 else colors := 3;

WriteResult;

end;

BEGIN

Run;

writeln(nl,' Fini');

readln;

END.

// DevC++: square.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; // kich thuoc toi da cua nen nha

const char * fn = "square.inp";

const char * gn = "square.out";

const char bl = ' ';

int a[mn][mn]; // nen nha

int n; // chieu dai nen nha

int x, y; // vi tri lo thoat nuoc;

int colors; // so mau

int sx,sy; // goc tren trai cua manh dang xet

int d,c; // dong (d) va cot (c) chua o trong

int qdc, qxy; // qdc: manh chua o trong d c; qxy: manh chua o x y

int dx, dy; // huong dich chuyen o trong

// P R O T O T Y P E S

void ReadData(); // doc du lieu: n, x, y

void Fill(); // lat nen nha

void Move(); // di chuyen o trong tu vi tri (d,c) den vi tri (x,y)

void WriteResult(); // Ghi file

void Down(int);// Lat len

void Right(int);// Lat phai

void Copy(int); // dich cheo

void Run();

void ToCenter(int); // di chuyen o trong den giua manh

int Quater(int n, int x, int y);// manh phan tu chua o (x,y) trong manh nxn

void NewPos(int); // toa do moi

void Equalize(int);// can bang 2 manh

void ISwap(int, int, int, int);

// I M P L E M E N T A T I O N

int main() {

Run();

cout << endl << " Fini" << endl;

cin.get();

return 0;

}

void ReadData() {

ifstream f(fn);

f >> n >> x >> y;

f.close();

}

void Down(int k) { // Lật xuống

int i,ii = k, j, k2 = k*2;

for (i = k+1; i <= k2; ++i,--ii)

for (j = 1; j <= k; ++j)

a[i][j] = 4-a[ii][j];

}

void Right(int k) { // Lật phải

int i, j, jj = k, k2 = 2*k;

for (j = k+1; j <= k2; ++j,--jj)

for (i = 1; i <= k; ++i)

a[i][j] = 4 - a[i][jj];

}

void Copy(int k) { // Dịch chéo

int i, j ;

for (i = 1; i <= k; ++i)

for (j = 1; j <= k; ++j)

a[i+k][j+k] = a[i][j];

}

void Fill() { // Lát nền nn

int k;

a[1][1] = a[1][2] = a[2][1] = 1;

a[2][2] = 2;

for (k = 2; k < n ; k *= 2) {

Copy(k); Right(k); Down(k);

}

a[n][n] = 0;

}

void ToCenter(int k) { // đưa ô (c,d) về tâm

int nd = d+sx, nc = c+sy;

k = k/2;

for (int i = 1; i <= k; ++i) {

a[nd][nc] = a[nd+dx][nc+dy];

nd += dx; nc += dy;

a[nd][nc] = 0;

}

d += k*dx; c += k*dy; // tọa độ mới của (c,d)

}

// Manh chua (x,y) trong hinh [1..n,1..n]

// 0 1

// 2 3

int Quater(int n, int x, int y) {

int q = 0;

n /= 2;

if (x > n) q += 2;

if (y > n) ++q;

return q;

}

void NewPos(int n) {// Cập nhật tọa độ (x,y) và (c,d)

if (x > n) x -= n;

if (y > n) y -= n;

if (d > n) d -= n;

if (c > n) c -= n;

switch(qxy) {

case 1: sy += n; break;

case 2: sx += n; break;

case 3: sx += n; sy += n; break;

}

}

// doi cho a[x][y] va a[u][v]

void ISwap(int x, int y, int u, int v) {

int t = a[sx+x][sy+y]; a[sx+x][sy+y] = a[sx+u][sy+v]; a[sx+u][sy+v] = t;

}

void Equalize(int k) { // di chuyen o trong (d,c)

// den manh chua qxy

int k2 = k/2;

dx = (d == k) ? -1 : 1;

dy = (c == k) ? -1 : 1;

ToCenter(k); // d, c den vi tri moi; a[d][c] = 0

switch(qdc) {

case 0: if (qxy==1) {

ISwap(d,c,k2,k2+1);

d = k2; c = k2+1;

}

else if (qxy==2) {

ISwap(d,c,k2+1,k2);

d = k2+1; c = k2;

};

break;

case 1: if (qxy==0) {

ISwap(d,c,k2,k2);

d = c = k2;

}

else if (qxy==3) {

ISwap(d,c,k2+1,k2+1);

d = c = k2+1;

};

break;

case 2: if (qxy==0) {

ISwap(d,c,k2,k2);

d = c = k2;

}

else if (qxy==3) {

ISwap(d,c,k2+1,k2+1);

d = c = k2+1;

};

break;

case 3: if (qxy==1) {

ISwap(d,c,k2,k2+1);

d = k2; c = k2+1;

}

else if (qxy==2) {

ISwap(d,c,k2+1,k2);

d = k2+1; c = k2;

};

break;

}

qdc = qxy;

}

void Move() {

int k;

k = d = c = n;

sx = sy = 0;

while (k > 2) {

if (x==d && y == c) return;

qdc = Quater(k,d,c); // manh chua (d,c)

qxy = Quater(k,x,y); // manh chua (x,y)

if (qdc != qxy)

// chinh dong d va cot c cho cung manh voi (x,y)

Equalize(k);

k /= 2; NewPos(k);

}

// k = 2. Final

ISwap(d,c,x,y);

}

void WriteResult() {

ReadData();

ofstream g(gn);

g << n ;

g << endl << x << bl << y;

g << endl << colors;

int i,j;

for (i = 1; i <= n; ++i) {

g << endl;

for (j = 1; j <= n; ++j)

g << a[i][j] << bl;

}

g.close();

}

void Run() {

ReadData();

Fill();

Move();

colors = (n == 2) ? 1 : 3;

WriteResult();

}

4.8 Test


Bạn hãy giúp Ban Giám khảo cuộc thi viết một chương trình kiểm tra bài giải Lát nền 2 nói trên. Dữ liệu vào chính là output file square.out. Dữ liệu ra ghi trong output file test.out các thông tin sau đây:

0 – nếu kết quả đúng;

1 – nếu đặt sai lỗ thoát nước;

2 – nếu đặt gạch sai;

3 – nếu số màu công bố khác với số màu thực lát.

Thuật toán

Trước hết mở file square.out đọc thông tin bao gồm các giá trị: n – chiều dài cạnh của nền nhà; (x,y)  vị trí (dòng, cột) của ô trống; colors  số màu đã dùng. Tiếp đến đọc dữ liệu 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:

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.

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 + 22 + …+ 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
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)

v = (x[j]=='0') ? 2*v : 2*v+1;

h[v] = ch; ++ch;

}

cout << endl << endl;

// Giải mã

v = 1;

while (!f.eof()) {

f >> ch;

if (ch == '0' || ch == '1') {

cout << ch;

v = (ch=='0') ? 2*v : 2*v+1;

if (h[v] != 0) {

g << h[v];

v = 1;

}

}

}

f.close(); g.close();

}


Каталог: tailieu
tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning
tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm
tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc
tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI
tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1
tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng
tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp
tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam

tải về 2.51 Mb.

Chia sẻ với bạn bè của bạn:
1   ...   8   9   10   11   12   13   14   15   ...   21



Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý
    Quê hương
BÁO CÁO
Tài liệu