Rút gọn xâu có các kí tự trùng??? [Archive] – Diễn Đàn Tin Học

—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_Baby

Đơ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;

condecodon2003Dùng 1 mảng 0 .. 255 để lưu lại, chỉ mất 1 vòng for
onelove27chưa thử nhưng thank những bác nhiều, nghe chừng chắc là ổn
onelove27

**************************************
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

condecodon2003

Vậ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_Baby

Vậ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!

pineflower

Dù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. 🙂

condecodon2003

Đâ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.

pineflower

Đâ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. ^ ^

condecodon2003Thì đây là vô hiệu những kí tự trùng, mỗi kí tự chỉ còn Open 1 lần thôi mà. Theo bạn sẽ phải viết như thế nào : – /
thuonghcm

tô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.

thuonghcmhay 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 hoàn toàn có thể, conde hãy giúp tôi 1 số bài đã pposst trước đây đi ? cảm ơn nhiều nhé .
pineflower

Thì đâ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 ^ ^

condecodon2003

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 ^ ^

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

thuonghcmtrọn vẹn đúng chuẩn, ,, hỏng biết là con dê đơn độc hay là con dế đơn độc mà tài quá
nguyenhonghanh

to 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.

thuonghcm

Nhậ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 ?

nguyenhonghanh

anh ơ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.

onelove27

to 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

onelove27

—à 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.

condecodon2003

hoà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 ạ ;))

condecodon2003

to 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

condecodon2003

anh ơ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

thuonghcm

Nhậ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 ?

thuonghcm

bà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.

onelove27

Vậ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!

condecodon2003

– À 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.

onelove27

– 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à.

condecodon2003fillchar ( a, sizeof ( a ), false ) < ==> for i : = 1 to n do a [ i ] : = false
Master_Baby

– 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 : abz
Output :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).

condecodon2003

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.

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_BabyKo còn quan điểm ! ! ! lol
nguyenhonghanh

to condecodon: anh giỏi thật đấy
em cũng ko còn ý kiến gì 😀

hoangtu6868

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. ^ ^
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

Heroboss12

Nhậ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

dancuipascalCái này dùng lưu lại thành phần có phải là nhanh hơn ko hềy ?
Powered by vBulletin ® Version 4.2.0 Copyright © 2022 vBulletin Solutions, Inc. All rights reserved .

Source: https://mix166.vn
Category: Thủ Thuật