Exercices corrigés algorithme récursif

Les exercices corrigés suivants concernent le principe d’algorithme récursif, par exemple Fibonacci, les tours de Hanoï et bien d’autres cas mathématiques.

algorithme récursif

Упражнение 1

Réécrire les algorithmes suivants sous forme récursive sous forme terminal quand c’est possible.

algorithme récursif exercices corrigés récursif terminal récursité multiple arbre d'appels

algorithme récursif

algorithme récursif

Un dernier pour la route. Cette fois il faut comprendre ce qu’il fait avant de le rendre récursif terminal !

algorithme pgcd

algorithme récursif terminal

algorithme récursif terminal

algo3 est déjà récursif mais non terminal. Puisque l’algorithme renvoit 2^нет, on va changer sa structure pour le rendre terminal.

algorithme récursif terminal

Pour le dernier algorithme, il faut d’abord comprendre qu’il calcule le pgcd entre a et b. Faites un test à la main, vous comprendrez que le premier embranchement ne sert à rien, on va donc l’enlever pour la récursion. La variable r n’est pas présente pour remplacer la valeur de a et b, donc elle ne rentrera pas dans la récursion.

algorithme pgcd

Упражнение 2

Le problème de Fibonacci (1170 – 1250) :

« Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? Les lapins ne meurent jamais.”

Donc si on prend un exemple les 7 premiers mois.

Mois

1

2

3

4

5

6

7

Couple

1

1

2

3

5

8

13

a – Exprimez la population de couples du mois n en fonction des mois précédents.

b – Ecrire un algorithme itératif qui calcule le nombre de couples au bout de 12 mois.

c – Modifier l’algorithme itératif pour calculer le nombre de mois au bout duquel la population de couples de lapins dépasse 300.

d – Ecrire l’algorithme récursif pour calculer le nombre de couples de lapins après n mois.

a –

Le nombre de couples de lapins au mois n est la somme des couples existants le mois d’avant (au mois n − 1) et des couples naissants au mois n.

Or, le texte précise que tous les couples existants deux mois auparavant (au mois n − 2) se reproduisent.

Par conséquent, au mois n ≥ 2 le nombre de lapins est égale à la somme du mois n-1 et n-2. Au mois 0 et au mois 1, il n’existe qu’un seul couple.

b –

Exercices corrigés algorithme récursif algorithme récursif

c –

Exercices corrigés algorithme récursif algorithme récursif

d –

algorithme récursif fibonacci

On ne calculera pas la complexité la dessus. Pour ceux qui veulent perdre la tête je vous invite ici : https://miashs-www.u-ga.fr/prevert/Prog/Complexite/nombresFibonacci.html

Упражнение 3

a – Ecrire un algorithme qui calcule le maximum de 2 nombres réels 

b – Ecrire un algorithme récursif qui calcule le maximum de 3 nombres réels en utilisant l’algorithme du a. Montrer l’arbre d’appels.

c – Ecrire un algorithme récursif  qui calcule le maximum de 4 nombres réels en utilisant l’algorithme du a. Montrer l’arbre d’appels.

a –

algorithme récursif maximum

b –

algorithme récursif maximum

Ici, Maximum2 fait office de condition terminal de l’algorithme récursif. La pile d’appels est la suivante :

algorithme récursif maximum

c –

algorithme récursif maximum

La pile d’appels est la suivante :

algorithme récursif maximum

Упражнение 4

a – Est-ce que les algorithmes ci-dessous sont des algorithmes récursifs ? 

b – Est-ce qu’ils sont terminaux ?

c – Est-ce qu’ils se terminent ?

algorithme récursif log

algorithme récursif puissance

algorithme récursif somme

a –

Les algorithmes log et somme sont récursifs : chacun contient au moins un appel à lui même, par contre, puissance ne l’est pas : il fait appel à l’algorithme puis. Il faut remplacer puis par puissance.

b – 

log est terminal, puissance et somme ne le sont pas car ils demandent un calcul lors de la récursion.

c –

log se termine pour tout entier x. L’itération de la division entière par 2 mène à 0, et le cas de base 0 se termine par l’exécution de retourner. 

Pour l’algorithme puissance (corrigé), le cas de base 0 se termine par l’excéution de retourner. Si l’algorithme se termine pour la valeur n−1 alors il se termine aussi pour la valeur n est exécutant retourner. N’oubliez pas qu’un utilisateur peut rentrer n’importe quoi comme puissance(2, – 5) donc il faut bien vérifier sa terminaison.

somme ne se termine pas lorsque n est strictement positif. En effet, l’algorithme pour n se termine seulement si l’algorithme se termine pour n+1. Or, il n’existe pas d’entier strictement positif pour lesquels l’agorithme s’arrête.

Упражнение 5

a – On souhaite écrire une fonction récursive qui calcule le carré d’un entier. Pour cela il va falloir se servir d’une relation entre carre(n) et carre(n-1) sachant que carre(1)=1. Représenter la pile d’appels pour carre(5).

b – Les combinaisons sont un concept de mathématiques décrivant les différentes façons de choisir un nombre donné d’objets dans un ensemble de taille donnée. Par exemple combien il est possible de tirer 6 boules de Loto sur 60 dans le moulinet. Ou de piocher 3 cartes dans un jeu de tarot. La combinaison de choisir p éléments parmi n éléments se notent C(p,n)=(n/p)*C(p-1, n-1). On a aurri C(0,n)=1 et C(n,n)=1. 

Ecrire la fonction récursive non terminale puis la fonction récursive terminale, et montrer la pile d’appels pour C(3,7). Via la fonction terminale, en déduire la fonction itérative.

c – Pour les combinaisons, on préfère généralement éviter la méthode du b car les divisions peuvent créer des problèmes d’arrondis. On va plutôt se servir de la relation suivante : C(p,n)=C(p,n-1)*C(p-1, n-1). Ecrire la fonction récursive et la pile ou arbre d’appels pour C(2,4).

a – Pour trouver un lien entre carre(n) et carre(n-1), on utilise la formule : (n+ 1)² = n² + 2n+ 1. On l’écrit en fonction de n vers n-1 : n² = (n−1)²+2(n−1)+1 d’où carre(n)=carre(n-1)+2*n-1. Le tour est joué !

algorithme récursif carré

La pile d’appels est :

algorithme récursif carré

b – Tout est dit dans l’énoncé, il ne reste qu’à l’écrire.

algorithme récursif combinaison

Voici la liste d’appels pour C(3,7) :

algorithme récursif combinaison

Et maintenant pour la version terminale, c’est un peu plus compliqué car il faut se questionner sur ce qu’on doit garder en mémoire pour la récursion. A chaque itération on a fait n/p fois le précédent, donc n/p * (n-1)/(p-1). On aurait pu l’écrire n(n-1)/p(p-1). Donc on pourrait stocker d’un côté la multiplication de n décroissant et de l’autre de p décroissant.

algorithme récursif combinaison

Voici la pile d’appels pour C(3,7,1,1) :

algorithme récursif combinaison

On déduit de la fonction terminale la fonction itérative. Il suffit de faire un Tant Que la condition d’arrêt n’est pas atteinte.

algorithme récursif combinaison

c – On a déjà la relation récursive dans l’énoncé.

algorithme récursif combinaison

Voici l’arbre d’appels pour C(2,4) :

algorithme récursif combinaison

Упражнение 6

On définit la fonction de McCarthy comme suivant :

algorithme de mccarthy

Que fait la fonction pour n>100 ? pour n=98, 99, 100 ? En général pour n<=100 ?

On va faire un peu de mathématique… Si n > 100 on aura n-10. Le problème se pose quand on commence avec n<=100. Calculer pour 98, 99 et 100. On va faire une démonstration directe.

Pour n entre 90 et 100 compris – soit 11 valeur consécutive, ça nous servira plus tard. On fera Carthy(Carthy(n+11)) donc on dépassera la valeur de 100. Donc on aura Carthy(n+1) au final. Si n+1 n’est toujours pas supérieur à 100, on remet le couvert. Donc on s’arrête quand on passera de 100 à 101, or Carthy(101)=101-10=91.

En reprend ce qu’on a laissé au début du précédent paragraphe. Sur les 11 dernières valeurs consécutives, on aura un résultat de 91. On note que tout nombre entre 0 et 89, auquel on rajoute 11 tant que c’est inférieur à 90 aura une valeur finale entre 90 et 100 compris.

On en déduit que Carthy sur une valeur de 100 ou moins donnera la valeur de 91.

Il fallait bien un peu de mathématique. L’informatique n’est qu’une autre façon syntaxique de faire des maths !

Exercice 7

On parle de récursivité croisée lorsque deux fonctions s’appellent l’une l’autre récursivement.

On va tester sur une récursivité croisée pour savoir si un nombre est pair (vrai) ou impair (faux). Voici la proposition :

algorithme récursif croisé

Testez pour pair(2), impair(3), pair(3) et impair(2). L’algorithme est-il correct ? Sinon le changer pour vérifier la correction ← P.S: si le prof demande ça c’est que l’algo a un problème CQFD

Evidemment l’algo n’est pas correct. Prenons pair(3) → impair(2) → pair(1) → impair(0) → pair(-1) → impair(-2) → etc. C’est que les conditions d’arrêts ne marchent que si le nombre de la méthode pair est pair et la méthode impair est impair. On va seulement changer la méthode impair.

récursivité croisée pair impair

A vous de retester si c’est correct maintenant !

Exercice 8

Il est impossible de conclure sur le récursif sans parler des fameuses Tours de Hanoï (la hantise des étudiants et parfois aussi des chargés de TD et prof !). On va donc s’y prendre doucement.

tours de hanoi

On dispose de n plateaux de taille différentes, et de 3 tiges, numérotées de 0 à 2.

Initialement, tous les plateaux sont situés sur la tige i. Le but est de les transférer sur la tige j, en respectant les règles suivantes :

– On ne peux déplacer qu’un plateau à la fois.

– Les plateaux doivent toujours rangés par taille décroissante sur une tige (le plus grand en bas puis par ordre décroissant en remontant sur la tige).

1 – Résolvez le problème à la main si n = 2, i = 0 et j = 2 (donc 2 plateaux, ils sont tous de base sur la tige 0 et on veut les mettre sur la tige 2).

2 – Résolvez le problème à la main si n = 3, i = 0 et j = 2 (donc 3 plateaux, ils sont tous de base sur la tige 0 et on veut les mettre sur la tige 2).

3 – Supposez qu’un de vos amis sache résoudre le problème pour un certain n, et n’importe quels i et j. On vous demande de résoudre le problème pour n + 1. Vous avez le droit d’utiliser l’aide de votre ami. Comment vous y prenez-vous ?

4 – Ecrire la fonction récursive qui permet de résoudre ce problème pour tous n, i, j (Si vous y arrivez sans tricher félicitation ! Sinon c’est normal on est presque tous passé par ce grand moment d’incompréhension et de remise en cause de sa carrière…)

1 – 

On transfère le petit plateau de 0 à 1. 

On transfère le grand plateau de 0 à 2. 

On transfère le petit plateau de 1 à 2.

2 –

On transfère le petit plateau de 0 à 2. 

On transfère le plateau moyen de 0 à 1.

On transfère le petit plateau de 2 à 1. (on a déplacé 2 plateaux de 0 vers 1). 

On transfère le grand plateau de 0 à 2. 

On transfère le petit plateau de 1 à 0. 

On transfère le plateau moyen de 1 à 2. 

On transfère le petit plateau de 0 à 2. (on a déplacé 2 plateaux de 1 vers 2).

3 –

On déplacer n plateaux de i à l’emplacement qui n’est ni i ni j (par les séries de trois manipulations du point 2). On déplace ensuite le dernier plateau (le plus gros) de i à j. On remet à contribution l’ami pour déplacer les n plateaux vers j. 

4 –

Si vous trouvez ça… champagne ! On va renommé pour plus de facilité les tiges en d pour celle de départ, a pour celle d’arrivé et r pour celle qui reste

tours de hanoi

Делиться
ru_RURU
%d такие блоггеры, как: