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 N và k 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, k cho 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.
6 £ N £ 500, 1 £ k £ N. N cho biết chiều dài xâu S, k cho 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ứ i
là [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 Sanh
giá 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ứ k
trong 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.
Không có nhận xét nào:
Đăng nhận xét