Addition sur des entiers longs

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:

1. On veut additionner a et b, tous deux de type Entier_long
2. On inverse a->Chiffres_sign[] et b->Chiffres_sign
3. Soit i un index initialisé à zéro
4. Soit r un nombre entier initialisé à zéro pour mémoriser la retenue
5. Si i est strictement inférieur à a->taille ET à b->taille, alors:
6. On calcul chiffre = a->Chiffres_sign[i] + b->Chiffres_sign[i] + r
7. Sinon, si i est strictement inférieur à a->taille, alors:
8. On calcul chiffre = a->Chiffres_sign[i] + r
9. Sinon:
10. On calcul chiffre = b->Chiffres_sign[i] + r
11. FinSi
12. r = chiffre / 10 (division euclidienne, encore appelée division entière, à mémoriser pour le prochain tour)
13. chiffre = chiffre % 10
14. On pose resultat->Chiffres_sign[i] = chiffre
15. On incrémente i de 1
16. On repart au numéro 5 tant que i est strictement inférieur à a->taille OU à b->taille
17. En sortant de la boucle, si r n'est pas nul, on rajoute un resultat->Chiffres_sign[i] = r
18. 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);

---

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 ...

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 ?

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.

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 ;)

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à !

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)

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 !

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 !

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.

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é).

J'avais volontairement mis un "etc" :aie:

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...

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)

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).

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 ?