madamasterclass.com
-
Connexion
Connexion
Exercices corrigés sur les langages et programmation en python - récursivité
Soit \(u_n\) la suite d'entiers définie par
\[
\left \{
\begin{array}{c @{=} c}
u_{n+1} = \frac{u_n}{2} & si\: u_n \: est\: pair, \\
u_{n+1} = 3 . u_n +1 & sinon.
\end{array}
\right.
\]
avec \(u_0\) un entier quelconque plus grand que \(1\).
Écrire une fonction récursive syracuse \((u_n)\) qui affiche les valeurs successives de la suite un tant que un est plus grand que \(1\).
La conjecture de Syracuse affirme que, quelle que soit la valeur de \(u_0\), il existe un indice \(n\) dans la suite tel que \(u_n = 1\). Cette conjecture défie toujours les mathématiciens.
def syracuse(u):
# Affiche la valeur actuelle de u
print(u, end=' ')
# Cas de base : si u est 1, la suite s'arrête
if u == 1:
return
# Applique la règle de la suite
if u % 2 == 0: # u est pair
syracuse(u // 2)
else: # u est impair
syracuse(3 * u + 1)
# Exemple d'utilisation
u0 = 7 # Choisissez une valeur initiale pour u0 (doit être > 1)
print("Suite de Syracuse à partir de", u0, ":")
syracuse(u0)
On considère la suite \((u_n)\) définie par la relation de récurrence suivante, où \(a\) et \(b\) sont des réels quelconques :
\[
\left \{
\begin{array}{c @{=} c}
a \in ℝ & si\: n \: =\: 0, \\
b \in ℝ & si\: n \: =\: 1, \\
3u_{n-1} + 2u_{n-2} + 5 \: \forall \: \: n \geq \: 2.
\end{array}
\right.
\]
Écrire une fonction récursive \(serie(n, a, b)\) qui renvoie le \(n^{ème}\) terme de cette suite pour des valeurs \(a\) et \(b\) données en paramètres.
def serie(n, a, b):
# Cas de base : si n est 0, retourner a
if n == 0:
return a
# Cas de base : si n est 1, retourner b
elif n == 1:
return b
# Cas général : appliquer la relation de récurrence
else:
return 3 * serie(n - 1, a, b) + 2 * serie(n - 2, a, b) + 5
# Exemple d'utilisation
n = 5
a = 1 # Exemple de valeur pour a
b = 2 # Exemple de valeur pour b
terme = serie(n, a, b)
print("Le terme u_{} de la suite est : {}".format(n, terme))
Écrire une fonction récursive \(boucle (i, k)\) qui affiche les entiers entre \(i\) et \(k\). Par exemple, \(boucle (0,3)\) doit afficher \(0\:\:\: 1\:\:\: 2\:\:\: 3\).
def boucle(i, k):
# Affiche l'entier actuel
print(i, end=' ')
# Cas de base : si i atteint k, on arrête la récursion
if i < k:
boucle(i + 1, k)
# Exemple d'utilisation
boucle(0, 3)
Écrire une fonction récursive \(pgcd (a, b)\) qui renvoie le \(PGCD\) de deux entiers \(a\) et \(b\).
def pgcd(a, b):
# Cas de base : si b est 0, le PGCD est a
if b == 0:
return a
# Appel récursif : PGCD de b et le reste de a divisé par b
return pgcd(b, a % b)
# Exemple d'utilisation
a = 48
b = 18
resultat = pgcd(a, b)
print("Le PGCD de", a, "et", b, "est :", resultat)
Écrire une fonction récursive \(nombre\_de\_chiffres (n)\) qui prend un entier positif ou nul \(n\) en argument et renvoie son nombre de chiffres. Par exemple, \(nombre\_de\_chiffres (34126)\) doit renvoyer \(5\).
def nombre_de_chiffres(n):
# Cas de base : si n est 0, il a 1 chiffre
if n == 0:
return 1
# Cas de base : si n est un chiffre unique (1 à 9)
elif n < 10:
return 1
# Appel récursif : divise n par 10 et ajoute 1 au compteur
else:
return 1 + nombre_de_chiffres(n // 10)
# Exemple d'utilisation
n = 34126
resultat = nombre_de_chiffres(n)print("Le nombre de chiffres dans", n, "est :", resultat)
print("Le nombre de chiffres dans", n, "est :", resultat)
Explication :
1. Cas de base :
• Si `n` est 0, la fonction renvoie 1, car 0 a un chiffre.
• Si `n` est un chiffre unique (entre 1 et 9), la fonction renvoie 1.
2. Appel récursif :
Pour des valeurs supérieures à 9, la fonction divise `n`
par 10 pour supprimer le dernier chiffre et appelle récursivement `nombre_de_chiffres(n // 10)`,
en ajoutant 1 pour compter le chiffre supprimé.
Exemple d'utilisation :
Si vous appelez `nombre_de_chiffres(34126)`, la fonction renverra 5, car l'entier a 5 chiffres.
En s'inspirant de l'exercice 5, écrire une fonction récursive \(nombre\_de\_bits\_1(n)\) qui prend un entier positif ou nul et renvoie le nombre de bits valant \(1\) dans la représentation binaire de \(n\). Par exemple, \(nombre\_de\_bits\_1 (255)\) doit renvoyer \(8\).
def nombre_de_bits_1(n):
# Cas de base : si n est 0, il n'y a pas de bits à 1
if n == 0:
return 0
# Vérifie si le dernier bit est 1 (n & 1) et appelle récursivement avec n // 2
else:
return (n & 1) + nombre_de_bits_1(n // 2)
# Exemple d'utilisation
n = 255
resultat = nombre_de_bits_1(n)
print("Le nombre de bits à 1 dans", n, "est :", resultat)
Explication :
1. Cas de base :
Si `n` est 0, la fonction renvoie 0,
car il n'y a pas de bits à 1 dans la représentation binaire de 0.
2. Calcul récursif :
• La fonction utilise l'opération `n & 1` pour vérifier si le dernier bit de `n` est 1.
Si c'est le cas, cela renvoie 1, sinon 0.
• Elle appelle ensuite récursivement `nombre_de_bits_1(n // 2)` pour
traiter le reste de l'entier en décalant les bits vers la droite.
Exemple d'utilisation :
Si vous appelez `nombre_de_bits_1(255)`, la fonction renverra 8,
car la représentation binaire de 255 est `11111111`, qui contient 8 bits à 1.
Écrire une fonction récursive \(appartient (v, t, i)\) prenant en paramètres une valeur \(v\), un tableau \(t\) et un entier \(i\) et renvoyant \(True\) si \(v\) apparaît dans \(t\) entre l'indice \(i\) (inclus) et \(len (t)\) (exclu), et \(False\) sinon. On supposera que \(i \)est toujours compris entre \(0\) et \(len (t)\).
def appartient(v, t, i):
# Cas de base : si i est égal à la longueur du tableau, v n'est pas trouvé
if i >= len(t):
return False
# Vérifie si l'élément courant est égal à v
if t[i] == v:
return True
# Appel récursif avec l'index suivant
return appartient(v, t, i + 1)
# Exemple d'utilisation
tableau = [1, 2, 3, 4, 5]
valeur = 3
indice = 2
resultat = appartient(valeur, tableau, indice)
print("La valeur", valeur, "appartient au tableau à partir de l'indice", indice, ":", resultat)
Explication :
1. Cas de base :
Si `i` est égal à la longueur de `t`, cela signifie que nous avons atteint la fin du tableau sans trouver `v`,
donc la fonction renvoie `False`.
2. Vérification de l'élément courant :
Si l'élément à l'indice `i` est égal à `v`,
la fonction renvoie `True`.
3. Appel récursif :
Si l'élément courant n'est pas égal à `v`,
la fonction s'appelle récursivement avec l'indice `i + 1` pour vérifier le reste du tableau.
Exemple d'utilisation :
Dans l'exemple donné, si vous appelez `appartient(3, [1, 2, 3, 4, 5], 2)`,
la fonction renverra `True`, car la valeur 3 apparaît dans le tableau à partir de l'indice 2.
Le triangle de Pascal (nommé ainsi en l'honneur du mathématicien Blaise Pascal) est une présentation des coefficients binomiaux sous la forme d'un triangle défini ainsi de manière récursive:
\[
\left \{
\begin{array}{c @{=} c}
1 & si\:\: p \: =\: 0 \:\:ou \:\: n \: =\: p, \\
C(n-1,p-1) + C(n-1,p) & sinon.
\end{array}
\right.
\]
Écrire une fonction récursive \(C(n,p)\) qui renvoie la valeur de \(C(n, p)\), puis dessiner le triangle de Pascal à l'aide d'une double boucle \(for\) en faisant varier \(n\) entre \(0\) et \(10\).
def C(n, p):
# Cas de base : C(n, 0) et C(n, n) sont tous deux égaux à 1
if p == 0 or n == p:
return 1
# Cas général : utilise la relation de récurrence
return C(n - 1, p - 1) + C(n - 1, p)
# Affichage du triangle de Pascal
def triangle_de_pascal(n):
for i in range(n + 1):
# Affiche les espaces pour former le triangle
print(" " * (n - i), end="")
for j in range(i + 1):
print(C(i, j), end=" ")
print() # Nouvelle ligne après chaque ligne du triangle
# Exemple d'utilisation
n = 10
triangle_de_pascal(n)
Explication :
1. Fonction `C(n, p)` :
• Cas de base : Si \(p = 0\) ou \(n = p\), la fonction renvoie 1.
• Cas général : La fonction utilise la relation de récurrence pour calculer \(C(n, p)\).
2. Fonction `triangle_de_pascal(n)` :
• Cette fonction génère et affiche le triangle de Pascal jusqu'à la ligne \(n\).
• Une boucle externe parcourt les lignes du triangle,
et une boucle interne parcourt les éléments de chaque ligne.
• Des espaces sont ajoutés avant chaque ligne pour aligner le triangle correctement.
Résultat :
Lorsque vous exécutez le code, vous obtiendrez une représentation du triangle de Pascal jusqu'à \(n = 10\) :
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Chaque ligne du triangle représente les coefficients binomiaux pour une valeur donnée de \(n\).
La courbe de Koch est une figure qui s'obtient de manière récursive. Le cas de base à l'ordre 0 de la récurrence est simplement le dessin d'un segment d'une certaine longueur 1, comme ci-dessous.
Le cas récursif d'ordre \(n\) s'obtient en divisant ce segment en trois morceaux de même longueur \(1/3\), puis en dessinant un triangle équilatéral dont la base est le morceau du milieu, en prenant soin de ne pas dessiner cette base. Cela forme une sorte de chapeau comme dessiné sur la figure de droite ci-dessus. On réitère ce processus à l'ordre \(n-1\) pour chaque segment de ce chapeau (qui sont tous de longueur \(1/3\)). Par exemple, les courbes obtenues à l'ordre 2 et 3 sont données ci-dessous (à gauche et à droite, respectivement).
Écrire une fonction \(koch (n, 1)\) qui dessine avec \(Turtle\) un flocon de Koch de profondeur \(n\) à partir d'un segment de longueur \(1\).
Éducation
solution en cours ...
Écrire une fonction récursive \(dec\_to\_bin(n:int)->list\) qui renvoie la représentation binaire d’un nombre \(n\) sous forme d'une liste.
Par ex: \(dec\_to\_bin(5)\) renvoie \([1,0,1]\)
def dec_to_bin(n: int) -> list:
# Cas de base : si n est 0, retourner une liste vide
if n == 0:
return []
# Appel récursif : divise n par 2 et ajoute le reste à la liste
return dec_to_bin(n // 2) + [n % 2]
# Exemple d'utilisation
n = 5
resultat = dec_to_bin(n)
print("La représentation binaire de", n, "est :", resultat)
Explication :
1. Cas de base :
Si \(n\) est égal à 0, la fonction retourne une liste vide.
Cela signifie que nous n'avons pas encore de bits à ajouter.
2. Appel récursif :
La fonction appelle récursivement `dec_to_bin(n // 2)`,
qui traite la division entière de \(n\) par 2.
Cela permet de construire la représentation binaire en décomposant le nombre.
3. Construction de la liste :
À chaque niveau de récursion, le reste de \(n\) divisé par 2 (`n % 2`) est ajouté à la fin de la
liste retournée par l'appel récursif.
Exemple d'utilisation :
Si vous appelez `dec_to_bin(5)`, la fonction renverra \([1, 0, 1]\),
qui est la représentation binaire de 5.
Vous devez écrire une fonction récursive qui retourne la puissance d'un nombre.
1. Écrire une fonction puissance(base, exp) qui calcule \( \text{base}^{\text{exp}} \) de manière récursive.
2. Tester votre fonction avec des valeurs telles que \( \text{base} = 2 \) et \( \text{exp} = 3 \).
def puissance(base, exp):
if exp == 0:
return 1
return base * puissance(base, exp - 1)print(puissance(2, 3)) # Retourne 8
Écrire une fonction récursive pour inverser une chaîne de caractères.
1. Écrire une fonction inverser_chaine(chaine) qui retourne la chaîne inversée.
2. Tester votre fonction avec la chaîne "Python".
def inverser_chaine(chaine):
if len(chaine) == 0:
return ""
return chaine[-1] + inverser_chaine(chaine[:-1])print(inverser_chaine("Python")) # Retourne "nohtyP"
Le nombre de Catalan est une suite de nombres qui ont de nombreuses applications en combinatoire, notamment dans le comptage des façons de parenthésier une expression ou de compter des chemins dans une grille. Le nième nombre de Catalan peut être calculé par la formule :
\[ C(n) = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} \]
1. Écrire une fonction catalan(n) qui retourne le nième nombre de Catalan.
2. Tester votre fonction avec \( n = 5 \).
def catalan(n):
if n == 0:
return 1
result = 0
for i in range(n):
result += catalan(i) * catalan(n - 1 - i)
return resultprint(catalan(5)) # Retourne 42
Écrire une fonction récursive pour compter le nombre de chiffres dans un entier.
1. Écrire une fonction compter_chiffres(n) qui retourne le nombre de chiffres dans l'entier \( n \).
2. Tester votre fonction avec des nombres comme 12345 et 100000.
def compter_chiffres(n):
if n < 10:
return 1
return 1 + compter_chiffres(n // 10)print(compter_chiffres(12345)) # Retourne 5
print(compter_chiffres(100000)) # Retourne 6
Créer une fonction récursive pour trouver le maximum dans une liste.
1. Écrire une fonction maximum(liste) qui retourne le plus grand élément de la liste.
2. Tester votre fonction avec la liste [3, 5, 2, 8, 1].
def maximum(liste):
if len(liste) == 1:
return liste[0]
max_suivant = maximum(liste[1:])
return max(liste[0], max_suivant)print(maximum([3, 5, 2, 8, 1])) # Retourne 8
Écrire une fonction récursive pour déterminer si une chaîne de caractères est un palindrome.
1. Écrire une fonction est_palindrome(chaine) qui retourne True si la chaîne est un palindrome, sinon False.
2. Tester votre fonction avec des chaînes comme "radar" et "python".
def est_palindrome(chaine):
if len(chaine) <= 1:
return True
if chaine[0] != chaine[-1]:
return False
return est_palindrome(chaine[1:-1])print(est_palindrome("radar")) # Retourne True
print(est_palindrome("python")) # Retourne False
La suite de Lucas est une suite de nombres qui commence par 2 et 1, et chaque terme suivant est la somme des deux termes précédents. Ainsi, les premiers nombres de la suite sont : 2, 1, 3, 4, 7, 11, 18, etc.
1. Écrire une fonction lucas(n) qui retourne le nième nombre de Lucas.
2. Tester votre fonction avec des valeurs comme \( n = 5 \).
def lucas(n):
if n == 0:
return 2
if n == 1:
return 1
return lucas(n - 1) + lucas(n - 2)print(lucas(5)) # Retourne 11
Écrire une fonction récursive pour calculer la somme des chiffres d'un nombre entier.
1. Écrire une fonction sommes_chiffres(n) qui retourne la somme des chiffres de \( n \).
2. Tester votre fonction avec des nombres comme 123 et 4567.
def sommes_chiffres(n):
if n == 0:
return 0
return n % 10 + sommes_chiffres(n // 10)print(sommes_chiffres(123)) # Retourne 6
print(sommes_chiffres(4567)) # Retourne 22
Créer une fonction récursive pour générer les permutations d'une chaîne de caractères.
1. Écrire une fonction permutations(chaine) qui retourne une liste de toutes les permutations possibles de la chaîne.
2. Tester votre fonction avec la chaîne "abc".
def permutations(chaine):
if len(chaine) == 1:
return [chaine]
perms = []
for i, char in enumerate(chaine):
for perm in permutations(chaine[:i] + chaine[i+1:]):
perms.append(char + perm)
return permsprint(permutations("abc")) # Retourne ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Écrire une fonction récursive pour compter le nombre de fois qu'un élément apparaît dans une liste.
1. Écrire une fonction compter_occurrences(liste, element) qui retourne le nombre d'occurrences de element dans liste.
2. Tester votre fonction avec une liste et un élément choisi.
def compter_occurrences(liste, element):
if not liste:
return 0
return (1 if liste[0] == element else 0) + compter_occurrences(liste[1:], element)print(compter_occurrences([1, 2, 3, 1, 4, 1], 1)) # Retourne 3
Les mathématiques ont souvent la réputation d'être une discipline austère et difficile, mais ...
Read more.Plongez dans l'univers fascinant des suites numériques, où chaque terme révèle des patterns surprenants et des applications pratiques dans les mathématiques et au-delà.
Read more.Découvrez comment les fonctions tissent des liens entre les nombres et les concepts, transformant des idées abstraites en outils puissants pour résoudre des problèmes du quotidien.
Read more.
