Chuyên đề Xâu Kí Tự BDHSG Tin 9 - 123doc

Chuyên đề bồi dưỡng học sinh giỏi tin học 9 tổng hợp lí thuyết và các dạng bài tập cơ bản và nâng cao về xâu kí tự trong pascal. Các bài tập có lời giải cho học sinh thực hành `......................................................................................................

CHUYÊN ĐỀ XÂU KÍ TỰA- KIẾN THỨC CƠ BẢN

I CÁCH KHAI BÁO VÀ TRUY XUẤT ĐẾN PHẦN TỬ XÂU

1 Cách khai báo:

Var: STRING[độ dài của xâu];

- Xâu ký tự trong bộ nhớ nó chiếm số byte bằng số ký tự cực đại được khai báocộng với byte đầu tiên chứa số ký tự hiện có của xâu Độ dài tối đa của xâu ký tự là 255

- Ngoài ra có các kiểu khai báo khác của xâu như:

3 Truy cập từng phần tử của xâu ký tự:

Việc truy cập đến phần tử trong xâu tương tự mảng 1 chiều được thông qua tên

biến kiểu STRING và chỉ số của nó

Ví dụ: St := 'Le Thanh Lam'; write(st[4]);

Hai xâu ký tự được gọi là bằng nhau khi chúng hoàn toàn giống nhau (có độ dàinhư nhau)

Ví dụ: st1:=’tin’; st2:=’ hoc’; khi đó st1>st2

3 Các thủ tục và hàm chuẩn xử lý xâu ký tự

a Hàm length(st): cho độ dài thực của xâu ký tự st

Ví dụ: st:=’tin hoc’ thì LENGTH(st) cho bằng 7

b Hàm upcase(ch): Cho ký tự hoa của ký tự ch

Ví dụ: ch:= 'a'; ch:= upcase(ch) ® ch = 'A'

Ví dụ: Viết đoạn chương trình nhập vào một xâu ký tự Đổi xâu đó sang chữ inhoa rồi in kết quả ra màn hình

var s,s1:string; i:integer;

begin

var s,s1:string; i:integer;

begin

write('nhap xau s:');

readln(s);

s1:='';

for i:=1 to length(s) do

if s[i] in ['A' 'Z'] then s1:=s1+ chr(ord(s[i])+32)

else s1:=s1+s[i];

for i:=length(s1) downto 1 do write(s1[i]);

readln;

end

e Thủ tục DELETE(st, pos, num): xóa num ký tự trong xâu st kể từ vị trí pos

Ví dụ: st= ‘tin hoc’; Delete(st,4,4); lúc đó st cho ra là ‘tin’

f Hàm POS(st1,st2): hàm cho vị trí tìm thấy đầu tiên của xâu s1 trong xâu s2.

Ví dụ: POS(‘tin’,‘tin hoc’) = 1

Ví dụ: Viết đoạn chương trình nhập vào một xâu ký tự In ra xâu đó sau khi đãxóa hết ký tự trắng thừa trong xâu (Ký tự trắng thừa là các ký tự đầu xâu, cuối xâu vànếu giữa xâu có 2 ký tự trắng liên tiếp nhau thì có một ký tự trắng thừa)

- Để xóa ký tự trắng cuối xâu ta thực hiện lệnh:

while s[length(s)] = ' ' do delete(s,length(s),1);

- Để xóa ký tự trắng giữa xâu ta thực hiện lệnh:

while pos(' ',s)<>0 do delete(s, pos(' ',s),1);

var s:string;

write('nhap xau s:');

readln(s);

while s[1]=' ' do delete(s,1,1);

while s[length(s)]=' ' do delete(s,length(s),1);

while pos(' ',s)<>0 do delete(s,pos(' ',s),1);

write(s);

readln;

end

g Thủ tục INSERT(st1, st2, pos): Thủ tục cho kết quả bằng cách chèn xâu ký tự có tên

là st1 vào xâu st2 tại vị trí pos, những ký tự đứng sau pos sẽ được dời về phía sau củaxâu ký tự st2

Ví dụ: st1:= ‘tin ‘; st2:=’hoc kho’; INSERT(st1,st2,5) ® st2=’hoc tin kho’;

Ví dụ: Viết đoạn chương trình nhập vào 3 xâu s1, s2, s (với xâu s1 xuất hiện một

và chỉ đúng 1 lần trong xâu s) Tìm và thay thế xâu s1 thành xâu s2 trong xâu s

Chẳng hạn: s1 := 'hoc'; s2:= 'bai tap'; s :='hoc tin hoc'; kết quả sau khi thay thế s1thành s2 là s = 'bai tap tin hoc'

var s1,s2,s: string; i:byte;

h Thủ tục STR(value, st): Thủ tục này thực hiện việc chuyển đối giá trị kiểu số(value)

sang dạng xâu ký tự và gán cho biến st

Ví dụ: n:=2014; STR(n,st) sẽ cho kết quả xâu st là: st=’2014’;

i Thủ tục VAL(st, value,code) đổi một xâu ký tự st sang dạng số và gán cho biến value,

nếu biến đối thành công thì code sẽ nhận giá trị bằng 0 ngược lại thì cho giá trị kháckhông

Ví dụ: VAL(‘2014’,value,code) lúc này code sẽ nhận giá trị bằng 0 và value=2014

Ví dụ: Viết đoạn chương trình nhập vào số tự nhiên a có n con số Hãy tạo ra sốmới b từ số a bằng cách in ngược có số xuất hiện trong a Chẳng hạn số a = 123 thìb=321

var a,b:Qword; s,s1:string; i,code:longint;

begin

j Hàm CONCAT(s1,s2,…,sn): hàm cho ra 1 xâu mới bằng cách nối đuôi các xâu s1,s2,

…,sn lại với nhau

Ví dụ: CONCAT(‘hoc ’, ‘tin ’) = ‘hoc tin’;

k Hàm COPY(st, pos, num): sao chép trong xâu st, num ký tự tại vị trí pos,

Ví dụ: st=’tin hoc’; COPY(st,5,3) = ‘hoc’;

Ví dụ: Viết đoạn chương trình nhập vào một xâu S (không có dấu cách vô nghĩa).Đưa ra từ dài nhất xuất hiện trong xâu S Chẳng hạn: s = 'xin chao ban' ®kết quả tìmđược là từ 'chao'

* Ý tưởng: Dùng hàm pos để xác định ví trí ký tự trống xuất hiện đầu tiên trongxâu s Từ đó xác định độ dài của từ đầu tiên trong s Nếu ta thực hiện xóa đi từ đầu tiêntrong xâu s và lặp lại thao tác trên ta sẽ tìm được từ tiếp theo, đồng thời ta sẽ tìm được

Phương pháp chung: Để thực hiện các phép tính hoặc xử lý với số nguyên ngoài

phạm vi biểu diễn được cung cấp, cách đơn giản nhất là sử dụng xâu kí tự để biểu diễnvới mỗi ký tự của xâu tương ứng với một chữ số của số nguyên lớn tính từ trái qua phải.Dưới đây chúng tôi xin đưa ra một số ứng dụng kiểu xâu trong xử lý số lớn

Bài 1 Cộng, trừ 2 số nguyên lớn

Cho hai số nguyên dương lớn có có độ dài không quá 200 chữ số Hãy đưa ratổng và hiệu của 2 số nguyên đó

* Ý tưởng: Sử dụng xâu để lưu 2 số lớn Trước hết cho 2 xâu bằng nhau bằng cách

chèn thêm nhiều ký tự '0' vào trước xâu ngắn hơn Việc thực hiện cộng 2 số sẽ đượcthực hiện bằng cách cộng lần lượt các cặp ký tự số tương ứng từ phải sang trái của cácxâu (Đối với phép trừ 2 số nguyên thực hiện tương tự)

Dữ liệu vào:

Ghi một hoặc nhiều dòng Mỗi dòng ghi một dãy kí số Số dòng không vượt quá

100 Mỗi dòng ghi từ 1 đến 100 kí số Bảo đảm rằng có ít nhất một dòng mà kí số đầutiên khác 0

Dữ liệu ra:

Ghi ra số lớn nhất đã có thể viết trên cuộn giấy trước khi bị xé rách

Ví dụ

Input Output2

2000466

66220004

* Ý tưởng: Lưu các số dưới dạng mảng kiểu xâu, thực hiện sắp xếp mảng theo

thứ tự tăng dần theo tiêu chí sắp xếp là phần tử s[i] đứng trước phần từ s[j] khi (s[i]ghép với s[j]) > (s[j] ghép với s[i])

* Chương trình tham khảo

var s: array[0 1000] of string;

i,n,j: word;

{===================}

procedure qsort(L,H: word);

var tg,k:string;

Bài 3 Tỡm số (Đề thi học sinh giỏi tỉnh lớp 11 tỉnh Hà Tĩnh năm học 2007-2008)

Cho trước một xâu kí tự, trong đó có ít nhất 5 chữ số Hãy loại

bỏ một số kí tự ra khỏi xâu sao cho 5 kí tự cuối cùng còn lại theo

- Thực hiện xóa các kí tự số chỉ giữ lại 5 số để tạo thành số lớn nhất bằng cách lầnlượt đi tìm 4 chữ số lớn nhất có trong xâu còn lại.

* Chương trình tham khảo:

Bài 4 Số nhỏ nhất (Đề thi học sinh giỏi lớp 11 tỉnh Hà Tĩnh năm 2008-2009)

Một số nguyên dương n rất lớn có thể được cho bởi P (P£20) số nguyên dương A

và P xâu ký tự s1, s2, ,sp (độ dài các xâu không vượt quá 255) chỉ gồm các số thậpphân bằng cách viết s1 liên tiếp A1 lần rồi viết s2 liên tiếp A2 lần, , viết sp liên tiếp Aplần

Giả sử với số n được cho như trên và cho trước số nguyên dương k nhỏ hơn sốchữ số của N Hãy tìm cách gạch đi k chữ số của N để nhận được một số có giá trị nhỏnhất

Ví dụ:

a1=3, a2 = 4, a3 = 2s1 = 123, s2=0, s3 = 45

* Ý tưởng: Ở bài toán này N là số nguyên lớn nên ta sử dụng xâu để biểu diễn nó,

giả sử số n lớn được ghép lại bởi m ký tự khác nhau khi đó sau khi xóa ta còn lại m-kchữ số trong n Lần lượt đi tìm m chữ số nhỏ nhất trong xâu còn lại ta được kết quả cầntìm

* Chương trình tham khảo:

For i:=1 to p do readln(a[i]);

for i:=1 to p do readln(s[i]);

2 Dạng 2 Biến đổi xâu

Phương pháp chung: Đây là dạng cơ bản thường gặp, việc biến đổi xâu được

thực hiện trên mỗi ký tự trong xâu nên cần nắm rõ các hàm, thủ tục trên kiểu dữ liệu xâu

để vân dụng một cách linh hoạt vào từng bài tập cụ thể

Bài 1 Rút gọn xâu (Đề thi HSG lớp 12 tỉnh Nghệ An năm 2009-2010)

Cho một xâu S chỉ gồm các chữ cái in thường với độ dài tối đa 250 ký tự Em hãyviết chương trình để tạo ra xâu SG từ xâu S bằng cách xóa các ký tự liên tiếp giốngnhau trong xâu S và chỉ để lại một kí tự đại diện trong đoạn đó

Dữ liệu vào: Đọc từ file văn bản XAUGON.INP chứa xâu S chỉ gồm các chữ cái in

Bài 2 Nộn và giải nộn (Đề HSG lớp 12 tỉnh Hà Tĩnh năm 2010-2011)

Một xâu kí tự có thể "nén" theo cách sau: Một xâu con gồmn>1 kí tự giống nhau, chẳng hạn gồm n kí tự "a" sẽ đợc ghi thành na

Ví dụ xâu 'aaaabbcd' sẽ đợc nén thành 4a2bcd Hãy viết chơngtrình nén và giải nén (Chú ý trong các xâu đợc nén phải không cóchữ số)

Dữ liệu vào: Cho trong tệp string.INP

Kết quả: Ghi vào tệp String.Out

* í tưởng: Với việc nộn xõu ta lần lượt đi

đếm cỏc ký tự giống nhau liờn tiếp trong xõu và sử dụng một xõu kq để lưu kết quả tỡmđược cho đến khi xột hết xõu (việc giải nộn được thực hiện ngược lại)

* Chương trỡnh tham khảo

for i:=2 to length(s1) do

if s1[i]=s1[i-1] then inc(d)

Cho xâu s (có độ dài không vượt quá 106) chỉ gồm các ký tự từ 'a' đến 'z' Cho biết

có bao nhiêu loại ký tự xuất hiện trong s và đưa ra một ký tự xuất hiện nhiều nhất trong

s cùng với số lần xuất hiện của ký tự đó

* Ý tưởng:

- Với xâu có độ dài tối đa 106 ta sẽ sử dụng khai báo kiểu xâu Ansistring

- Sử dụng mảng đánh dấu B['a' 'z'] of longint để đếm số lần xuất hiện các ký tự

trong xâu s với B[ch] = d có nghĩa là ký tự ch xuất hiện d lần

- Lần theo các giá trị của mảng B ta được số lượng các ký tự khác nhau (tức sốlượng phần tử có giá trị khác không trong mảng B) và tìm giá trị lớn nhất của mảng B ta

sẽ tìm được ký tự xuất hiện nhiều lần nhất

* Chương trình tham khảo:

writeln('so luong ki tu khac nhau:',dem);

writeln('ky tu xuat hien nhieu lan nhat la ',kt,' so lan xh ',max);

Bài 4 Gửi thư (nguồn http://vn.spoj.com/problems/NKLETTER)

Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới một đối tác củamình Văn bản là một xâu S các chữ cái la tinh in thường Để bảo mật nội dung văn bản,ông Giám đốc gửi 2 bức thư Bức thư thứ nhất là phần đầu Sb của xâu S, bức thư thứ 2

là phần cuối Se của S Hai bức thư Sb và Se đảm bảo đầy đủ nội dung của S, tuy nhiên

có thể một phần cuối của Sb có thể được viết lặp lại trong phần đầu của Se, song số kí

tự được viết lặp lại không biết trước

Ví dụ: với văn bản S=’truongnguyenduquannhat’ tạo ra hai bức thư:

- Kết quả bài toán là length(s1)+length(s2) - max

* Chương trình tham khảo:

3 Dạng 3 Các bài tập xâu Palindrome

Phương pháp chung: Xâu Palindrome hay còn gọi là xâu đối xứng, có nghĩa một

xâu khi đọc các ký tự trong xâu từ trái sang phải cũng giống từ phải sang trái thì xâu đóđược gọi là xâu Palinhdrome

Với những bài tập kiểm tra xâu Palindrome hay tìm kiếm xâu có tính chấtPalindrome thì trước hết nên xây dựng hàm kiểm tra tính chất đối xứng của một xâu với

độ phức tạp O(n), trên cơ sở đó chúng ta đi giải quyết những bài tập khó hơn

Bài 1 Xâu Palindrome 1

Cho một xâu S có độ dài không vượt quá 106 Kiểm tra xem xâu S có phải là xâuPalindrome hay không?

* Ý tưởng: Một xâu s có tính chất đối xứng khi s[i] = s[n-i+1] với i chạy từ 1 đếnlength(s) div 2 Dựa trên cơ sở đó ta xây dựng hàm kiểm tra

* Chương trình tham khảo

Bài 2 Xâu con Palindrome 2

Cho một xâu S có độ dài không vượt quá 1000 kí tự; tìm xâu palindrome dài nhất

là xâu con của S

* Ý tưởng: Sử dụng phương pháp quy hoạch động bằng cách sử dụng mảng 2

chiều F và giá trị F[i, j] = true/false nếu đoạn gồm các kí tự từ i đến j của S có/không làpalindrome

Ta có công thức là:

- F[i, i] = True

- F[i, j] = F[i+1, j-1]; ( nếu s[i] = s[j] )

- F[i, j] = False; ( nếu s[i] <> s[j] )

* Đoạn chương trình tham khảo

var s:ansistring; n,i,j,d,max,k,csd,csc:longint;

F[i, j] := ( F[i+1, j-1] ) and (s[i] = s[j] );

if (f[i,j]=true) and (d>max) then

begin max:=d; csd:=i; csc:=j; end;

end;

for i:=csd to csc do write(s[i]);

readln;

end

Bài 3 Xâu Palindrome 3

Một xâu gọi là đối xứng nếu xâu đó đọc

từ trái sang phải cũng giống nh đọc từ phải sang

trái Cho một xâu S hãy tìm số kí tự ít nhất cần

thêm vào sâu S để S trở thành xâu đối xứng

Dữ liệu vào: xau_dx.inp gồm

Gồm một dòng là xâu S

Dữ liệu ra: Ghi vào tệp xau_dx.out

- Dòng 1: Đa ra số lợng kí tự ít nhất cần chèn thêm vào

- Dòng 2: Các kí tự cần chèn

* ý tởng:

- Gọi S2 là xâu đảo của xâu S1 ban đầu, T là xâu con chungdài nhất của S1 và S2 Khi đó các kí tự của S1 không thuộc T chính làcác kí tự cần chèn vào S1 để S1 trở thành xâu đối xứng

- Bài toán trở thành tìm dãy con chung dài nhất của hai dãy

t-ơng ứng là 2 xâu S1 và S2 bằng pht-ơng pháp quy hoạch động

Sử dụng mảng L[0 max,0 max] để lu độ dài dãy con chung dàinhất với L[i,j] là độ dài dãy con chung dài nhất của hai dãy xâu s1 vàs2:

Khi đó:

L[0,j] = 0 với (N = length(s1))

L[i,0] = 0 với (M = length(s2))

Với , :

Nếu s1[i] = s2[j] thì L[i,j]:= L[i-1,j-1] + 1

ngược lại L[i,j] = max{L[i-1,j], L[i,j-1]}

if (s1[i]=s2[j]) then L[i,j]:=L[i-1,j-1]+1

else L[i,j]:= max(L[i-1,j], L[i,j-1]);

begin doc; xuly; inkq; end.

Bài 4 Robot công nghiệp (Đề thi HSG lớp 11 tỉnh Hà Tĩnh năm học 2010-2011)

Trong một nhà máy có trang bị loại Robot công nghiệp để thực hiện việc tự độnghoá gia công các sản phẩm Việc gia công các sản phẩm của Robot được thực hiện đồngthời trên hai sản phẩm cùng một lúc theo tiến trình: Với mỗi loại thao tác gia công đượcRobot thực hiện trên sản phẩm thứ nhất xong rồi chuyển sang thực hiện trên sản phẩmthứ hai Để hoàn thành một sản phẩm, Robot có thể thực hiện tới N loại thao tác giacông (N≤ 24) và mỗi loại thao tác gia công đã thực hiện trên một sản phẩm nào đó rồithì không thực hiện lại trên sản phẩm đó nữa Robot hoạt động bằng lệnh là một dãy ký

tự in hoa, mỗi ký tự là lệnh thực hiện cho một loại thao tác gia công Lệnh thực hiện cácloại thao tác gia công khác nhau là các ký tự khác nhau Việc đọc dòng lệnh và thựchiện lệnh của Robot được tiến hành theo các chu trình như sau:

+ Chu trình thứ nhất: Đọc ký tự thứ nhất, thực hiện lệnh tương ứng trên sản phẩmthứ nhất Tiếp theo đọc ký tự thứ N, thực hiện lệnh tương ứng trên sản phẩm thứ hai + Chu trình thứ hai: Đọc ký tự thứ hai, thực hiện lệnh tương ứng trên sản phẩm thứnhất Tiếp theo đọc ký tự thứ N-1, thực hiện lệnh tương ứng trên sản phẩm thứ hai + Chu trình thứ ba: Đọc ký tự ba, thực hiện lệnh tương ứng trên sản phẩm thứ nhất.Tiếp theo đọc ký tự thứ N-2, thực hiện lệnh tương ứng trên sản phẩm thứ hai

Tương tự với các chu trình còn lại để đọc hết dòng lệnh

Với một xâu S các ký tự in hoa có số lượng các ký tự là chẵn và không quá N x 2,hãy xác định xem nó có phải là một dòng lệnh của Robot đã nói ở trên hay không?

Dữ liệu vào: Tệp văn bản ROBOT.INP có cấu trúc:

- Dòng đầu tiên ghi 1 số là độ dài xâu S

- Dòng thứ 2 ghi xâu S

Dữ liệu ra: Tệp văn bản ROBOT.OUT ghi thông báo ‘CO’ nếu xâu S là dòng

lệnh của Robot, ngược lại ghi thông báo ‘KHONG’

* Chương trình tham khảo:

for i:=1 to n div 2 do

if s[i] <> s[n-i+1] then

Bài 1 Đếm xâu con

Cho xâu s (có độ dài không vượt quá 103) chỉ gồm các ký tự từ 'a' đến 'z' Đếm sốlượng xâu con liên tiếp khác nhau nhận được từ xâu s

Ví dụ: S = 'abab' có 7 xâu con là: a, b, ab, ba, aba,bab,abab

* Ý tưởng: Lưu các xâu con có độ dài i (với i từ 1 đến length(s)) vào một mảng,sau đó sắp xếp mảng tăng dần rồi thực hiện đếm số lượng các xâu con khác nhau tađược số lượng xâu con có độ dài i

* Chương trình tham khảo:

k:=a[(x+y)div 2];

repeat

while a[x]<k do inc(x);

while a[y]>k do dec(y);

Bµi 2 X©u con (Đề thi học sinh giỏi lớp 12 tỉnh Nghệ An năm học 2008-2009)

Cho tríc hai x©u kÝ tù S1 vµ S2 ViÕt ch¬ng tr×nh tÝnh sè lÇnlÆp l¹i cña x©u S1 trong x©u S2

D÷ liÖu: Vµo tõ tÖp v¨n b¶n XAU.INP gåm:

- Dßng ®Çu tiªn chøa x©u S1.

- Dßng thø hai chøa x©u S2

KÕt qu¶: Ghi ra tÖp v¨n b¶n XAU.OUT:

- ChØ mét dßng duy nhÊt ghi sè lÇn lÆp l¹i cña x©u S1 trong x©uS2

VÝ dô:

ababababababa

4

* Ý tưởng: Sử dụng hàm Pos(s1,s2) để xác định có hay không xuất hiện xâu s1trong xâu s2 Giả sử giá trị hàm trả về là i khác 0, ta tăng biến đếm lên 1 và xóa ký tựthứ i trong xâu s2, tiếp tục quá trình trên cho đến khi hoặc i=0 hoặc xâu s2 rổng

* Chương trình tham khảo:

Yêu cầu: Hãy trả lời câu hỏi của người dẫn chương trình.

Dữ liệu: Vào từ tập tin văn bản CNDK.INP gồm hai dòng:

+ Dòng 1 ghi số N là số lượng số đã hiện lên màn hình, (2 £ N £ 100)

+ Dòng 2 ghi lần lượt N số, mỗi số có giá trị không quá 32000.

Kết quả: Ghi ra tập tin văn bản CNDK.OUT số ô tối thiểu của “chiếc nón”.

Lưu ý: Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.

* Chương trình tham khảo: