M t số bài t p về đối x ng:ộ ậ ứ
1. Cho trước m t xâu ký t , ki m tra xem xâu đó có đối x ng hay khống?ộ ự ể ứ 2. Cho trước m t dãy số nguyền, ki m tra xem dãy đã cho có đối x ng hay ộ ể ứ
khống?
3. Cho trước m t số nguyền, ki m tra xem số đã cho có đối x ng hay khống?ộ ể ứ 4. Cho m t dãy số nguyền. Hãy đ c ra các số đối x ng có trong dãy.ộ ọ ứ
5. Đ c ra tât c các số nguyền đối x ng có m ch số (m<=6).ọ ả ứ ữ
6. Cho trước m t số nguyền. Hãy ki m tra xem số đó có đối x ng nh phân hayộ ể ứ ị khống?
7. In ra tât c các số v a đối x ng th p phân, v a đối x ng nh phân trong ả ừ ứ ậ ừ ứ ị đo n n t i m.ạ ớ
Bài 8. Đối xứng gương
Xét t p các ch cái La tinh in hoa sau:ậ ữ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M t số ch cái có các tính chât đ c bi t nh sau:ộ ữ ặ ệ ư
a) Đối x ng gứ ương qua tr c đối x ng đ ng, ví d ch cái A có tính chât nh v y. ụ ứ ứ ụ ữ ư ậ Ngoài ch A còn có các ký tữ ự
"H","I","M","O","T","U","V","W","X","Y".
b) Đối x ng gứ ương qua tr c đối x ng ngang, ví d ch cái B có tính chât nh v y. Cùng v i B còn có các ký tụ ứ ụ ữ ư ậ ớ ự
"C","D","E","H","I", "K","O","X".
c) Khống đ i khi xoay ký t 180ổ ự 0, ví d ch S. Các ký t "H","I","N","O","X","Z" cũng có tính chât này.ụ ữ ự
M t xâu có tính chât đ c bi t nều nh mốPi ký t c a xâu đều có tính chât đ c bi t đó.ộ ặ ệ ư ự ủ ặ ệ
Yêu cầu: V i xâu cho trớ ước khống quá 250 ký t , hãy xác đ nh xâu có tính chât a), b) hay c) hay khống?ự ị D li u vào:ữ ệ Cho trong file DOIXUNG.INP, gốm m t dòng ch a m t xâu kí t .ộ ứ ộ ự
D li u ra:ữ ệ Xuât ra file văn b n ả DOIXUNG.OUT theo đ nh d ng sau: Nều xâu đã cho khống có tính chât đ c bi t,ị ạ ặ ệ ghi NO. Nều xâu đã cho có tính chât đ c bi t, thì:ặ ệ
Dòng đâu ghi YES
Dòng th hai ghi số ứ 1 nều xâu đã cho có tính chất a); ghi số 2 nều xâu đã cho có tính chất b); ghi số 3 nều xâu đã cho có tính chất c); ghi số 0 nều xâu đã cho có cả 3 tính chất trền.
Ví d :ụ
DOIXUNG.INP DOIXUNG.OUT DOIXUNG.IN
P DOIXUNG.OUT
HELLO NO OTO YES
1
9, Cho trước m t xâu ký t , hãy đ c ra các xâu con đối x ng dài nhât.ộ ự ọ ứ
10. Cho m t dãy số nguyền, Hãy đ c ra tât c các đo n con liền tiềp đối x ngộ ọ ả ạ ứ dài nhât.
T tư ưởng thu t toán và l i gi i tham kh oậ ờ ả ả
Bài 1: T tư ưởng thu t toán: ậ
- Xây d ng hàm ki m tra đối x ngự ể ứ - G i hàm ki m tra, rối kềt lu n.ọ ể ậ {var st:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
read(f,st);
if ktdx(st) then write(g,'CO') else
Write(g,'KHONG');
close(f);
Close(g);
End. }
Bài 2: T tư ưởng thu t toán: ậ - Duy t toàn b dãy.ệ ộ
- Đềm nh ng phân t khác nhau qua tr c đối x ng.ữ ử ụ ứ - D a vào biền đềm đ kềt lu n.ự ể ậ
{var a:array[1..1000] of longint;
n,i,d:longint; w:string;
f,g:text;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,n);
for i:=1 to n do read(f,a[i]);
for i:=1 to n do
if a[i]<>a[n-i+1] then inc(d);
if d=0 then write(g,'CO') else write(g,'KHONG');
close(f);
close(g);
end. }
Bài 3: T tư ưởng thu t toán: ậ
- Xây d ng hàm ki m tra đối x ng.ự ể ứ - Chuy n số thành xâu.ể
- G i hàm ki m tra, rối kềt lu n.ọ ể ậ
{ var a:array[1..1000] of longint;
n,i,d:longint; w:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,n);
str(n,w); {Chuy n số thành xâu}ể if ktdx(w) then write(g,'CO') else write(g,'KHONG');
close(f);
close(g);
end.}
{Doc ra cac so doi xung co trong day}
Bài 4: T tư ưởng thu t toán: ậ
- Xây d ng hàm ki m tra đối x ng.ự ể ứ - Chuy n lân lể ượ ừt t ng số về xâu.
- G i hàm ki m tra, rối kềt lu n.ọ ể ậ
{var a:array[1..1000] of longint;
n,i,d:longint; w:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,n);
for i:=1 to n do read(f,a[i]);
for i:=1 to n do begin
str(a[i],w);
if ktdx(w) then begin
inc(d);
write(g,w,' ');
end;
end;
if d=0 then
write(g,'KHONG CO');
close(f);
close(g);
end.}
{============Doc ra so doi xung co m chu so======}
Bài 5: T tư ường thu t toán: ậ
- Xây d ng hàm ki m tra đối x ng.ự ể ứ - Xây d ng hàm mũ.ự
- Duy t tât c các số có m ch số.ệ ả ữ - Chuy n t ng số thành xâuể ừ - G i hàm KTDX. ọ
{var a:array[1..1000] of longint;
m,n,i,d:longint; w:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
function mu(p,q:integer):longint;
begin
if q=0 then mu:=1
else mu:=p*mu(p,q-1);
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,m);
for i:=mu(10,m-1) to mu(10,m)-1 do begin
str(i,w);
if ktdx(w) then begin
inc(d);
write(g,w,' ');
end;
end;
if d=0 then
write(g,'KHONG CO');
close(f);
close(g);
end.}
{================Kiem tra so doi xung nhi phan=========}
Bài 6: T tư ưởng thu t toán: ậ
- Xây d ng hàm ki m tra đối x ngự ể ứ - Xây d ng hàm đ i nh phân.ự ổ ị - G i hàm ki m tra, rối kềt lu n.ọ ể ậ
{var a:array[1..1000] of longint;
m,n,i,d:longint; w:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
function DNP(k:longint):string;
var st:string;
begin st:='';
repeat
if k mod 2=0 then st:='0'+st else st:='1'+st; k:=k div 2;
until k=0;
DNP:=st;
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,m);
if ktdx(dnp(m)) then write(g,'CO')
else
write(g,'KHONG');
close(f);
close(g);
end.}
{= In ra cac so vua Doi xung nhi phan vua doi xung thap phan tu n toi m=}
Bài 7: T tư ường thu t toán: ậ
- Xây d ng hàm ki m tra đối x ngự ể ứ - Xây d ng hàm đ i nh phânự ổ ị - G i hàm ki m tra, rối kềt lu n.ọ ể ậ
{var a:array[1..1000] of longint;
m,n,i,d:longint; w:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
function DNP(k:longint):string;
var st:string;
begin st:='';
repeat
if k mod 2=0 then st:='0'+st else st:='1'+st; k:=k div 2;
until k=0;
DNP:=st;
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,n,m);
for i:=n to m do begin
str(i,w);
if (ktdx(w)) and (ktdx(dnp(i))) then begin
write(g,i,' ');
inc(d);
end;
end;
if d=0 then
write(g,'KHONG CO');
close(f);
close(g);
end.}
{==========Doi xung guong=========}
Bài 8: T tư ưởng thu t toán: ậ
- Xây d ng hàm ki m tra đối x ngự ể ứ
- Ki m tra xâu đã cho xem các ký t thu c tính chât nàoể ự ộ
- Xét t ng tính châtừ
- G i hàm ki m tra, rối kềt lu n.ọ ể ậ
{var a:array[1..1000] of longint;
m,n,i,d,d1,d2:longint; st:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,st);
for i:=1 to length(st) do begin
if st[i] in['A','H','I','M','O','T','U','W','X','Y'] then inc(d);
if st[i] in['B','C','D','E','H','I','K','O','X'] then inc(d1);
if st[i] in['S','H','I','N','X','Z'] then inc(d2);
end;
if (ktdx(st)) and (d=length(st))and (d1=length(st))and (d2=length(st)) then
write(g,'YES ',0) else
if (ktdx(st)) and (d=length(st)) then write(g,'YES ',1)
else
if (ktdx(st)) and (d1=length(st)) then write(g,'YES ',2)
else
if (ktdx(st)) and (d2=length(st)) then write(g,'YES ',3)
else write(g,'NO');
close(f);
close(g);
end. }
{==================Xau con doi xung dai nhat==============}
Bài 9: T tư ưởng thu t toán: ậ
- Xây d ng hàm ki m tra đối x ngự ể ứ - Dùng hai biền đềm (Xuối, ngược)
- Copy đo n gi a hai biền đ ki m tra, nều đx thì l u l i vào m ngạ ữ ể ể ư ạ ả - Săp xềp m ng gi m dân.ả ả
- Duy t l i chuốPi ban đâu, nều đo n nào đối x ng có chiều dài đo n nào ệ ạ ạ ứ ạ l n nhât thì in ra.ớ
{var a:array[1..100] of string;
m,n,i,j,d:longint; st,tg:string;
f,g:text;
function ktdx(s:string):boolean;
var k:integer;
begin
ktdx:=false;
for k:=1 to length(s) do
if s[k]<>s[length(s)-k+1] then exit;
ktdx:=true;
end;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,st);
i:=1;
repeat
j:=length(st);
repeat
if (ktdx(copy(st,i,j-i+1))) then begin
inc(d);
a[d]:= copy(st,i,j-i+1) ; end;
dec(j);
until j=i;
inc(i);
until i=length(st);
for i:=1 to d-1 do for j:=i+1 to d do
if length(a[i])<length(a[j]) then
begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; end;
for i:=1 to length(st)-1 do
if ktdx(copy(st,i,length(a[1]))) then writeln(g, copy(st,i,length(a[1])));
close(f);
close(g);
end.}
{===========Doan con lien tiep doi xung dai nhat=======}
Bài 10: T tư ưởng thu t toán: ậ
- Dùng hai biền đềm thu n và ngậ ược.
- Ki m tra đo n gi a hai biền đềm đó, nều đx thì đánh dâu đi n đâu và ể ạ ữ ể đi m cuối, đống th i tìm chiều dài đx l n nhât.ể ờ ớ
- Duy t l i các đo n đx, có nh ng đo n nào có chiều dài l n nhât thì in ra.ệ ạ ạ ữ ạ ớ
{ var a,c,d:array[1..1000] of longint;
m,n,i,j,k,h,max,d1:longint;
f,g:text;
begin
assign(f,'bl.inp');reset(f);
assign(g,'bl.out'); rewrite(g);
readln(f,n);
for i:=1 to n do read(f,a[i]);
i:=1;
repeat
j:=n;
repeat d1:=0;
for k:=i to j do
if a[k]<>a[j-k+i] then inc(d1);
if d1=0 then begin
if j-i>=max then begin
max:=j-i;
inc(h);
d[h]:=i; c[h]:=j;
end;
end;
dec(j);
until j=i;
inc(i);
until i=n;
if h=0 then
write(g,'KHONG CO DOAN CON THOA MAN') else
Begin
for i:=1 to h do if c[i]-d[i]=max then begin
for j:=d[i] to c[i] do
write(g,a[j],' ');
writeln(g);
end;
end;
close(f);
close(g);
end.}
