TD d'informatique No. 3 :
la récursivité

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 27 novembre 2000

Il serait bien que chacun en traite au moins deux exercices. Dans ces programmes, il est interessant de faire écrire sur l'écran les arguments des fonctions recursives pour en suivre le deroulement. Il est INDISPENSABLE de réfléchir aux algorithmes à employer avant de commencer à programmer !

1   Écriture d' un nombre en base 2

Écrire un programme qui prenne en argument un entier et qui écrive ce nombre en base 2. Ce programme doit utiliser une fonction récursive.

2   Résolution d'une équation par dichotomie

Écrire la fonction qui prend un argument réel x et qui calcule x5 + 3x4 + 2x3 + x2 + 3x + 1. Écrire une fonction récursive qui cherche une racine de la fonction précédente par dichotomie. Écrire une fonction non récursive qui fasse la même chose. Comparer les deux.

3   Puissances d'une matrice

On représente les matrices de taille 2 × 2 par des tableaux de 4 réels. Écrire une fonction qui calcule le produit de deux matrices. Écrire une fonction qui calcule la puissance n-ième d'une matrice. Pour cela, on se servira des faits suivants : M0 = I, M2n = Mn × Mn et Mn + 1 = Mn × M.

4   Flocon de Von Koch

Le flocon de Von Koch est une figure obtenue en traçant un triangle équilatéral, puis en remplaçant récursivement chaque segment ___ par _/\_. Écrire une fonction qui dessine un flocon de Von Koch.

5   La courbe du dragon

La courbe du dragon est une courbe définie récursivement. À l'ordre 1, elle se compose d'un segment PQ. La courbe du dragon à l'ordre n entre deux points P et Q se compose de la courbe à l'ordre n-1 entre P et R, suivie de la courbe à l'ordre n - 1 entre R et Q, où PQR est un triangle isocèle rectangle en R, et R est à droite du segment PQ. Si les coordonnées de P et Q sont respectivement (x, y) et (z, t), celles de R sont donc : ((x+z)/2 + (t -y) /2, (y+t)/2 - (z-x)/2). Écrire un programme qui dessine la courbe du dragon.

This document was translated from LATEX by HEVEA.