რეკურსიის დახმარებით განვსაზღვროთ სიტყვა პალინდრომია თუ არა

პალინდრომი არის სიტყვა, რომელიც წინიდანაც და უკნიდანაც ერთნაირად იკითხება. მაგალითად, „როგორ“ არის პალინდრომი, მაგრამ „როგორი“ არ არის.

როგორ გამოვიყენოთ რეკურსია იმის დასადგენად, არის თუ არა სიტყვა პალინდრომი? დავიწყოთ ბაზისის გააზრებით. წარმოიდგინეთ სიტყვა a. ის პალინდრომია. რეალურად, არ არის აუცილებელი, პალინდრომი იყოს ნამდვილი სიტყვა რომელიმე ენაში. პალინდრომი ჰქვია ასოების ნებისმიერ მიმდევრობას, რომელიც ერთნაირად იკითხება წინიდანაც და უკნიდანაც, როგორიცაა xyzyzyx. ასოების მიმდევრობას ვუწოდებთ სტრიქონს (სტრინგს). ასე რომ, შეგვიძლია, ვთქვათ, რომ ნებისმიერი სტრიქონი, რომელიც შეიცავს მხოლოდ ერთ ასოს ნაგულისხმევად არის პალინდრომი. სტრიქონი შეიძლება, არ შეიცავდეს არც ერთ ასოს; 0 ასოს მქონე სტრიქონს ცარიელ სტრიქონს ვეძახით. ცარიელი სტრიქონი აგრეთვე არის პალინდრომი, ვინაიდან ერთნაირად „იკითხება“ წინიდანაც და უკნიდანაც. ანუ, ახლა ვთქვათ, რომ ნებისმიერი სტრიქონი, რომელიც შეიცავს მაქსიმუმ ერთ ასოს არის პალინდრომი. ეს ჩვენი ბაზისია: ზუსტად ერთასოიანია ან ნულასოიანი სტრიქონი არის პალინდრომი.

იმ შემთხვევაში რა ხდება, თუ სტრიქონი შეიცავს ორ ან მეტ ასოს? აქ რეკურსიულ შემთხვევასთან გვაქვს საქმე. განვიხილოთ პალინდრომი rotor. მისი პირველი და ბოლო ასოები ერთი და იგივეა და ეს თვისება უნდა სრულდებოდეს ნებისმიერი პალინდრომისთვის. მეორე მხრივ, თუ პირველი და ბოლო ასოები არ არის ერთი და იგივე, როგორც motor-ის შემთხვევაში, მაშინ შეუძლებელია, სტრიქონი პალინდრომი იყოს. ასე რომ, ახლა გვაქვს გზა, რომლის მიხედვითაც შეგვიძლია, გამოვაცხადოთ, რომ სტრიქონი არ არის პალინდრომი: როდესაც მისი პირველი და ბოლო ასოები განსხვავებულია. შეგვიძლია, ეს სიტუაცია სხვა ბაზისად წარმოვიდგინოთ, რადგან პასუხი დაუყოვნებლივ გვაქვს. დავუბრუნდეთ შემთხვევას, როცა პირველი და ბოლო ასოები ერთმანეთს ემთხვევა, რას გვეუბნება ეს? სტრიქონი შეიძლება იყოს პალინდრომი. ასევე შეიძლება, რომ არ იყოს. სტრიქონში rater, პირველი და ბოლო ასოები ერთი და იგივეა, მაგრამ სტრიქონი არ არის პალინდრომი. წარმოიდგინეთ, პირველი და ბოლო ასოები რომ მოვაშოროთ, რაც დაგვიტოვებს სტრიქონს ate. მაშინ დარჩენილი სტრიქონის პირველი და ბოლო ასოები განსხვავებულია და ამით ვიგებთ, რომ rater არ არის პალინდრომი.

ასე რომ, აი, როგორ ვარკვევთ რეკურსიულად, სტრიქონი არის თუ არა პალინდრომი. თუ პირველი და ბოლო ასოები განსხვავდება, მაშინ ვაცხადებთ, რომ სტრიქონი არ არის პალინდრომი. წინააღმდეგ შემთხვევაში, მოვაშოროთ პირველი და ბოლო ასოები და გავარკვიოთ, დარჩენილი სტრიქონი — ქვეამოცანა — არის თუ არა პალინდრომი. შემცირებული სტრიქონის პასუხი გამოვაცხადოთ თავდაპირველი სტრიქონის პასუხად. როგორც კი სტრიქონს ჩამოვიყვანთ ერთ ან ნულ ასომდე, ვაცხადებთ მას პალინდრომად. აი, ჩვენ მიერ განხილული ორი სიტყვის ვიზუალიზაცია:

როგორ აღვწერდით ამას ფსევდოკოდში?

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.