Scribd
Importer
114 vues2 pages

Récursivité et algorithmes en TD 8

Le document présente plusieurs exercices sur la récursivité. Il introduit la notion de palindrome et demande d'écrire des solutions récursives et itératives pour déterminer si une chaîne est un palindrome. Il présente également des exercices sur le calcul récursif de combinaisons et sur l'analyse de la pile d'exécution lors d'appels récursifs.

Transféré par

Laribi Takwa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
114 vues2 pages

Récursivité et algorithmes en TD 8

Le document présente plusieurs exercices sur la récursivité. Il introduit la notion de palindrome et demande d'écrire des solutions récursives et itératives pour déterminer si une chaîne est un palindrome. Il présente également des exercices sur le calcul récursif de combinaisons et sur l'analyse de la pile d'exécution lors d'appels récursifs.

Transféré par

Laribi Takwa
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Institut Supérieur d’Informatique et de Multimédia de Sfax ANNEE UNIVERSITAIRE : 2022-2023

SECTION: P-LSI

Module : Algorithmes et structures de données I


TD 8 : La récursivité
Exercice 1
Un palindrome est un mot qui peut être lu indifféremment de droite à gauche ou de gauche à droite.
Exemples : AZIZA, LAVAL, RADAR, 2002, etc.
On vous propose la solution itérative sans utilisation de pointeurs :
Fonction palindrome (ch : chaine, début : entier, fin : entier) : Booléen
Début
Tant que (début <= fin) Faire
Si ch[début] ≠ ch[fin] Alors
retourne Faux
Sinon
début ← début+1
fin ←fin-1
Finsi
FinTQ
retourne Vrai
Fin
Donner une solution itérative et une solution récursive avec utilisation de pointeurs.
Exercice 2
Quel est le résultat affiché par la procédure Affiche pour n=4 ?

Procédure Affiche (n : entier)


Début
Si (n>0) alors
Affiche (n-2)
Ecrire (n)
Affiche (n-1)
Finsi
Fin

Exercice 3
Ecrire une fonction de recherche dichotomique récursive.
Exercice 4
Le nombre de combinaisons représente le nombre de sous-ensembles de cardinal p d’un ensemble de
×
cardinal n. Il est défini par = 1 si p = 0 ou si p = n, et par = . (On utilise ici la division entière)
1. Ecrire une fonction récursive combRec(n,p) qui calcule le nombre de combinaisons . Avec n et p
deux entiers positifs tels que p ≤ n.
2. Compléter le tableau suivant pour simuler la pile d’exécution lors de l’appel combRec(7,3).

Fonction n p Résultat
Appels successifs combRec 7 3 ……
combRec …… …… ……
combRec …… …… ……
Descente Remontée
combRec …… …… ……

Page 1 sur 2
3. Soit les sous-programmes combRecV2(n,p) et combRecUV(n,p,u,v) où n et p sont deux entiers
positifs tels que p ≤ n, et u et v deux paramètres supplémentaires :
Fonction combRecUV (n : entier, p : entier, u : entier, v : entier) : entier
Si (p=0 ou n=p) Alors
Retourne u div v
Sinon
Retourne comRecUV(n-1, p-1, u*n, v*p)
FinSi
Fin

Procédure combRecV2 (n : entier, p : entier)


comRecUV(n, p, 1, 1)
Fin

Compléter le tableau suivant afin de simuler la pile d'exécution lors d'un appel à combRecV2(7,3).

Sous-programme n p u v résultat
combRecV2 7 3 ……
Appels successifs
combRecUV …… …… …… …… ……
combRecUV …… …… …… …… ……
Descente combRecUV …… …… …… …… …… Remontée
combRecUV …… …… …… …… ……

4. Ecrire une fonction itérative combIter(n,p), dérivée automatiquement de la fonction


combRecUV(n,p,u,v) qui calcule le nombre de combinaisons .

Exercice 5
Soit la fonction F suivante :

Fonction F(n : entier) : entier


Début
Si(n=1) Alors
Retourner 1
Sinon
Retourner f(n-1) + 2*n-1
Finsi
Fin

Quel est le résultat retourné par F dans le cas où on fait son appel par la valeur 5 ?

Page 2 sur 2

Vous aimerez peut-être aussi