Chương trình đối xứng và thuận thế thu gọn
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (90.52 KB, 12 trang )
Chương trình đối xứng và thuận thế thu gọn
Nguyễn Xuân Huy
Giả sử ta có chương trình P xử lýdữ liệu theo một trật tự T nào đó. Giả sử với một trật tự T
nói trên, chươngtrình P biến đổi dữ liệu vào X thành dữ liệu ra Y. Thử hỏi, liệu ta có thể
xâydựng một chương trình P thực hiện theo trật tự T để biến đổi Y thành x đượckhông
Trong một số trường hợp, điều này là có thể và chương trình P xây dựngtheo phương pháp
trên được gọi là chương trình đối xứng với chương trình P.
Bài 1. Cho a= (a1,a2,..,aN) là một hoán vị của dãy số tựnhiên 1..N. Ta xây dựng dãy
b=(b1,b2,..,bN)và gọi là thuận thế của hoán vị a như sau:
Với mọi i=1..N, bi là số lượngcác phần tử nhỏ thua a
i
và đứng trước a
i
.
Thí dụ, với N= 7;a=(6,1,3,5,7,4,2) ta có thuận thế của a là b= (0,0,1,2,4,2,1).
a) ChoN và một hoán vị a. Hãy tìm thuận thế của a.
b) ChoN và một thuận thế b. Hãy tìm hoán vị sinh ra thuận thế b.
Bài giải
a) Giảsử ta có một hoán vị a[1..N] của 1..N. Dễ thấy rằng với mọi i=1..N, để tínhb[i] ta chỉ
việc đếm số lượng các phần tử đứng trước a[i] và nhỏ thua a[i]
{Cho hoan vi (HV) tim thuan the(TT). Phuong an 1}
Procedure HVTT (var a, b: mang);
var i: word;
begin
for i:= 1 to N do
begin
b[i] := 0;
for j:= 1 to i-1 do
if a[j] < then>
inc (b[i]);
end;
end;
Tuy nhiên theo cách này chúng tasẽ gặp đôi chút khó khăn trong việc giải câu b). Ta thử
tìm lời giải khác.
Xét dãy n số tự nhiên 1, 2,...,n. Ta gọi dãy này là hoán vị đơn vị. Ta để ýrằng với mỗi số i
trong dãy trên sẽ có i - 1 phần tử đứng trước i và nhỏ hơn i.Nói cách khác, thuận thế của
hoán vị đơn vị chính là dãy 0,1,... ,(n-1). Bây giờ ta xét một hoán vị tuỳ ý a[1..n].Để ý rằng
với mỗi j=1..n, a[i] cho biết trong hoán vị đơn vị sẽ có a[j] -1 phầntử nhỏ hơn và đứng
trước nó. Thế thì mỗi khi có a[i] trong hoán vị trên nhỏ hơna[j] và đứng bên phải a[j] thì
a[j] chỉ còn a[j] - 2 phần tử nhỏ hơn nó và đứngtrước nó.. Nhận xét này dẫn đến thuật toán
xác định thuận thế của một hoán vị nhưsau:
Lần lượt duyệt ngược từ i=n đến1.
Với mỗi j từ 1 đến i xét: nếua[j] ≥ a[i] thì giảm a[j] đi 1 đơn vị.
Thuật toán này sửa hoán vị a[1.. n]thành thuận thế a[1..n] nên được gọi là thuật toán xử lý
tại chỗ. Nó không đòihỏi mảng phụ.
(* Cho hoan vi a [1..n], sinhthuan the a[1..n] *)
Procedure HVTT;
var i,j: word;
begin
for i:= n downto 1 do
for j:= 1 to i do
if a[j] >= a[i] then
dec (a[j]); end;
Điểm lợi của thuật toán này làkhi cần khôi phục tính hoán vị từ thuận thế ta chỉ việc viết
thuật toán trên theochiều ngược lại. Ta có:
(* Cho thuan the a[1..n], khoiphuc hoan vi a[1..n] bang phuong phap doi xung*)
Procedure TTHV;
var i, j: word;
begin
for i:= 1 to n do
for j:= i downto 1 to
if a[j] >= a[i] then
inc (a[j]); end;
Bạn đọc hãy đối chiếu haithuật toán trên để phát hiện ra tính đối xứng lạ kỳ của chúng.
Chương trình. Phần chính củachương trình dưới đây là vòng lặp với các bước sau:
+ Tạo ngẫunhiên một hoán vị của 1..n lưu trong mảng a: Thủ tục SinhHoanVi;
+ Hiển thị hoánvị đã tạo a[1..n]: Thủ tục XemMang;
+ Lưu tạm hoánvị a vào mảng b để so sánh sau này: b:= a;
+ Sinh thuậnthế từ hoán vị a[1..n], lưu thuận thế này ngay trong a: Thủ tục HVTV;
+ Hiển thịthuận thế tìm được tức là hiển thị mảng a[1.. n]: XemMang;
+ Khôi phục lạihoán vị từ thuận thế a[1..n], lưu hoán vị này ngay trong a: Thủ tục TTHV;
+ So sánh mảnga với mảng b để kiểm tra tính đúng của thuật toán: Hàm Sanh;
+ Vòng lặp kếtthúc khi ta bấm phím ESC.
Hàm Sanh hai mảng a[1..n] vàb[1..n] cho ra giá trị 0 nếu a=b; 1 nếu a>b và -1 nếu a< the^
cu. sa?nh, so phe?p cua gia?tri. ddi.nh quye^?t se~ b[i] va` a[i] nhau, kha?c tie^n dda^`u
tu+ pha^`n la.i, Ngu+o+.c a="b." nhauthi` ba(`ng dde^`u mang hai u+?ng tu+o+ng mo^~i
Ne^?u so^?. da~y nhu+ sa?nh ddu+o+.cso Hai>
Nếu a[i] >b[i] thì Sanh = 1;
Nếu a[i] <b[i] thì Sanh =-1;
Chương trìnhPascal
(* Thuan the thugon *)
uses crt;
const MN=100; n=9;
ESC =#27;
type Mang =array [0..MN] of byte;
var a, b: Mang;
(* Hien thimang a[1..n] *)
ProcedureXemMang;
var i: word;
begin
for i:= 1 to ndo
write (a[i]:3);
end;
(* Sinh ngẫunhiên một hoán vị cho Mảng a[1..n] *)
ProcedureSinhHoanVi;
var i, j, t:word;
begin
for i:= 1 ton do
a[i]:= i;
for i:= 1 ton do
begin
j:=random (n) +1;
t:=a[1];
a[1]:=a[j];
a[j]:=t;
end;
end;
(* Cho hoan vi a[1..n], sinh thuan the a[1..n] *)
Procedure HVTT;
var i, j:word;
begin
for i:=ndownto 1 do
for j:= 1to i do
if a[j]>= a[i] then
dec (a[j]);end;
(* Cho thuanthe a[1..n], khoi phuc hoan vi a[1..n] bang phuong phap doi xung *)
Procedure TTHV;
var i, j: word;
begin
for i:=1 to ndo
for j:= idownto 1 do
if a[j]>= a[i] then
inc (a[j]);end;
(* So sanh haiMang a[1..n] va b[1..n] *);
functionSanhMang (var a, b: Mang): integer;
var i: word;
begin
for i:= 1 ton do
