4259 - PalRec

Cerința

Scrieți funcția recursivă cu antetul
def PalRec(a, st, dr)
care primind ca parametri un vector a de numere întregi și doi întregi st și dr, returnează 1 dacă secvența a[st], a[st+1], ..., a[dr] din vector este un palindrom, sau returnează 0 în caz contrar.

Restricții și precizări

• st ≤ dr
• Numele funcției este PalRec.
• Se recomandă utilizarea recursivității în rezolvarea problemei. De asemenea, se recomandă să nu se folosească alte funcții suplimentare.

Exemple

Dacă a = (3,5,6,5,3,3,5,-1,5), atunci PalRec(a,2,4) = 1 deoarece 5,6,5 este palindrom. PalRec(a,4,7) = 1 deoarece 5,3,3,5 este palindrom. PalRec(a,1,4) = 0 deoarece 3,5,6,5 nu este palindrom.

Explicație

Funcția PalRec verifică dacă un șir de caractere a este palindrom folosind o abordare recursivă.

Argumentele funcției sunt:

• a - șirul de caractere de verificat
• st - poziția începutului intervalului verificat (începe de la 0)
• dr - poziția sfârșitului intervalului verificat (începe de la len(a) - 1)

Prima condiție if din funcție verifică cazul de bază al recursiei, când intervalul de verificat este redus la o singură literă. Funcția returnează 1, deoarece orice literă este palindrom în sine.

A doua condiție if verifică dacă primele și ultimele caractere ale intervalului de verificat sunt egale. Dacă da, funcția continuă verificarea pentru următorul interval, eliminând prima și ultima literă ale intervalului prin apelarea recursivă a funcției PalRec cu pozițiile începutului și sfârșitului incrementate și, respectiv, decrementate.

Dacă cele două caractere nu sunt egale, funcția returnează 0, semnificând că șirul nu este palindrom.

Rezolvare

<syntaxhighlight lang="python"> def validate_st_dr(st, dr):

   if isinstance(st, int) and isinstance(dr, int) and st <= dr:
       return True
   else:
       return False

def PalRec(a, st, dr):

   if st >= dr:
       return 1
   if a[st] != a[dr]:
       return 0
   return PalRec(a, st + 1, dr - 1)

def main():

   a = input("Introduceti un sir de caractere: ")
   st = input("Introduceti st: ")
   dr = input("Introduceti dr: ")
   try:
       st = int(st)
       dr = int(dr)
       if validate_st_dr(st, dr):
           result = PalRec(a, st, dr)
           if result == 1:
               print("Sirul introdus este palindrom.")
           else:
               print("Sirul introdus nu este palindrom.")
       else:
           print("Valorile st si dr nu sunt valide.")
   except ValueError:
       print("Valorile st si dr trebuie sa fie numere intregi.")

</syntaxhighlight>