Bài toán kiểm tra xâu đối xứng tin 11 năm 2024

Question

– Cách đơn giản nhất là ta sẽ đọc ngược lại xâu S và lưu vào biến S1. sau đó kiểm tra 2 xâu có hoàn toàn giống nhau hay không?

ví dụ:

S=”abcde” => S1=”edcba”. 2 xâu này không giống nhau nên không là xâu đối xứng.

S=”aabccbaa” => S1=”aabccbaa”. 2 xâu này giống nhau hoàn toàn nên kết luận được là xâu đối xứng.

– Đây cũng là cách mà trong sách giáo khoa Tin học 11 chia sẻ.

Đầu tiên chúng ta sẽ tạo xâu đảo ngược so với xâu ban đầu,

VAR s1:string; for i:=length(s) downto 1 do

s1:=s1+s[i];

Sau đó chúng ta so sánh if (s1=s) then …..

a. Code kiểm tra xâu đối xứng cách 1 Pascal

program kiem_tra_xau_doi_xung; uses crt; var s, s1: string

i:integer;

begin

clrscr;
writeln('Nhap vao xau s: '); 
readln(s);
for i:=length(s) downto 1 do
    s1:=s1+s[i];
if (s1=s) then 
    writeln('Xau doi xung') 
else 
    writeln('Xau khong doi xung');
readln;

end.

b. Code kiểm tra xâu đối xứng cách 1 c++

include <iostream>

include <string>

using namespace std; int main() {

string s, s1="";
getline(cin,s);
for (int i=s.length()-1; i>=0; i--)
    s1=s1+s[i];
if (s1==s)
    cout << "La xau doi xung";
else
    cout << "ko la xau doi xung";
return 0;

}

2. Kiểm tra xâu đối xứng cách 2

– Cách thứ 2 cải tiến từ cách thứ nhất, thay vì sinh lại một xâu nghịch đảo rồi so sánh thì chúng ta so sánh trực tiếp từng kí tự trên xâu gốc, nên thời gian chạy sẽ nhanh hơn cách thứ nhất.

– Nhận xét chung: do xâu đối xứng là xâu khi đảo ngược lại sẽ giống hoàn toàn vơi xâu gốc nên chúng ta có thể xét dựa vào so sánh lần lượt các phần tử đầu xâu với các phần tử cuối xâu.

ví dụ s=”abba”

ta có s[1]=s[4], s[2]=s[3] nên kết luận nó là xâu đối xứng.

Như vậy chúng ta chỉ cần cho biến i chạy từ 1 đến (độ dài xâu) chia 2 và so sánh s[i] với s[(độ dài xâu) – i +1] nếu tồn tại một chỗ mà 2 kí tự khác nhau chúng ta có thể kết luận ngay nó ko đối xứng.

Khi chạy chương trình, nhập vào xâu: ' vui ma hoc hoc ma vui' thì chương trình đưa ra thông báo: "xau khong la palindrome", còn khi nhập vào xâu 'abcddcba' thì chương trình đưa ra thông báo: "Xâu là palindroine?".

Kết quả của chương trình cho như hình 52 dưới đây :

Để viết lại chương trình dùng biến xâu thì ta cần khai thác khả năng tham chiếu đến từng kí tự trong xâu thông qua vị trí của xâu này. Như vậy, không cần thiết phải tạo một xâu mới để cuối cùng so sánh hai xâu, mà chỉ cần sánh cặp kí tự ở vị trí đối xứng nhau để kết luận có phải hay không.

Bởi vậy, ta có thể dùng một biến logic để ghi nhận sự phát hiện này. Trước vòng lặp thực hiện các so sánh nói trên, cần không chuyển biến logic ở mỗi bước lặp, hễ hai kí tự được so sánh khác nhau thì biến logic đó sẽ phải thay đổi giá trị.

Chương trình sau đây dùng để kiểm tra xem xâu nhập vào có phải là xâu palindrome hay không.

vai i, X: byte;

a: string;

palii: boolean;

begin

write (Nhap vao xau: ’ );

reailn(a) ;

X:= length(a); {xac dinh do dai cua xau}

palin:=true;

{khoi tao palin, tam coi xau a la palindrome}

for i:= 1 to X div 2 do {so sanh cap ki tu doi xung}

