Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Kiểm tra chuỗi đối xứng

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Kiểm tra chuỗi đối xứng   Sat 06 Mar 2010, 23:02

Đây cũng là một bài khá cơ bản trong Pascal.

Chuỗi đối xứng là chuỗi mà viết xuối hay viết ngược đều như nhau.

Trong bài này, mình sẽ giới thiệu các bạn hai cách.

Cách 1

Dựa vào đặc điểm của nó, ta sẽ dễ hiểu như sau. Với một chuỗi, ta viết ngược lại, nếu chuỗi viết ngược lại giống chuỗi ban đầu thì chuỗi ban đầu đối xứng (và dĩ nhiên chuỗi viết ngược lại cũng đối xứng). Dựa vào đó, ta có thuật toán sau

Code:
program chuoi_doi_xung;
uses crt;
var s,st:string; i:integer;
begin
 clrscr;
 write('nhap chuoi: ');readln(s);
 ss:='';
 for i:=length(s) downto 1 do
  st:=st+s[i]
 if s=st then writeln('chuoi doi xung.')
 else writeln('chuoi khong doi xung.');
readln;
end.


Được sửa bởi littlelee ngày Mon 08 Mar 2010, 19:19; sửa lần 1.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Sat 06 Mar 2010, 23:26

Cách 2

Dựa trên cách 1 ta có nhận xét sau: Chuỗi đối xứng phải có kí tự thứ i và kí tự thứ length(s)-i+1 bằng nhau. Ví dụ:
s=|a.1|a.2|a.3|a.4|...|a.n|
st=|a.n|...|a.4|a.3|a.2|a.1|
khi s=st thì a.1=a.n, a.2=a.n-1....
Như vậy sễ thấy công thức chung, a.i=a.length(s)-i+1 . Ta dựa vào đó để cải tiến thuật toán. Ta sẽ cho biế i chạy tiwf 1 đến length(s) div 2, nếu s[i]=s[length(s)-i+1] thì bỏ qua, ngược lại thì gán lại biến kiểm tra là false. Bài cụ thẻ sẽ như sau.

Code:
program chuoi_doi_xung;
uses crt;
var s:string; i:integer;bl:boolean;
begin
 clrscr;
 write('nhap chuoi: ');readln(s);
 bl:=true;
 for i:=1 to length(s) do
  if s[i]<>s[length(s)-i+1] then bl:=false;
 if bl=true then write('doi xung')
 else write('khong doi xung');
readln;
end.


Được sửa bởi littlelee ngày Mon 08 Mar 2010, 19:20; sửa lần 1.
Về Đầu Trang Go down
vankhoa1260
Gà con


Tổng số bài gửi : 19
Join date : 09/02/2010
Age : 21
Đến từ : Thiên Đường

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 08 Mar 2010, 18:34

bạn oi!Sửa "readlb" thanh "readln" cho mấy bạn khác khỏi bị sai.
Về Đầu Trang Go down
vankhoa1260
Gà con


Tổng số bài gửi : 19
Join date : 09/02/2010
Age : 21
Đến từ : Thiên Đường

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 08 Mar 2010, 18:39

bài như thế này là tốt lắm rồi. Nhưng bạn cần post nhiều bài căn bản như vậy hơn nữa
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 08 Mar 2010, 19:18

OK ok, mình đánh trực tiếp nên có lỗi, sorry, sửa lại liền
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Wed 17 Mar 2010, 19:34

Littlelee làm bài này không sai nhưng câu lệnh for bị dư nhiều quá không cần thiết (bạn nên giới hạn vòng for lại phân nửa chiều dài xâu thôi)
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 26 Jul 2010, 20:32

Cách 1:
Code:

Function          Xaudoixung(S:String): boolean;
Var                i,n : integer;
Begin
                      N:=length(S);
                      For i := 1 to (n div 2) do
                      If s[i]<>s[n+1-i] then
                      Begin
                                  Xaudoixung:=false;
                                  Exit;
                      End;
                      Xaudoixung:=True;
End;
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 26 Jul 2010, 20:36

Cách 2:
Code:

Function      palindrome(s : string) : boolean;
Var            i, j : integer;
begin
                i := 1;
                j := length(n);
                while i<=j do
                begin
                            if s[i] <> s[j] then
                            begin
                                          palindrome := false;
                                          exit;
                          end;
                          inc(i);
                          dec(j);
                  end;
                  palindrome := true;
End;
Về Đầu Trang Go down
http://thongtra.forum-viet.com
nham00
Gà mờ


Tổng số bài gửi : 7
Join date : 06/09/2010

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 06 Sep 2010, 22:42

tớ lại có một ý tưởng khác
ta sẽ for i từ 1 đến độ dài chuỗi
tại i ta xét xem nó có phải là tâm kí tự đối xứng ko or nhóm tâm 2 kí tự của chuỗi con nào ko
vì vậy ta chỉ tốn 2 dòng for
với dòng for thứ 2 chỉ tốn nhiều nhất length(s) div 2 thôi
đồng thời dòng for thứ nhất, nếu ta dùng nhánh cận thì ta ko cần chạy tới length(s) đâu
Về Đầu Trang Go down
nham00
Gà mờ


Tổng số bài gửi : 7
Join date : 06/09/2010

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 06 Sep 2010, 22:44

code tớ chưa đánh xong nên chưa đưa lên được
Về Đầu Trang Go down
nham00
Gà mờ


Tổng số bài gửi : 7
Join date : 06/09/2010

Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Mon 06 Sep 2010, 23:10

đây là code của tớ:

{chuoi doi xung}
const inp='chuoi.inp';
out='chuoi.out';
maxint=100000;
var i,j,n,max:longint;
s,sl:ansistring;
f:text;
procedure tam1(i:longint);
begin
j:=0;
while (i-j>0)and(i+j<=n)and(s[i-j]=s[i+j]) do inc(j);
if j*2-1>max then max:=j*2-1;
end;
procedure tam2(i:longint);
begin
j:=0;
while (i-j+1>0)and(i+j<=n)and(s[i-j+1]=s[i+j]) do inc(j);
dec(j);
if j*2>max then max:=j*2;
end;
begin
assign(f,inp);
reset(f);
readln(f,n);
repeat
readln(f,sl);
if sl<>'' then s:=s+sl;
until sl='';
close(f);
assign(f,out);
rewrite(f);
for i:=1 to n-1 do
begin
if (i>1)and(s[i-1]=s[i+1]) then tam1(i);
if s[i]=s[i+1] then tam2(i);
if n-i<max div 2 then break;
end;
if max=0 then max:=1;
writeln(f,max,#32);
close(f);
end.
[code]
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Today at 21:28

Về Đầu Trang Go down
 
Kiểm tra chuỗi đối xứng
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Chuối chưng caramel
» Bánh tét chuối
» Sự Tích Mèo Và Chuột
» [Paint tool SAI] [WIP] Tô màu mắt bằng chuột
» Mẫu Móc Chuột MicKey

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến