Chuyên đề Xâu Kí Tự - Tài Liệu Text - 123doc

Tải bản đầy đủ (.pdf) (47 trang)

1. Trang chủ
>>
2. Giáo Dục - Đào Tạo
>>
3. Trung học cơ sở - phổ thông

Chuyên đề Xâu kí tự

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (591.2 KB, 47 trang )

CHUYÊN ĐỀ XÂU KÍ TỰA­ KIẾN THỨC CƠ BẢNI. CÁCH KHAI BÁO VÀ TRUY XUẤT ĐẾN PHẦN TỬ XÂU1. 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áo cộ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ư:                   + Shortstring: Chính là String.                   + longstring: là mảng ký tự có kiểu char. Thông thường kiểu char có kích thước 16 bit nên mảng có kích thước tối đa 16 bit = 65535 ký tự.                    + ansistring (chỉ  có trong free pascal mà không có trong turbo pascal) có kích thước gần 2GB = 230 B nên thường được xem là vô hạn.2. Cách nhập/xuất:          Cách đọc hay viết kiểu STRING cũng tương tự  như các kiểu dữ  liệu khác, ta sử dụng các thủ tục READ, hoặc WRITE.          Ví dụ: Readln(st);  Writeln(st);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]);          ­> Kết quả: cho ra chữ T.II. CÁC THAO TÁC TRÊN XÂU KÝ TỰ1. Phép cộng xâu:          Ví dụ:          st1:=’tin’; st2:=’ hoc’; St=st1 + st2;           ­> St = ‘tin hoc’2. Phép so sánh:            Hai   xâu   ký   tự   có   thể   so   sánh   với   nhau   bằng   các   phép   so   sánh   =,   >,   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'1          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ữ in  hoa rồi in kết quả ra màn hìnhvar s,s1:string; i:integer;begin  write('nhap xau s:');  readln(s);  s1:='';  for i:=1 to length(s) do s1:=s1+ upcase(s[i]);  write(s1);  readln;end.c. Hàm Ord(ch): Cho mã của ký tự ch trong bảng mã ASCII          Ví dụ: ch:='a'; n:= Ord(ch) ® n= 97d. Hàm Chr(n): Cho ký tự có mã là n          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ữ thường rồi in xâu đó ra màn hình theo thứ tự ngược lại          * Ý tưởng: Để  thực hiện chuyển đổi ký tự  ch  ở  dạng hoa sang dạng thường  trước hết ta sử dụng hàm ord(ch) để lấy mã ký tự đó, sau đó sử dụng hàm chr(ord(ch)+32) để được ký tự  thường của ký tự  hoa ch (vì mã của ký tự  hoa ch lệch mã ký tự thường tương ứng là 32 như: ord('A')=65, ord('a')=97)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)          * Ý tưởng:          ­ Sử dụng hàm Pos(' ',s) để biết được vị trí i nào đó xuất hiện ký tự trắng và sử dụng thủ tục Delete(s,i,1) để xóa ký tự thứ i trong xâu s          ­ Để xóa ký tự trắng đầu xâu ta thực hiện lệnh:          while s[1]=' ' do delete(s,1,1);2          ­ Để 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;begin  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ủa xâ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 ế s1 thành s2 là s = 'bai tap tin hoc'var s1,s2,s: string; i:byte;begin  write('nhap s1:');  readln(s1);  write('nhap s2:');  readln(s2);  write('nhap xau s:');  readln(s);  i:= pos(s1,s);  delete(s,i,length(s1));  insert(s2,s,i);  write(s);  readln;end.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ác không3           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=321var a,b:Qword; s,s1:string; i,code:longint;begin write('nhap a:'); readln(a); str(a,s); s1:=''; for i:=length(s) downto 1 do s1:=s1+s[i]; val(s1,b,code); write(b); readln;end.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  trong xâ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ên trong 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 từ có độ dài lớn nhất.          * Chương trình:var s,tumax:string;begin write('nhap xau s:'); readln(s); while pos(#32,s)0 do  begin     if pos(#32,s)>length(tumax) then tumax:=copy(s,1,pos(#32,s));     delete(s,1,pos(#32,s));  end; writeln(tumax); readln;end.B. CÁC DẠNG BÀI TẬP THƯỜNG GẶP41. Dạng 1. Xử lý số nguyên lớn          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ễn vớ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 ra  tổ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ẽ được thự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ác xâu (Đối với phép trừ 2 số nguyên thực hiện tương tự)          * Đoạn chương trình:function  Add(s1,s2:string):string;var  i,nho,z,x,y:longint;  s:string;begin   while length(s1)=s2 then sub:=sub1(s1,s2)      else  sub:='­'+sub1(s2,s1);end;Bài 2. Ghép số lớn ( />       Vaxia đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với anh trai  Petia về thành quả vừa đạt được. Tuy nhiên,  khi Vaxia vừa ra khỏi phòng để gọi anh trai thì cô em Kachia chạy vào phòng và xé rách cuộn giấy thành một số  mảnh. Kết quả là trên mỗi mảnh có một hoặc vài kí số theo thứ tự đã viết. Bây giờ Vaxia không  thể  nhớ  chính xác mình đã viết số  gì. Vaxia chỉ  nhớ  rằng đó là một số  rất lớn. Để làm hài lòng cậu em trai, Petia quyết định truy tìm  số nào là lớn nhất mà Vaxia đã có thể viết lên cuộn giây trước khi bị xé. Bạn hãy giúp Petia làm việc này.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ố đầu tiê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 Output2662200042000466336           * Ý 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ảovar s: array[0..1000] of string;i,n,j: word;{===================}procedure qsort(L,H: word);var tg,k:string;beginif l>=h then exit;i:=l; j:=h;tg:=s[(l+h) div 2];repeatwhile tg+s[i]s[j]+tg do dec(j);if ilength(s);     for i:=1 to 5 do     begin          k:=i;          for j:=i to length(s)+i­5 do              if s[k]i then delete(s,i,k­i);     end;     writeln(copy(s,1,5));8end;{===========================}Begin     Nhap;      xuly;     readln;end.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ập phâ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 Ap lầ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ụ:VàoKết quảp=3, k =1144a1=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­k chữ 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ần tìm.          * Chương trình tham khảo:{$MODE OBJFPC}Var  A               :array[1..20] of longint;     S               :array[1..20] of ansistring;     st,kq           :ansistring;     k,i,p,m,j      :longint;{==============}Procedure             nhap;Begin    st:='';      Write('Nhap p '); Readln(p);      Write('Nhap k ');Readln(k);      For i:=1 to p do readln(a[i]);      for i:=1 to p do readln(s[i]);      for i:=1 to p do        For j:=1 to A[i] do             st:=st+S[i];End;9{===============}Procedure       xuly;var m:longint; sm:ansistring; code:integer;    Begin     j:=0;     m:=length(st)­k;      Repeat         sm:='9';         dec(m);             For i:=j+1 to length(st)­m do                If sm>st[i] then                  Begin                     sm:=st[i];                     j:=i;                  End;          kq:=kq+sm;      Until m=0;     Val(kq,m,code);     Write(m);    End;{===============}BEGIN   nhap;   xuly;   ReadlnEND.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ãy viế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ống nhau 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 thường.Kết quả: Ghi ra file văn bản XAUGON.OUT là xâu SG tìm được.Ví dụ:XAUGON.INPXAUGON.OUThhooocccsssiiiiinnnhhhhocsinh10*ítng:Duytt uxõuncuixõu,gp2kýt liờntipkhỏcging nhauthỡxúaimtkýt.*Chngtrỡnhthamkho:constfi='xaugon.inp';fo='xaugon.out';Vars:string;f:text;{========}proceduredoc;beginassign(f,fi);reset(f);readln(f,s);end;{========}procedurexuly;varch,kt:char;i,max,dem:longint;beginassign(f,fo);rewrite(f);i:=1;whilei1kítựgiốngnhau,chẳnghạngồmnkítự"a"sẽđợcghithànhna.Vídụxâu'aaaabbcd'sẽđợcnénthành4a2bcd.Hyviếtchơngtrìnhnénvàgiảinén.(Chúýtrongcácxâuđợcnénphảikhôngcóchữsố).Dữliệuvào:Chotrongtệpstring.INPKếtquả:GhivàotệpString.Outstring.inpaaaabbcd11string.out4a2bcd3a2baaabb          * Ý 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ảoconst  fi='string.inp';       fo='string.out';var    f,g:text; s1,s2:string;{================}procedure  doc;begin  assign(f,fi); reset(f);  readln(f,s1);  readln(f,s2);  close(f);end;{================}procedure  nen;var   s,kq:string; i,d:integer; ch:char;begin  d:=1; s1:=s1+#32;ch:=s1[1];  kq:='';  for i:=2 to length(s1) do   if s1[i]=s1[i­1] then inc(d)   else    begin      str(d,s);      if d1 then kq:=kq+s+ch else kq:=kq+ch;      d:=1;      ch:=s1[i];    end;  writeln(g,kq);end;{================}procedure   giainen;var s,kq,so:string; i,j,code,n:integer; ch:char;begin   i:=1;  kq:='';   repeat12      so:='0';      while s2[i] in ['1'..'9'] do  begin so:=so+s2[i];inc(i); end;      val(so,n,code);      if n>1 then        for j:=1 to n do kq:=kq+s2[i]      else kq:=kq+s2[i];      inc(i);   until i> length(s2);  writeln(g,kq);end;{================}begin  assign(g,fo); rewrite(g);  doc;  nen;  giainen;  close(g);end.Bài 3. Ký tự khác nhau          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:Var  s:ansistring;     b:array['a'..'z'] of longint;{========}procedure  nhap;begin write('nhap xau s:'); readln(s);end;{========}procedure  xuly;var  ch,kt:char; i,max,dem:longint;begin  for ch:='a' to 'z' do b[ch]:=0;13  for i:=1 to length(s) do inc(b[s[i]]);  dem:=0;  max:=0;  for ch:='a' to 'z' do   begin   if b[ch]0 then inc(dem);   if b[ch]>max then      begin        max:=b[ch];        kt:=ch;      end;   end;  writeln('so luong ki tu khac nhau:',dem);  writeln('ky tu xuat hien nhieu lan nhat la ',kt,' so lan xh ',max);end;{=========}begin  nhap;  xuly;  readln;end.Bài 4. Gửi thư (nguồn  />          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ủa  mì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ư:Sb=’truongnguyendu’ và Se=’nguyenduquannhat’Yêu cầu: Cho hai xâu Sb và Se, hãy xác định một xâu S có thể  là nội dung của bức thư sao cho độ dài của xâu S là ngắn nhất.Dữ liệuDòng đầu chứa xâu Sb, dòng thứ hai chứa xâu Se. Mỗi xâu có độ dài không quá 250.Kết quảGhi ra độ dài của xâu S tìm được.Ví dụDữ liệutruongnguyendunguyenduquannhat Kết quả22          * Ý tưởng:14          ­ Lần lượt xét các xâu con d, c tương  ứng tính từ  cuối xâu s1 và đầu xâu s2,  nếu d=c thì ta lưu lại độ dài của xâu d. Quá trình cứ tiếp tục và ta nhận được độ dài xâu con chung dài nhất cần tìm (giả sử là max).          ­ Kết quả bài toán là length(s1)+length(s2) ­ max          * Chương trình tham khảo:var s,s1,d,c:string;    i,kq,n,h,k,max:integer;begin   readln(s);   read(s1);   i:=1; h:=length(s);   k:=length(s1); n:=min(h,k); max:=0;   while imax) then      begin        max:=d;        csd:=i;        csc:=j;      end;  end; for i:=csd to csc do write(s[i]); readln;end.16Bài3.XâuPalindrome3xau_dx.inp Xau_dx.outedbabcd2ecMộtxâugọilàđốixứngnếuxâuđóđọctừtráisangphảicũnggiốngnhđọctừphảisangtrái.ChomộtxâuShytìmsốkítựítnhấtcầnthêmvàosâuSđểStrởthànhxâuđốixứng.Dữliệuvào:xau_dx.inpgồmGồmmộtdònglàxâuSDữliệura:Ghivàotệpxau_dx.outưDòng1:ĐarasốlợngkítựítnhấtcầnchènthêmvàoưDòng2:Cáckítựcầnchèn*ýtởng:ưGọiS2làxâuđảocủaxâuS1banđầu,TlàxâuconchungdàinhấtcủaS1vàS2.KhiđócáckítựcủaS1khôngthuộcTchínhlàcáckítựcầnchènvàoS1đểS1trởthànhxâuđốixứngưBàitoántrởthànhtìmdyconchungdàinhấtcủahaidytơngứnglà2xâuS1vàS2bằngphơngphápquyhoạchđộng.SửdụngmảngL[0..max,0..max]đểluđộdàidyconchungdàinhấtvớiL[i,j]làđộdàidyconchungdàinhấtcủahaidyxâus1vàs2:Khiđó:L[0,j]=0với(N=length(s1))L[i,0]=0với(M=length(s2))Với,:Nếus1[i]=s2[j]thìL[i,j]:=L[iư1,jư1]+1ngclạiL[i,j]=max{L[iư1,j],L[i,jư1]}*Chơngtrìnhthamkhảoprogramxau_doi_xung;constmaxn=100;varL:array[0..maxn,0..maxn]ofbyte;kq:array[1..maxn]ofboolean;m:integer;s1,s2:string;f:text;{==========}proceduredoc;vari:integer;beginassign(f,'daycon.inp');reset(f);readln(f,s1);m:=length(s1);s2:='';fori:=mdownto1dos2:=s2+s1[i];17  close(f);end;{==========}function   max(x,y:integer):integer;begin   if x>y then max:=x else max:=y;end;{===========}procedure   xuly;var i,j:integer;begin  fillchar(L,sizeof(L),0);  for i:=1 to m do    for j:=1 to m do      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]);end;{====================}procedure  inkq;var i,j,d:integer;begin    assign(f,'daycon.out'); rewrite(f);    writeln(f,m­L[m,m]);    fillchar(kq,sizeof(kq),false);    i:=m; j:=m;    while (i>0) and (j>0) do        if s1[i]=s2[j] then            begin              kq[i]:=true;              dec(i); dec(j);            end        else           if L[i,j]=L[i,j­1] then dec(j) else dec(i);    For i:=1 to m do       if kq[i] = false then write(f,s1[i],' ');    close(f);end;{====================}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ự động hoá 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  18hiện đồng thờ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 được Robot 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ẩm thứ  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 gia cô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ồi thì 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ác loạ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ực hiệ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ẩm thứ 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’Tệp ROBOT.INPTệp ROBOT.OUT6COCBAABCTệp ROBOT.INPTệp ROBOT.OUT6KHONGACBDCA            * Ý tưởng: Với yêu cầu của đề bài, bài toán trở thành kiểm tra xâu đầu vào có đối xứng hay không?          * Chương trình tham khảo:19var s:ansistring;    n,i:longint;    kt:boolean;    f,g:text;{==========}begin assign(f,'robot.inp'); reset(f); assign(g,'robot.out'); rewrite(g); readln(f,n); readln(f,s); kt:=true; for i:=1 to n div 2 do  if s[i]  s[n­i+1] then    begin      kt:=false;      break;    end; if kt then write(g,'yes') else write(g,'no'); close(f); close(g);end.4. Dạng 4. Tìm xâu con          Phương pháp chung: Để  tìm các xâu con của xâu ban đều thỏa mãn một điểu  kiện cho trước thì thường sử dụng phương pháp vét cạn với bộ dữ liệu đầu vào nhỏ,  tuy nhiên nên sử dụng linh hoạt các phương pháp khác như phương pháp quy hoạch  động trong trường hợp bài toán có bộ dữ liệu lớn.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:{$MODE OBJFPC}program bai1;var   d,i,j,t:longint;s:ansistring;        a:array[1..10000]of ansistring;{======================}procedure Q_sort(l,h:longint);var x,y:longint;k,tg:string;begin        x:=l;        y:=h;20        k:=a[(x+y)div 2];repeat        while a[x]k do dec(y);        if xy;if xl then Q_sort(l,y);end;{=====================}procedure  xuly; var  kq:longint;beginwrite('nhap xau s  ');readln(s);kq:=0;for i:=1 to length(s) do        begin        d:=1;        for j:=i to length(s) do                begin                  a[d]:=copy(s,j­i+1,i);                  inc(d);                end;        Q_sort(1,d­1); a[d+1]:=' ';        for t:=1 to d­1 do           if a[t]a[t+1] then inc(kq);        end; write(kq);end;{=============}begin  xuly;  readln ;end.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Çn lÆp l¹i cña x©u S1 trong x©u S2.21Dữliệu:VàotừtệpvănbảnXAU.INPgồm:ưDòngđầutiênchứaxâuS1.ưDòngthứhaichứaxâuS2.Kếtquả:GhiratệpvănbảnXAU.OUT:ưChỉmộtdòngduynhấtghisốlầnlặplạicủaxâuS1trongxâuS2.Vídụ:XAU.INPXAU.OUTababababababa4*ítng:SdnghmPos(s1,s2)xỏcnhcúhaykhụngxuthinxõus1trongxõus2.Gisgiỏtrhmtrvlikhỏc0,tatngbinmlờn1vxúakýtthitrongxõus2,tiptcquỏtrỡnhtrờnchonkhihoci=0hocxõus2rng.*Chngtrỡnhthamkho:{$modeobjfpc}Vars1,s2:ansistring;f,g:text;dem:longint;beginassign(f,'xau.inp');reset(f);assign(g,'xau.out');rewrite(g);readln(f,s1);readln(f,s2);dem:=0;while(pos(s1,s2)0)and(length(s2)0)dobegininc(dem);delete(s2,pos(s1,s2),1);end;writeln(g,dem);close(f);close(g);end.Bi3.Chicnúnkdiu(thihcsinhgiilp12tnhPhỳYờnnmhc2009ư2010)MtlntrongchngtrỡnhChicnúndiuk, phnchidnhchokhỏn gi,thayvỡoỏnchnhmikhi,ngidnchngtrỡnhtmỡnhquaychicnúnvchohinlờnmnhỡnhtrcmtkhỏngitrongtrngquaycỏcstrongcỏcụmkimch th lnltiqua.Chicnúnquayỳngmts nguyờnvũng,nờntrongdóys hinlờnmnhỡnh,s cuicựngtrựngvis utiờn.Sauú,ngidn chngtrỡnhmimtkhỏngi cuitrngquay(ch nhỡnthymnhỡnhmkhụngnhỡnthychicnún)chobitchicnúncútithiubaonhiờuụ?22Yê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.Ví dụ:    CNDK.INPCNDK.OUT135 3 1 3 5 2 5 3 1 3 5 2 56          * Ý tưởng: Nhận thấy nếu ghép toàn bộ các số hiện lên màn hình (trừ số cuối  cùng) vào một xâu S thì trong xâu S sẽ luôn tồn tại một xâu s1 dài nhất mà khi ghép  liên tiếp một số lần xâu s1 ta sẽ được xâu s. Số lần xuất hiện xâu s1 là kết quả cần  tìm. Bài toán trở thành tìm xâu con dài nhất s1.          * Chương trình tham khảo:{$ mode objfpc}Var s1,s2,s:ansistring;    f,g:text;    dem,n,i,x: longint;begin  assign(f,'CNKD.inp'); reset(f);  assign(g,'CNKD.out'); rewrite(g);  readln(f,N);  s:='';  FOR i:=1 to n do   begin     read(f,x);     str(x,s1);     s:=s+s1;   end;  dem:=0;  delete(s,length(s),1);  for i:=1 to length(s) do    begin     s2:=s;     s1:=copy(s2,1,i);     while (pos(s1,s2)0) and (length(s2)0) do delete(s2,1,i);     if length(s2)=0 then          begin           dem:=i; write(dem);           break;23end;end;writeln(g,dem);close(f);close(g);readln;end.Bài4.ChuỗiconlớnnhấtCho2chuỗiX=x1x2...xNtrongđóxilàcácsốtừ0đến9.Y=y1y2...yMtrongđóyilàcácsốtừ0đến9vàM,NL[i,j­1] then L[i,j]:=L[i­1,j] else L[i,j]:=L[i,j­1];  max:=L[m,n]; writeln(max);end;{=============}procedure  in_kq; var i,j,is,js,so:byte; ch:char;begin  Is:=length(x);Js:=length(y);so:=0;      repeat         for ch:='9' downto '0' do          begin            i:=is; j:=js;            while (x[i]<>ch) and(i>0) do dec(i);            while (y[j]<>ch) and(j>0) do dec(j);            if L[i,j]=max­so then              begin      kq:=ch+kq;      Is:=i; Js:=j;   break;              end;          end;           inc(so);       until max=so;   write(kq);end;{=================}begin   doc;   kq:=' '; xuli1; in_kq; readln; end.IV. BÀI TẬP ÁP DỤNGBài 1. chuỗi đối xứng (nguồn  />          Một chuỗi được gọi là đối xứng (palindrome) nếu như  khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.           Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước.  Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.Dữ liệu vàoGồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.Kết quảGồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều  kết quả, chỉ cần in ra một kết quả bất kỳ.Giới hạnChuỗi s có độ dài không vượt quá 2000.Ví dụ25

Tài liệu liên quan

• Tài liệu THÔNG TIN VỀ NGÀY TRÁI ĐẤT NĂM 2000
  • 24
  • 488
  • 1
• Tài liệu THONG TIN VE NGAY TRAI DAT
  • 19
  • 433
  • 1
• Tài liệu THÔNG TIN CÁC NGÀNH NGHỀ (TƯ VẤN TUYỂN SINH ĐẠI HỌC CAO ĐẲNG)
  • 65
  • 495
  • 2
• Tài liệu Thông tin về nhà văn Kim Lân
  • 2
  • 592
  • 0
• Tài liệu Thông tin về nhà văn Kim Lân
  • 2
  • 446
  • 1
• Tài liệu Thong tin ve trai dat nam 2000
  • 24
  • 356
  • 0
• Tài liệu Thong tin ve trai dat nam 2000
  • 24
  • 350
  • 0
• Tài liệu THÔNG TIN VỀ NGUYỆN VỌNG 3 docx
  • 5
  • 344
  • 0
• Tài liệu Thông Tin và hướng dẫn xin thị thực nhập cảnh du học Canada ppt
  • 4
  • 592
  • 2
• Chuyên đề hiđroxit lưỡng tính tài liệu, ebook, giáo trình
  • 7
  • 1
  • 4

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(591.2 KB - 47 trang) - Chuyên đề Xâu kí tự Tải bản đầy đủ ngay ×