Palindrome
Olympic Quốc tế, năm 2000, Bắc Kinh, Trung
Quốc.
Dãy kí tự s được gọi là đối xứng (palindrome) nếu các
phần tử cách đều đầu và cuối giống nhau. Cho dãy s tạo bởi n kí tự gồm các chữ
cái hoa và thường phân biệt và các chữ số. Hãy cho biết cần xoá đi từ s ít nhất
là bao nhiêu kí tự để thu được một dãy đối xứng. Giả thiết rằng sau khi xoá bớt
một số kí tự từ s thì các kí tự còn lại sẽ tự động xích lại sát nhau.
Dữ liệu vào ghi trong tệp văn bản PALIN.INP với cấu trúc như sau:
|
PALIN.INP
|
PALIN.OUT
|
|
9
baeadbadb
|
4
|
Dòng đầu tiên là giá trị n, 1
£ n £ 1000.
Dòng thứ hai là n kí tự của
dãy viết liền nhau.
Dữ liệu ra ghi trong tệp văn bản PALIN.OUT: số lượng kí tự cần xóa.
Thí dụ, với dãy s gồm 9 kí
tự, s = 'baeadbadb'
thì cần xoá ít nhất 4 kí tự, chẳng hạn,
các kí tự thứ 5, 7, 8 và 9 sẽ thu được dãy đối xứng chiều dài 5 là baeab:
baeadbadb ® baeab
Dĩ nhiên là có nhiều cách xoá. Thí dụ, có thể xoá
các kí tự thứ 2, 3, 4 và 6 từ dãy s để thu được dãy con đối xứng khác là bdadb với cùng chiều dài
5:
baeadbadb ® bdadb
Tuy nhiên đáp số là số ít nhất các kí tự cần loại bỏ khỏi s thì là duy nhất và bằng 4.
Bài giải
Bài toán này đã được
nhiều bạn đọc
công bố lời giải với một mảng hai chiều kích thước n2
hoặc vài ba mảng một chiều kích thước n, trong đó n là chiều dài của dữ liệu vào.
Với một nhận xét nhỏ ta có thể phát hiện ra rằng chỉ cần
dùng một mảng một chiều kích thước n và một vài biến đơn là đủ.
Gọi dãy dữ liệu vào là s.
Ta tìm chiều dài của dãy con đối xứng v dài nhất trích từ s. Khi đó số kí tự cần xoá
từ s sẽ là t = length(s) - length(v). Dãy con ở đây được hiểu là dãy thu được từ s bằng cách xoá đi một số phần tử trong s. Thí dụ với dãy
s = baeadbadb
thì dãy con đối xứng dài nhất của s sẽ là baeab hoặc bdadb,…
Các dãy này đều có chiều dài 5.
Lập hệ
thức: Gọi p(i, j) là chiều dài của dãy con dài nhất thu được khi giải bài toán với dữ liệu vào
là đoạn s[i..j]. Khi đó p(1, n) là chiều dài của dãy con đối xứng dài nhất trong dãy n
kí tự s[1..n] và do đó số kí tự cần loại bỏ khỏi dãy
s[1..n] sẽ là
n-p(1,n)
Đó chính là đáp số của bài
toán.
Ta liệt kê một số tính
chất quan trọng của hàm hai biến p(i,
j). Ta có:
-
Nếu i > j, tức là chỉ số đầu
trái lớn hơn chỉ số đầu phải, ta quy ước đặt p(i, j) = 0.
-
Nếu i = j thì p(i, i) = 1 vì dãy khảo sát chỉ chứa đúng 1 kí tự nên nó là đối xứng.
-
Nếu i < j và s[i] = s[j] thì p(i, j) = p(i + 1, j – 1) + 2. Vì hai kí
tự đầu và cuối dãy s[i,j] giống
nhau nên chỉ cần xác định chiều dài của dãy con đối xứng dài nhất trong đoạn
giữa là s[i + 1, j – 1] rồi cộng
thêm 2 đơn vị ứng với hai kí tự đầu và cuối dãy là được.
-
Nếu i < j và s[i] ¹ s[j], tức là hai kí
tự đầu và cuối của dãy con s[i..j] là khác nhau thì ta khảo sát hai
dãy con là s[i..(j – 1)] và s[(i
+ 1)..j] để lấy chiều dài của dãy con đối xứng dài nhất trong hai
dãy này làm kết quả:
p(i,j) = max(p(i,j-1),p(i+1,j))
Vấn đề đặt ra
là cần tính p(1, n). Mà muốn
tính được p(1, n) ta phải
tính được các p(i, j) với mọi i, j = 1..n.
Phương án đệ quy
Phương án đệ quy dưới đây như mô tả trong hàm nguyên rec(i, j) tính trực tiếp giá trị p(i, j) theo các tính chất đã liệt kê. Đáp số cho bài toán khi đó sẽ là n-rec(1,n)
(*------------------------------------
Phuong an de quy
------------------------------------*)
function rec(i,j:
integer): integer;
begin
if i > j
then rec := 0
else if i = j
then rec := 1
else {i < j}
if s[i] = s[j]
then rec := rec(i+1,j-1)+2
else {i < j
& s[i] ¹ s[j]}
rec := max(rec(i,j-1),rec(i+1,j));
end;
|
|
|
j-1
|
j
|
|
|
|
b
|
a
|
e
|
a
|
d
|
b
|
a
|
d
|
b
|
|
|
|
|
|
|
|
|
u
|
v
|
w
|
x
|
y
|
z
|
{
|
|
|
}
|
|
|
|
|
|
|
b
|
j
|
1
|
1
|
1
|
3
|
3
|
5
|
5
|
5
|
5
|
|
|
|
|
|
|
a
|
k
|
0
|
1
|
1
|
3
|
3
|
3
|
3
|
3
|
3
|
|
i
|
|
[i,j-1]
|
[i,j]
|
|
e
|
l
|
0
|
0
|
1
|
1
|
1
|
1
|
3
|
3
|
3
|
|
i+1
|
|
[i+1,j-1]
|
[i+1,j]
|
|
a
|
m
|
0
|
0
|
0
|
1
|
1
|
1
|
3
|
3
|
3
|
|
|
|
|
|
|
d
|
n
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
3
|
3
|
|
|
|
|
|
|
b
|
o
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
3
|
|
|
|
|
|
|
a
|
p
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
|
|
|
|
|
|
d
|
q
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
|
|
|
|
|
|
b
|
r
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
|
|
|
|
|
|
Gía trị của hàm p(i,j) đối với dãy baeadbadb
i,j=1..9
|
||||||||||
Dùng một mảng hai chiều
Gọi đệ quy sẽ phát
sinh các lời gọi hàm trùng lặp như đã phân
tích trong bài toán 7.1. Ta khắc phục điều này bằng cách
sử dụng một mảng hai chiều để tính trước các giá trị của hàm p(i,
j), mỗi giá trị được tính tối đa một lần. Nếu dùng
một mảng hai chiều, thí dụ mảng p[0..n, 0..n] thì giá trị của p[i, j] sẽ được điền lần lượt theo
từng cột, từ cột thứ 1 đến cột thứ n. Tại mỗi cột ta điền từ dưới lên
trên. Ta lưu ý:
-
Phần tử tại cột i, dòng j là giá trị p[i, j] chính là chiều dài của dãy con
đối xứng dài nhất khi khảo sát dãy
con s[i..j].
-
Với các trị i > j, ta quy định p[i, j] = 0. Như vậy nửa tam
giác dưới của ma trận p sẽ chứa toàn 0.
-
Nếu i = j thì p[i, j] = 1. Như vậy, mọi trị trên đường chéo chính của ma trận p sẽ là 1.
-
Với các ô còn lại, toạ độ (i, j) sẽ thoả điều kiện i < j, nên p[i, j] sẽ được tính như sau:
if s[i] = s[j] then p[i,j] =
p[i+1,j-1]+2
else p[i,j] := max(p[i,j-1],p[i+1,j])
Bạn hãy thử điền một vài
giá trị cho bảng trên để rút ra quy luật.
Hãy bắt đầu với cột 1: p[1, 1] = 0;
Sau đó đến cột 2:
p[2, 2] = 1;
p[1, 2] = max(p[1, 1], p[2, 2]) = 1, vì
s[1] ¹ s[2].
Rồi đến cột 3:
p[3,3]=1;
p[2,3] = max(p[2, 2], p[3, 3]) = 1, vì s[2]
¹ s[3];
p[1,3]
= max(p[1,2], p[2,3]) = 1, vì s[1] ¹ s[3],…
Dùng hai mảng một chiều
Ta sẽ không theo đuổi phương án dùng mảng hai chiều mà hãy căn cứ vào quy luật điền mảng hai chiều để vận dụng
cho hai mảng một chiều là v[0..(n + 1)] và d[0..(n + 1)]. Theo kinh
nghiệm, ta nên khai báo kích thước mảng rộng hơn chừng hai phần tử để sử dụng các phần tử này như những lính canh chứa các giá trị khởi đầu phục vụ cho các trường hợp chỉ số i, j nhận các giá trị 0 hoặc n + 1.
Giả sử mảng v chứa các giá trị đã điền của cột j – 1 trong mảng hai chiều p. Ta sẽ điền các giá trị cho cột j của mảng p vào mảng một chiều d. Như vậy, tại bước j, phần tử v[i]
sẽ ứng với phần tử p[j – 1, i] còn phần tử d[i] sẽ ứng với p[j, i].
Thủ tục điền trị cho cột d tại bước j
dựa theo kết quả lưu trong cột v của
bước j – 1 khi đó sẽ như sau:
for i := j-1
downto 1 do
begin
if s[i] = s[j] then d[i] := v[i+1]+2
else d[i] := max(v[i],d[i+1]);
end;
Sau mỗi lần lặp với j := 1..n ta chuyển giá
trị của d cho v để chuẩn bị cho
bước tiếp theo.
(*---------------------------------
Quy hoach dong voi 2 mang
1 chieu d, v
----------------------------------*)
procedure
QHD2;
var i,j:
integer;
begin
fillchar(v,sizeof(v),0);
for j := 1 to
n do
begin
d[j] := 1;
for i :=
j-1 downto 1 do
begin
if s[i]= s[j] then d[i] := v[i+1]+2
else d[i] := max(v[i],d[i+1]);
end;
v := d;
end;
writeln(nl,n-d[1]);
{dap so}
end;
Dùng một mảng một chiều
Có thể chỉ sử dụng một mảng một chiều d cho bài toán này với nhận xét sau đây. Tại bước cập nhật thứ j, với mỗi i = (j – 1)..1 ta có d[i]
= p[i, j] và được tính như sau:
s
Nếu s[i] = s[j] thì d[i] tại bước j bằng d[i + 1] tại bước j – 1 cộng với 2.
s
Nếu s[i] ¹ s[j] thì
d[i] tại bước j bằng max(d[i]
tại bước j – 1, d[i + 1] tại bước j).
Nếu ta tính từ dưới lên, tức là tính d[i]
với i = n..1 thì d[i + 1] cũ sẽ bị ghi đè. Ta dùng hai biến phụ t và tr để bảo lưu giá trị này.
(*---------------------------------
Quy hoach dong
voi mang 1 chieu d
----------------------------------*)
procedure
QHD1;
var i,j,t,tr:
integer;
begin
for j := 1 to
n do
begin
tr := 0;
d[j] := 1;
for i := j-1 downto 1 do
begin
t := d[i];
if s[i]= s[j] then d[i] := tr+2
else d[i] := max(d[i],d[i+1]);
tr := t;
end;
end;
writeln(nl,n-d[1]);
{dap so}
end;
Dĩ nhiên phương án dùng
một mảng một chiều sẽ được coi trọng vì tiết
kiệm được miền nhớ. Tuy nhiên, tinh ý một chút, bạn sẽ phát hiện ra rằng thời
gian tính toán theo phương án này không ít hơn phương án dùng hai mảng một
chiều. Thật vậy, để tính mỗi phần tử ta phải dùng thêm hai phép gán, trong khi
dùng hai mảng một chiều ta chỉ phải thêm một phép gán cho mỗi phần tử. Hơn nữa,
dùng hai mảng một chiều thường tránh được nhầm lẫn, do đó
nhiều người thường chọn phương án này.
Toàn văn chương trình với ba phương án, đệ quy, dùng hai mảng một chiều và dùng một mảng một chiều khi đó sẽ như sau.
(* Pascal *)
uses crt;
const mn = 51;
bl = #32; nl = #13#10;
fn = 'palin.inp';
gn = 'palin.out';
type mi1 = array[0..mn] of
integer;
mi2 = array[0..mn] of mi1;
mc1 = array[0..mn] of char;
var n: integer; { Chieu dai xau }
f,g: text;
s: mc1; { xau can xu li }
d,v: mi1;
c: mi2;
procedure
Doc; tự viết
function Max(a,b: integer):
integer; tự viết
(*-----------------------------------
Phuong an de
quy
------------------------------------*)
function rec(i,j: integer):
integer; tự viết
(*------------------------------------
Quy hoach dong voi mang 2 chieu c
-------------------------------------*)
function QHD2C: integer; tự viết
(*---------------------------------
Quy hoach dong voi 2 mang
1 chieu d, v
----------------------------------*)
function QHD2DV: integer; tự viết
(*---------------------------------
Quy hoach dong voi mang 1 chieu d
----------------------------------*)
function QHD1: integer; tự viết
procedure Test;
begin
Doc;
writeln(nl,'Phuong an 1: De qui:
',n-rec(1,n));
writeln(nl,'Phuong an 2: Mang 2 chieu:
',n-QHD2C);
writeln(nl,'Phuong an 3: Hai Mang 1 chieu D,
V: ',n-QHD2DV);
writeln(nl,'Phuong an 4: Mang 1 chieu D:
',n-QHD1);
end;
BEGIN
Test;
readln;
END.
Hay quá, cảm ơn Nhập Vân Long
Trả lờiXóa