[TP06] Palindromes - Récursif - [LINFO1103] Introduction à l'algorithmique

[TP06] Palindromes - Récursif

Implémentez une version récursive de l'algorithme itératif étudié dans l'exercice précédent. Votre implémentation récursive doit garder la même complexité que l'algorithme itératif.

On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :

le cas de base,

comment traiter le cas de base,

comment construire la solution actuelle (taille n) si je connais une solution pour un problème plus petit (par exemple de taille n-1).

Rappel du problème :

Un palindrome est une séquence qui est indépendante du sens de lecture, c'est-à-dire une séquence qui est identique qu'elle soit lue de gauche à droite ou de droite à gauche. Par exemple, les mots radar et kayak sont des palindromes, le mot bonbon n'en est pas un.

Vous êtes chargés d'implémenter les fonctions is_palindrome_rec et is_palindrome étant donné les propriétés suivantes :

Une séquence contenant aucun caractère peut être considérée comme un palindrome.
Une séquence contenant exactement un caractère est un palindrome.
Une séquence est un palindrome si le premier et dernier caractère sont identiques, que le deuxième et avant-dernier caractère sont identiques, ...

Vous noterez que les chaînes de caractères Python (str) peuvent être vues comme des tableaux immuables. Cela signifie :

que vous pouvez utiliser les str comme des tableaux (list) mais que, comme les tuples en Python, vous ne pouvez pas modifier leur contenu
supposons que s = "hello" alors s[:2] renvoie "he", s[1] renvoie "e" et s[2:] renvoie "llo"
lorsque, comme ci-dessus, on extrait une sous-chaîne d'une chaîne s de longueur $n$ , cette extraction se réalise en réalité en recopiant les caractères concernés dans une nouvelle chaîne.
Par conséquent,
- accéder à s[:2] s'exécute en temps constant $\Theta(1)$ car on n'a qu'un nombre constant de caractères (ici les 2 premiers) à recopier, quelle que soit la longueur totale $n$ de la chaîne s.
- accéder à s[2:] s'exécute en $O(n)$ car on doit recopier $n - 2$ caractères de la chaîne s, donc tous sauf les 2 premiers.

Cole este comando no seu terminal:

A senha para conectar é

Questão 1: Identification de palindromes (récursif)

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier palindrome_rec.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def is_palindrome_rec(s):
    """
    pre: `s` est un str
    post: détermine récursivement si `s` est un palindrome ou non
    """

return False

 
return False

Questão 2: Complexité temporelle

Quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.

Comme d'habitude, $n$ désigne la taille du problème, c'est-à-dire dans ce cas-ci le nombre de caractères de la chaîne s.

$O(\log(n))$

$\Omega(\sqrt{n})$

$O(n)$

$\Theta(n^2)$

$O(n^2)$

$\Theta(n)$

Autores	Vincent Branders, Pierre Dupont
Prazo de entrega	26/03/2025 14:00:00
Limite de submissão	No limitation

Informações

Entrar