next up previous contents
suivant: Applications avec GMP monter: Programmation en C précédent: Programmation en C   Table des matières

Exercice 32 - Euclide étendu

Nous voulons ecrire un programme C affichant sous forme de tableau l'exécution de l'algorithme d'Euclide étendu :

[klaus@localhost arithmetique]$ ./tableau 86 55 1
------------------------------------------------
|     a|      b|      q|      r|      u|      v|
|------|-------|-------|-------|-------|-------|
|    86|     55|      1|     31|    -39|     61|
|    55|     31|      1|     24|     22|    -39|
|    31|     24|      1|      7|    -17|     22|
|    24|      7|      3|      3|      5|    -17|
|     7|      3|      2|      1|     -2|      5|
|     3|      1|      3|      0|      1|     -2|
|     1|      0|       |       |      1|      1|
------------------------------------------------

Pour ce faire, complétez le code suivant :

tableauEuclideVide.c


#include<stdio.h>
#include<stdlib.h>

typedef struct ligne
{
  long a;
  long b;
  long quotient;
  long reste;
  long u;
  long v;
  struct ligne* suivante;
}ligne;

/********************************************************/

/*
  Cree une ligne, initialise ses champs.
*/

ligne* creerLigne(long a, long b, 
		  long quotient, long reste, 
		  long u, long v,
		  ligne* suivante)
{
  ligne* l = (ligne*)malloc(sizeof(ligne));
  if (l == NULL)
    {
      printf("No memory left\n");
      exit(0);
    }
  l->a = a;
  l->b = b;
  l->quotient = quotient;
  l->reste = reste;
  l->u = u;
  l->v = v;
  l->suivante = suivante;
  return l;
}

/********************************************************/

/*
  Met a jour les valeurs de u et de v dans le maillon l.
*/

void calculeUV(ligne* l)
{
}

/********************************************************/

/*
  Execute l'algorithme d'Euclide etendu, retourne 
  la liste des lignes du tableau.
*/

ligne* euclideEtendu(long a, long b, long lastV)
{
    return NULL;
}

/********************************************************/

/*
  Libere la memoire occupee par tous les maillons.
*/

void detruitLignes(ligne* l)
{
  if (l != NULL)
    {
      detruitLignes(l->suivante);
      free(l);
    }
}

/********************************************************/

/*
  Affiche les lignes du tableau.
*/

void afficheLignes(ligne * l)
{
  if (l != NULL)
    {
      if (l->suivante != NULL)
	printf("| %10ld| %10ld| %10ld| %10ld| %10ld| %10ld|\n", 
	       l->a, l->b, l->quotient, l->reste, l->u, l->v);
      else
	printf("| %10ld| %10ld|           |           | %10ld| %10ld|\n", 
	       l->a, l->b, l->u, l->v);
      afficheLignes(l->suivante);
    }
}

/********************************************************/

/*
  Affiche le tableau.
*/

void afficheTableau(ligne* l)
{
  printf("------------------------------------------------"\
	 "-------------------------\n");
  printf("|          a|          b|          q|          r"\
	 "|          u|          v|\n");
  printf("|-----------|-----------|-----------|-----------"\
	 "|-----------|-----------|\n");
  afficheLignes(l);
  printf("------------------------------------------------"\
	 "-------------------------\n");
}

/********************************************************/

/*
  Prend en parametre a, b et fv, retourne une solution particuliere de 
  	au + bv = pgcd(a, b)
  fv est la valeur donnee a v dans la derniere etape.
*/

int main(int argv, char** argc)
{
  ligne* l = euclideEtendu(strtol(*(argc + 1), NULL, 10), 
			   strtol(*(argc + 2), NULL, 10), 
			   strtol(*(argc + 3), NULL, 10));
  afficheTableau(l);
  detruitLignes(l);
  return 0;
}



klaus 2010-08-05