Palindrome



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ài5:  
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 nhiu bn đọc công b li gii vi mt mng hai chiu kích thước n2hoc vài ba mng mt chiu kích thước n, trong đó n là chiu dài ca d liu vào.
Vi mt nhn xét nh ta có th phát hin ra rng ch cn dùng mt mng mt chiu kích thước n và mt vài biến đơn là đủ.
Gi dãy d liu vào là s. Ta tìm chiu dài ca dãy con đối xng v dài nht trích t s. Khi đó s kí t cn xoá từ s st = length(s) - length(v). Dãy con đây được hiu là dãy thu được t s bng cách xoá đi mt s phn t trong s. Thí d vi dãy s = baeadbadbthì dãy con đối xng dài nht ca s sbaeab hoc bdadb,… Các dãy này đều có chiều dài 5.
Lp hthc: Gi p(i, j) là chiu dài ca dãy con dài nht thu được khi gii bài toán vi d liu vào là đon s[i..j]. Khi đó p(1, n) là chiu dài ca dãy con đối xng dài nht trong dãy nkí t s[1..n] và do đó s kí t cn loi b khi dãy s[1..n] s
n-p(1,n)
Đó chính là đáp s ca bài toán.
Ta lit kê mt s tính cht quan trng ca hàm hai biến p(i, j). Ta có:
-   Nếu i > j, tc là ch s đầu trái ln hơn ch s đầu phi, ta quy ước đặt p(i, j) = 0.
-   Nếu i = j thì p(i, i) = 1 vì dãy kho sát ch cha đúng 1 kí t nên nó là đối xng.
-   Nếu i < js[i] = s[j] thì p(i, j) = p(i + 1, j – 1) + 2. Vì hai kí t đầu và cui dãy s[i,j] ging nhau nên ch cn xác định chiu dài ca dãy con đi xng dài nht trong đoạn giữa là s[i + 1, j – 1] ri cng thêm 2 đơn v ng vi hai kí t đầu và cui dãy là được.
-   Nếu i < js[i] ¹ s[j], tc là hai kí t đầu và cui ca dãy con s[i..j] là khác nhau thì ta kho sát hai dãy con là s[i..(j – 1)] và s[(i+ 1)..j] để lấy chiu dài ca dãy con đối xng dài nht trong hai dãy này làm kết qu:
p(i,j) = max(p(i,j-1),p(i+1,j))
Vn đề đặt ra là cn tính p(1, n). Mà mun tính được p(1, n) ta phi tính được các p(i, j) vi mi 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 trc tiếp giá tr p(i, j) theo các tính cht đã lit kê. Đáp s cho bài toán khi đó s 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
Gi đệ quy s phát sinh các li gi hàm trùng lp như đã phân tích trong bài toán 7.1. Ta khc phc điu này bng cách s dng mt mng hai chiu để tính trước các giá tr ca hàm p(i, j), mi giá tr được tính ti đa mt ln. Nếu dùng mt mng hai chiu, thí d mng p[0..n, 0..n] thì giá tr ca p[i, j] s được đin ln lượt theo tng ct, t ct th 1 đến ct th n. Ti mi ct ta đin t dưới lên trên. Ta lưu ý:
-       Phần tử ti ct i, dòng j là giá tr p[i, j] chính là chiu dài ca dãy con đối xứng dài nht khi kho sát dãy con s[i..j].
-       Vi các tr i > j, ta quy định p[i, j] = 0. Như vy na tam giác dưới ca ma trn p s chứa toàn 0.
-       Nếu i = j thì p[i, j] = 1. Như vy, mi tr trên đường chéo chính ca ma trn p s là 1.
-       Vi các ô còn li, toạ độ (i, j) s thoả điu kin 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])
Bn hãy th đin mt vài giá tr cho bng trên để rút ra quy lut.
Hãy bt đầu vi ct 1: p[1, 1] = 0;
Sau đó đến ct 2:
p[2, 2] = 1; p[1, 2] = max(p[1, 1], p[2, 2]) = 1, vì s[1] ¹ s[2].
Ri đến ct 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 đui phương án dùng mng hai chiu mà hãy căn c vào quy lut đin mng hai chiu để vn dng cho hai mng mt chiu là v[0..(n + 1)] và d[0..(n + 1)]. Theo kinh nghim, ta nên khai báo kích thước mng rng hơn chng hai phn t để s dng các phn t này như nhng lính canh cha các giá tr khi đầu phc v cho các trường hp ch s i, j nhn các giá tr 0 hoc n + 1.
Giả s mng v cha các giá tr đã đin ca ct j – 1 trong mng hai chiu p. Ta s đin các giá tr cho ct j ca mng p vào mng mt chiu d. Như vy, tại bước j, phn t v[i] s ng vi phn t p[j  1, i] còn phn t d[i] s ng vi p[j, i].  Thủ tục điền trị cho cột d tại bước jdự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 mi ln lp vi j := 1..n ta chuyn giá tr ca d cho v để chun 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 dng mt mng mt chiu d cho bài toán này vi nhn xét sau đây. Ti bước cp nht th j, vi mi 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, tc là tính d[i] vi i = n..1 thì d[i + 1] cũ s b ghi đè. Ta dùng hai biến ph ttr để bo 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 mt mng mt chiu s được coi trng 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 nhm lẫn, do đó nhiu người thường chn phương án này.
Toàn văn chương trình vi ba phương án, đệ quy, dùng hai mng một chiu và dùng mt mng mt chiu 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.

Không có nhận xét nào:

Đăng nhận xét