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 R²

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