Exercices⚓︎
Exercice 1
Écrire une fonction récursive puissance
qui prend en paramètres deux nombres x
et n
qui renvoie le nombre \(x^n\).
Correction
1 2 3 4 5 |
|
Exercice 2
On rappelle que le PGCD (plus grand diviseur commun de deux nombres) vérifie la propriété suivante : si la division euclidienne de \(a\) par \(b\) s'écrit \(a = b \times q + r\), alors \(pgcd(a,b)=pgcd(b,r)\).
Cette propriété est à la base de l'algorithme d'Euclide
Exemple : \(pgcd(24,18)=pgcd(18,6)=pgcd(6,0)\), donc \(pgcd(24,18)=6\)
Écrire une fonction récursive pgcd
qui prend en paramètres deux nombres a
et b
et qui renvoie leur PGCD.
Exercice 3
La conjecture de Syracuse (ou de Collatz) postule ceci :
Prenons un nombre \(n\) : si \(n\) est pair, on le divise par 2, sinon on le multiplie par 3 puis on ajoute 1. On recommence cette opération tant que possible. Au bout d'un certain temps, on finira toujours par tomber sur le nombre 1.
Q1. Écrire une fonction récursive syracuse
qui prend en paramètres une entier n
et qui écrivant tous les termes de la suite de Syracuse commençant à n
, et s'arrêtant (on l'espère...) à la valeur 1.
Correction
1 2 3 4 5 6 7 8 |
|
Remarque : comme notre fonction syracuse
ne renvoie pas de valeur numérique (elle ne fait qu'afficher une valeur), le return
du test de parité est en fait inutile.
Mais le return
du cas de base est lui primordial pour que le code s'arrête !
1 2 3 4 5 6 7 8 |
|
Q2. On appelle «temps de vol» le nombre d'étapes nécessaires avant de retomber sur 1. Modifier la fonction précédente afin qu'elle affiche le temps de vol pour tout nombre n
.
Exercice 4
Reproduire le dessin suivant, à l'aide du module turtle
.
turtle
est un hommage au langage LOGO inventé par Seymour Papert au MIT à la fin des années 60.
Exercice 5
Proposer une nouvelle fonction récursive puissance_mod
qui prend en paramètres deux nombres x
et n
et qui renvoie le nombre \(x^n\). Pour optimiser la fonction déjà construite à l'exercice 1, utiliser le fait que :
- si \(n\) est pair, \(a^n=(a \times a)^{n/2}\)
- sinon \(a^n=a \times (a \times a)^{(n-1)/2}\)
Exercice 6
Écrire un algorithme récursif dicho_recursive
qui prend en paramètres une liste triée (par ordre croissant) lst
et une valeur val
et qui renvoie un booléen indiquant la présence ou non de la valeur val
dans une liste lst
.
Exemple d'utilisation :
>>> lst = [2,4,5,5,7,9,11,15,16,18,19]
>>> dicho_recursive(lst, 16)
[2, 4, 5, 5, 7, 9, 11, 15, 16, 18, 19]
[9, 11, 15, 16, 18, 19]
[16, 18, 19]
[16]
True
>>> dicho_recursive(lst, 6)
[2, 4, 5, 5, 7, 9, 11, 15, 16, 18, 19]
[2, 4, 5, 5, 7]
[5, 5, 7]
[5, 7]
[5]
False
Aide :
Les techniques de slicing (hors-programme) permettent de couper une liste en deux :
>>> lst = [10, 12, 15, 17, 18, 20, 22]
>>> lst[:3]
[10, 12, 15]
>>> lst[3:]
[17, 18, 20, 22]
Exercice 7
On considère le jeu des Tours de Hanoï. Le but est de faire passer toutes les assiettes de A vers C, sachant qu'une assiette ne peut être déposée que sur une assiette de diamètre inférieur.
Une version jouable en ligne peut être trouvée ici.
- S'entraîner et essayer d'établir une stratégie de victoire.
- Observer les images ci-dessous :
Écrire une fonction récursive hanoi(n, depart, inter, arrivee)
qui donnera la suite d'instructions (sous la forme " A vers C") pour faire passer une pile de taille n de depart
vers arrivee
en prenant inter
comme intermédiaire.
Exercice 8
Cet exercice a pour objectif le tracé du flocon de Von Koch.
L'idée est de répéter de manière récursive la transformation ci-dessous : chaque segment de longueur l
donne naissance à 4 segments de longueur l/3
, en construisant une pointe de triangle équilatéral sur le deuxième tiers du segment.
Q1. Créer une fonction récursive floc(n, l)
qui trace à une «profondeur» n
un segment de longueur l
.
Indications
- l'instruction de tracé n'a lieu que quand
n
vaut 0. - l'étape
n
fait 4 appels successifs à l'étapen-1
.
Q2. Créer une fonction triangle(n, l)
qui trace le flocon complet.
Exercice 9
- Exercice 04.2 de la BNS 2022
- Application sur Capytale à retrouver ici
Exercice 10
Exercice 4 du sujet Amérique du Nord J1
Exercice 11
Exercice 1 du sujet Centres Étrangers J2 2022
Exercice 12
Exercice 1 du sujet Amérique du Nord J2 2024