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 :
#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;
}