Entraînement Récursivité - 8 Novembre

CPUMons : exercices sur la récursivité (08/11/2018).
Pour les prochains exercices les données reçues seront lues grâce à des input() et non en
arguments de vos fonctions.
De plus, les programmes demandés doivent, au moins en partie, être récursifs.
Question 0 : Compter à rebours (par récursivité).

Afin de mieux comprendre la récursivité, vous décidez d’écrire une fonction récursive
d’un algorithme basique : celui qui affiche tous les naturels inférieurs à un certain nombre.
Entrée : - Un naturel N.
Sortie : Aucune.
Effet de bord : Affiche tous les naturels inférieurs à N, chacun sur une ligne dans l’ordre
décroissant.
Exemple :
Entrée :
4
Sortie :
4
3
2
1
0
Question 1 : exponentiation rapide.

Il existe une technique afin de calculer plus rapidement un nombre à une puissance
naturelle qu’avec la méthode « naïve ». En effet, la méthode naïve consiste à calculer xn en
faisant x*x*…*x (n fois) ; tandis que cette méthode se base sur la parité de l’exposant et utilise
les propriétés associées.
En effet, on a :
Si n = 0 : xn = 1
Sinon, si n pair : xn = (xn/2)2
Sinon, si n impair : xn = x * xn-1
Implémentez cette technique via une fonction récursive.
Entrée : - Deux nombres séparés par un espace : x et n avec n ∈ ℕ.
Sortie : - la valeur de xn.
Effet de bord : Aucun.
Question 2 : La tête à Toto ?!

Qui n’a jamais entendu parler du résultat de 0 + 0 ? (cf. : nom de l’exercice)
En effet, même en informatique, on voit « clairement » :
(0 + 0) (1)
qui donne bien la tête DE Toto (si vous n’en êtes pas convaincu, convainquez-vous-en !).
On peut aussi constater que, mathématiquement, (0 + 0) = 0. (1.1)
De ce fait, on peut utiliser (1.1) dans (1) pour remplacer toutes les occurrences de ‘0’
par (0 + 0), ce qui donne :
((0 + 0) + (0 + 0)) (2)
On peut ainsi procéder encore une fois et remplacer tous les ‘0’ dans (2), par « (0 + 0) ».
On a donc :
(((0 + 0) + (0 + 0)) + ((0 + 0) + (0 + 0))) (3)
Il vous est donc demandé d’écrire un programme qui affichera la tête DE Toto
correspondante après N remplacements consécutifs des ‘0’ par ‘(0 + 0)’.
Entrée : - Un nombre naturel N.
Sortie : - Aucune
Effet de bord : - Imprime la tête DE Toto correspondante après N remplacements
consécutifs de ‘0’ par ‘(0 + 0)’.
Exemples :
Entrée 1 :
3
Sortie 1 :
(((0 + 0) + (0 + 0)) + ((0 + 0) + (0 + 0)))
Entrée 2 :
0
Sortie 2 :
0
Question 3 : pgcd et ppcm.
Vous venez d’apprendre dans votre cours de mathématiques qu’il existait une propriété
très pratique pour calculer le pgcd de deux nombres tous deux non nuls. En effet, soient a, b
deux nombres naturels tels que b ≠ 0, on a la propriété suivante :
pgcd(a, b) = pgcd(b, a mod b)
Veuillez écrire un programme qui va calculer le pgcd et le ppcm de deux nombres. L’une
des deux fonctions DOIT être récursive. (Aide : le calcul du ppcm peut être écrit en une seule
ligne.)
Entrée : - deux nombres naturels, a et b.
Sortie : - un tuple composé du pgcd(a, b) et ppcm(a, b)
Effet de bord : - Aucun.
Exemple :
Entrée :
36 132
Sortie :
(12, 396)
Question 4 : Les Tours de Hanoï.

(Attention : exercice plus difficile !!!)
Le problème des Tours de Hanoï est un jeu de réflexion imaginé par le mathématicien
français Edouard Lucas.
Le problème consiste à déplacer des disques de diamètres différents d'une tour de

« départ » à une tour d'« arrivée » en passant par une tour « intermédiaire », et ceci en un
minimum de coups, tout en respectant les règles suivantes :
• on ne peut déplacer plus d'un disque à la fois ;

• on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un
emplacement vide.
Voici un exemple de résolution lorsque la tour est constituée de 3 disques :
Il vous est donc demandé de rédiger un algorithme de MOINS DE 10 LIGNES afin de

résoudre ce problème dans le cas général où la tour de départ est formée de N disques.
Entrée : - Un entier N inférieur à 15.
Sortie : - Aucune.
Effet de bord : - Pour chaque déplacement d’une tour A vers une tour B , le
programme affiche : ‘A → B’.

Entraînement Récursivité - 8 Novembre

Transféré par

Droits d'auteur :

Formats disponibles

Entraînement Récursivité - 8 Novembre

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Entraînement Récursivité - 8 Novembre

Transféré par

Droits d'auteur :

Formats disponibles

CPUMons : exercices sur la récursivité (08/11/2018).

Question 0 : Compter à rebours (par récursivité).

Question 1 : exponentiation rapide.

Question 2 : La tête à Toto ?!

Question 4 : Les Tours de Hanoï.

Le problème consiste à déplacer des disques de diamètres différents d'une tour de

• on ne peut déplacer plus d'un disque à la fois ;

Il vous est donc demandé de rédiger un algorithme de MOINS DE 10 LIGNES afin de

Entrée : - Un entier N inférieur à 15.

Vous aimerez peut-être aussi