Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

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

Go down 
5 posters
Tác giảThông điệp
littlelee
Admin
Admin
littlelee


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeSat 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
littlelee


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeSat 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
vankhoa1260


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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
vankhoa1260


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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
littlelee


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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ỏ
administrators


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeWed 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
Hovanthong


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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
Hovanthong


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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ờ
nham00


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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ờ
nham00


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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ờ
nham00


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

Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitimeMon 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





Kiểm tra chuỗi đối xứng Empty
Bài gửiTiêu đề: Re: Kiểm tra chuỗi đối xứng   Kiểm tra chuỗi đối xứng I_icon_minitime

Về Đầu Trang Go down
 
Kiểm tra chuỗi đối xứng
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» chuoi doi xung
» Bản kiểm điểm
» Các nhà vật lý tìm kiếm vật chất tối ( sưu tầm đấy)
» Pascal: Kiểm tra tính nguyên tố của một số
» GOOGLE EARTH.-Một phương pháp tìm kiếm định vị của google.

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