MP, PSI et la TSI

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Exercices corrigés de récursivité en Python ( Série 12)

Pré-requis

Pour bien comprendre ces problèmes, vous devriez apprendre ces cours :

 
Exercice 1 :

Soit une chaine de caractères :

Ecrire un algorithme récursif permettant de déterminer sa longueur
Exercice 2 :

Rendre récursive la fonction somme suivante :

def somme(L):
                s=0 :
                for val in L :
                           s+=val
                return s
Exercice 3 :

Pour convertir un nombre entier positif N de la base décimale à la base binaire, il faut opérer par des divisions successives du nombre N par 2. Les restes des divisions constituent la représentation binaire.

Ecrire une fonction récursive « Binaire » permettant d’imprimer à l’écran la représentation binaire d’un nombre N (voir exemple en face).
Exercice 4 :

La suite de Fibonacci est définie comme suit :

Ecrire un programme récursif calculant Fib(n)
Exercice 5 :

Soit la suite définie par :

Ecrire un programme récursif permettant de calculer le nième terme de la suite;
Exercice 6 :

Un nombre N est pair si (N-1) est impair, et un nombre N est impair si (N-1) est pair.
Ecrire deux fonctions récursives mutuelles pair (N) et impair (N) permettant de savoir si un nombre N est pair et si un nombre N est impair.

Exercice 7 :

Soit un tableau X de N entiers.

Ecrire une fonction récursive simple permettant de déterminer le maximum du tableau
Exercice 8 :

Un tableau X est trié par ordre croissant si x(i)<=x(i+1) pour i

Elaborer un algorithme récursif permettant de vérifier qu’un tableau X est trié ou non
Exercice 9 :

Un mot est un palindrome si on peut le lire dans les deux sans de gauche à droite et de droite à gauche. Exemple KAYAK est un palindrome.

Ecrire une fonction récursive permettant de vérifier si un mot est palindrome.
Exercice 10 :

Soit un tableau d’’entiers contenant des valeurs 0 ou bien 1. On appel composante connexe une suite contigue de nombres égaux à 1. On voudrait changer la valeur de chaque composante connexe de telle sorte que la première composante ai la valeur 2 la deuxième ai la valeur 3, la 3ème ait la valeur 4 et ainsi de suite. Réaliser deux fonctions :

  1. La première fonction n’est pas récursive et a pour rôle de chercher la position d’un 1 dans un tableau.
  2. La deuxième fonction est récursive. Elle reçoit la position d’un 1 dans une séquence et propage une valeur x à toutes les valeur 1 de la composante connexe.
Exercice 11 :

Soit une image binaire représentés dans une matrice à 2 dimension. Les éléments m[i][j] sont dits pixels et sont égaux soit à 0 soit à 1. Chaque groupement de pixels égaux à 1 et connectés entre eux forment une composante connexe(figure). L’objectifs est de donner une valeur différente de 1 à chaque composante (2 puis 3 puis 4 etc.)

  1. Ecrire une fonction récursive propager permettant de partir d’un point (i,j) situé à l’intérieur d’une composante connexe et de propager une étiquette T à tous les pixels situés à l’intérieur de la composante.
  2. Ecrire une fonction etiqueter permettant d’affecter une étiquette différente à chaque composante connexe.

Télécharger la correction 

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :