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


Module I20
(Durée: 1h30)


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

Les 3 exercices sont indépendants ; donner 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. On représente un nombre entier positif x par le tableau a de ses chiffres, en base b, de telle sorte que :
    x = a0 + a1 b + a2 b2¼+ an bn
    On dit que ak est le chiffre de poids k ; noter que l'ordre des chiffres dans le tableau (poids croissants) est l'inverse de celui utilisé pour écrire habituellement x (poids décroissants). On appellera MAX le nombre maximal de chiffres autorisés ; on pourra (mais ce n'est pas obligatoire) utiliser une déclaration :
        typedef int nombre [MAX];
    
    Veiller, dans tous les cas, à la qualité des en-têtes de fonctions.

    1. Ecrire, en langage C, une fonction qui affiche les chiffres de x dans l'ordre habituel, c'est à dire en commençant par le premier chiffre non nul de poids le plus fort.

      Note : ici, comme dans le reste de l'exercice, on ne demande aucune conversion d'une base dans une autre.

    2. Ecrire, en langage C, une fonction qui calcule la somme x+y ; pourquoi est-elle différente de la fonction qui calcule la somme de deux polynômes ?

      Comment proposez-vous de traiter le cas où le nombre de chiffres de x+y dépasse MAX ?

    3. On souhaite manipuler les nombres les plus grands possibles, pour une valeur donnée de MAX ; quel est alors, à votre avis, le meilleur choix pour la base b ? Justifier soigneusement votre réponse, en vérifiant en particulier que la fonction précédente, pour le calcul de la somme, reste correcte.

  2. On représente, comme en cours, un nombre complexe par la structure :
      struct complexe {double reel, imaginaire; };
    
    et on dispose des fonctions :
      struct complexe somme (struct complexe u, struct complexe v);
      struct complexe produit (struct complexe u, struct complexe v);
      double module (struct complexe z);
    
    Soit f la fonction définie par f(z) = z2+c , où c désigne une constante complexe, et soit zn la suite définie par la récurrence :
    z0 = z , zn = f(zn-1) pour n > 0.

    1. Ecrire, en langage C, la fonction f.

    2. Ecrire, en langage C, la fonction booléenne qui indique si zn se trouve dans le disque, centré en l'origine, de rayon r.

      Note : veiller à bien spécifier les paramètres de cette fonction.

  3. On considère la fonction suivante, vue en cours, qui affiche la décomposition en facteurs premiers d'un entier :
      void decompose (long n) {
        long d;
        for (d = 2; d * d <= n;)
          if (n % d == 0) {
            printf (" %d", d);
            n = n / d;
          }
          else d++;
        printf (" %d\n", n);
      }
    
    Par exemple, si n = 200, cette fonction affiche : 2 2 2 5 5.

    Modifier cette fonction pour qu'elle affiche chaque facteur avec sa multiplicité ; par exemple, si n = 200, la fonction modifiée affiche : 2 puissance 3, 5 puissance 2.

Corrigé

    1. (5 points) Il faut parcourir les chiffres de droite à gauche (dans le tableau), jusqu'à trouver un chiffre non nul (comme pour calculer le degré d'un polynôme), puis afficher tous les suivants :
        void afficher (nombre x) {
          int i, j;
          
          for (i = MAX - 1; i > 0 && x [i] == 0; i--);
          for (j = i; j >= 0; j--)
            printf ("%d", x [j]);
          printf ("\n");
        }
      

      Variantes et remarques :

      • On peut écrire l'en-tête sous la forme :

        void afficher (int *x) ou : void afficher (int x [])

      • L'oubli de i > 0 dans la condition i > 0 && x [i] == 0 est une faute (mineure dans le contexte de l'examen), car x peut représenter le nombre nul.

      • On peut ne pas utiliser de variable j, et écrire la seconde boucle :

        for (; i >= 0; i--) printf ("%d", x [i]);

    2. (5 points) Pour faire la somme de deux nombres, il faut modifier la fonction qui effectue la somme de deux polynômes, en tenant compte des retenues, pour que les chiffres ne dépassent jamais la base :
        void somme (nombre z, nombre x, nombre y, int base) {
          int i, retenue = 0;
          
          for (i = 0; i < MAX; i++) {
            z [i] = x [i] + y [i] + retenue;
            if (z [i] >= base) {
              retenue = 1;
              z [i] = z [i] - base;
            }
            else
              retenue = 0;
          }
        }
      

      Noter que la base est un paramètre de cette fonction, car il est impossible d'additionner x et y sans connaître la base utilisée.

      Le nombre de chiffres de x+y dépasse MAX si et seulement si la fonction se termine avec retenue = 1. Le moyen le plus simple de le signaler à l'utilisateur (qui en fera ce qu'il voudra), est de transformer cette fonction en une fonction booléenne : remplacer void par int dans l'en-tête, et ajouter

      return retenue;

      à la fin (2 points).

      Remarque : certains étudiants n'ont pas utilisé de variable retenue , et ont écrit :

          for (i = 0; i < MAX; i++) {
            z [i] = x [i] + y [i] + z [i];
            if (z [i] >= base) {
              z [i + 1] = 1;
              z [i] = z [i] - base;
            }
            else
              z [i + 1] = 0;
          }
      
      Mais cette solution est fausse pour la première et la dernière valeur de i : z [0] n'est pas initialisé, et surtout z [MAX] n'existe pas.

    3. (3 points) Il faut choisir la base b aussi grande que possible, en veillant à ce que la somme de deux chiffres reste inférieure au plus grand entier positif représentable en machine ; si les entiers sont représentés avec 16 chiffres binaires, la plus grande valeur de b possible est donc 215-1 (en fait il faut alors remplacer le type int par unsigned int , ce qui sort du cadre de I2).

    1. (4 points)
        struct complexe f (struct complexe z, struct complexe c) {
          return somme ( produit (z, z), c );
        }
      

    2. (5 points) Il faut calculer zn par récurrence, puis comparer son module au rayon du disque ; cette fonction comporte quatre paramètres : le point de départ z, la valeur de c, l'indice n (un entier), et le rayon r (un réel).

        int disque (struct complexe z, struct complexe c,
                    int n, double r) {
          int i;
          for (i = 1; i <= n; i++)
            z = f (z, c);
          return ( module (z) <= r );
        }
      

      La variante suivante est évidemment correcte, mais peu élégante :

          if ( module (z) <= r )
            return 1;
          else
            return 0;
      

  1. (6 points) La solution la plus simple est de remplacer la condition if par une boucle while :
      void decompose (long n) {
        long d;
        int multiplicite;
        for (d = 2; d * d <= n; d++) {
          multiplicite = 0;
          while (n % d == 0) {
            multiplicite++;
            n = n / d;
          }
          if (multiplicite > 0)
            printf ("%d puissance %d, ", d, multiplicite);
        }
        if (n > 1)
          printf ("%d", n);
        printf ("\n");
      }
    
    Ne pas oublier if (multiplicite > 0) avant printf. La solution voisine :
      int multiplicite = 0;
    
      for (d = 2; d * d <= n;) {
        if (n % d == 0) {
          multiplicite++;
          n = n / d;
        }
        else {
          if (multiplicite > 0)
            printf ("%d puissance %d, ", d, multiplicite);
          multiplicite = 0;
          d++;
        }
      }
    
    a été considérée comme correcte, mais en fait elle pose des problèmes délicats quand on sort de la boucle : le dernier diviseur d a-t-il bien été affiché, et sinon est-il égal à n ?


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