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.

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 :

• quotient pour calculer le quotient,
• reste pour calculer le reste (plus facile).

4.2. Deuxième version

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

• en entrée, deux paramètres n et d,
• en sortie, deux variables q et r (en Python, il faudra utiliser global).

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 :

• produit,
• maximum,
• minimum,

Pour aller plus loin :

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

• map(f,l) qui prend en paramètre une fonction et une liste et qui retourne la liste des images des éléments de l par f,
• filter(f,l) qui prend en paramètre une fonction prédicat (qui retourne un booléen) et une liste et qui retourne la liste des éléments de l qui ont leur image par f vraie.

7. Calcul de 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'

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 :

• pascal(2,4) vaut 6,
• afficher les termes de la cinquième ligne (la numéro 4) : 1 4 6 4 1,
• afficher les termes d’une ligne plus conséquente comme
  1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1.

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$ :

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

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.