Bài toán ABBA - đối gương

Chương trình Pascal cho bài toán ABBA

Nguyễn Xuân Huy




Trong bài "ABBA hay phép đối xứng gương và các thao tác" đăng trong Tin học & Nhà Trường số 1/1999 có nói đến hai thuật toán giải bài chuyển các khối bê tông lát đường băng. Thể theo yêu cầu của bạn đọc, trong số này chúng tôi sẽ giới thiệu chương trình thực thi và đánh giá độ phức tạp của hai thuật toán đó. Chúng tôi cũng sẽ giới thiệu một thủ thuật đơn giản để đo thời gian cho các bạn tiện dùng sau này.
Trước hết ta nhắc lại bài toán ở dạng vắn tắt và dễ lập trình như sau:
Bài toán (chuyển phần tử): Cho mảng nguyên a[1..N] và một số tự nhiên K<= N/2. Hãy chuyển K phần tử từ đầu mảng về cuối mảng.
Bài toán này được giải bằng hai giải thuật:
- Giải thuật tự nhiên với độ phức tạp K(N+1) phép gán.
- Giải thuật đối xứng với độ phức tạp 3N phép gán.
Trước hết ta tổ chức dữ liệu cho bài toán.
Tổ chức dữ liệu
Ta dùng một mảng a chứa 16000 phần tử kiểu word. Như vậy N sẽ là hằng số có giá trị 16000. Chọn K bằng một nửa của N, tức là chọn 8000 cho giá trị K. Các đại lượng này sẽ được khai báo tổng thể như sau:
Const
N=16000;
K=8000;
Type Mang=array[1..N] of word;
Var a: Mang;
Ta sẽ triển khai chương trình cho hai giải thuật như đã giới thiệu trong bài viết ở số 1.
Giải thuật tự nhiên
Sơ đồ 1. Sơ đồ thô
Chuyển K lần, mỗi lần 1 phần tử từ đầu mảng về cuối mảng.
Sơ đồ 2. Sơ đồ tinh chế lần thứ nhất
for i :=1 to K do        begin           x:= a[1];           {Dịch các phần tử a[2..N] về bên trái một vị trí.}           a[N]:=x;      end;
Để dịch các phần tử a[2..N] về bên trái 1 vị trí ta dùng sơ đồ 3 sau đây:
Sơ đồ 3. Dịch các phần tử a[2..N] về bên trái 1 vị trí
  for j:=2 to N do       a[j-1]:=a[j]; Phối hợp các sơ đồ 2 và 3 ta thu được thủ tục ChuyenTuNhien sau đây:
Procedure ChuyenTuNhien;   Var    i,j: word;           x: word; begin    for i:=1 to K do           begin               x:=a[1]; {Lấy phần tử đầu }               {Dịch trái 1 đơn vị}              for j:=2 to N do                a[j-1]:=a[j];                a[N]:=x; {Đặt phần tử đầu vào cuối mảng}          end; end;
Giải thuật đối xứng Trước hết xin thay mặt Ban biên tập của phụ san Tin học và Nhà Trường  thành thật xin lỗi bạn đọc về một vài lỗi chế bản trong bài đăng ở số 1. Chúng tôi xin đề nghị sửa lại hai lỗi sau: Lỗi thứ nhất: Trang 12, cột 1, dòng 29. Tính chất 2 của phép đối xứng gương bị in sai, thay cho dấu nháy kép các bạn sửa giúp lại thành dấu nháy đơn như sau: (AB)` = B`A`. Lỗi thứ hai: Trang 12, cột 1, dòng 49. Xin sửa lại như sau: (A`B`)`=B``A``=BA.
Sau đây chúng ta triển khai giải thuật đối xứng, thực hiện nhanh hơn giải thuật tự nhiên.
Sơ đồ 1. Chuyển đối xứng  Đặt A=a[1..K]; B=a[K+1..N], áp dụng công thức (A`B`)`=B``A``=BA ta sẽ thu được ngay kết quả cần tìm. Gọi DoiXung(d,c) là thủ thuật thực hiện phép đối xứng đoạn a[d..c] của mảng a, nghĩa là Doixung(d,c)=(a[d..c])`. Ta có ngay giải thuật ChuyenDoiXung sau đây: Procedure ChuyenDoiXung; Begin   DoiXung(1,K); {A`}   DoiXung(K+1,N); {B`}   DoiXung(1,N); {(..)`} End;
Sơ đồ 2.  DoiXung Thủ tục đối xứng đoạn a[d..c] sẽ đổi chỗ từng cặp phần tử cách đều đầu và cuối như sau: Procedure DoiXung(d,c: word); Var x: word; begin    while d