UNIVERSITÉ BORDEAUX I Département premier cycle Sciences
Janvier 1995


Module I20
(Durée: 1h30)


Notes de cours et de TD autorisées. Autres documents interdits.

Les 3 exercices sont indépendants ; donnez des réponses simples et précises : les fonctions C demandées sont très courtes (quelques lignes). Ecrire des généralités, ou copier des fonctions vues en cours ou en TD, vous fera perdre du temps sans vous rapporter aucun point.

  1. Pour calculer une valeur approchée de l'intégrale :
    ó
    õ
    b

    a 
    f(x)dx
    on peut diviser l'intervalle [a b] en n segments égaux, délimités par les points :
    x0 = a, x1, x2¼, xn = b
    et remplacer f, sur chaque segment [xi xi+1], par la fonction constante égale à f(xi) ; en d'autres termes on approche f par une fonction en escalier.

    Ecrire, en langage C, la fonction integrale , qui effectue ce calcul approché ; on suppose la fonction f écrite par ailleurs. Veiller à spécifier au mieux les paramètres.

    Une meilleure approximation est obtenue en remplaçant f, sur [xi xi+1], par la fonction constante égale à :

    f(xi)+f(xi+1)
    2
     ;
    écrire la version modifiée correspondante de la fonction integrale, en veillant à ne pas calculer deux fois la même valeur f(x).

  2. On considère la suite un définie par la récurrence suivante :
    ì
    ï
    ï
    í
    ï
    ï
    î
    u0
    =
    1
    un+1
    =
    u0 un + u1 un-1 + ¼+ un u0
    =
    n
    å
    k = 0 
    uk un-k , n ³ 0
    Calculer les cinq termes u1, u2, ¼, u5 de la suite. Ecrire, en langage C, la fonction suite , qui remplit un tableau avec les n+1 premiers termes u0, ¼, un de la suite. Veiller à spécifier au mieux les paramètres.

  3. On considère la fonction suivante :
      #define MAX 20
      
      void f (int *t, int *u, int n) {
        int i, j;
        
        for (j = 0; j <= MAX; j++)
          u [j] = 0;
        for (i = 0; i < n; i++) {
          j = t [i];
          u [j]++;
        }
      }
      
    On suppose donné un tableau notes, contenant les dix valeurs suivantes :
    12 14 10 8 12 12 15 8 13 10 ,
    et déclaré un tableau : int a [MAX + 1]; quel est le résultat de l'appel :

    f (notes, a, 10) ?

    Que calcule, de façon générale, la fonction f ?

    Cette fonction comporte une instruction dangereuse : laquelle ? Que faudrait-il ajouter pour rendre cette fonction sûre ?

Corrigé

  1. En posant :
    d = b-a
    n
    la méthode de calcul proposée consiste à remplacer :
    ó
    õ
    b

    a 
    f(x)dx  par :  n-1
    å
    i = 0 
    df(xi)
    La fonction C n'utilise pas de tableau ; chaque xi se déduit du précédent en ajoutant d, qu'on calcule une seule fois, en début de fonction.
    double integrale (double a, double b, int n) {
      int i;
      double x = a, delta = (b - a) / n, s = 0;
      
      for (i = 0; i < n; i++) {
        s = s + f (x);
        x = x + delta;
      }
      return s * delta;
    }
    

    De nombreuses variantes sont possibles, par exemple, sans utiliser de variable x (mais au prix de multiplications supplémentaires) :

      for (i = 0; i < n; i++)
        s = s + f (a + i * delta);
    

    La seconde méthode de calcul (plus précise) consiste à remplacer :

    ó
    õ
    b

    a 
    f(x)dx  par :  n-1
    å
    i = 0 
    d f(xi)+f(xi+1)
    2
    = d æ
    ç
    è
    f(a)+f(b)
    2
    + n-1
    å
    i = 1 
    f(xi) ö
    ÷
    ø
    d'où la fonction modifiée, très voisine de la précédente :
    double integrale (double a, double b, int n) {
      int i;
      double x = a, delta = (b - a) / n, s = ( f(a) + f(b) ) / 2;
      
      for (i = 1; i < n; i++) {
        x = x + delta;
        s = s + f (x);
      }
      return s * delta;
    }
    

    Si on ne remarque pas la simplification ci-dessus, on peut écrire aussi, pour éviter de calculer inutilement deux fois f à chaque itération :

      double
        x = a, delta = (b - a) / n,
        s = 0, u = f (a), v;
      
      for (i = 0; i < n; i++) {
        x = x + delta;
        v = f (x);
        s = s + (u + v) / 2;
        u = v;
      }
    

  2. Les premières valeurs de la suite sont :
    u1 = 1 , u2 = 2 , u3 = 5 , u4 = 14 , u5 = 42 .
    Contrairement aux récurrences à deux ou trois termes, celle-ci exige un tableau pour sa traduction en C :
    void suite (long *u, int n) {
      int i, j;
      
      u [0] = 1;
      for (i = 1; i <= n; i++) {
        u [i] = 0;
        for (j = 0; j < i; j++)
          u [i] = u [i] + u [j] * u [i - j - 1];
      }
    }
    

    Evidemment, la solution suivante est équivalente :

      for (i = 0; i < n; i++) {
        u [i + 1] = 0;
        for (j = 0; j <= i; j++)
          u [i + 1] = u [i + 1] + u [j] * u [i - j];
      }
    

  3. L'appel : f (notes, a, 10) remplit le tableau a avec les valeurs suivantes :
    i
    0
    ¼
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    ¼
    20
    a[i]
    0
    0
    0
    2
    0
    2
    0
    3
    1
    1
    1
    0
    0
    0

    La fonction f enregistre, dans le tableau u, le nombre d'occurrences de chaque note dans le tableau t (par exemple pour préparer un histogramme).

    L'instruction dangereuse est j = t [i]; u [j]++ , car elle suppose que le tableau t ne contient que des entiers entre 0 et 20 ; des fautes de saisie peuvent alors entraîner un comportement dangereux (ou un "plantage") du programme. Il est conseillé d'écrire plutôt :

      j = t [i];
      if (j >= 0 && j <= MAX)
        u [j]++;
    


File translated from TEX by TTH, version 1.96.
On 23 Sep 1999, 17:07.