Cho hoán vị a = (a1,a2,...,aN) của
N số nguyên dương đầu tiên 1,2,...,N. Một thuận thế của a là dãy b = (b1,b2,...,bN)
trong đó bi là số lượng các phần tử nhỏ thua ai và đứng
trước ai, bi = ||{aj
| aj < ai, j < i}||. Biết trước N, 2 £ N £ 1000.
a) Cho một hoán vị a, tính thuận thế b của a.
b) Cho thuận thế b, tìm hóan
vị a.
c) Mọi thuận thế đều có phần tử đầu tiên (trái nhất) là 0 nên ta có
thể bỏ phần tử này. Ngoài ra, nếu trong thuận thế còn có phần tử 0 nữa ta bỏ
thêm 1 phần tử 0 để thu được một dãy có M = N-1 hoặc M = N-2 phần tử và gọi dãy này là thuận thế thu gọn c. Cho
một thuận thế thu gọn. Hãy tìm hoán vị nhỏ nhất theo trật tự từ điển sinh ra
thuận thế thu gọn này.
Thí dụ, với N = 5,
a) Cho a = (2,5,1,4,3) ta tính được b = (0,1,0,2,2),
b) Cho
b = (0,1,0,2,2) ta tìm được a = (2,5,1,4,3),
c) Cho thuận thế thu gọn c = (1,2,2), N = 5, ta tìm được a = (2,3,5,4,1).
Để ý rằng hai hoán vị (2,5,1,4,3) và (2,3,5,4,1) cùng sinh ra
thuận thế thu gọn (1,2,2), nhưng hoán vị (2,3,5,4,1) nhỏ hơn.
Dữ liệu vào: text file THUANTHE.INP
Dòng đầu tiên: N
Từ dòng thứ hai trở đi: N
phần tử của hoán vị a.
Dòng tiếp theo: M
Trên các dòng tiếp theo: M
phần tử của thuận thế thu gọn.
Dữ liệu trên cùng một dòng cách nhau qua dấu cách.
Dữ liệu ra: Hiển thị trên màn hình theo trật tự sau:
Câu a: Cho hoán vị a, tìm thuận thế b.
Câu b: Cho thuận thế b, tìm hoán vị a.
Câu c: Cho thuận thế thu gọn c tìm hoán
vị nhỏ nhất a.
Thuật toán
Việc xác định thuận thế b từ hoán vị a là dễ dàng. Hai câu b và c là hơi khó. Chúng ta sẽ sử
dụng kỹ thuật đối xứng để trình bày một thuật toán do Dijkstra đề xuất. Theo
thuật toán này thì thủ tục cho câu a và b là đối xứng nhau. Thuật toán tiến
hành xử lý tại chỗ, nghĩa là không sử dụng mảng phụ mà trực tiếp biến đổi hoán
vị a thành thuận thế lưu luôn trong a và ngược lại.
Trước hết ta nhận
xét rằng với hoán vị đơn vị e = (1,2,...,N) thì có đúng ei phần tử
không lớn hơn ei và không đứng sau phần tử ei, i = 1..N.
Vậy, nếu trong một hoán vị a mà ta thấy một phần tử aj ³ ai và j £ i thì ta khẳng định rằng chỉ còn đúng aj-1
phần tử không lớn hơn aj và không đứng sau phần tử aj.
Ta khai báo các
biến x, y, a là các mảng để chứa các hoán vị và thuận thế:
const MN = 1000;
type mi1 = array[0..MN] of integer;
var x,y,a: mi1;
Thủ tục biến đổi hoán vị a sang thuận thế a khi đó sẽ như
sau:
procedure HoanViThuanThe(var a: mi1;n: integer);
var i,j: integer;
begin
for i := n downto 1 do
for j:=1 to i do
if (a[j] >= a[i])
then dec(a[j]);
end;
Để thu được hoán vị a từ thuận thế a ta chỉ cần viết thủ tục
xử lý theo chiều ngược lại. Hai thủ tục như vậy gọi là đối xứng nhau.
procedure ThuanTheHoanVi(var a: mi1;n: integer);
var i,j: integer;
begin
for i := 1 to n do
for j := i downto 1 do
if (a[j] >= a[i])
then inc(a[j]);
end;
Hai thủ tục này đều có độ phức tạp N2.
Câu c được giải như sau. trước hết thêm một số 0 vào đầu
trái của dữ liệu vào a. Sau đó xét hiệu N-M. Nếu N-M=1 thì chứng tỏ thuận thế
thu gọn a chỉ khuyết một số 0. Ta chỉ việc gọi thủ tục ThuanTheHoanVi(a,N)
là thu được kết quả. Trường hợp N-M=2 thì ta phải bù thêm một số 0 nữa vào một
vị trí nào đó trong a. Ta lần lượt đặt số 0 này vào đầu phải (vị trí N) rồi
chuyển dần nó về đầu trái, mỗi lần một vị trí và gọi thủ tục ThuanTheHoanVi
để sinh ra một dãy a[1..N] sau đó kiểm tra xem dãy này có phải là hoán vị của
1..N hay không. Nếu đúng, ta dừng thuật toán và cho ra kết quả. Để kiểm tra một
dãy a[1..N] có phải là một hoán vị của 1..N ta sử dụng một mảng d[1..N] đánh
dấu xem mỗi phần tử a[i] có xuất hiện đúng 1 lần hay không. Tuy nhiên trước đó
ta phải kiểm tra điều kiện 1 £ a[i] £ N để đảm bảo rằng a[i] nằm trong giới hạn của chỉ số
mảng d.
procedure ThuanTheThuGon(var
a: mi1; n,m: integer);
var b: mi1;
i: integer;
begin
move(a[1],a[2],m*sizeof(integer));
a[1] := 0; inc(m);
if (n = m) then
begin
ThuanTheHoanVi(a,n);
exit;
end;
b := a;
for i := n downto 2 do
begin
{ Them 0 tai vi tri i
}
a := b;
move(a[i],a[i+1],(n-i)*sizeof(integer));
a[i] := 0;
ThuanTheHoanVi(a,n);
if LaHoanVi(a,n) then exit;
end;
end;
function LaHoanVi(var
a: mi1; n: integer): Boolean;
var d: mi1;
i: integer;
begin
LaHoanVi := false;
fillchar(d,sizeof(d),0);
for i := 1 to n do
begin
if (a[i] < 1) or (a[i]
> n) then exit;
if (d[a[i]] = 1) then
exit;
d[a[i]] := 1;
end;
LaHoanVi := true;
end;
Độ phức tạp
Thủ tục move(a,b,M) copy m byte từ mảng a sang mảng b. Thủ tục ThuanTheThuGon có độ phức tạp N3 vì nó gọi thủ tục ThuanTheHoanVi N lần. Hàm kiểm tra một dãy a[1..N] có phải là hoán vị đòi hỏi N thao tác và sử dụng một mảng phụ d để đánh dấu các phần tử đã xuất hiện.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét