Correction du TD n°12

Exercice 1

Calcul d'une suite de factoriels

001 fonction factoriels(n) : Tableau [n] de entier
002 Données n : entier
003 Locales i : entier { Indice de parcours pour le calcul }
004 { des factoriels }
005 t : Tableau [n] de entier { Resultat fonction }
006 t[0] := 1
007 pour i de 1 à n-1 faire
008 t[i] := (i+1)*t[i-1]
009 fait
010 Resultat : t
011 fin fonction

Autre solution pour les factoriels de 0 à n

001 fonction factoriels(n) : Tableau [n+1] de entier
002 Données n : entier
003 Locales i : entier { Indice de parcours pour le calcul }
004 { des factoriels }
005 t : Tableau [n+1] de entier { Resultat fonction }
006 t[0] := 1
007 pour i de 1 à n faire
008 t[i] := i*t[i-1]
009 fait
010 Resultat : t
011 fin fonction

Exercice 2

Calcul d'une suite de nombres de Fibonacci

001 fonction fibonacci(n) : Tableau [n+1] de entier
002 Données n : entier
003 Locales i : entier { Indice de parcours pour le calcul }
004 { des nombre de Fibonacci }
005 t : Tableau [n+1] de entier { Resultat fonction }
006 t[0] := 0
007 t[1] := 1
008 pour i de 2 à n faire
009 t[i] := t[i-1]+t[i-2]
010 fait
011 Resultat : t
012 fin fonction

Exercice 3

Complexité des algorithmes des 2 exercices précédents

Ces deux algorithmes présentent la même complexité.
Ils sont basés sur une simple boucle "pour" d'itération entre 1 ou 0 et n, donc s'exécutant en n itérations.

La complexité est donc en o(n).

Exercice 4

Structures de données de stockage de polygones de R2

Plusieurs structures de données sont possibles:

- Un tableau de réel à deux indices de tailles N et 2 permettra de stocker N fois 2 valeurs
  -> N couples (abscice, ordonnée) pour un polygone de N sommets.
  Avantage : Simplicité
  Inconvénient : Rigidité (impossible d'ajouter ou de supprimer un sommet de manière directe)
  Inconvénient : Le tableau de 2 réels représentant un sommet ne met pas clairement en évidence le fait que le réel d'indice 0 est l'abscice et le réel d'indice 1 est l'ordonnée.
- Un tableau de réel à un indice de taille N pour stocker N valeurs d'abscice
  Un tableau de réel à un indice de taille N pour stocker N valeurs d'ordonnée
  Avantage : Simplicité
  Inconvénient : Rigidité (impossible d'ajouter ou de supprimer un sommet de manière directe)
  Inconvénient : 2 variables pour une seule structure de données
- Un tableau de réel à deux indices de tailles MAX et 2 permettra de stocker au maximum MAX fois 2 valeurs
  Une variable n pour indiquer le nombre de sommets effectivement stockés (au indices 0 à n-1)
  -> MAX couples (abscice, ordonnée) pour un polygone.
  Avantage : Simplicité
  Inconvénient : 2 variables pour une seule structure de données

Exercice 5

Calcul du centre d'un polygone

La 1ère structure de la question 4 est utilisée.

Exercice 6

Calcul du périmètre d'un polygone

La 3ème structure de la question 4 est utilisée.

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr