Addition sur des entiers longs

Version imprimable

Bonjour,
Je dois faire plusieurs opérations sur des entiers longs. Mais je bloque déjà à l'opération.
J'ai crée un type Entier_long qui contient un signe, une taille, et un tableau dans lequel est stocké chaque chiffre de mon entier long.

Je n'arrive pas trop m'en sortir, car il faut gérer plusieurs points :
-la taille des 2 entiers à comparer
-leur signe respectif
-le cas d'une retenue en plein milieu du nombre, mais aussi dans le cas où la retenue fait "grandir" la taille du nombre de +1.
-J'en oublie peut-être...

J'ai fait une multitude de tests, mais aucun n'était bon.
Je laisse une esquisse du dernier que j'ai testé, ça se trouve je suis sur la bonne voie...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 void Addition (Entier_long a, Entier_long b) { int taille_1=0, taille_2=0; int reste=0, i=0, s; int Max=0, Min=0; taille_1=a.taille; taille_2=b.taille; Entier_long NbGrand, NbPetit; int somme[Max+2]; if(taille_1>=taille_2) { Max=taille_1; Min=taille_2; NbGrand=a; NbPetit=b; } else { Max=taille_2; Min=taille_1; NbGrand=b; NbPetit=a; } for(i=0;i<Min;i++) { s=NbGrand.Chiffres_sign[i]+NbPetit.Chiffres_sign[i]+reste; reste=s/10; s=s%10; somme[i]=s; } for(i=Min;i<Max;i++) { s=NbGrand.Chiffres_sign[Max]+reste; reste=s/10; s=s%10; somme[i]=s; } /* Affichage de l'addition */ for(i=1;i<Max+1;i++) { printf("%d", somme[i]); } }
J'ai tourné le problème dans divers sens, donc la méthode que je propose n'est peut-être pas la bonne, c'est la dernière que j'ai testé.( dans ce code je ne m'occupe pas encore des signes, si j'arrive déjà à additionner 2 nombres positifs ce sera un bon début)
Est-ce que quelqu'un pourrait m'aider ou me guider ?
Je peux afficher d'autres parties de mon code si besoin.

Merci d'avance !

14/03/2016, 09h37
nnovic

Hello,

Il manque une info importante: le détail de ta structure "Entier_long" et surtout comment tu renseignes tous les champs.

Le point sensible de ton code c'est: comment sont rangés les chiffres ? D'après ce que tu as déjà codé, il est impératif que le chiffre des unités soit dans Chiffres_sign[0], le chiffre des dizaines dans Chiffres_sign[1], etc ... C'est-à-dire dans l'ordre inverse de celui dans lequel on écrit les nombres.

Par ailleurs, ta boucle d'affichage a un offset de 1 case, je n'ai pas compris pourquoi!

Pour rebondir sur les conseils de nnovic, es-tu assuré du bon fonctionnement du reste du programme que nous n'avons pas ici ? Je veux dire, la toute première version validée (les « fondations ») devrait ressembler à quelque chose de ce genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    // ...
} longint;
 
int longint_create(longint *i) {
    // ...
}
 
void longint_destroy(longint *i) {
    // ...
}
 
void longint_set(longint *dst, long value) {
    // ...
}
 
void longint_print(FILE *stream, const longint *i) {
    // ...
}
 
int main(int argc, char *argv[]) {
    longint i;
    if (longint_create(&i) != 0)
        return 1;
 
    longint_print(stdout, &i);
 
    longint_set(&i, 16549823l);
    longint_print(stdout, &i);
 
    longint_destroy(&i);
    return 0;
}

14/03/2016, 11h02
St-42-FCM-57
Bonjour,

Tout d'abord merci pour vos 2 réponses.

Concernant la déclaration de la structure, voici son code :
Code:

1 2 3 4 5 6 7 typedef struct { char signe; int taille; int Chiffres_sign[Dim]; /* Dim vaut 400, il y a un define Dim 400 en haut du programme */ }Entier_long;
Ensuite, pour remplir mon Chiffre_sign[], je fais une boucle de 0 à x.taille (x.taille exclut) donc si mon nombre est 123, je rentre le 1, puis le 2, puis le 3. Du coup en faisant comme ça, mon chiffre des unités se trouve dans la dernière case, ça parait plus logique de faire comme ceci, que de rentrer un nombre à l'envers ?
Durant mes divers essais, j'avais également fait des essais avec des boucles partant de la fin jusqu'au début du nombre, mais ce n'était pas concluant. Dans mon cas, c'était cette méthode à adopter ?
Concernant le "Max+1", c'était un peu expérimental, mais c'était fait pour le cas où le résultat est plus long (en taille) que mes 2 nombres à additionner.

Le reste du programme fonctionne oui, enfin il fait ce que je souhaite (c'est-à-dire comparer mes 2 nombres, afficher l'opération souhaitée, ...) . Mais ce n'est cependant pas exactement comme le tien, Matt_Houston.
14/03/2016, 11h28
nnovic

Citation:

Envoyé par Stéphanois57

Ensuite, pour remplir mon Chiffre_sign[], je fais une boucle de 0 à x.taille (x.taille exclut) donc si mon nombre est 123, je rentre le 1, puis le 2, puis le 3. Du coup en faisant comme ça, mon chiffre des unités se trouve dans la dernière case, ça parait plus logique de faire comme ceci, que de rentrer un nombre à l'envers ?

Fais une addition avec un papier et un stylo, tu verras que tu commences bien par additionner les chiffres par la fin. D'abord les unités, ensuite les dizaines, puis les centaines... Concentre-toi sur ça pour commencer.

Oui oui ça je sais, j'avais déjà fait, mais je ne parvenais pas à ce que je voulais.
Je crois que j'avais écris quelque chose comme ça :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
void Addition (Entier_long a, Entier_long b)
{
    int taille_1=0, taille_2=0;
    int reste=0, i=0, s;
    int Max=0, Min=0;
    taille_1=a.taille;
    taille_2=b.taille;
    int Somme[Max+2];
 
    if(taille_1>=taille_2)
    {
        Max=taille_1;
        Min=taille_2;
 
    }
    else
    {
        Max=taille_2;
        Min=taille_1;
    }
 
    for (i=Max ; i>0 ; i--)
    {
        s=a.Chiffres_sign[i]+b.Chiffres_sign[i]+reste;
        if (s>9)
        {
            Somme[i]=s%10;
            reste=1;
        }
        else
        {
            Somme[i]=s;
            reste=0;
        }
    }
    /* Affichage de l'addition */
    for(i=0;i<Max+2;i++)
    {
        printf("%d", Somme[i]);
    }
}

Le principe est bien comme ça ?

Le problème en faisant ça, c'est que si les 2 nombres n'ont pas la même taille il y un a.Chiffres_sign[i] ou b.Chiffres_sign[i] qui n'existe pas.

14/03/2016, 15h36
nnovic

Citation:

Envoyé par Stéphanois57

Le problème en faisant ça, c'est que si les 2 nombres n'ont pas la même taille il y un a.Chiffres_sign[i] ou b.Chiffres_sign[i] qui n'existe pas.

En effet. Pour un même indice 'i', le contenu de "a.Chiffres_sign[i]" et de "b.Chiffres_sign[i]" peuvent très bien être de rangs différents, ce qui faussera le calcul. Tu auras ce problème pour les autres opérations, d'ailleurs.

A mon avis, la solution la plus élégante pour s'en sortir est d'inverser l'ordre dans lequel tu stockes les chiffres dans "Chiffres_sign[]". Ainsi, tu auras toujours le chiffre des unités dans "Chiffres_sign[0]", le chiffre des dizaines dans "Chiffres_sign[1]", et ainsi de suite. Et tu pars sur la base du premier code qui tu as posté pour faire l'addition.
14/03/2016, 15h41
jopopmk

Salut,

ta structure est-elle une contrainte ? Sinon tu pourrais utiliser une chaîne de caractères comme tableau. Avantages :
- prends moins de place en mémoire,
- taille variable non limitée (cf. ta question sur la "retenue finale"),
- parcours facilité grâce au null de fin (cf. ta question sur les longeurs des entiers),
- directement sérialisable/affichable.

A noter que tu peux pousser un peu plus le principe et essayer de faire fonctionner ton code pour des réels en "fixed point style".

Bon dev.
14/03/2016, 16h02
St-42-FCM-57
Ah oui donc il faudrait que je fasse une structure qui inverse l'ordre de mon nombre ? Et la procédure deviendrait ensuite quelque chose du genre :
Code:

1 2 3 4 5 6 7 8 void Addition (Entier_long a, Entier_long b) { Inverse (a,b) **Le style de programme que j'ai posté précédemment ** Inverse(somme) }
C'est bien ça dans l'esprit ?

Mais en faisant ca, admettons que mon nombre a ait une taille de 2 chiffres et mon nombre b de 4 chiffres.
Exemple : 12 + 5734
En inversant, mes deux première cases de 12 vont être vides, est-ce que le compilateur va arriver à comprendre 4+rien ?
Je sais pas si je suis très clair.

Oui concernant la structure c'est une contrainte... je suis obligé de faire avec.
14/03/2016, 16h21
nnovic

1 pièce(s) jointe(s)

J'ai essayé de synthétiser ce que tu dois obtenir dans le schéma ci-dessous:
Pièce jointe 203871

Dommage, voilà à quoi peut ressembler une addition de deux entiers naturels en utilisant des chaînes de caractères :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char* add(char *val1, char *val2) {
	int len1 = strlen(val1),
		len2 = strlen(val2),
		rest = 0;
	char *result = malloc(((len1 > len2 ? len1 : len2) +2)*sizeof(char)),
		 *cur1 = val1 +len1 -1,
		 *cur2 = val2 +len2 -1,
		 *curr = result;
	while (cur1 >= val1 || cur2 >= val2) {
		int dig1 = (cur1 < val1) ? 0 : *cur1-- -'0',
			dig2 = (cur2 < val2) ? 0 : *cur2-- -'0',
			vadd = dig1 +dig2 +rest;
		*curr++ = (vadd %10) +'0';
		rest = vadd /10;
	}
	if (rest) *curr++ = rest +'0';
	*curr = 0;
	strrev(result);
	return result;
}

20 lignes pile et c'est torché.
Pour gérer les entiers relatifs il faudra écrire la fonction de soustraction.

D'accord, franchement merci beaucoup !

Je vais essayer de faire ça maintenant.

Je viens de faire une procédure d'inversement :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void InverserTableau(Entier_long a) { int i1=0; int i2=a.taille; int x; while(i1<i2) { x=a.Chiffres_sign[i1]; a.Chiffres_sign[i1]=a.Chiffres_sign[i2]; a.Chiffres_sign[i2]=x; i1=i1+1; i2=i2-1; } }
donc dans le programme principal j'appelle InverserTableau(a)
et ensuite je fais un affichage pour voir si ça inverse bien :
Code:

1 2 3 4 5 for (i=0; i<a.taille ;i++) { printf("%d", a.Chiffres_sign[i]); }
mais ça n'affiche rien, ca me souligne la 1ère ligne du "for" et dit : Thread 1: Breakpoint 1.1

J'ai fait une erreur dans la procédure d'inversement ?

14/03/2016, 17h13
St-42-FCM-57

Bon, j'ai un peu touché à tout, et je n'ai plus le problème du breakpoint. Mais ça ne m'inverse pas mon nombre. Pourtant j'ai refait sur papier, et il me semble que c'est la bonne méthode que j'ai appliqué. Il y a peut-être un problème dans les variables que j'ai utilisé alors ?
14/03/2016, 17h19
nnovic
A priori, je dirais ici:
Code:

1 2 int i2=a.taille;
Attention: pour un tableau de taille N, les index valides vont de 0 à N-1
14/03/2016, 17h28
jopopmk

Effectivement l'index final n'est pas le bon, mais c'est pas le seul souci : le param Entier_long est passé par copie.
14/03/2016, 17h32
St-42-FCM-57
Oui effectivement ça doit être :
Code:

1 2 int i2=a.taille-1;
Mais ca m'affiche le nombre que je rentre, donc il ne s'inverse. Un peu comme s'il ne gardait pas en mémoire l'inversement ?

Rectification : oui c'est vrai jopopmk. C'est assez galère tous ces pointeurs lorsqu'on est novice...

Avec ce code ça à l'air de marcher :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void InverserTableau(Entier_long *a) /* Inverse le tableau Chiffres_sign[] de Entier_long */
{
    int i1=0;
    int i2=((*a).taille-1);
    int x;
    while(i1<i2)
    {
        x=(*a).Chiffres_sign[i1];
        (*a).Chiffres_sign[i1]=(*a).Chiffres_sign[i2];
        (*a).Chiffres_sign[i2]=x;
        i1=i1+1;
        i2=i2-1;
    }
}

Bien sûr, ne pas oublier les & après...

14/03/2016, 17h57
jopopmk

T'as un souci avec la flèche ? :oops:
14/03/2016, 18h14
St-42-FCM-57

C'est la même chose non ?

Mais j'ai un soucis, et je ne comprends pas.
Quand un de mes 2 nombres est plus petit.
Ex: 979 et 21. Le résultat de l'addition doit être 1000
979 est stocké comme [9], [7], [9]
21 est stocké comme [2], [1]

On inverse
979 devient 979
et 21 devient 12.

Là le problème c'est qu'il va faire
9+2=1 retenue 1
7+1+retenue=9
9+rien=9
= 199 --> on inverse et ça devient 991. Ce n'est pas le bon résultat.
Ca c'est quand je le fais tourner à la main.

Quand je rentre ces mêmes nombres, le résultat affiché est 00.
Donc il y a 2 problèmes, un qui vient de l'algorithme, et un autre.

D'un point de vue algorithmique, pour résoudre le problème, il faudrait que 21 soit stocké en [0], [2], [1], afin que lors de l'inversement, le problème soit résolu en devenant [1], [2], [0].
Mais ça, je ne vois vraiment pas comment l'écrire...

Je viens de faire ça pour remédier à mon problème :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
void Addition (Entier_long a, Entier_long b)
{
    int taille_1=0, taille_2=0;
    int reste=0, i=0, s;
    int MaxTaille=0, MinTaille=0;
    taille_1=a.taille;
    taille_2=b.taille;
    int TailleTab=MaxTaille+1;
    int Somme[TailleTab];
 
    if(taille_1>=taille_2)
    {
        MaxTaille=taille_1;
        MinTaille=taille_2;
 
    }
    else
    {
        MaxTaille=taille_2;
        MinTaille=taille_1;
    }
    int j=0; /* Mettre des 0 devant le nb le plus petit ( en longueur ) */
    int TabInt[MaxTaille];
    if(b.taille<a.taille)
    {
        for (i=0;i<b.taille; i++)
        {
            TabInt[i]=b.Chiffres_sign[i];
        }
        for (i=0;i<(a.taille-b.taille);i++)
        {
            b.Chiffres_sign[i]=0;
        }
        for(i=i;i<a.taille;i++)
        {
            b.Chiffres_sign[i]=TabInt[j];
            j=j+1;
        }
    }
    else if (a.taille<b.taille)
        {
            for (i=0;i<a.taille; i++)
            {
                TabInt[i]=a.Chiffres_sign[i];
            }
            for (i=0;i<(b.taille-a.taille);i++)
            {
                a.Chiffres_sign[i]=0;
            }
            for(i=i;i<b.taille;i++)
            {
                a.Chiffres_sign[i]=TabInt[j];
                j=j+1;
            }
        }
 
 
    printf("b.Chiffre = ");
    for (i=0;i<MaxTaille;i++)
    {
        printf(" %d ",b.Chiffres_sign[i]);
    }
    printf("\n");
    printf("a.Chiffre = ");
    for (i=0;i<MaxTaille;i++)
    {
        printf(" %d ",a.Chiffres_sign[i]);
    }
    printf("\n");
 
 
    InverserTableau(&a);
    InverserTableau(&b);
 
    for (i=0 ; i<MaxTaille ; i++)
    {
        s=a.Chiffres_sign[i]+b.Chiffres_sign[i]+reste;
        if (s>9)
        {
            Somme[i]=s%10;
            reste=1;
        }
        else
        {
            Somme[i]=s;
            reste=0;
        }
    }
 
    /* Affichage de l'addition */
    for(i=TailleTab;i>=0;i--)
    {
        printf("%d", Somme[i]);
    }
}

Grâce aux affichages, on peut voir que le nombre le plus petit est complété par un ou des 0 devant. Mais il doit avoir une histoire de pointeurs, car si je lance mon programme comme ça, j'ai le même problème qu'avant, donc je pense qu'il faut ajouter des pointeurs, mais je ne sais pas où les mettre.

PS :

Je viens d'ajouter des pointeurs partout. Je n'ai pas de problèmes de compilation, donc je pense qu'ils sont bons.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
void Addition (Entier_long *a, Entier_long *b)
{
    int taille_1=0, taille_2=0;
    int reste=0, i=0, s;
    int MaxTaille=0, MinTaille=0;
    taille_1=a->taille;
    taille_2=b->taille;
    int TailleTab=MaxTaille+1;
    int Somme[TailleTab];
 
    if(taille_1>=taille_2)
    {
        MaxTaille=taille_1;
        MinTaille=taille_2;
 
    }
    else
    {
        MaxTaille=taille_2;
        MinTaille=taille_1;
    }
 
    int j=0;
    int TabInt[MaxTaille];
 
    if(b->taille < a->taille)
    {
        for (i=0;i<b->taille; i++)
        {
            TabInt[i]=b->Chiffres_sign[i];
        }
        for (i=0;i<(a->taille-b->taille);i++)
        {
            b->Chiffres_sign[i]=0;
        }
        for(i=i;i<a->taille;i++)
        {
            b->Chiffres_sign[i]=TabInt[j];
            j=j+1;
        }
    }
    else if (a->taille < b->taille)
        {
            for (i=0;i<a->taille; i++)
            {
                TabInt[i]=a->Chiffres_sign[i];
            }
            for (i=0;i<(b->taille-a->taille);i++)
            {
                a->Chiffres_sign[i]=0;
            }
            for(i=i;i<b->taille;i++)
            {
                a->Chiffres_sign[i]=TabInt[j];
                j=j+1;
            }
        }
 
 
    printf("b.Chiffre AVANT inversion = ");
    for (i=0;i<MaxTaille;i++)
    {
        printf(" %d ",b->Chiffres_sign[i]);
    }
    printf("\n");
    printf("a.Chiffre AVANT inversion = ");
    for (i=0;i<MaxTaille;i++)
    {
        printf(" %d ",a->Chiffres_sign[i]);
    }
    printf("\n");
 
    InverserTableau(&*a);
    InverserTableau(&*b);
 
    printf("b.Chiffre APRES inversion = ");
    for (i=0;i<MaxTaille;i++)
    {
        printf(" %d ",b->Chiffres_sign[i]);
    }
    printf("\n");
    printf("a.Chiffre APRES inversion  = ");
    for (i=0;i<MaxTaille;i++)
    {
        printf(" %d ",a->Chiffres_sign[i]);
    }
    printf("\n");
 
    for (i=0 ; i<MaxTaille ; i++)
    {
        s=a->Chiffres_sign[i]+b->Chiffres_sign[i]+reste;
        if (s>9)
        {
            Somme[i]=s%10;
            reste=1;
        }
        else
        {
            Somme[i]=s;
            reste=0;
        }
    }
 
    /* Affichage de l'addition */
    for(i=TailleTab;i>=0;i--)
    {
        printf("%d", Somme[i]);
    }
    printf("\n");
}

Cependant le résultat n'est toujours pas bon, n'y aurait-il pas un problème de pointeur avec le x par hasard dans cette procédure ? Car je me suis aperçu que ca n'inverse pas, ou mal, le nombre où les 0 ont été ajouté. L'autre nombre s'inverse très bien.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void InverserTableau(Entier_long *a) /* Inverse le tableau Chiffres_sign[] de Entier_long */
{
    int i1=0;
    int i2=((*a).taille-1);
    int x;
    while(i1<i2)
    {
        x=(*a).Chiffres_sign[i1];
        (*a).Chiffres_sign[i1]=(*a).Chiffres_sign[i2];
        (*a).Chiffres_sign[i2]=x;
        i1=i1+1;
        i2=i2-1;
    }
}

Hello,

Bon, je crois que ton code devient trop compliqué par rapport à ce qu'il devrait être, donc je te propose de reprendre étape par étape. Pour commencer, on se concentre sur le fonction d'inversion.

1. Passage d'argument

Code:

void InverserTableau(Entier_long a);

Effectivement, comme l'a souligné jopopmk, si tu fais une fonction avec ce prototype, InverserTableau va travailler sur une copie de la variable que tu as passé en paramètre. La copie sera donc inversée, mais pas l'original, donc tu auras fais tout ça pour rien. Tu pourrais retourner le résultat de l'inversion de la façon suivante:
Code:

1 2 3 4 5 6 7 8 9 10 /* prend un Entier_long en paramètre, l'inverse, * et retourne le résultat. */ Entier_long InverserTableau(Entier_long a) { /* * faire le job... */ return resultat; }
L'inconvénient est que le type Entier_long est assez "gros", et il est donc plus efficace de passer par les pointeurs. Par contre, habituellement on écrira plutôt la fonction de la sorte:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void InverserTableau(Entier_long *a) /* Inverse le tableau Chiffres_sign[] de Entier_long */ { int i1=0; int i2=a->taille-1; int x; while(i1<i2) { x=a->Chiffres_sign[i1]; a->Chiffres_sign[i1]=a->Chiffres_sign[i2]; a->Chiffres_sign[i2]=x; i1=i1+1; i2=i2-1; } }
Maintenant, je te recommande de faire une batterie de tests sur cette fonction, et une fois que tu t'es assuré qu'elle fait le job sans faillir, on n'en parle plus.

2. Le calcul

Je n'ai pas compris pourquoi tu voulais ajouter des zéros. Je crois qu'à force de buter sur ce code, tu as fini par t'embrouiller. Donc, reprenons tranquillement sur ce qu'il y a à faire:

On veut additionner a et b, tous deux de type Entier_long
On inverse a->Chiffres_sign[] et b->Chiffres_sign
Soit i un index initialisé à zéro
Soit r un nombre entier initialisé à zéro pour mémoriser la retenue
Si i est strictement inférieur à a->taille ET à b->taille, alors:
On calcul chiffre = a->Chiffres_sign[i] + b->Chiffres_sign[i] + r
Sinon, si i est strictement inférieur à a->taille, alors:
On calcul chiffre = a->Chiffres_sign[i] + r
Sinon:
On calcul chiffre = b->Chiffres_sign[i] + r
FinSi
r = chiffre / 10 (division euclidienne, encore appelée division entière, à mémoriser pour le prochain tour)
chiffre = chiffre % 10
On pose resultat->Chiffres_sign[i] = chiffre
On incrémente i de 1
On repart au numéro 5 tant que i est strictement inférieur à a->taille OU à b->taille
En sortant de la boucle, si r n'est pas nul, on rajoute un resultat->Chiffres_sign[i] = r
Puis on inverse à nouveau a et b pour les remettre dans leur état d'origine

Voilà en gros. A prendre avec précautions, car j'ai fait ça vite. La question qu'il faut vite te poser, c'est où tu vas stocker le résultat de l'addition.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 /* avec ce prototype, la seule façon de récupérer le résultat de * mon addition c'est si a ou b stocke le résultat. Il peut en découler * pas mal de problèmes si tu oublies que les opérandes de ton opération * s'en trouvent modifiées. */ void Addition (Entier_long *a, Entier_long *b); /* tu pourrais retourner le résultat de cette façon, * mais ce ne serait pas très efficace en termes de temps * d'exécution, vu la taille de ton type Entier_long. */ Entier_long Addition (Entier_long *a, Entier_long *b); /* la meilleure alternative, pour moi, c'est d'ajouter un troisième * paramètre, qui serait un pointeur sur la variable où le résultat * doit être stocké. */ void Addition (Entier_long *a, Entier_long *b, Entier_long *resultat);
Ouf! bon, je te laisse méditer tout ça, il est vraiment temps que je retourne au boulot!
Bon courage

@nnovic: Penser à utiliser des pointeurs const pour les entiers longs qui ne seront pas modifiés:

Code:

1
2
3
4
5
6
7
8
/*Exemple 1 ("code deux adresses")*/
void Addition (Entier_long *a, Entier_long const *b);
 
/*Exemple 2*/
Entier_long Addition (Entier_long const *a, Entier_long const *b);
 
/*Exemple 3 ("code trois adresses")*/
void Addition (Entier_long const *a, Entier_long const *b, Entier_long *resultat);

15/03/2016, 10h14
jopopmk

Re,

oui c'est la même chose, la flèche va éviter de surcharger ton code.
Et non, le fait d'utiliser des pointeurs plutôt que des copies n'est pas le souci (du moins pour ce problème).
Par contre le problème des pointeurs, dans ta fonction Addition, c'est que l'inversion est permanente.

J'ai un peu du mal à lire et comprendre ton algo dans ce code un peu fouilli (pour rester sommaire) et je ne peux pas tester ton code, mon compilo est en C89 : même si ça compilait (ce qui n'est pas le cas) j'aurais des erreurs à l'exécution.

Perso :
- je passerai un troisième Entier_long* qui servirait de sortie pour le résultat,
- je parcourerai a et b depuis la fin, sans les inverser, à l'aide de pointeurs
- j'écrirai à l'envers dans c avant de, lui, l'inverser
Avantages : simplification du code, pas de modification des entrées, pas de complétion inutile avec des zéros, pas de tableau intermédiaire, pas de boucle for toutes les 5 lignes, pas de gestion de qui est le plus long ...
16/03/2016, 18h41
St-42-FCM-57

1 pièce(s) jointe(s)

Bonjour,

J'ai modifié la procédure d'inversement en mettant des flèches comme tu vous me l'avez dit.
J'ai ensuite fait des tests dessus, et elle a l'air de fonctionner correctement (elle fonctionnait déjà).

Ensuite, je dois avouer que je suis un peu embrouillé car vous me proposez 2 méthodes différentes.
Celle de jopopmk est sans doute plus élaborée, mais je suis assez novice en C, et j'ai des doutes sur les pointeurs (rien que le fait de pointer sur la dernière valeur de a.Chiffres_sign et b.Chiffres_sign me parait abstrait, car ils n'ont pas la même taille).

Donc je pense plutôt tenter comme nnovic me l'a dit, et c'est ce qui se rapproche le plus de ce que j'ai déjà fait.
Concernant les 0 que j'ajoute au début de mon nombre le plus petit, ça marche bien, j'ai testé plusieurs exemples sur papier.
Voici comment j'ai raisonné (pièce jointe).

Si vous comprenez pourquoi je mets des 0, est-ce que je dois continuer à le faire ou non ?

Je vais quand même me pencher sur le pseudo-code de nnovic. J'ai juste une question : c'est un faire...tant que (do...while() ) qu'il faut utiliser entre l'étape 5 et 15 inclus ?
17/03/2016, 09h49
jopopmk
Re,

je suis exactement comme toi : j'ai du mal à appréhender ton algo c'est pour ça que j'expose le mien :mrgreen:
Je te laisse donc poursuivre comme tu le sens, j'en profite juste pour faire quelques explications sur les pointeurs :
* un pointeur est un int qui contient une adresse (une position dans la mémoire),
* tu peux voir ce qu'il y a comme valeur à cette adresse en utilisant le caractère *
* pour une variable tu peux connaitre son adresse en utilisant le caractère &
* un tableau est en fait un pointeur vers le premier élément du tableau
Imaginons un tableau définit comme suit : int tab[10] = {0};
Alors :
- tab est l'adresse du premier élément du tableau
- tab équivaut donc à &(tab[0])
- tab+2 est l'adresse du première élément auquel on ajoute 2x la taille du type de base (ici un int)
- tab+2 est donc l'adresse du 3ème élément de ton tableau
- *(tab+2) est donc la valeur du troisième élément du tableau
Evidemment, pour ne pas pourrir la définition du tableau on ne manipulera pas directement tab, mais un autre int* qu'on aura préalablement fait pointé sur tab.

En espérant que ça t'aide un peu à comprendre le principe.
La notion de pointeur et la manipulation des adresses sont des bases importantes du C.

Bon dev.

Citation:

Envoyé par jopopmk

un tableau est en fait un pointeur vers le premier élément du tableau

Ce n'est pas exactement vrai.

Dans le cas normal, le tableau est converti implicitement en pointeur vers son premier élément, mais n'est pas lui-même un pointeur.
La preuve, c'est que si tu tentes de prendre son adresse avec un pointeur de pointeur:
Code:

1 2 3 int tab[10] = {0}; int** pTab; pTab = &tab;
Un compilo correctement configuré te dira que quelque chose n'est pas bon.

Ce qu'il faut, c'est un pointeur de tableau:
Code:

1 2 3 int tab[10] = {0}; int *(pTab)[10]; /* Oui c'est une notation bizarre. Il faut comprendre ça comme "int[10]* pTab;" */ pTab = &tab;
Mais quand le tableau est passé en paramètre de fonction, alors dans ce cas-là uniquement, le tableau est un pointeur.
Voici un code illustrant les deux cas:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void TestArrayC(int arrParam[20]) { int localArr[20]; int **pp; int (*pArr)[20]; pp = &arrParam; /*pArr = &arrParam;*/ /* warning: assignment from incompatible pointer type */ /*pp = &localArr;*/ /* warning: assignment from incompatible pointer type */ pArr = &localArr; (void)pp; (void)pArr; (void)arrParam; }
Les lignes commentées donnent un warning si on les décommente.

17/03/2016, 10h49
jopopmk

Il s'agit de lui faire comprendre le principe sachant qu'il dit être perdu.
Je remplace le "en fait" par un "peut être considéré" si tu préfères ;)
17/03/2016, 19h04
St-42-FCM-57

Bonjour,

Merci à vous pour les explications sur les pointeurs. C'est vrai que c'est un peu plus parlant d'avoir une synthèse comme ça, que les cours plutôt longs que l'on trouve sur internet.
Je pense qu'à force de manipuler différents codes où les pointeurs seront nécessaires, ça va finir par rentrer ;).

Pour en revenir à mon addition, elle a l'air de fonctionner, sans ajouter de 0. J'ai testé divers combinaisons, et ça me donne le résultat attendu.

Bon maintenant, il faut que je m'occupe du signe, c'est-à-dire si j'ai (+NombreA) + (-NombreB), il revient à faire une soustraction. Je vais essayer de créer une procédure de soustraction qui interviendra lorsque j'ai un nombre négatif.
Il faut déjà se souvenir de, comment nous posions les soustractions à l'école primaire... :mouarf: Non, sérieusement, je crois m'en souvenir un minimum, donc je vais tenter de retranscrire la méthode en algo.

Si je bloque, je reviendrai vers vous.
En attendant merci pour tout déjà !
17/03/2016, 19h57
picodev

Citation:

Envoyé par Médinoc

[...]
Mais quand le tableau est passé en paramètre de fonction, alors dans ce cas-là uniquement, le tableau est un pointeur.
[...]

En fait un tableau est toujours convertit en pointeur pointant sur le premier élément sauf dans 3 cas : quand il est l'opérande des opérateurs sizeof, _Alignof et &. (cf norme C11 section 6.3.2.1.3)
17/03/2016, 20h27
nnovic

Citation:

Envoyé par Stéphanois57

Bon maintenant, il faut que je m'occupe du signe, c'est-à-dire si j'ai (+NombreA) + (-NombreB), il revient à faire une soustraction. Je vais essayer de créer une procédure de soustraction qui interviendra lorsque j'ai un nombre négatif.

Hello,
Oui ça me semble être une bonne approche. Bon courage pour la suite !
23/03/2016, 16h44
St-42-FCM-57
Bonjour,

Bon, j'ai réussit à finir mon addition, et à faire ma soustraction. C'est une bonne chose !
Je reviens vers vous, car j'ai un petit soucis pour commencer ma multiplication. En fait, c'est un soucis d'algorithme (et non pas un soucis de programmation pour le moment).
Quand on fait une multiplication à la main (par ex : 260 * 470 ), on commence commence par multiplier le 0 du 470 par le 0 du 260, ensuite 0*6... et ainsi de suite.
Ca donne ça :
Code:

1 2 3 4 5 6 7 8 9 260 * 470 __________ 000 + 18200 + 104000 __________ 122200
Je ne vois pas comment 'stocker' mes lignes à additionner. Je sais que le nombre de ligne est le même que le nombre de chiffres qui composent l'opérande b (si on considère a=260 et b=470).
C'est vraiment ce problème de "stockage" qui me bloque pour l'instant, car je ne vois pas comment générer n lignes si mon nombre b comporte n chiffres. De plus, je pense qu'il faut ajouter des 0 à la fin des lignes (à partir de la 2ème) : 0 à la 2ème ligne, 00 à la troisième ligne , 000 à la quatrième (n'existe pas dans mon exemple) ... soit (n-1) zéro si on a n lignes. On peut aussi travailler sur les inverses comme précédemment pour la fonction d'addition.
Je n'ai pas vraiment de code à vous proposer du coup, mais j'avais pensé à faire 2 boucles 'for' comme suit :
Code:

1 2 3 for (i=b.taille-1 ; i>=0 ; i--) for (j=a.taille-1 ; i>=0 ; j--)
Cependant je ne suis pas sûr de partir sur une base juste.
Pourriez-vous m'aider ?

Merci d'avance !
24/03/2016, 08h10
ternel
En fait, tu peux stocker la ligne en cours et le résultat "jusque là".
```
            260
*           470
      __________
            000
+         18200
+        104000
      __________
         122200
```
En fait, il suffirait de
définir le résultat final comme 0
calculer 0*260 = 0, et l'ajouter au résultat final.
calculer 70*260=18200 puis l'ajouter au résultat final
etc
retourner le résultat final.
24/03/2016, 13h32
St-42-FCM-57

Je ne sais pas si c'est une faute de frappe et que tu as oublié le 4 devant 70, mais si ce n'est pas le cas, pourquoi ne multiplier que par 70 et non pas par 470 ?

Mes stockages, vaut-il mieux les ranger dans une variable int (qui risque de saturer car je suis censé travailler avec des entiers longs), ou les ranger en créant une nouvelle variable de type Entier_long ?
Je ne peux pas prévoir à l'avance la taille de mon résultat ? Il faut donc incrémenter la taille au fur et à mesure de l'avancée du calcul ?

Bonjour,

Ce que Leternel essaye de t'expliquer est que pour multiplier 2 entiers longs il faut savoir :

additionner deux entiers longs
multiplier un entier long par un nombre s'écrivant avec un chiffre
multiplier par un entier long par 10 = décaler tous les chiffres d'une position à gauche et ajouter un 0 à droite
utiliser un accumulateur pour faire plusieurs additions une à la fois

Ton exemple 260*470 donne :
260*470 = (260*4)*10*10 + (260*7)*10 + (260*0)
ce qu'on peut aussi réécrire
260*470 = [ (260*4)*10+(260*7) ] * 10 + (260*0)

Du coup un premier algo donnerait :
Code:

1 2 3 4 5 6 7 8 fonction multiplier(entier long op1, entier long op2) : entier long début accumulateur : entier long = 0 pour i de nombre de chiffre de opérande 2 à 1 faire accumulateur = multiplier_par_10(accumulateur) + multiplier(op1, chiffre en position i de op2) fin pour renvoyer accumulateur fin
Reste à écrire la multiplication par 10 (facile) et la multiplication par un nombre de un chiffre (pas compliqué).

24/03/2016, 14h31
ternel

J'avais volontairement mis un "etc" :aie:
28/03/2016, 16h43
St-42-FCM-57

Bonjour,
Désolé de répondre seulement maintenant, je n'ai pas trop eu le temps avant.

Dans les méthodes que vous me proposez, il faut utiliser une fonction d'addition. Seulement, moi ce n'est pas une fonction, c'est une procédure d'addition que j'ai. Il faut que change ma procédure en fonction, ou une procédure arrivera également à faire le travail pour la multiplication ? (ce serait dommage pour moi de changer ma procédure en fonction, car je m'étais bien bataillé avec tous ces pointeurs, mais bon...)

EDIT : J'ai finalement changé mes procédures en fonction, ça marche aussi bien, ça me faisait juste mal au cœur pour mes pointeurs... :oops:

Cependant, je suis désolé, mais malgré vos explications, je ne comprends pas comment faire ma multiplication...
29/03/2016, 09h08
ternel

procédure ou fonction, ca ne change rien.
Quelle que soit le choix, tu peux écrire une instruction qui fait une addition de deux nombres et place le résultat dans un troisième.
Partant de là, il te faut une opération intermédiaire: la multiplication par un nombre rond comme 1000 ou 200 (dans ton exemple, 0, 70 et 200)
29/03/2016, 09h32
nnovic
Hello,

Alors, pour rebondir sur le message de picodev, il faudrait que tu décomposes les actions d'une multiplication "à la main".

En gros, lorsque que tu multiplies deux nombres de plusieurs chiffres chacun, tu réalises plusieurs petites multiplications, dont tu additionnes les résultats. Par exemple:
Code:

1 2 3 4 5 6 7 8 9 260 x 470 ------ 000 (résultat de 0 x 260) 1820. (résultat de 7 x 260) 1040.. (résultat de 4 x 260) ------ 122200
Donc la première chose que tu as besoin de réaliser, c'est une fonction qui multiplie un nombre entier quelconque (ex: 260) par un nombre d'un seul chiffre (ex: 0, 7, 4, ...)
Cette fonction te servira de brique de construction pour développer ensuite une fonction qui multiplie un nombre entier quelconque pour un autre (ex: 260 x 470).
29/03/2016, 09h39
ternel

J'apporte une précision, en C, il n'y a pas de procédure.
Il n'y a que des fonctions, qui éventuellement ne retourne pas de valeur (type de retour: void).

Il n'est pas rare d'entendre parler de procédure pour une telle fonction, mais c'est une reprise d'un vocabulaire plus ancien.

Bonjour,

J'ai réussit à faire ça pour le moment :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
Entier_long Multiplication(Entier_long a, Entier_long b)
{
	Entier_long Acopie = a; /* Travail sur des copies de a et b */
	Entier_long Bcopie = b;
 
	if (Bcopie.taille>Acopie.taille) /* Toujours avoir le nb le plus petit (en taille) en 2eme operande */
	{
		Entier_long temp; /* Variable pour l'inversement */
		temp = Acopie; /* temp <-- a */
		Acopie = Bcopie; /* a <-- b */
		Bcopie = temp; /* b <-- temp */
	}
	int chiffre;
	Entier_long TabInter; /* TabInter qui stocke les valeurs à additionner */
	TabInter.taille = Acopie.taille;
	TabInter.signe = '+';
 
	int cpt;
	Entier_long resultat;
	resultat.taille = b.taille;
	for (cpt = 0; cpt < resultat.taille; cpt++)
	{
		resultat.Chiffres_sign[cpt] = 0;
	}
	resultat.signe = '+';
	int retenue = 0;
 
	int i, j, k=0 ;  /* k indice pour remplir dans l'ordre TabInter.Chiffres_sign[] */
	for (j = Bcopie.taille - 1; j >= 0; j--) /* Indice sur B. Operande du bas dans multiplication a la main */
	{
		for (i = Acopie.taille - 1; i >= 0; i--) /* Indice sur A. Operande du haut dans multiplication a la main */
		{
			chiffre = Bcopie.Chiffres_sign[j] * Acopie.Chiffres_sign[i] + retenue;
			if (chiffre <= 9)
			{
				TabInter.Chiffres_sign[k] = chiffre;
				retenue = 0;
			}
			else if (chiffre > 9 && i>0)
			{
				retenue = chiffre / 10;
				TabInter.Chiffres_sign[k] = chiffre % 10;
			}
			else if (chiffre > 9 && i == 0) /* on est au niveau du chiffre le plus a gauche de A, il faut donc afficher toute la variable chiffre */
			{
				TabInter.taille = TabInter.taille + 1;
				TabInter.Chiffres_sign[k] = chiffre % 10;
				TabInter.Chiffres_sign[k+1] = chiffre / 10;
			}
			k = k + 1;
		}
 
	}
	InverserTableau(&TabInter);
	return TabInter;
}

Bon là je retourne TabInter car je voulais essayer dans un premier temps de multiplier le chiffre le plus à droite de b par tous ceux de a. Apparemment, ce que j'ai fait fonctionne.
Après, je ne sais pas si mon stockage est bon pour arriver à ce que je souhaite ? Et en faisant comme ceci, je ne vois pas comment générer mes autres lignes à additionner ?