UNIVERSITÉ BORDEAUX 1 Session de Juin 1996
Département de formation premier cycle


Module I20
(Durée: 1h30)


Polycopié, notes de cours et de TD autorisées. Autres documents interdits.

Le sujet comporte une page recto-verso. 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 tout réel x et tout entier positif n, on définit :
    (x)n = x(x-1)(x-2)¼(x-n+1)
    (noter que ce produit comporte n facteurs).

    Ecrire en langage C la fonction f définie par :

    f(x,n) = n
    å
    k = 1 
    (x)k
    xk

  2. On appelle inversion, dans un tableau d'entiers t, tout couple (i,j) d'indices tel que :
    i < j  et  ti > tj

    Ecrire une fonction C qui calcule le nombre d'inversions d'un tableau t de taille n.

  3. Le crible d'Eratosthène permet d'obtenir rapidement une (petite) liste de nombres premiers ; par exemple, pour calculer la liste des nombres premiers inférieurs à 100, on part d'une liste de tous les entiers inférieurs à 100, puis on barre tous les multiples de 2 (sauf 2), tous les multiples de 3 (sauf 3), tous les multiples de 5 (sauf 5), et tous les multiples de 7 (sauf 7) ; les "survivants" forment la liste souhaitée. Si cet algorithme ne vous est pas familier, essayez-le sur un petit exemple (par exemple pour obtenir la liste des nombres premiers inférieurs à 20) !

    Voici une traduction en langage C :

    #define MAX 100
    int barre[MAX];
    
    void crible (int n) {
      ...
    }
    
    void liste_premiers () {
      int n;
      
      for (n = 0; n < MAX; n++) barre[n] = 0;
      crible (2); crible (3); crible (5); crible (7);
      for (n = 2; n < MAX; n++)
        if (! barre[n]) printf (" %d", n);
      printf ("\n"); 
    }
    

    1. Compléter la fonction crible.

    2. Si on remplace 100 par 200, dans la définition de MAX, comment faut-il modifier la fonction liste_premiers ?

    3. Ecrire une version de la fonction liste_premiers, qui soit correcte pour toute valeur de MAX.

      Note : cette question est probablement plus difficile que les autres, bien que la réponse soit aussi courte que d'habitude.

Corrigé

  1.   double f (double x, int n) {
        int k;
        double s = 0, t = 1;
        
        for (k = 0; k < n; k++) {
          t = t * (x - k) / x;
          s = s + t;
        }
        return s;
      }
    

  2. La solution la plus simple est la suivante :
      int inversions (int *t, int n) {
        int i, j, compteur = 0;
        
        for (i = 0; i < n; i++)
          for (j = i + 1; j < n; j++)
            if ( t[i] > t[j]) compteur++;
        return compteur;
      }
    
    Note : on peut aussi bien écrire la première boucle :

      for (i = 0; i < n - 1; i++) .

    La solution suivante n'est pas fausse, mais maladroite :

      int inversions (int *t, int n) {
        int i, j, compteur = 0;
        
        for (i = 0; i < n; i++)
          for (j = 0; j < n; j++)
            if ( i < j && t[i] > t[j]) compteur++;
        return compteur;
      }
    

    1. La solution la plus simple est la suivante :

        void crible (int n) {
          int i;
          
          for (i = 2 * n; i < MAX; i = i + n)
            barre[i] = 1;
        }
      

      Note : on peut en fait commencer le crible avec i=n*n, car les multiples de n précédents ont déjà été barrés.

      Cette solution est de loin préférable à la suivante, qui effectue de nombreux calculs inutiles :

        void crible (int n) {
          int i;
          
          for (i = n + 1; i < MAX; i++)
            if (i % n == 0)
              barre[i] = 1;
        }
      

      Attention : avec cette solution, ajouter

            else
              barre[i] = 0;
      
      est une grave erreur.

    2. Si on remplace 100 par 200, dans la définition de MAX, il faut ajouter :

      crible (11); crible (13);

      dans la fonction liste_premiers.

    3. De façon générale, il faut appeler la fonction crible pour tout nombre premier inférieur à la racine carrée de MAX ; soit :

        for (n = 2; n * n < MAX; n++)
          if (! barre[n]) crible (n);
      


File translated from TEX by TTH, version 1.96.
On 2 Nov 1999, 14:16.