Cho chuỗi Str làm đầu vào. Mục tiêu là kiểm tra chuỗi có phải palindrome (đối xứng) hay không bằng hàm đệ quy. Chuỗi palindrome khi đọc từ đầu hoặc cuối đều cho từ giống nhau. Chuỗi rỗng coi là palindrome. Đảo ngược ký tự palindrome cho chuỗi giống gốc.
Ví dụ palindrome: madam, abcba, malayalam.
Ví dụ
Đầu vào - Str = "malayalam"
Đầu ra - Chuỗi đầu vào là palindrome.
Giải thích - Str[0..8] = malayalam, đảo ngược = malayalam. Hai chuỗi giống nhau.
Đầu vào - Str = "tutorial"
Đầu ra - Chuỗi đầu vào không phải palindrome.
Giải thích - Str[0..7] = tutorial, đảo ngược = lairotut. Hai chuỗi khác nhau.
Phương pháp sử dụng trong chương trình dưới đây
Kiểm tra nếu chuỗi chỉ có 1 ký tự thì là palindrome. Ngược lại đệ quy duyệt chuỗi cho các ký tự còn lại, dừng nếu ký tự đối ứng khác nhau.
Nhập chuỗi Str[] và tính độ dài.
Nếu length == 0 thì result = 1.
Ngược lại result = checkPalindrome(Str, 0, length-1) với 0 là chỉ số đầu, length-1 là chỉ số cuối.
Hàm checkPalindrome(char str[], int first, int last) trả về 0 nếu ký tự nào không khớp.
Nếu first == last (chỉ còn 1 ký tự) trả về 1.
Ngược lại: first++, last--, đệ quy checkPalindrome(str, first, last).
Cuối đệ quy nếu result = 1 thì palindrome, ngược lại không.
In kết quả trong main.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; int checkPalindrome(char str[], int first, int last){ if (first < last + 1){ first++; last--; return checkPalindrome(str, first, last); } if (first == last){ return 1; } if (str[first] != str[last]){ return 0; } return 1; } // Driver Code int main(){ char Str[] = "madam"; int result; int length = strlen(Str); if (length == 0){ result=1; } else{ result=checkPalindrome(Str, 0, length - 1); } if (result==1){ cout << "Chuỗi đầu vào là palindrome."; } else{ cout << "Chuỗi đầu vào không phải palindrome."; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Chuỗi đầu vào là palindrome.