if a [i. ] oa [x-i + 1 ]

then palin: =false;

if palin then writeln: Xau la palindrome’)

else writeln(’Xau khong la palindrome’);

readln

End.

Khi chạy chương trình, nhập vào xâu: 'He 2007 ' thì chương trình đưa ra thông báo: "xau khong la palindrome”, còn khi nhập vào xau 'abcddcba' thì chương trình đưa ra thông báo: "xau la palindrome" kết quả của chương trình cho như hình 53 dưới đây:

Tuy nhiên, ta có thể không dùng vòng for-do mà dùng while-do hay repeat-until và có thể không cần dùng biến logic. Chương trình sau đây đáp ứng được yêu cầu đặt ra:

var x: byte;

a: string;

palin: boolean;

begin

write('Nhap vao xau: ' ) ,

readln(a);

X: =length (a) , {xac dinh do dai cua xa} i:=1;

while (i<=(x div 2)) and (a [i] =a [x-i + 1] ) do i: = i +1,ế if i> (x div 2) then writeln('Xau la palindrome')

else writeln('Xau khong la palindrome');

readln

End.

Khi chạy chương trình, nhập vào xâu: 'tin hoc hoc tin' thì chương trình đưa ra thông báo: 'xau khong la palindrome", còn khi nhập vào xâu ' ABCDDCBD' thì chương trình cũng đưa ra thông báo: “xau khong la palindrome", còn khi nhập vào xâu: ' ABCD0770DCBA' thì chương trình đưa ra thông báo: “xau la palindrome" .

Kết quả của chương trình cho như hình 55 dưới đây:

Bài 2. Để giải quyết bài toán này, chúng ta nhận thấy rằng:

Cần ghi nhận số lần xuất hiện của từng chữ cái. Có tất cả 26 chữ cái ' A ' ' z '. Có thể dùng một mảng với chỉ số là kí tự từ 'A ' đến 'z' để ghi nhận số lần xuất hiện của các kí tự trong xâu s. Bởi vậy, chúng ta dùng một mảng một chiều để đếm số lần xuất hiện của một kí tự trong xâu s. Cụ thể, để ghi nhận số lần xuất hiện của kí tự, ta có thể dùng dem[A] để ghi nhận số lần xuất hiện kí tự A (hay kí tự a, vì không phân biệt chữ hoa hay chữ thường).

Để giải quyết vấn đề không phân biệt chữ hoa hay chữ thường ta cần dùng hàm Upcase(c).

Do một kí tự xuất hiện trong xâu s có thể không phải là một chữ cái nên khi duyệt lần lượt từng kí tự trong xâu s, cần kiểm tra xem kí tự đó có phải là chữ cái hay không để ghi nhận số lần xuất hiện của nó. Chúng ta đã gặp đoạn chương trình kiểm tra một kí tự có là chữ số hay không ở ví dụ 5 tiết học 12. Từ đó, có thể viết được đoạn chương trinh làm việc duyệt từng phần tử cùa xâu và đếm.

Dàn ý của chương trình:

phần khai báo

begin

{nhập xâu S}

N: = length (S);

{Khởi tạo cho màng Dem}

for i: =1 to N do {Neu s[i] là chữ cái thì đém tăng cho s[1]

for c:='A' to Z do {Thông báo sô lần xuất hiện của c}

End.

Chương trình nhập từ bàn phím một xâu kí tự và thông báo ra màn hình số lần xuất hiện của mỗi chữ cái tiếng Anh trong (không phân biệt chữ hoa hay chữ thường).

Program tinh_ki_tu,

var s,sl: string;

i, j, n: integer;

dem: array [ 'A’ . . 'z ’ ] of integer;

c: char ;

begin

write(’Nhap vao xau: ');

readln(S);

n:= length(s);

for C:= 'A' to 'Z' do {khoi tao cho mang dem} dem[c]:= 0 ; s 1 : = ’ ' ;

readln

End.

Khi nhập vào lần lượt các xâu: 'anh' và 'em' ; 'anh em trong mot nha ' thì chương trình cho các kết quả theo thứ tự như sau: 'em va em' ,' em em trong mot nha ' . Kết quả chương trình cho như hình 57 dưới đây:

mẹo hay