UNIVERSITÉ BORDEAUX 1 Session de Janvier 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. Ecrire en langage C la fonction qui, à deux tableaux d'entiers positifs p, a associe :
      n-1
      Õ
      i = 0 
      piai
      où n désigne le plus petit indice tel que pn = 0.

      Note : le calcul devra être fait directement, sans recourir à une fonction puissance écrite par ailleurs.

    2. On suppose disponible une fonction booléenne int premier (long x) qui indique si l'entier x est premier ; en utilisant cette fonction, écrire en langage C une fonction booléenne qui indique si les n premiers éléments du tableau p sont des nombres premiers distincts.

      Notes : comme ci-dessus, n désigne le plus petit indice tel que pn = 0. Une fonction booléenne est une fonction dont le résultat est vrai (1) ou faux (0).

  1. On suppose qu'un polynôme est représenté, comme en cours, par le tableau de ses coefficients, et on pourra utiliser librement le type polynome et la fonction degre définis en cours.

    1. Ecrire en langage C la fonction qui, à un polynôme A, associe :
      ó
      õ
      1

      0 
      A(t) dt

    2. Ecrire en langage C la fonction qui, à un polynôme A, associe le polynôme B défini par :
      ì
      ï
      ï
      í
      ï
      ï
      î
      B¢ = A
      ó
      õ
      1

      0 
      B(t) dt = 0

  2. On suppose disponible une fonction int hasard (int n) qui fournit aléatoirement un entier compris entre 0 et n-1. On utilise hasard (2) pour simuler une marche aléatoire sur un axe : selon le résultat, on fait un pas en avant ou un pas en arrière ; de même, on utilise hasard (4) pour simuler une marche aléatoire sur un quadrillage plan : selon le résultat, on fait un pas vers le Nord, ou vers l'Est, ou vers le Sud, ou vers l'Ouest. Dans tous les cas, on part de l'origine, et on appelle retour à l'origine tout passage par le point de départ après k pas (k > 0).

    1. Ecrire, en langage C, une fonction qui simule une marche aléatoire de n pas sur un axe ; cette fonction devra calculer l'abscisse du point d'arrivée, l'abscisse du point le plus à droite atteint au cours de la marche, et le nombre de retours à l'origine.

      Note : on tentera de bien spécifier, soit en définissant une structure, soit en utilisant pour paramètres des adresses, la façon dont cette fonction retourne simultanément les trois résultats demandés.

    2. Ecrire, en langage C, une fonction qui simule une marche aléatoire d'au plus n pas, sur un quadrillage plan, jusqu'au premier retour à l'origine, et calcule le nombre de pas effectués.

Corrigé

    1. Une double boucle suffit :
      long produit (int *p, int *alpha) {
        long x = 1;
        int i, j;
        
        for (i = 0; p [i] > 0; i++)
          for (j = 0; j < alpha [i]; j++)
            x = x * p [i];
        return x;
      }
      

      Noter que cette solution est correcte même pour un exposant ai nul, ou un vecteur vide. L'énoncé n'indique pas de taille MAX pour les vecteurs p et a ; celle-ci n'est donc pas connue, et il n'est pas nécessaire d'écrire, dans ces conditions :

      for (i = 0; i < MAX && p [i] > 0; i++)

    2. On termine le calcul dès qu'un pi n'est pas premier, ou dès qu'un pi figure déjà dans le tableau ; si par contre tous les éléments de p franchissent positivement les tests, le résultat est vrai (1).
      int premiers_distincts (int *p) {
        int i, j;
        
        for (i = 0; p [i] > 0; i++) {
          if (! premier (p[i]) )
            return 0;
          for (j = 0; j < i; j++)
            if (p [j] == p [i])
              return 0;
        }
        return 1;
      }
      

    1. Si
      A = n
      å
      i = 0 
      ai Xi
      l'intégrale définie vaut :
      ó
      õ
      1

      0 
      A(t) dt = é
      ë
      n
      å
      i = 0 
      ai Xi+1 / (i+1) ù
      û
      1
      0 
      = n
      å
      i = 0 
      ai
      i+1
      d'où la fonction C :
      double integrale (polynome a) {
        double s = 0;
        int i, n = degre (a);
        
        for (i = 0; i <= n; i++)
          s = s + a[i] / (i+1);
        return s;
      }
      

    2. La primitive B, avec terme constant nul, vaut :
      B = n
      å
      i = 0 
      ai Xi+1 / (i+1)
      Il suffit ensuite de calculer le terme constant de telle sorte que :
      ó
      õ
      1

      0 
      B(t) dt = 0
      void primitive  (polynome b, polynome a) {
        int i, n = degre (a);
        
        b [0] = 0;
        for (i = 0; i <= n; i++)
          b [i+1] = a[i] / (i+1);
        for (i = n + 2; i <= DEGRE_MAX; i++)
          b [i] = 0;
        b [0] = - integrale (b);
      }
      

      Noter qu'il faut prendre garde à bien annuler les termes de degré supérieur à n+1. Il est bon de signaler, sur la copie, que le calcul d'une primitive B n'a de sens que si A n'est pas de degré maximal.

    1. En définissant une structure, on a la solution suivante :
      struct marche {
        int position, droite, retour;
      };
      
      struct marche simul1 (int n) {
        struct marche m = {0, 0, 0};
        int i, x = 0;
        
        for (i = 0; i < n; i++) {
          if ( hasard (2) )
            { x++; if (m.droite < x) m.droite = x; }
          else x--;
          if (x == 0) m.retour++;
        }
        m.position = x;
        return m;
      }
      

      On peut évidemment éviter la variable x, en la remplaçant par m.position. En utilisant des adresses, la solution devient :

      void simul1 (int n, int *position, int *droite, int *retour) {
        int i, x = 0;
        
        for (i = 0; i < n; i++) {
          if ( hasard (2) )
            { x++; if (*droite < x) *droite = x; }
          else x--;
          if (x == 0) (*retour)++;
        }
        *position = x;
      }
      

      On peut, comme précédemment, éviter la variable x, en la remplaçant par *position.

    2. En deux dimensions, on retourne le nombre de pas dès qu'on retourne à l'origine ; sinon, on convient de retourner 0.
      int simul2 (int n) {
        int i, h, x = 0, y = 0;
        
        for (i = 0; i < n; i++) {
          h = hasard (4);
          if (h == 0) y++;
          else if (h == 1) x++;
          else if (h == 2) y--;
          else x--;
          if (x == 0 && y == 0)
            return i + 1;
        }
        return 0;
      }
      
      Noter que l'instruction switch est mieux adaptée à des choix multiples, comme ici, mais elle n'a pas été présentée en cours.


File translated from TEX by TTH, version 1.96.
On 2 Nov 1999, 13:50.