Kênh 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!
Monday, January 13, 2014



abc - sắp theo chỉ dẫn - gia sư tin học
               Cho xâu S gồm N kí tự tạo từ các chữ cái 'a'..'z'. ta gọi S là xâu mẫu. Từ xâu mẫu S này người ta tạo ra N xâu thứ cấp bằng cách dịch xâu S qua trái i vị trí theo dạng vòng tròn, tức là i kí tự đầu xâu lần lượt được chuyển về cuối xâu, i = 0, 1,…, N - 1. Như vậy xâu thứ cấp với i = 0 sẽ trùng với xâu mẫu S. Giả sử ta đã sắp tăng N xâu thu được theo trật tự từ điển. Hãy tìm xâu thứ k trong dãy.
Tên chương trình: abc.pas.
Dữ liệu vào: tệp văn bản abc.inp có cấu trúc như sau:
-         Dòng thứ nhất chứa hai số tự nhiên Nk cách nhau qua dấu cách,
6
£ N £ 500, 1 £ k £ N. N cho biết chiều dài xâu S, kcho biết vị trí của xâu thứ cấp trong dãy được sắp tăng theo thứ tự từ điển.
-         Dòng thứ hai: xâu mẫu S.
Dữ liệu ra: tệp văn bản abc.out gồm một dòng chứa xâu thứ k trong dãy được sắp.
Thí dụ:
abc.inp
abc.out
6 3
dabdec
cdabde

Bài giải
Ta gọi xâu s ban đầu là xâu mẫu, các xâu được sinh ra bởi phép quay là xâu thứ cấp. Để ý rằng các xâu mẫu cũng là một xâu thứ cấp ứng với phép quay 0 vị trí. Ta có thể nhận được xâu thứ cấp thứ i bằng cách duyệt xâu mẫu theo vòng tròn kể từ vị trí thứ i về cuối, đến vị trí thứ n. Sau đó duyệt tiếp tục từ vị trí thứ 1 đến vị trí thứ i - 1. Ta kí hiệu xâu thứ cấp thứ ilà [i]. Thí dụ, nếu xâu mẫu s = 'dabdec' thì xâu thứ cấp thứ 2 sẽ là [2] ='abdecd'. Để tìm xâu thứ k trong dãy được sắp, trước hết ta cần sắp tăng các xâu đó theo trật tự từ điển sau đó lấy xâu thứ k trong dãy được sắp làm kết quả. Để sắp tăng được các xâu này mà không phải sinh ra các xâu mới ta dùng một mảng phụ id gọi là mảng chỉ dẫn. Trước khi sắp ta gán id[i]:= i. Sau khi sắp thì id[i] sẽ cho biết tại vị trí thứ i trong dãy được sắp là xâu thứ cấp nào. Trong thí dụ trên, id[3] = 6 là xâu thứ cấp [6]. Giá trị 3 cho biết cần tìm xâu thứ k = 3 trong dãy sắp tăng các xâu thứ cấp. Giá trị 6 cho biết xâu cần tìm là xâu thứ 6 trong dãy các xâu thứ cấp được sinh ra lúc đầu, tức là lúc chưa sắp.


Xâu thứ cấp
Sắp tăng
id[i] = ?
j
[1] = S
dabdec
[2]
2
k
[2]
abdecd
[3]
3
l
[3]
bdecda
[6]
6
m
[4]
decdab
[1]
1
n
[5]
ecdabd
[4]
4
o
[6]
cdabde
[5]
5
Sắp chỉ dẫn các xâu thứ cấp
Thuật toán QuickSort sắp nhanh các xâu thứ cấp do Hoare đề xuất có độ phức tạp N.log2Nđược trình bày như sau:
Init: for i:=1 to n do id[i]:=i;
procedure idquicksort(d,c: integer);
var i, j, m, y: integer;
begin
i:=d;
j:=c;
m:=id[(i+j) div 2]; {phan tu giua}
while i <= j do
begin
while Sanh(id[i],m)<0 do inc(i); {doan trai}
while Sanh(m,id[j])<0 do dec(j); {doan phai}
{doi cho neu can}
if (i <= j) then
       begin
y:= id[i];
id[i]:= id[j];
id[j]:= y;
inc(i); dec(j);
    end;
