Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



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(vara: 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
LẬP TRÌNH
tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts