tite fractale

Récursivité, exercices

Tous les exercices de cette page sont d’abord à rédiger en pseudo-code avec un papier et un crayon. Une fois que le professeur à contrôlé votre travail, tester sur machine en Python (penser aux doctests).

1. Contrôle de l’entrée utilisateur

Écrire une procédure récursive qui demande un nombre positif à l’utilisateur et ne retournera ce nombre que s’il est positif. Sinon, demander à l’utilisateur de recommencer.

def entree_positive():
    n = int(input())
    if ... :
        ...
    else:
        ...

nombre = entree_positive()
print(nombre)

Notez bien que l’on veut pouvoir affecter le résultat de la procédure à une variable (voir ci-dessus). Le test ne doit pas afficher None.

2. Factorielle

Retrouver la fonction récursive qui calcule la factorielle d’un nombre entier (vue en cours).

Rappels :

$$\begin{aligned} 4! &= 4 × \underbrace{3×2×1}_{3!} \\\\ n! &= n × \underbrace{(n-1)×…×2×1}_{(n-1)!} \\\\ \end{aligned}$$

3. Produit et Puissance

Écrire une fonction récursive qui calcule le produit de deux entiers positifs, puis une autre qui élève un nombre flottant à une puissance entière.

$m×n = m + m×(n-1)$
$m^n = m × m^{(n-1)}$

L’algorithme de la somme vu en cours et ceux du produit et de la puissance auraient-il pu être étendus aux flottants ?

4. Division euclidienne

On considère la division euclidienne de n par d.

4.1. Première version

Écrire deux fonctions récursives :

Le quotient est nul si … (point d’appui). Sinon, c’est qu’on peut faire un paquet de plus que dans la division de … par ….
Le reste vaut `n` si … (le même point d’appui). Sinon, le reste est le même que dans la division de … par … (plus facile que le quotient car il n’y a pas de calcul à faire sur le retour de l’appel récursif).
Sur un exemple : $$\begin{array}{lclcc} 7 & = & 3&×&2 + 1 \\ 7 - 2 & = & (3-1)&×&2 + 1 \\ \end{array}$$ On voit que quand on isole un paquet de 2, le reste ne varie pas, mais le quotient diminue d’une unité.

4.2. Deuxième version

Écrire une procédure récursive qui a pour paramètres :

et qui affecte respectivement à q et à r le quotient et le reste de la division euclidienne de n par d.

5. PGCD

Écrire l’algorithme d’Euclide sous la forme d’une fonction récursive.

Remarque : Il est intéressant de remarquer qu’il n’est pas utile de mettre des deux nombres dans l’ordre. Cela se fait en quelque sorte « tout seul ».

6. Travail sur les listes

De la même façon que dans le cours, écrire les fonctions récursives :

Pour aller plus loin :

En utilisant l’instruction Python (pas besoin de pseudo-code préalable) liste.append(valeur), écrire les fonctions :

7. Calcul de Pi

formules pour calculer Pi

8. Nombre en chiffres romains

On a les valeurs suivantes :

M = 1000
D = 500
C = 100
L = 50
X = 10
V = 5
I = 1

Si le premier chiffre d'un nombre romain a une valeur inférieure au deuxième, alors on le soustrait de la valeur de tout le reste, sinon on l'additionne à la valeur de tout le reste.

Si le nombre romain a un seul chiffre, alors on prend simplement la correspondance (M=1000, …).

Évidemment, pour calculer tout le reste, il faut appliquer à nouveau ce principe, ce qui rend ce principe récursif.

Écrire cet algorithme en pseudo-code, puis le tester en Python une fois qu’il a été vérifié par le professeur.

Rappel : en Python, une chaîne de caractères est une liste.

>>> 'blabla'[0]
'b'
>>> 'blabla'[1:]
'labla'
Soit `evaluer` la fonction qui évalue un nombre écrit en chiffres romains et `valeur` la fonction qui retourne la `valeur` d'un chiffre romain.
Point d'appui :
Si r est un simple caractère,
`evaluer(r) = valeur(r)`.
Cas général :
Si la valeur du premier chiffre romain est supérieure à la valeur du deuxième,
`evaluer(r) = evaluer(reste) + valeur(premier chiffre)`.
Si la valeur du premier chiffre romain est plus petite que la valeur du deuxième,
`evaluer(r) = evaluer(reste) - valeur(premier chiffre)`.

9. Triangle de Pascal

Le triangle de Pascal est le tableau des coefficients qui sont utilisés pour le développement de certaines expressions comme : $(a+b)^2$ ou $(a+b)^n$ (entre autres).

Ce triangle est le suivant :

    0 1 2 3 4
0 : 1
1 : 1 1
2 : 1 2 1
3 : 1 3 3 1
4 : 1 4 6 4 1

On obtient chaque coefficient en additionnant le nombre qui lui est situé au-dessus ainsi que celui qui lui est situé au-dessus à gauche.

Le numéro qui est en tête de chaque ligne de ce triangle est la puissance à laquelle $a+b$ est élevée :

$$\begin{aligned} (a+b)^0 &= 1 \\\\ (a+b)^1 &= 1×a + 1×b \\\\ (a+b)^2 &= 1×a^2 + 2×ab + 1×b^2 \\\\ (a+b)^3 &= 1×a^3 + 3×a^2b + 3×ab^2 + 1×b^3 \\\\ (a+b)^4 &= 1×a^4 + 4×a^3b + 6×a^2b^2 + 4×ab^3 + 1×b^4 \\\\ \end{aligned}$$

On remarque que la diagonale est toujours à 1 (point d'appui). On remarque que la première colonne est toujours à 1 (point d'appui). Pour tout autre élément qui se trouve à la ligne y et à la colonne x, le résultat est la somme de l'élément de coordonnées $(y-1,x)$ et de l'élément de coordonnées $(y-1,x-1)$.

Écrire cet algorithme en pseudo-code, puis le tester en Python une fois qu’il a été vérifié par le professeur.

Une fois sur la machine, il y a deux façons de vérifier votre algorithme :

Pour aller plus loin :

Il peut être intéressant de vérifier certaines des propriétés du triangle de Pascal, notamment celle avec la suite de Fibonacci que l’on a vue en cours.

10. Calcul de la racine carrée par la méthode de Newton

Voir l’article Wikipedia.

Soit $X$ le nombre dont on recherche la racine carrée et $R_1$ une valeur approchée de celle-ci. La formule suivante nous fournit une valeur beaucoup plus précise, que nous nommerons $R_2$ :

$$ R_2 = \frac{R_1 + \frac{X}{R_1}}{2}$$

Appliquer la formule pour $X = 5$ et $R_1 = 2$ :

On trouve $R_2 = 2,25$. Cette valeur approche mieux la réalité puisque $2,25^2 = 5,0625$.

Appliquons à nouveau la formule avec $2,25$ comme nouvelle valeur de $R_1$.

Avec $R_1 = 2,25$, on trouve $R_2 = 2,2361$.

Si nous élevons au carré cette nouvelle valeur, nous obtenons $5,00014321$.

Cette précision est déjà honorable et elle peut être suffisante. Toutefois, si nous souhaitons un plus petit écart avec la réalité nous devons appliquer la formule avec $R_1 = 2,2361$ et nous obtiendrons :

L'élévation au carré de cette nouvelle valeur de $R_2$ fournit $5,0000000011189$.

Écrire cet algorithme en pseudo-code, puis le tester en Python une fois qu’il a été vérifié par le professeur.




Christophe Gragnic, avec des morceaux d’un pdf de Christophe Després du LIUM au Mans, le 26/09/2014, 15h05'58".






Page générée le 04/12/2016, 10h08'07" (source).
historique de la page
historique global

 TogetherJS