Chuỗi và các bài toán trên chuỗi

ên chuỗi Bài toán: Tìm kiếm chuỗi p có chiều dài là m trong chuỗi a có chiều dài n. Có hai trường hợp xảy ra sau khi tìm kiếm đó là: - Nếu không tìm thấy chuỗi p trong chuỗi a thì kết quả là 0. - Nếu tìm thấy chuỗi p trong chuỗi a thì kết quả là vị trí của ký tự đầu tiên của lần tìm thấy đầu tiên. Sau đây chúng ta lần lượt đi vào phân tích từng giải thuật cụ thể : 2.1. Giải thuật Brute- Force. a. Nội dung của giải thuật - Đối với vị trí kí tự thứ i của chuỗi a (i=1,2,…,n-m+1) ta so sánh các ký tự tương ứng từ trái qua phải: p[1] với a[i] p[2] với a[i+1] …………. p[m] với a[i+m+1] - Gọi: i - chỉ số của chuỗi a. j - chỉ số của chuỗi p. Nếu a[i] = p[j] thì ta tăng chỉ số i và j lên 1(xét đến ký tự tiếp theo) Nếu a[i]p[j] thì ta cho j chỉ về đầu chuỗi p (j=1) và i chỉ về vị trí ký tự kế tiếp khi bắt đầu tìm kiếm lần cuối cùng (i = i-j+2). Giải thuật kết thúc khi j>m hoặc i>n. - Ta khai báo : Type St =string[255]; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 4 Index = 1..255; c. Giải thuật: Chương trình thực hiện giải thuật này như sau: program Brute_Force; uses crt; type st=string[50]; var a,p:st; {a chứa chuỗi nguồn , p là chuỗi đích, n độ dài chuỗi a ,m là độ dài chuỗi p} procedure init; var i,j:integer; begin writeln('Nhập chuỗi a:'); readln(a); writeln('Nhập chuỗi p:'); readln(p); end; procedure Result; begin writeln('Chuỗi cần tìm là:',p) end; Function Brutesearch(p,a:st):integer; var i,j,m,n:integer; begin m:=length(p); n:=length(a); i:=1; j:=1; repeat if a[i]=p[j] then begin i:=i+1; j:=j+1; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 5 end else begin i:=i-j+2; j:=1; end; until(j>m)or (i>n); if j>m then Brutesearch:=i-m; else Brutesearch:=0; end; begin clrscr; Init; Brutesearch(a,p); write('Vị trí của ký tự đầu của chuỗi p trong a là:',Brutesearch(p,a):2); writeln; Result; readln; end. Ví dụ: Ta xét một ví dụ cụ thể sau: Cho chuỗi a=’ 0101101001110011101011100’ n=27, chuỗi p=’ 010011’ m=6 stt So sánh 2 giá trị Chí số mới của i và j Chú thích 1 a[1]=p[1] i=2;j=2 2 a[2]=p[2] i=3;j=3 3 a[3]=p[3] i=4;j=4 4 a[4]p[4] i=2,j=1 i=i-j+2 5 a[2]p[1] i=3;j=1 - 6 a[3]=p[1] i=4;j=2 Tăng i và j lên 1 7 a[4]=p[2] i=5;j=3 - 8 a[5]p[3] i=4;j=1 i=i-j+2 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 6 9 a[4]p[1] i=5;j=1 - 10 a[5]p[1] i=6;j=1 - 11 a[6]=p[1] i=7;j=2 tăng i và j lên 1 12 a[7]=p[2] i=8;j=3 - 13 a[8]=p[3] i=9;j=4 - 14 a[9]=p[4] i=10;j=5 - 15 a[10]=p[5] i=11;j=6 - 16 a[11]=p[6] i=12;j=7 giải thuật kết thúc do j>m Đến đây giải thuật kết thúc giá trị trả về ở đây là 6 của lần tìm thấy đầu tiên a=’ 0101101001110011101011100’ p=’ 010011’ d. Phân tích giải thuật Trường hợp xấu nhất của giải thuật này là trường hợp cả hai chuỗi p và a đều gồm các số 0 và kết thúc là số 1. Khi đó với n-m +1 lần tìm kiếm ta phải so sánh m ký tự của chuỗi p với các ký tự tương ứng của chuỗi a. Số lần so sánh : Cmax=m*(n-m+1) Ta có thể cải tiến giải thuật này bằng giải thuật Knuth- Morris-Pratt. 2.2. Giải thuật Knuth- Morris- Pratt. a. Nội dung của giải thuật - Trong giải thuật Brute-Force ta nhận thấy khi so sánh đến ký tự p[j]a[i] thì ta đã có j -1 kí tự đầu tiên của chuỗi p bằng với các j-1 ký tự cuối cùng trước a[i] của chuỗi a. Ví dụ : Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 7 chuỗi a là :’1010100111’ chuỗi p là :’10100111‘ - Ta nhận thấy a[5] và p[5] khác nhau. Khi đó ta không cần cho j=1 nữa mà cho j về 3 để so sánh vì ta nhận thấy 3 ký tự đầu tiên của chuỗi p bằng với 3 ký tự đang xét cuối cùng của của chuỗi a. Do đó ta không cần cho i quay về vị trí trước nữa mà vẫn tiếp tục cho i tăng. Ta sử dụng mảng next[1…m] để để ghi nhận giá trị j quay về . Phần tử next[j] sẽ cho giá trị mới của j khi phát hiện hai ký tự khác nhau. Mảng next[1…m] được xác định như sau : - Sử dụng chuỗi p1 hoàn toàn giống p. Cho chuỗi p1 di chuyển từ trái qua phải đồng thời so sánh với chuỗi p và dừng lại khi các kí tự đầu tiên của chuỗi p1 trùng với các kí tự của chuỗi p. Các kí tự trùng này sẽ xác định giá trị của next. - Nếu sự khác nhau này được phát hiện ở p[j] thì next[j] :=1+số ký tự trùng nhau +.với j=1 next[j]=0 +.với j>1 next[j] := lµ sè lín nhÊt k<j sao cho k-1 ký tù ®Çu tiªn cña p1 trïng víi k-1 ký tù cuèi cïng cña j-1 (t¹i thêi ®iÓm ®ang xÐt) ký tù ®Çu tiªn cña p. - Khi x¸c ®Þnh next [j] viÖc di chuyªn p1 qua ph¶i dõng l¹i khi ph¸t hiÖn c¸c ký tù ®i tr­íc cña chuçi p1 trïng víi c¸c ký tù cña chuçi p hoÆc khi p1[1]=p[j]. - Khi xác định next[j] việc di chuyển chuỗi p1 qua phải sẽ dừng lại khi phát hiện các kí tự đi trước của chuỗi p1 bằng với các kí tự của chuỗi p hoặc khi p1[1] gặp p[j]. b. Giải thuật : program Knuth_Morris_Pratt; uses crt; type st=string[50]; Index=1..50; var a,p:st;{a chứa chuỗi nguồn, p là chuỗi đích;n là độ dài của a;m la độ dài của p} Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 8 procedure init; var i,j:integer; begin writeln('Nhập chuỗi a:'); readln(a); writeln('Nhập chuỗi p:'); readln(p); end; procedure Result; begin writeln('Chuỗi cần tìm là:',p); end; Function Kmsearch(p,a:st):integer; var i,j,m,n:integer; next:array[index]of integer; procedure Initnext; begin i:=1; j:=0; next[1]:=0; repeat if(j=0)or(p[i]=p[j])then begin i:=i+1; j:=j+1; next[i]:=j; end; else j:=next[j]; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 9 until i=m; end; begin m:=length(p); n:=length(a); {Tạo mảng next} Initnext; i:=1; j:=1; repeat if (j=0) or (a[i]=p[j]) then begin i:=i+1; j:=j+1; end; else begin j:=next[j]; end; until(j>m)or (i>n); if j>m then Kmsearch:=i-m else Kmsearch:=0; end; begin clrscr; Init; Kmsearch(a,p); write('Vị trí của ký tự đầu của chuỗi p trong a là:',Kmsearch(p,a):2); writeln; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 10 Result; readln; end. c. Ví dụ cụ thể Cho chuỗi a : 101'01.0'011'1 i =10 p : 101'00.1'11 j =8 Các bước sẽ được thể hiện trong bảng sau : j next[j] chuỗi 2 1 101’001’11 (p) 101’001’11 (p1) 3 1 101’001’11 101’001’11 4 2 101’001’11 101’001’11 5 3 101’001’11 1 01’001’11 6 1 101’001’11 1 01’001’11 7 2 101’001’11 1 01’001’11 8 101’001’11 101’001’11 Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 11 Số lần so sánh Cmax=n+m. Ta thấy số lần so sánh đã giảm đi nhiều lần. 2.3. Giải thuật Boyer –Moore a. Nội dung giải thuật: - Giải thuật Boyer-Moore tương tự với giải thuật Knuth-Morris-Pratt. Đối với giải thuật Boyer, ta xét chuỗi p1 từ phải qua trái trong khi ta so sánh chuỗi p với chuỗi a. Cách xây dựng mảng next của giải thuật Boyer-Moore là phần tử next[j] là số vị trí kí tự mà chuỗi p sẽ di chuyển qua phải đối với chuỗi p1 để có được vị trí khác nhau ở kí tự thứ j kể từ phải qua trái của chuỗi p. b. Giải thuật: Để xác định vị trí mới của j khi có sự so sánh trùng nhau ta dùng mảng skip. Hàm Function Ord(c:char):integer trả về số thứ tự của ký tự c trong bộ ký tự (đánh số từ 1). Khi đó skip[c]=m nếu c không phải là một ký tự của chuỗi p skip[c]=m-j nếu c là kí tự thứ j của chuỗi p. Ta có giải thuật : Program Boyer-Moore; Use crt; Type St=string[50]; Const Charno=255; procedure init; begin writeln(‘ hay nhap chuoi a:’); readln(a); writeln(‘nhap chuoi p:’); readln(p); end; procedure result; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 12 begin writeln(‘chuoi can tim la:’,p); end; Function Bmsearch (p,a:st):integer; Var i,j,m,n:integer; skip :array[1..charno]of interger; procedure Initskip; var i:1..charno; j:integer; begin for i:=1 to charno do skip[i]=m; for j:=1 to m do if skip[ord(p[j])]=m then skip[ord(p[j])]=m-j; end; begin m:=length(p); n:=length(a); initskip; i:=m; j:=m; repeat if a[i]=p[j] then begin i:=i-1; j:=j-1; end; begin if m-j+1>skip[ord(a[i])] then i:=i+m-j+1 else i:=i+skip[ord(a[i])]; j:=m; end; until (jn); if j<1 then Bmsearch:=i+1;{tim thay} else Bmsearch:=0; end; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 13 begin clrscr; init; bmsearch(a,p); write(‘vi tri cua ky tu dau cua chuoi p trong a la :’,bmsearch(p,a):2) ; writeln ; result ; readln ; end. c. Phân tích giải thuật Số lần so sánh : Cmax=m+n Số bước thực hiện trong trường hợp bộ ký tự không nhỏ và chuỗi p không lớn là: S=n/m {$M $4000,0,0} Program Bai_tap_tren_xau; uses crt; type m= array [1..9] of string; const menu:m=(' 1. Dao nguoc xau ',' 2. Tinh chieu dai cua xau',' 3. Chi so cua xau',' 4. Lay xau ky tu con', ' 5. In xau khong de quy',' 6. In xau de quy',' 7. Bai 5.2',' 8. Bai 5.5',' 9. Thoat'); type infor=char; ref=^elemen; elemen=record info:infor; link:ref; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 14 end; var first:ref; const max=1000; type stacks=record index:integer; data:array[1..max] of integer; End; stackc=record index:integer; data:array[1..max] of char; end; stackR=record index:integer; data:array[1..max] of real; End; var step:integer; d,g:ref; ch1,h,c1:char; i1,n,f,e,b1,b2:integer; i:integer; s:string; stack:stackc; kt:boolean; t:real; nu,r: integer; stack1:stacks; {---------------------------------------------------------} Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 15 function themdau(var first:ref;NewInfo:Infor):ref; var p:ref; begin new(p); p^.info:=NewInfo; p^.link:=first; first:=p; themdau:=p; end; {--------------------------------------------------------} function themcuoi(var q:ref;NewInfo:Infor):ref; var p,scan:ref; begin New(p); p^.Info:=NewInfo; p^.link:=nil; if q = nil then q:=p else Begin scan:=q; while scan^.linknil do scan:=scan^.link; scan^.link:=p; End; themcuoi:=p; end; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 16 {--------------------------------------------------------} procedure xoadau(var first:ref); var p:ref; begin if firstnil then begin p:=first; first:=p^.link; dispose(p); end; end; {-----------------------------------------------------} procedure xoacuoi(var first:ref); var p,q:ref; begin q:=first; p:=q^.link; if(first=nil)then exit; if(p=nil)then begin dispose(q); first:=nil; end else begin while(p^.linknil) do Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 17 begin p:=p^.link; q:=q^.link; end; dispose(p); q^.link:=nil; end; end; {----------------------------------------------------------} procedure inra(first:ref); var p:ref; begin p:=first; while(pnil) do begin write(p^.info); p:=p^.link; end; end; {---------------------------------------------------------} procedure dao(var first:ref); var a,b,c:ref; begin if(first=nil) then exit else if (first^.link=nil) then Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 18 exit else a:=nil; b:=first; c:=first^.link; while(cnil) do begin b^.link:=a; a:=b; b:=c; c:=c^.link; end; b^.link:=a; first:=b; end; {-----------------------------------------------------------} function chieudai(first:ref):integer; var dem:integer; p:ref; begin p:=first; dem:=0; while(pnil) do begin p:=p^.link; dem:=dem+1; end; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 19 chieudai:=dem; end; {-----------------------------------------------------------} function chiso(first:ref;d:integer):infor; var p:ref; dem:integer; begin p:=first; dem:=1; while(demnil) do begin p:=p^.link; inc(dem); end; if(p=nil) then chiso:=#0 else chiso:=p^.info; end; {-------------------------------------------------------------} function xaukitucon(var first:ref;p,n:integer):ref; var i,dem:integer; daumoi,duoimoi,temp,q:ref; begin dem:=1; q:=first; while(demnil)do Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 20 begin q:=q^.link; inc(dem); end; if(q=nil) then begin xaukitucon:=nil; exit; end; new(daumoi); daumoi^.info:=q^.info; duoimoi:=daumoi; for i:=2 to n do begin q:=q^.link; if(qnil) then begin new(temp); temp^.info:=q^.info; duoimoi^.link:=temp; duoimoi:=temp; end else break; end; duoimoi^.link:=nil; xaukitucon:=daumoi; end; {------------------------------------------------------------} Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 21 procedure inxau(first:ref); {khong de quy} var p:ref; begin p:=first; while(pnil) do begin write(p^.info); p:=p^.link; end; end; {----------------------------------------------------------} procedure inxaudq(first:ref); var p:ref; begin p:=first; if(first=nil) then exit else begin write(p^.info); inxaudq(p^.link); end; end; {-----------------------------------------------------} procedure writestacks(stack:stacks); var i:integer; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 22 begin for i:=0 to stack.index do write(stack.data[i]); end; {--------------------------------------------------------} procedure lnits(var stack:stacks); begin stack.index:=0; end; {---------------------------------------------------------} function emptys(var stack:stacks):boolean; begin if stack.index=0 then emptys:=true else emptys:=false; end; {-------------------------------------------------------------} function Pushs(var stack:stacks;dt:integer):boolean; Begin if stack.index=max+1 then pushs:=false else Begin inc(stack.index); pushs:=true; stack.data[stack.index]:=dt; end; End; {--------------------------------------------------------} function pops(var stack:stacks;var dt:integer):boolean; begin Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 23 if stack.index=0 then pops:=false else begin pops:=true; dt:=stack.data[stack.index]; dec(stack.index); end; end; {-----------------------------------------------------------} Procedure WriteStack(stack:stackc); var i:integer; Begin For i:=0 to stack.index do write(stack.data[i]); End; {-------------------------------------------------------------} procedure WriteState(ch:char;P:string; stack:stackc); Begin inc(step); write(step:3,' '); write(ch:5); write(p:20);{Hien thi tung buoc} write(' '); writestack(stack);{Hien thi tung buoc} writeln; if step mod 23=0 then Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 24 Begin write('Press enter to continue...'); readln; end; End; {-----------------------------------------------------------} Function Priority(Token:char):integer; Begin case Token of '(',')': Priority:=0; '-','+': Priority:=1; '*','/': Priority:=2; '^': Priority:=3; End; End; {-------------------------------------------------------------} Procedure Init(var stack:stackc); Begin stack.index:=0; End; {-------------------------------------------------------------} Procedure InitR(var stack:stackR); Begin stack.index:=0; End; {--------------------------------------------------------------} function TheTop(var stack:stackc):char; Begin if stack.index=0 then Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 25 TheTop:=#0 else TheTop:=stack.data[stack.index]; End; {-------------------------------------------------------------} function Empty(var stack:stackc):boolean; Begin if stack.index=0 then Empty:=true else Empty:=false; End; {--------------------------------------------------------------} function EmptyR(var stack:stackR):boolean; Begin if stack.index=0 then EmptyR:=true else EmptyR:=false; End; {--------------------------------------------------------------} function Push(var stack:stackc;dt:char):boolean; Begin if stack.index=max+1 then push:=false else Begin inc(stack.index); push:=true; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 26 stack.data[stack.index]:=dt; end; End; {---------------------------------------------------------------} function PushR(var stack:stackR;dt:Real):boolean; Begin if stack.index=max+1 then pushR:=false else Begin inc(stack.index); pushR:=true; stack.data[stack.index]:=dt; end; End; {--------------------------------------------------------} function Pop(var stack:stackc;var dt:char):boolean; Begin if stack.index=0 then Pop:=false else Begin Pop:=True; dt:=stack.data[stack.index]; dec(stack.index); End; End; {---------------------------------------------------------} function PopR(var stack:stackR;var dt:Real):boolean; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 27 Begin if stack.index=0 then PopR:=false else Begin PopR:=True; dt:=stack.data[stack.index]; dec(stack.index); End; End; {----------------------------------------------------------} function DeleteBlank(s:string):string; var i,j:integer; Begin j:=0; i:=1; while i<=length(s) do Begin if s[i]' ' then Begin inc(j); s[j]:=s[i]; End; inc(i); End; delete(s,j+1,length(s)-j); DeleteBlank:=s; End; {-------------------------------------------------------} Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 28 function Polish(s:string; var p:string) :boolean; var i,j:integer; stack:stackc; ch:char; Begin Polish:=true; s:=DeleteBlank(s); s:=s+')'; init(stack); push(stack,'('); i:=1; p:=''; while not Empty(stack) do Begin if upcase(s[i]) in ['A'..'Z'] then Begin p:=p+upcase(s[i]); WriteState(s[i],p,stack); end else Begin if s[i]='(' then Begin Push(stack,s[i]); WriteState(s[i],p,stack); End else if s[i] =')' then Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 29 Begin pop(stack,ch); while ch'(' do Begin p:=p+ch; pop(stack,ch); End; WriteState(s[i],p,stack); End else if s[i] in ['-','+','/','*','^'] then Begin{Coi nhu la phep tinh} while (Priority(TheTop(stack))>=Priority(s[i])) do Begin pop(stack,ch); p:=p+ch; End; push(stack,s[i]); WriteState(s[i],p,stack); End else Begin Polish:=false; exit; End; End; inc(i); End; End; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 30 {---------------------------------------------------------} function Value(s:string;var outValue:real):boolean; {------------------} function Add(a,b:real):real; Begin Add:=a+b; End; {------------------} Function Sub(a,b:real):real; Begin Sub:=a-b; End; {------------------} Function Mul(a,b:real):real; Begin Mul:=a*b; End; {------------------} Function Divi(a,b:real; var c:real):boolean; Begin if b=0 then Divi:=false else Begin Divi:=true; c:=a/b; End; End; {-------------------} Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 31 Function expl(a,b:real;Var c:real):boolean; var temp:real; Begin if a<=0 then expl:=false else Begin expl:=true; c:=exp(b*ln(a)); End; End; {--------------------} type values=record exist:boolean; value:real; end; var temp,temp2,t:real; a:array['A'..'Z'] of values; i:integer; ch:char; stack:stackR; Check:boolean; {Main of value} Begin For ch:='A' to 'Z' do a[ch].exist:=false; for i:=1 to length(s) do if s[i] in ['A'..'Z'] then a[s[i]].exist:=true; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 32 for Ch:= 'A' to 'Z' do if a[ch].exist= true then Begin write('Nhap gia tri cho bien ',ch,':'); readln(a[ch].value); End; s:=s+')'; i:=1; initR(stack); while(s[i]')') do Begin if upcase(s[i]) in ['A'..'Z'] then Begin pushR(stack,a[s[i]].Value); End; if s[i] in ['-','+','/','*','^'] then Begin popR(stack,temp); popR(stack,temp2); Check:=true; case s[i] of '-':t:=Sub(temp,temp2); '+':t:=Add(temp,temp2); '*':t:=mul(temp,temp2); '/':check:=divi(temp,temp2,t); '^':check:=expl(temp,temp2,t); end; if check=false then Begin Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 33 value:=false; exit; end else Begin pushR(stack,t); End; End; inc(i); End; Value:=true; popR(stack,outValue); End; {--------------------------------------------------------------} Procedure mahoa( var s:string; dd:integer); var i:integer; begin for i:=1 to dd-length(s) do s:=s+' '; end; {----------------------------------------------------------------} Procedure taonen; {tao nen} var i:integer; begin textbackground(15); for i:=1 to 50 do Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 34 writeln('±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±±± ±±±±±±±±±±±±±±±±±±±±±±±±±±±'); end; {----------------------------------------------------------------} Procedure thoat; var ch:char; begin textbackground(4); textcolor(14); gotoxy(21,6); write('ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿'); gotoxy(21,7); write('³ Ban co muon thoat khong (C/K) ? ³'); gotoxy(21,8); write('ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ'); repeat ch:=readkey; case upcase(ch) of 'C' : begin textbackground(0);textcolor(7);clrscr;halt;end; 'K' : exit; end; until (upcase(ch)='C')or(upcase(ch)='K'); end; {----------------------------------------------------------------} Procedure dohoa; {tao do hoa va thuc don} var i2,t1:integer; ch:char; begin Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 35 textbackground(9); textcolor(15); gotoxy(25,3);write('ÉÍÍÍÍÍÍÍÍÍÍÍÍThuc donÍÍÍÍÍÍÍÍÍÍÍÍ»'); for i:=1 to 9 do begin mahoa(menu[i],32); gotoxy(25,3+i);write('º',menu[i],'º'); end; gotoxy(25,4+i);write('ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ'); t1:=1; textbackground(4); textcolor(14); gotoxy(26,4);write(menu[1]); repeat ch:=readkey; case ch of #80 : begin textbackground(9); textcolor(15); gotoxy(26,3+t1); write(menu[t1]); if t1=9 then t1:=1 else t1:=t1+1; textbackground(4); textcolor(14); gotoxy(26,3+t1); write(menu[t1]); Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 36 end; #72 : begin textbackground(9); textcolor(15); gotoxy(26,3+t1); write(menu[t1]); if t1=1 then t1:=9 else t1:=t1-1; textbackground(4); textcolor(14); gotoxy(26,3+t1); write(menu[t1]); end; #13 : begin case t1 of 1 :Begin clrscr; writeln(' Thu tuc dao nguoc chuoi'); writeln; write('Nhap so phan tu cua xau:'); readln(n); writeln; for i:=1 to n do Begin write('Nhap ky tu thu ',i,':'); readln(h); themcuoi(first,h); End; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 37 writeln; write('Chuoi sau khi nhap vao:'); inxau(first); dao(first); writeln; writeln; write('Chuoi sau khi duoc dao nguoc:'); inxau(first); readln; while firstnil do xoacuoi(first); dohoa; End; 2 :Begin clrscr; writeln(' Thu tuc dem so phan tu trong xau'); writeln; write('Nhap vao mot xau bat ky :'); repeat ch:=readkey; Begin write('',ch); themcuoi(first,h); End; until ch=#13; writeln; writeln; f:=chieudai(first); Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 38 writeln; write('chieu dai xau tren la :',f-1); writeln; readln; while firstnil do xoacuoi(first); dohoa; End; 3 :Begin clrscr; writeln(' Thu tuc lay chi so cua xau'); writeln; write('Nhap so phan tu cua xau:'); readln(n); writeln; write('nhap vi tri can lay:'); readln(e); writeln; for i:=1 to n do Begin write('Nhap ky tu thu ',i,':'); readln(h); themcuoi(first,h); End; writeln; write('Chuoi sau khi nhap vao:'); inxau(first); writeln; Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 39 c1:=chiso(first,e); writeln; write('ki tu duoc lay la:',c1); readln; while firstnil do xoacuoi(first); dohoa; End; 4 :Begin clrscr; writeln(' Thu tuc lay xau ky tu con'); writeln; write('Nhap so phan tu cua xau:'); readln(n); writeln; write('nhap vi tri bat dau lay:'); readln(b1); writeln; write('nhap so ki tu can lay:'); readln(b2); writeln; for i:=1 to n do Begin write('Nhap ky tu thu ',i,':'); readln(h); themcuoi(first,h); End; writeln; write('Chuoi sau khi nhap vao:'); inxau(first); Vâ Minh Phæ – Bæ m«n Khoa häc m¸y tÝnh 40 writeln; g:=xaukitucon(first,b1,b2)