Mot So Bai Tap Ve Xau - Tài Liệu Text - 123doc

Tải bản đầy đủ (.doc) (20 trang)

1. Trang chủ
>>
2. Công Nghệ Thông Tin
>>
3. Kỹ thuật lập trình

Mot so bai tap ve xau

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 (192.26 KB, 20 trang )

MỘT SỐ KIẾN THỨC LÝ THUYẾTĐể xử lý các chuỗi văn bản, Pascal đưa ra một kiểu dữ liệu mới gọi là xâu kýtự và được định nghĩa bằng từ khóa STRING. Xâu ký tự là dữ liệu bao gồm một dãycác ký tự trong bảng mã ASSCII. Tuy nhiên độ dài của String tối đa chỉ 255 mà thựctế thì ta thường gặp xâu có độ dài rất lớn cỡ hàng ngàn, vậy có cách nào để có thểkhắc phục được điều đó, chúng tôi xin trình bày một số nội dung mà chúng tôi đã tìmhiểu và vận dụng có hiệu quả trong quá trình giảng dạy và bồi dưỡng đội tuyển.I. 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á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ư:+ 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, tasử 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ênbiế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 =, >, st23. 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ự stVí dụ: st:=’tin hoc’ thì LENGTH(st) cho bằng 7.b. Hàm upcase(ch): Cho ký tự hoa của ký tự chVí 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ìnhvar s,s1:string; i:integer;beginwrite('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ã ASCIIVí dụ: ch:='a'; n:= Ord(ch) → n= 97d. Hàm Chr(n): Cho ký tự có mã là nVí 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ườngtrướ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;beginwrite('nhap xau s:');readln(s);s1:='';for i:=1 to length(s) doif 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í posVí 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’) = 1Ví 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);- Để 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;beginwrite('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 saucủ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ệnmộ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;beginwrite('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ểusố(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ếnvalue, 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ôngVí dụ: VAL(‘2014’,value,code) lúc này code sẽ nhận giá trị bằng 0 vàvalue=2014Ví 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 rasố 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;beginwrite('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âus1,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ếtquả 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êntrong 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;beginwrite('nhap xau s:');readln(s);while pos(#32,s)0 dobeginif pos(#32,s)>length(tumax) thentumax:=copy(s,1,pos(#32,s));delete(s,1,pos(#32,s));end;writeln(tumax);readln;end.III. CÁC DẠNG BÀI TẬP THƯỜNG GẶP1. Dạng 1. Xử lý số nguyên lớnPhương pháp chung: Để thực hiện các phép tính hoặc xử lý với số nguyênngoà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ớnCho 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ằngcá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áicủ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;beginwhile length(s1)=s2 then sub:=sub1(s1,s2)else sub:='-'+sub1(s2,s1);end;MỘT SỐ BÀI TẬP VẬN DỤNGBài 1: Sửa xâuViết chương trình nhập vào từ bàn phím một xâu kí tự, trong đó nếu tính từ trái sangphải thì kí tự # là dấu hiệu xoá đi một kí tự đứng ngay trước nó nếu có. Sau đó in ra xâu đãsửa chữa theo đúng quy định.Ví dụ: Ta#oi thi hoc sinua#h###nh gioi tin hoj#c có nghĩa là ‘Toi thi hoc sinh gioi tinhoc’Dữ liệu vào: Tệp Suaxau.inp chứa xâu kí tự cần sửaDữ liệu ra: Tệp Suaxau.out chứa xâu đã sửa.Bài 2: Cho một xâu ký tự gồm các chữ cái. Hãy viết chương trình đưa ra màn hình xâucon gồm các kí tự khác nhau dài nhất.Ví dụ: cho xâu S='abacbcdaebcf'.Kết quả: S='abcdef'Bài 3. Cho hai xâu nhị phân độ dài n cho trước S1, S2. Hãy viết chương trình biến đổixâu S1 thành S2. Các phép biến đổi phải được hiện rõ trên màn hình. Ví dụ với S1='0101'và S2='1100' thì kết quả sẽ thể hiện như sau:Vị trí 1: số 0 --> 1Vị trí 4: số 1 --> 0Bài 4: Cho nhập vào 1 xâu S gồm các kí tự. Hãy lập trình đưa ra màn hình mảng cáccụm kí tự số.Ví dụ: s=’ab123c45deg891’Kết quả của mảng:123 45 891Bài 5: Cho xâu kí tự S1='TIN HOC' và xâu kí tự S2 bất kỳ. Viết chương trình cho biếtxâu S1 có xuất hiện trong xâu S2 hay không. Nếu có thì xâu S1 xuất hiện trong xâu S2 baonhiêu lần?Ví dụ: S2='TIN HOC abc Tin hoc sds TIN HOC'.Kết quả: S1 xuất hiện trong S2 là 2 lầnBài 6: Biến đổi xâuCho trước một xâu nhị phân độ dài bất kỳ được đưa vào từ file văn bản INPUT.TXT.Cần biến đổi xâu nhị phân này về dạng toàn số 0. Các phép biến đổi có thể chỉ là một trongcác loại sau:Biến đổi xâu con 11 thành 00Biến đổi xâu con 010 thành 000Hãy chỉ ra một cách biến đổi xâu đã cho thành xâu toàn số 0. Kết quả thể hiện trongfile OUTPUT.TXT như sau:Dòng đầu tiên của OUTPUT.TXT chứa xâu ban đầu, sau đó mỗi dòng là 1 xâu tiếp theosau một phép biến đổi, xâu cuối cùng là xâu toàn số 0.Ví dụ:INPUT.TXTOUTPUT.TXT1101001111010011110100000001000000000000INPUT.TXTOUTPUT.TXT10101101Khong the bien doi duocBài 7: Sắp số trong xâuNhập 1 xâu s bao gồm số và kí tự, in ra xâu đã sắp xếp số theo thứ tự tăng dần còn vị trícác kí tự vẫn giữ nguyên.Bài 8. Cho trước hai xâu ký tự S1, S2. Viết chương trình tìm một xâu con chung cực đạigồm các phần tử liên tiếp của hai xâu trên.Bài 9: Xâu kí tựCó không quá 1000 chiến sỹ công an tham gia trong một chiến dịch truy quét tội phạmở tỉnh X. Các chiến sỹ công an được chia thành không quá 26 đội. Để dễ điều hành, bộ chỉhuy chiến dịch quy định ký hiệu cho mỗi đội là một chữ cái in thường nằm trong khoảng từ‘a’ đến ‘z’. Hai đội khác nhau thì có 2 kí hiệu khác nhau. Các chiến sỹ công an thuộc độinào thì được gắn một ký hiệu của đội đó. Nếu lấy ký hiệu đã gắn cho tất cả các chiến sỹcông an tham gia chiến dịch ghép lại thì được một xâu ký tự.Hãy xác định số lượng các chiến sỹ công an trong mỗi đội.Dữ liệu vào: là tệp văn bản XAU.INP chứa một xâu kí tự là kết quả của việc ghép kýhiệu đã gắn cho tất cả các chiến sỹ công an tham gia chiến dịch.Dữ liệu ra: là tệp văn bản XAU.OUT có không quá 26 dòng, mỗi dòng ghi ký hiệu cuảmỗi đội và số lượng thành viên cuả đội đó.Ví dụ:XAU.INPXAU.OUTabcada2b1c1d1Bài 10: Robot công nghiệp (Bài 1 HSG11 năm học 2011-2012)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 hiện đồng thờitrê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 Robotthự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ứ 2. Để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