Rút Gọn Xâu Có Các Kí Tự Trùng??? [Archive] - Diễn Đàn Tin Học

Diễn Đàn Tin Học > Lập trình > Các ngôn ngữ lập trình > Pascal/Delphi/Kylix > Rút gọn xâu có các kí tự trùng??? PDA

View Full Version : Rút gọn xâu có các kí tự trùng???

onelove2702-01-2007, 01:39---Em viết một hàm lọc bỏ các kí tự trùng trong xâu. ---Ví dụ: '1231123412344613' => '12346' hoặc '46321''26413'... ---Code: ************************************** {xâu: s} for i:=1 to length(s) do begin for j:=i+1 to length(s) do begin if s[i]=s[j] then delete(s,j,1); end; end; ************************************** ---Sai ở chỗ khi xóa đi một kí tự trong xâu thì các kí tự sau đó bị đẩy lên đầu 1 vị trí dẫn đến lần lặp kế tiếp sẽ bỏ qua phần tử chưa được xét (vì nó đã nằm ở vị trí của phần tử đã bị xoá). ---Xin các anh chỉ dùm em cách rút gọn hay hơn hoặc cách giải quết cho trường hợp trên! Master_Baby02-01-2007, 09:12Đơn giản là đừng có xài for ở vòng lặp trong nữa. Xài repeat hay while là ổn: nếu có thực hiện xóa thì ko tăng biến đếm, còn nếu ko thực hiện thì tăng biến đếm lên. Dừng khi biến đếm > độ dài xâu hiện tại. Đại loại như vầy: For .... Begin    j:=1;    Repeat       If st[i]=st[j]       Begin         {xóa}       End       else j:=j+1;    Until (i>length(st)); End; condecodon200302-01-2007, 11:23Dùng 1 mảng 0..255 để đánh dấu, chỉ mất 1 vòng for onelove2702-01-2007, 11:44chưa thử nhưng thank các bác nhiều, nghe chừng chắc là ổn onelove2702-01-2007, 18:58************************************** for i:=1 to length(s) do begin j:=i+1; repeat if s[i]=s[j] then delete(s,j,1) else j:=j+1; until (j>length(s)); end; ************************************** tôi nghĩ như vậy chuẩn hơn condecodon200303-01-2007, 01:48Vậy vẫn là O(n^2) rồi bạn ạ. Còn 1 điều khá quan trọng mà các bạn ko để ý đến đó là nếu xóa xâu đi thì độ dài xâu sẽ giảm đi, vì vậy mà ko được dùng for i:=1 to length(s) mà phải for downto Master_Baby03-01-2007, 09:12Vậy thì xài nốt repeat cho vòng ngoài. Mà sếp condecodon bảo 1 vòng for là làm thía nào cơ??? Chỉ đi sếp! pineflower03-01-2007, 14:38Dùng 1 mảng 0..255 để đánh dấu, chỉ mất 1 vòng for Tôi chưa hiểu bạn đánh dấu kiểu gì, nhưng bài này đâu cần phải đánh dấu. s1 := s[1]; for i := 2 to length(s) do if (s[i] <> s[i - 1) then s1 := s1 + s[i]; kết quả : s1. Còn nếu không thích dùng thêm xâu khác có thể vừa for vừa ghi trực tiếp ra. :) condecodon200303-01-2007, 17:21Đây là code mọi người có thể xem thử uses crt; var s : string; a : array[0..255] of boolean; i : integer; begin clrscr; write('Input A String:'); readln(s); fillchar(a,sizeof(a),false); for i := length(s) downto 1 do if a[ord(s[i])] then delete(s,i,1) else a[ord(s[i])] := true; writeln(s); readln; end. pineflower03-01-2007, 19:09Đây là code mọi người có thể xem thử uses crt; var s : string; a : array[0..255] of boolean; i : integer; begin clrscr; write('Input A String:'); readln(s); fillchar(a,sizeof(a),false); for i := length(s) downto 1 do if a[ord(s[i])] then delete(s,i,1) else a[ord(s[i])] := true; writeln(s); readln; end. Bạn làm như thế này bị sai rồi. Bạn đã chạy thử chưa thế : Như thế này sẽ chỉ còn giữ lại mỗi ký tự 1 lần xuất hiện thôi. Ví dụ S = aabaa lẽ ra sau khi rút gọn phải là aba nhưng theo cách của bạn sẽ chỉ còn lại ba. Tư tưởng for downto là đúng nhưng trong khi lập trình tối kị không được để 2 cận trong vòng lặp bị thay đổi. Mặc dù trong những trường hợp đơn giản thì có thể nhận thấy chương trình làm việc như thế nào, nhưng giả sử đang làm trong 1 project lớn, nhiều modun chương trình thì sẽ rất khó kiểm soát. ^ ^ condecodon200304-01-2007, 00:04Thì đây là loại bỏ các kí tự trùng, mỗi kí tự chỉ còn xuất hiện 1 lần thôi mà. Theo bạn sẽ phải viết như thế nào :-/ thuonghcm04-01-2007, 17:50tôi không nghĩ như bạn pineflower , nếu s:='aabaa'; thì KQ=aba mà là s sẽ là s:='ab';hay s:='ba';là đúng theo lời tác giả đấy. thuonghcm04-01-2007, 18:08hay lắm , condecodon2003 thật là tài, cách làm ngắn gọn, súc tích quá chừng luôn.Nếu có thể, conde hãy giúp tôi 1 số bài đã pposst trước đây đi? cảm ơn nhiều nhé. pineflower04-01-2007, 20:15Thì đây là loại bỏ các kí tự trùng, mỗi kí tự chỉ còn xuất hiện 1 lần thôi mà. Theo bạn sẽ phải viết như thế nào :-/ Mình xin lỗi nhé. Mình chưa đọc kỹ đề bài. Nếu đề là như thế thì Làm như bạn là đúng. Nhưng mình vẫn muốn nói là không nên thay đổi cận trong vòng lặp for. Mình xin lỗi một lần nữa ^ ^ condecodon200304-01-2007, 22:20Mình xin lỗi nhé. Mình chưa đọc kỹ đề bài. Nếu đề là như thế thì Làm như bạn là đúng. Nhưng mình vẫn muốn nói là không nên thay đổi cận trong vòng lặp for. Mình xin lỗi một lần nữa ^ ^ Sẽ chiều theo ý của bạn, nếu ko muốn thay đổi cận trong vòng lặp thì có thể sửa lại 1 chút uses crt; var s : string; a : array[0..255] of boolean; i : integer; begin clrscr; write('Input A String:'); readln(s); fillchar(a,sizeof(a),false); for i := length(s) downto 1 do a[ord(s[i])] := true; s := ""; for i := 0 to 255 do if a[i] then s := s + chr(a[i]); writeln(s); readln; end. Theo mình cái quan trọng ko fai là có nên thay đổi cận trong vòng lặp hay ko, mà quan trọng là người lập trình kiểm soát được nó và chắc chắn nó đúng thuonghcm05-01-2007, 12:50hoàn toàn chính xác ,,, hỏng biết là con dê cô đơn hay là con dế cô đơn mà tài quá nguyenhonghanh05-01-2007, 22:42to condecodon2003: anh ui, anh chạy thử code đó của anh chưa ạ ? hình như nó ko chạy được mà em thử viết cái này, các anh xem được ko nha .hì hì uses crt; var x: string; i,j: integer; begin clrscr; writeln('nhap xau:');readln(x); For i:=1 to length(x) do for j:=i+1 to length(x) do begin If x[j]=x[i] then delete(x,j,1); end; writeln('ket qua:',x); readln; end. thuonghcm06-01-2007, 09:13Nhập mảng n=100 phần tử. In "cái tổng" chung nhất "không thừa , không thiếu" mà cái mảng kia đem lại. VD: n=7 và nhập vào: 1 2 3 4 5 3 6 Vậy lúc này KQ=6 vì : khi Sử dụng hết mảng thì: ta có: 5+1=6;6=6;2+4=6;3+3=6 uh....... tức là mảng đã dùng hết, KQ chung của nó là =6 (có 4 trường hợp) CÁm ơn các bác đã đọc đề .Có bác nào có YK ? nguyenhonghanh06-01-2007, 18:14anh ơi, anh xem em làm được chưa nha. uses crt; var i,j,n: integer; a: array[1..100]of integer; begin clrscr; writeln('nhap n:');readln(n); For i:=1 to n do begin writeln('a[',i,']:');readln(a[i]); end; For i:=1 to n do for j:=i+1 to n do begin if a[i]+a[j]=54 then writeln(a[i],'+',a[j]); end; readln; end. onelove2706-01-2007, 18:55to condecodon2003: anh ui, anh chạy thử code đó của anh chưa ạ ? hình như nó ko chạy được mà em thử viết cái này, các anh xem được ko nha .hì hì uses crt; var x: string; i,j: integer; begin clrscr; writeln('nhap xau:');readln(x); For i:=1 to length(x) do for j:=i+1 to length(x) do begin If x[j]=x[i] then delete(x,j,1); end; writeln('ket qua:',x); readln; end. ---bạn ơi như vậy thì tôi hỏi làm gì. Ngay ở đề bài hỏi tôi đã chỉ ra lỗi sai của nó rồi mà. ---cách chữa của mấy bạn bên dưới mới ngon onelove2706-01-2007, 18:59---à xin lỗi mọi người lúc gửi bài tôi nhầm đề bài chút nhẽ ra '1231123412344613' => '12346' hoặc '46321''26413'... thì tôi lại post '1231123412344613' => '123' hoặc '321''213'... may mọi người vẫn hiểu ---nhưng bây giờ đã sửa. condecodon200308-01-2007, 16:04hoàn toàn chính xác ,,, hỏng biết là con dê cô đơn hay là con dế cô đơn mà tài quá Là con dê bác ạ ;)) condecodon200308-01-2007, 16:14to condecodon2003: anh ui, anh chạy thử code đó của anh chưa ạ ? hình như nó ko chạy được mà em thử viết cái này, các anh xem được ko nha .hì hì uses crt; var x: string; i,j: integer; begin clrscr; writeln('nhap xau:');readln(x); For i:=1 to length(x) do for j:=i+1 to length(x) do begin If x[j]=x[i] then delete(x,j,1); end; writeln('ket qua:',x); readln; end. Code của bạn nhiều lỗi lắm, thử với x = aaaaaaaaaaaaaaaaaa đi condecodon200308-01-2007, 16:18anh ơi, anh xem em làm được chưa nha. uses crt; var i,j,n: integer; a: array[1..100]of integer; begin clrscr; writeln('nhap n:');readln(n); For i:=1 to n do begin writeln('a[',i,']:');readln(a[i]); end; For i:=1 to n do for j:=i+1 to n do begin if a[i]+a[j]=54 then writeln(a[i],'+',a[j]); end; readln; end. Của bạn chỉ tìm được các cặp 2 số có tổng = 54 thôi :-p thuonghcm09-01-2007, 18:54Nhập mảng n=100 phần tử. In "cái tổng" chung nhất "không thừa , không thiếu" mà cái mảng kia đem lại. VD: n=7 và nhập vào: 1 2 3 4 5 3 6 Vậy lúc này KQ=6 vì : khi Sử dụng hết mảng thì: ta có: 5+1=6;6=6;2+4=6;3+3=6 uh....... tức là mảng đã dùng hết, KQ chung của nó là =6 (có 4 trường hợp) CÁm ơn các bác đã đọc đề .Có bác nào có YK ? thuonghcm10-01-2007, 17:55bài giải của HONGHANH đúng là chỉ có 2 phần tử của mảng có tổng = 54 thôi, --> chưa đạt Y/c VD : tôi có mảng:........a[5]=4; a[12]=20;a[19]=30; ..... thì code của bạn tiu rồi. onelove2710-01-2007, 21:27Vậy vẫn là O(n^2) rồi bạn ạ. Còn 1 điều khá quan trọng mà các bạn ko để ý đến đó là nếu xóa xâu đi thì độ dài xâu sẽ giảm đi, vì vậy mà ko được dùng for i:=1 to length(s) mà phải for downto - Tôi đồng ý là nếu vòng lặp thứ 2 của tôi mà dùng For là sai. - Việc sai này tôi đã chỉ ra ngay từ đầu bài hỏi. - Nhưng việc dùng For ..downto ..là không cần thiết. Vì việc so sánh kí tự ở vị trí n chỉ sẩy ra với các kí tự từ vị trí thứ n+1. Khác hẳn vòng lặp thứ 2 vì vòng thứ 2 này sẽ xóa ngay kí tự tại điểm đang xét dẫn đến khi tăng lên 1 sẽ bỏ qua kí tự vừa bị đẩy lên đầu. Không tin bạn thử chạy đoạn code tôi đã sửa xem đảm bảo đúng. - À bạn tiện thể giải thích hộ tôi cái code viết khá gọn của bạn không. Có một số tôi chưa được học qua. Cảm ơn bạn đã đóng góp ý kiến! condecodon200310-01-2007, 23:06- À bạn tiện thể giải thích hộ tôi cái code viết khá gọn của bạn không. Có một số tôi chưa được học qua. Cam ơn bạn đã đóng góp ý kiến! Cái này ko fai là 1 cái gì mà phải học cả bạn ạ, nó chỉ là 1 mẹo nhỏ thôi. Mảng a[] là mảng đánh dấu, a[i] = true <==> kí tự có mã ASCII là i có xuất hiện trong xâu, vậy thôi. onelove2710-01-2007, 23:49- Cụ thể thì như thế này: Tôi thắc mắc câu lệnh sau: "fillchar(a,sizeof(a),false);" - Tôi chưa nhìn thấy bao giờ nên không hiểu ý nghĩa mà. condecodon200311-01-2007, 08:25fillchar(a,sizeof(a),false) <==> for i := 1 to n do a[i] := false Master_Baby11-01-2007, 12:49- Vấn đề ở đây là độ dài xâu thay đổi, thế nên xài For...To hay For....Downto cũng đều ko ổn. Buộc phải dùng Repeat hoặc While để thử điều kiện. - Cách giải của sếp conde: Nếu mảng a chỉ để đánh dấu xem có sự hiện diện của ký tự ASCII mã i ko tức là ko thể lưu lại vị trí của ký tự đó. Để rõ ràng hơn xin nêu 1 VD: Input: bbaaazzz Output <của sếp conde - theo cách iem hiểu>: abz Output <chuẩn>:baz May là cái đề bài ko cần đáp án chuẩn mà đáp án xếp lung tung cũng được. (Nhưng như vầy đâu phải là rút gọn xâu đâu). condecodon200311-01-2007, 16:14uses crt; var s : string; a : array[0..255] of boolean; i : integer; begin clrscr; write('Input A String:'); readln(s); fillchar(a,sizeof(a),false); for i := length(s) downto 1 do if a[ord(s[i])] then delete(s,i,1) else a[ord(s[i])] := true; writeln(s); readln; end. Cái này ra kết quả đúng nhưng thứ tự ngược lại. Thực ra ko cần phải dùng đến delete mà chỉ cần đánh dấu là đủ uses crt; var s : string; a : array[0..255] of boolean; i : integer; begin clrscr; write('Input A String:'); readln(s); fillchar(a,sizeof(a),false); for i := 1 to length(s) do if not a[ord(s[i])] then begin a[ord(s[i])] := true; write(s[i]); end; readln; end. Với code này thì hi vọng bạn sẽ thỏa mãn :) Master_Baby12-01-2007, 06:56Ko còn ý kiến!!! lol nguyenhonghanh13-01-2007, 08:19to condecodon: anh giỏi thật đấy em cũng ko còn ý kiến gì :D hoangtu686819-06-2010, 09:35Bạn làm như thế này bị sai rồi. Bạn đã chạy thử chưa thế : Như thế này sẽ chỉ còn giữ lại mỗi ký tự 1 lần xuất hiện thôi. Ví dụ S = aabaa lẽ ra sau khi rút gọn phải là aba nhưng theo cách của bạn sẽ chỉ còn lại ba. Tư tưởng for downto là đúng nhưng trong khi lập trình tối kị không được để 2 cận trong vòng lặp bị thay đổi. Mặc dù trong những trường hợp đơn giản thì có thể nhận thấy chương trình làm việc như thế nào, nhưng giả sử đang làm trong 1 project lớn, nhiều modun chương trình thì sẽ rất khó kiểm soát. ^ ^ chi co the viet truong trinh rut gon xau ki tu trong tep duoc khong [=========> Bổ sung bài viết <=========] em nghi mai ma lam van khong ra ket qua Heroboss1219-06-2010, 10:47Nhập mảng n=100 phần tử. In "cái tổng" chung nhất "không thừa , không thiếu" mà cái mảng kia đem lại. VD: n=7 và nhập vào: 1 2 3 4 5 3 6 Vậy lúc này KQ=6 vì : khi Sử dụng hết mảng thì: ta có: 5+1=6;6=6;2+4=6;3+3=6 uh....... tức là mảng đã dùng hết, KQ chung của nó là =6 (có 4 trường hợp) CÁm ơn các bác đã đọc đề .Có bác nào có YK ? Vậy nếu trường hợp không thể tìm ra "cái tổng" đó thì sao dancuipascal19-06-2010, 17:48Cái này dùng đánh dấu phần tử có phải là nhanh hơn ko hềy ? Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.