end;
if d < j then idquicksort(d,j);
if i < c then idquicksort(i,c);
end;
Hàm Sanh(i,j) so sánh hai xâu thứ cấp [i] và [j] theo thứ tự từ điển và cho giá trị -1 nếu xâu thứ cấp [i] nhỏ hơn xâu thứ cấp [j], cho giá trị 1 nếu xâu thứ cấp [i] lớn hơn xâu thứ cấp [j] và 0 nếu hai xâu này giống nhau. Để so sánh hai xâu theo trật tự từ điển ta lần lượt duyệt từng cặp kí tự của mỗi xâu. Nếu hai xâu giống nhau tại mọi vị trí thì ta gán trị 0 cho hàm Sanh. Ngược lại, nếu tìm được vị trí khác nhau đầu tiên thì ta so sánh hai kí tự s[i] và s[j] tại vị trí đó và gán cho hàm Sanhgiá trị -1 nếu s[i] < s[j], ngược lại, tức là khi s[i] > s[j] thì gán giá trị 1 cho hàm Sanh.
Ta chỉ cần lưu ý là việc duyệt xâu phải thực hiện trên vòng tròn theo chiều quay của kim đồng hồ.
function Sanh(i,j: integer): integer;
var k: integer;
begin
for k:=1 to n do
begin
if s[i] <> s[j] then
begin
if s[i] < s[j] then Sanh:=-1
else Sanh:=1;
exit;
end;
if i=n then i:=1 else inc(i);
if j=n then j:=1 else inc(j);
end;
Sanh:=0;
end;
Hoare cũng cung cấp thêm thuật toán tìm phần tử thứ k trong dãy được sắp với độ phức tạp 2N. Ta vận dụng thuật toán này cho bài toán abc. Bản chất thuật toán này là như sau. Ta cũng sắp tăng các xâu thứ cấp theo thuật toán QuickSort nhưng không sắp hết mà chỉ quan tâm đến đoạn dữ liệu trong mảng có chứa phần tử thứ k. Lưu ý rằng sau một lần chia dữ liệu của đoạn id[d..c] ta thu được ba đoạn: đoạn id[d..j], id[j+1..i-1] và id[i..c], trong đó đoạn giữa là id[j+1..i-1] đã được sắp. Nếu k rơi vào đoạn thứ nhất là id[d..j] hoặc đoạn thứ ba là id[i..c] thì ta chỉ cần sắp tiếp đoạn đó. Hàm Find(k) cho ra vị trí gốc của xâu thứ cấp sẽ đứng thứ ktrong dãy đã sắp. Trong thí dụ trên Find(3)=6.
(*-------------------------------------
            Tim phan tu thu k
---------------------------------------*)
function Find(k: integer):integer;
var d, c, i, j, m, y: integer;
begin
d:=1 ;
c:=n;
while d <= c do
begin
i:=d;
j:=c;
m:=id[(i+j) div 2]; {phan tu giua}
while i <= j do
       begin
while Sanh(id[i],m)<0 do inc(i); {doan trai}
while Sanh(m,id[j])<0 do dec(j); {doan phai}
             {doi cho neu can}
             if (i <= j) then
                   begin
                      y:= id[i];
                      id[i]:= id[j];
                      id[j]:= y;
                      inc(i); dec(j);
                end;
end;
    if j < k then d:=i;
    if k < i then c:=j;
end;
find:=id[k];
end;
(*  Pascal  *)
(*----------------------------------
      ABC: Tim phan tu thu k
------------------------------------*)
program ABC;
{$B-}
uses crt;
const
MN = 501;
nl = #13#10; {xuong dong}
bl = #32; {dau cach}
fn = 'abc.inp';
gn = 'abc.out';
type
MI = array[0..MN] of integer;
MC = array[0..MN] of char;
var
f,g: text;
s: MC;
id: MI;
n,k: integer;
(*---------------------------------------------
            Doc du lieu:
      n: chieu dai xau s,
      k: vi tri xau thu cap trong day da sap
----------------------------------------------*)
procedure Doc;
var i: integer;
begin
assign(f,fn); reset(f);
readln(f,n,k);
for i:=1 to n do read(f,s[i]);
close(f);
end;
(*----------------------------------------
So sanh 2 xau thu cap [i] va [j].
Sanh(i,j)
= 0: neu [i] = [j]
= -1: neu [i] < [j]
= 1 neu [i] > [j]
----------------------------------------*)
function Sanh(i,j: integer): integer;
var k: integer;
begin
for k:=1 to n do
begin
if s[i] <> s[j] then
    begin
          if s[i] < s[j] then Sanh:=-1
                else Sanh:=1;
          exit;
    end;
if i=n then i:=1 else inc(i);
if j=n then j:=1 else inc(j);
end;
Sanh:=0;
end;
(*-------------------------------------
                  Tim phan tu thu k
---------------------------------------*)
function Find(k: integer):integer;
var d, c, i, j, m, y: integer;
begin
d:=1 ;
c:=n;
while d <= c do
begin
i:=d;
j:=c;
m:=id[(i+j) div 2]; {phan tu giua}
while i <= j do
       begin
while Sanh(id[i],m)<0 do inc(i); {doan trai}
while Sanh(m,id[j])<0 do dec(j); {doan phai}
             {doi cho neu can}
             if (i <= j) then
                   begin
                      y:= id[i];
                      id[i]:= id[j];
                      id[j]:= y;
                      inc(i); dec(j);
                end;
end;
    if j < k then d:=i;
    if k < i then c:=j;
end;
find:=id[k];
end;
{-----------------------------
      Ghi ket qua vao tep
-------------------------------}
procedure Ghi(k: integer);
var i: integer;
begin
assign(g,gn); rewrite(g);
for i:=1 to n do
begin
write(g,s[k]);
if k=n then k:=1 else inc(k);
end;
close(g);
end;
procedure run;
var i:integer;
begin
Doc;
for i:=1 to n do id[i]:=i;
Ghi(find(k));
end;
BEGIN
run;
END.

0 comments:

Post a Comment

Popular Posts