Partage

zBigInt

Solutions

<< 1 2 3 >>

18 février 2010 à 17:53:58

J'ai fait un petit truc rapidos sans retourner la chaîne

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

void soustraction(char * a, char * b, char * c) {
	(void)a, (void)b, (void)c;
	
}

void addition(char * a, char * b, char * c) {
	int i, j;
	int len_a, len_b, max;
	
	if (*a == '-' && *b != '-') {
		soustraction(b, a+1, c);
		return;
	}
	else if (*a != '-' && *b == '-') {
		soustraction(a, b+1, c);
		return;
	}
	else if (*a == '-' && *b == '-') {
		*c = '-';
		a++, b++, c++;
	}
	
	len_a = strlen(a);
	len_b = strlen(b);
	max = (len_a > len_b) ? len_a : len_b;
	
	for (i = 0; i <= max; i++)
		c[i] = 0;
	
	for (i = len_a-1, j = max-1; i >= 0; i--, j--)
		c[j] = a[i] - '0';
	
	for (i = len_b-1, j = max-1; i >= 0; i--, j--)
		c[j] += b[i] - '0';
	
	
	for (i = max-1; i > 0; i--) {
		if (c[i] > 9) {
			c[i] -= 10;
			c[i-1]++;
		}
	}
	
	if (c[0] > 9) {
		for (i = max; i > 0; i--)
			c[i] = c[i-1];
		c[1] -= 10;
		c[0] = 1;
		max++;
	}
	
	for (i = 0; i < max; i++)
		c[i] += '0';
}

int main(void) {
	char a[10] = "10";
	char b[10] = "90";
	char c[11] = "";
	
	addition(a, b, c);
	
	printf("%s\n", c);
	return 0;
}

Mais finalement je trouve ça beaucoup plus compliqué que de retourner la chaîne

colbseton

18 février 2010 à 17:57:10

C'est ce que j'ai fais, seulement la condition doit être

if( ... > 9) // et pas > 10

Sinon, quand il y aura un résultat de 10, il n'y aura pas de retenue.

Pouet_forever

18 février 2010 à 18:01:12

C'est édité

Et tu t'es compliqué un peu la vie

on peut améliorer

colbseton

18 février 2010 à 18:13:41

Je reposte le code final de la fonction addition :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define T 10

void reverse(char *s)
{
        int i, len = strlen(s);
        char tmp;

        for (i = 0; i < len-1-i; i++) {
                tmp = s[i];
                s[i] = s[len-1-i];
                s[len-1-i] = tmp;
        }
}

void addition(char *a, char *b, char *c)
{
        int i = 0, len = strlen(a);

        for (; i < len ; i++) {
                if (((a[i] -'0') + (b[i] - '0')) > 9) { // si l'addition est plus grande que 9
                        c[i] = (a[i] -'0') + (b[i] - '0') - 10 + '0'; // alors on stock le (résultat - 10)
                        a[i+1] = a[i+1] - '0' + ('1' - '0') + '0'; // et on ajoute la retunue  dans la case d'après
                }

                else c[i] = (a[i] -'0') + (b[i] - '0') + '0';//sinon on additionne normalement
        }

}

int main(void)
{
        char a[] = "0555", b[] = "0555", c[T] = "";

        reverse(a), reverse(b);
        addition(a,b,c);
        reverse(c);
        printf("%s\n", c);

        return 0;
}

Je pense là où je me suis compliqué la vie, c'est quand j'additionne. Je suis toujours en train de faire -'\0' et +'\0'

Il faut maintenant que je gère le cas où a et b ne sont pas de la même taille, les différentes bases et si les entrées sont :

char a[] = "50", b[] = "50";
//et non pas :
char a[] ="050", b[] = "050";

GurneyH

19 février 2010 à 4:10:24

@Pouet_forever : ton addition fonctione bien, il faut juste prendre garde à

for (i = 0; i <= max; i++)
    c[i] = 0;

En faisant plusieurs addition à la suite, les résultats sont faux.

Zeste de Savoir, le site qui en a dans le citron !

darkipod

19 février 2010 à 10:15:50

Citation : GurneyH

Je pense que retourner la chaîne est la solution la plus simple, car elle permet d'écrire dans la chaîne de destination en partant de la gauche.

On ne connait pas exactement la taille de la destination(à une unité près), donc c'est certainement plus facile d'étendre vers la droite que vers la gauche(indice -1).

Mais, il n'y a pas qu'une seule solution.

je reprends mon algo, en retournant la chaine.......car en plus de la retenue ou non ,le problème du signe se posera plus tard

et vu comment je m'y suis pris c'est pas gagné :euh:

colbseton

19 février 2010 à 13:35:25

Euh simple question, j'avais dans mon code cette fonction :

void reverse(char *s)
{
        int i, len = strlen(s) - 1;
        char tmp;

        for (i = 0; i < len-i; i++) {
                tmp = s[i];
                s[i] = s[len-i];
                s[len-i] = tmp;
        }
}

Dans mon main, je faisais ceci :

int main(void)
{
        char *a = "05", *b = "06";

        reverse(a), reverse(b);

        return 0;
}

Sauf que j'ai un segmentation fault, il faut que je déclare mes char en tableau pour faire sauter le bug, pourquoi ?

Edit : @GurneyH : j'en connais un qui regarde les J-O

GurneyH

19 février 2010 à 13:52:37

char *a = "05", *b = "06";

Ne déclare des chaînes littérales que si tu est certain de ne pas les modifier.
Vu que

reverse(a), reverse(b);

C'est horrible!

Tu ne peux pas pas modifier le contenu de a ou b, le comprtement est indéfini!

C'est déclarations sont équivalentes à

char const *a = "05";
  char const *b = "06";

Zeste de Savoir, le site qui en a dans le citron !

Pouet_forever

19 février 2010 à 20:03:39

@GurneyH : Ouais j'y avais pensé, mais bon dans ce cas il faut tout faire autrement

Si c contient déjà quelque chose, il faut prendre aussi la longueur de c en compte pour pouvoir faire le calcul exact. Mais si la chaîne passée en paramètre est non initialisée ça va segfault comme il faut :-°

Faut voir, l'exo demande quoi exactement ?

GurneyH

19 février 2010 à 21:33:14

Citation : Pouet

Faut voir, l'exo demande quoi exactement ?

Hum, hormis le fait que C doit être déclarée avec une taille suffisante, pas grand chose n'est précisé(mais qui écrit les énoncés? :-°

).
A mon sens la fonction additon doit remplir C avec un un résultat correct(a + b) quel que soit le contenu de C à l'appel de la fonction.

Zeste de Savoir, le site qui en a dans le citron !

colbseton

20 février 2010 à 13:45:59

Un premier jet pour la soustraction

, je ne gère pas encore le cas où a < b .

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define T 10

void reverse(char *s)
{
        int i, len = strlen(s) - 1;
        char tmp;

        for (i = 0; i < len-i; i++) {
                tmp = s[i];
                s[i] = s[len-i];
                s[len-i] = tmp;
        }
}

void soustraction(char *a, char *b, char *c)
{
        int i = 0, len = strlen(a);

        for(; i < len; i++) {
                if(((a[i] - '0') - (b[i] - '0')) < 0) {
                        a[i] = a[i] - '0' + 10 + '0'; // on rajoute 10
                        c[i] = (a[i] - '0') - (b[i] - '0') + '0';
                        b[i+1] = b[i+1] - '0' + 1 + '0'; // et on passe la retenue
                }

                else c[i] = (a[i] - '0') - (b[i] - '0') + '0';
        }
}

int main(void)
{
        char a[] = "10", b[] = "06", c[T] = "";

        reverse(a), reverse(b);
        soustraction(a,b,c);
        reverse(c);
        printf("%s\n", c);

        return 0;
}

J'ai remarqué qu'avec mes codes, je fais un débordement de pile (stack mashing c'est écrit) quand mes char dépassent le milliard

Pouet_forever

20 février 2010 à 14:00:08

Avec 100-6 je me retrouve avec a_4
Tu calcules 50 fois (a[i] - '0') tu penses pas qu'une variable serait le bienvenu ? (pareil pour b).

@ GurneyH : Heuu, ça veut dire que si j'appelle ma fonction addition il faut que j'additionne le résultat de a+b à c (donc a+b+c), et si je soustrais j'ai a-b+c ?

colbseton

20 février 2010 à 14:12:47

Euh oui, j'avais oublié de préciser que les chaines devait être de longueur égale.
Pour le a[i] - '0', comment veux tu que je stock ça puisque la valeur de a[i] change à chaque tour de boucle.

GurneyH

20 février 2010 à 14:16:40

Citation : Pouet_forever

Avec 100-6 je me retrouve avec a_4
Tu calcules 50 fois (a[i] - '0') tu penses pas qu'une variable serait le bienvenu ? (pareil pour b).

@ GurneyH : Heuu, ça veut dire que si j'appelle ma fonction addition il faut que j'additionne le résultat de a+b à c (donc a+b+c), et si je soustrais j'ai a-b+c ?

Non, non...
C doit contenir le résultat de A + B, c'est tout...
Seulement, Il faut que le résultat soit juste quelque soit le contenu de C au départ.

Zeste de Savoir, le site qui en a dans le citron !

Pouet_forever

20 février 2010 à 14:22:22

Heum j'ai pas dû tout comprendre :-°

Je pense que c'est ça que tu voulais :

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

void soustraction(char * a, char * b, char * c) {
	(void)a, (void)b, (void)c;
	
}

void addition(char * a, char * b, char * c) {
	int i, j;
	int len_a, len_b, max;
	
	if (*a == '-' && *b != '-') {
		soustraction(b, a+1, c);
		return;
	}
	else if (*a != '-' && *b == '-') {
		soustraction(a, b+1, c);
		return;
	}
	else if (*a == '-' && *b == '-') {
		*c = '-';
		a++, b++, c++;
	}
	
	len_a = strlen(a);
	len_b = strlen(b);
	max = (len_a > len_b) ? len_a : len_b;
	
	for (i = 0; i <= max; i++)
		c[i] = 0;
	
	for (i = len_a-1, j = max-1; i >= 0; i--, j--)
		c[j] = a[i] - '0';
	
	for (i = len_b-1, j = max-1; i >= 0; i--, j--)
		c[j] += b[i] - '0';
	
	
	for (i = max-1; i > 0; i--) {
		if (c[i] > 9) {
			c[i] -= 10;
			c[i-1]++;
		}
	}
	
	if (c[0] > 9) {
		for (i = max; i > 0; i--)
			c[i] = c[i-1];
		c[1] -= 10;
		c[0] = 1;
		max++;
	}
	
	for (i = 0; i < max; i++)
		c[i] += '0';
	c[max] = '\0';
}

int main(void) {
	char a[10] = "10";
	char b[10] = "90";
	char c[11] = "";
	
	addition(a, b, c);
	printf("%s\n", c);
	return 0;
}

GurneyH

20 février 2010 à 14:33:09

Citation : Pouet_forever

Je pense que c'est ça que tu voulais :

Là ça passe mes tests(comparaison avec gmp...), sans que je ne touche à rien...
Ce n'était pas le cas avant.

Là ça semble impec. Reste la soustraction. :diable:

Zeste de Savoir, le site qui en a dans le citron !

colbseton

20 février 2010 à 16:30:15

@Pouet :
A quoi te sert ce bout de code ?

if (c[0] > 9) {
	for (i = max; i > 0; i--)
		c[i] = c[i-1];
	c[1] -= 10;
	c[0] = 1;
	max++;
}

Puisque tu gères les retenues juste avant.
Et tant que j'y suis, je comprends pas ce que fait ta fonction soustraction

.
Ptite question, on a le droit de stocker des int dans un tableau de char ?

Pouet_forever

20 février 2010 à 16:42:51

Ca gère la première retenue en fait

Toutes les retenues sont gérées avant, mais pas la première. Si ya une retenue je décale toute la chaîne d'un 'cran' à gauche et je met la retenue

Ma fonction soustraction ne fait rien :lol:

Tu peux stocker un int tant qu'il ne dépasse pas la taille d'un char.

colbseton

20 février 2010 à 16:49:49

Citation : Pouet

Tu peux stocker un int tant qu'il ne dépasse pas la taille d'un char.

Si j'avais su, j'aurais fais un programme différent

. Je vais tenter d'une autre manière.
On est d'accord que tu prends les chaînes en partant du dernier indice ?

Pouet_forever

20 février 2010 à 16:55:09

C'est ce que je fais oui

colbseton

20 février 2010 à 17:25:03

J'ai repris ta technique Pouet, pour la fonction addition, mais ici je post la fonction soustraction.
Je n'ai toujours pas gérer le cas où a < b...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define T 10

void reverse(char *s)
{
        int i, len = strlen(s) - 1;
        char tmp;

        for (i = 0; i < len-i; i++) {
                tmp = s[i];
                s[i] = s[len-i];
                s[len-i] = tmp;
        }
}

void soustraction(char *a, char *b, char *c)
{
        int i, j;
        size_t len_a = strlen(a), len_b = strlen(b);
        size_t len_max = len_a > len_b ? len_a : len_b;

        for(i = 0; i < len_max; i++) c[i] = 0; // initialisation de la chaine

        i = 0, j = 0;

        for(; i < len_a && j < len_max; i++, j++)
                c[j] = a[i] -'0';

        i = 0, j = 0;

        for(; i < len_b && j < len_max; i++, j++) // on soustrait
                c[i] -= b[i] - '0';

        for(i = 0; i < len_max; i++) //on gère les retenues
                if(c[i] < 0) {
                        c[i] += 10;
                        c[i+1] -= 1;
                }

        for(i = 0; i < len_max; i++) // on convertit en char
                c[i] += '0';
}

int main(void)
{
        char a[] = "1006", b[] = "6", c[T] = "";

        reverse(a), reverse(b);
        addition(a,b,c);
        reverse(c);
        printf("%s\n", c);

        return 0;
}

Fonction addition modifiée à ma sauce

/* ne pas oublier la fonction reverse ! */

void addition(char *a, char *b, char *c)
{
        int i, j;
        size_t len_a = strlen(a), len_b = strlen(b);
        size_t len_max = len_a > len_b ? len_a : len_b;

        for(i = 0; i < len_max; i++) c[i] = 0; // initialisation de la chaine

        i = 0, j = 0;

        for(; i < len_a && j < len_max; i++, j++)
                c[j] = a[i] -'0';

        i = 0, j = 0;

        for(; i < len_b && j < len_max; i++, j++) // on additionne
                c[i] += b[i] - '0';

        for(i = 0; i < len_max; i++) //on gère les retenues
                if(c[i] > 9) {
                        c[i] -= 10;
                        c[i+1] += 1;
                }

        for(i = 0; i < len_max; i++) // on convertit en char
                c[i] += '0';
}

PS : Oui j'ai plagié

, mais j'aime cette méthode, elle est propre comparé à la mienne :-°

...

Pouet_forever

20 février 2010 à 17:40:33

Citation : Colb-Seton

Fonction addition modifiée à ma sauce

Hé oui, loupé

J'ai posté un autre code hein

colbseton

20 février 2010 à 18:01:41

Citation : Pouet_forever

Hé oui, loupé
J'ai posté un autre code hein

J'ai manqué cette ligne ?

c[len_max] = '\0';

Bof pas grave, je fais pas d'addition successive. :soleil:

Pouet_forever

20 février 2010 à 18:06:31

Voilà la soustraction :

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

void addition(char * a, char * b, char * c);
void soustraction(char * a, char * b, char * c);

#define SWAP_PTR(a, b) { char *tmp = a; a = b; b = tmp; }

void soustraction(char * a, char * b, char * c) {
	int i, j;
	int len_a, len_b, max;
	
	if (*a == '-' && *b != '-') {
		*c++ = '-';
		addition(a+1, b, c);
		return;
	}
	else if (*a != '-' && *b == '-') {
		addition(a, b+1, c);
		return;
	}
	else if (*a == '-' && *b == '-') {
		*c++ = '-';
		addition(a+1, b+1, c);
		return;
	}
	
	for ( ; *a && *a == '0'; a++)
		;
	for ( ; *b && *b == '0'; b++)
		;
	
	len_a = strlen(a);
	len_b = strlen(b);
	max = (len_a > len_b) ? len_a : len_b;
	
	/* Cas où a < b */
	if (len_a < len_b) {
		int tmp_len = len_a;
		len_a = len_b;
		len_b = tmp_len;
		*c++ = '-';
		SWAP_PTR(a, b)
	}
	/* Cas où les longueurs sont identiques.
	 * Il faut vérifier quel nombre est le plus grand. */
	else if (len_a == len_b) {
		for (i = 0; i < max; i++) {
			if (a[i] < b[i]) {
				SWAP_PTR(a, b)
				*c++ = '-';
				break;
			}
			else if (a[i] > b[i]) {
				break;
			}
		}
	}
	
	for (i = 0; i <= max; i++)
		c[i] = 0;
	
	for (i = len_a-1, j = max-1; i >= 0; i--, j--)
		c[j] = a[i] - '0';
	
	for (i = len_b-1, j = max-1; i >= 0; i--, j--)
		c[j] -= (b[i] - '0');
	
	
	for (i = max-1; i > 0; i--) {
		if (c[i] < 0) {
			c[i] += 10;
			c[i-1]--;
		}
	}
	
	if (c[0] == 0) {
		for (j = 0; j < max && c[j] == 0; j++)
			;
		max -= j;
		
		for (i = 0; i < max; i++, j++)
			c[i] = c[j];
	}
	
	if (max == 0) {
		c[0] = 0;
		max++;
	}
	
	for (i = 0; i < max; i++)
		c[i] += '0';
	c[max] = '\0';
}

void addition(char * a, char * b, char * c) {
	int i, j;
	int len_a, len_b, max;
	
	if (*a == '-' && *b != '-') {
		soustraction(b, a+1, c);
		return;
	}
	else if (*a != '-' && *b == '-') {
		soustraction(a, b+1, c);
		return;
	}
	else if (*a == '-' && *b == '-') {
		*c = '-';
		a++, b++, c++;
	}
	
	len_a = strlen(a);
	len_b = strlen(b);
	max = (len_a > len_b) ? len_a : len_b;
	
	for (i = 0; i <= max; i++)
		c[i] = 0;
	
	for (i = len_a-1, j = max-1; i >= 0; i--, j--)
		c[j] = a[i] - '0';
	
	for (i = len_b-1, j = max-1; i >= 0; i--, j--)
		c[j] += b[i] - '0';
	
	
	for (i = max-1; i > 0; i--) {
		if (c[i] > 9) {
			c[i] -= 10;
			c[i-1]++;
		}
	}
	
	if (c[0] > 9) {
		for (i = max; i > 0; i--)
			c[i] = c[i-1];
		c[1] -= 10;
		c[0] = 1;
		max++;
	}
	
	for (i = 0; i < max; i++)
		c[i] += '0';
	c[max] = '\0';
}

int main(void) {
	char a[10] = "-1000";
	char b[10] = "0";
	char c[11] = "";
	
	soustraction(a, b, c);
	printf("%s\n", c);
	return 0;
}

J'ai gardé le même principe que l'addition

colbseton

20 février 2010 à 18:20:21

Avec ça comme entrée :

char a[] = "6", b[] = "1000", c[T] = "";

Ça me renvoie *``a
Tu ne gères pas le cas où a < b, mais le cas où len_a < len_b.
'Fin le test était bon avec pour entrées :

//a et b doivent être de la même taille quand le résultat de la soustraction est -  ?
char a[] = "6", b[] = "7", c[T] = "";

Qu'est ce que ça fait ce bout de code

for ( ; *a && *a == '0'; a++)
		;
	for ( ; *b && *b == '0'; b++)
		;

edit : je viens juste de comprendre que tu gérais les chaînes avec "-"

.

Si j'ai bien compris quand tu fais b+1 ou a+1 ou c++, ou a++ ou b++, tu augmentes pour pas qu'on puisse toucher au caractère "-" ?

Pouet_forever

20 février 2010 à 18:54:19

Citation : Colb-Seton

Tu ne gères pas le cas où a < b, mais le cas où len_a < len_b.

C'est exactement pareil ! Si j'ai 1000 d'un part et 999 d'autre part, le premier nombre sera toujours supérieur que le deuxième quoi qu'il arrive !

Après j'ai juste oublié un petit truc :-°

je l'ai mis dans le else if mais pas dans le premier if ...
C'est édité

Et oui j'incrémente pour que le signe '-' reste intact

colbseton

20 février 2010 à 19:04:01

Mais ça sert à quoi ça ?

for ( ; *a && *a == '0'; a++)
		;
for ( ; *b && *b == '0'; b++)
	;

Tu parcours les chaines tant qu'elle contiennent le caractère '0' ? Quel intérêt ?

En tout cas ton code me plait bien, à part ptète la partie swap.
Bien joué

. Moi qui avait du mal pour gérer l'addition avec des tailles de chaine différentes :-°

GurneyH

20 février 2010 à 19:07:45

@Pouet, C ne contient que '\0' lorsque a et b sont éqaux.

Pour ton addition, problème avec les entiers relatifs.

-1000 - 0 -> _ '#

Zeste de Savoir, le site qui en a dans le citron !

Pouet_forever

20 février 2010 à 19:18:38

Citation : Colb-Seton

Mais ça sert à quoi ça ?

C'est au cas où j'ai des nombres qui commencent par des 0 (00010, 004225, 04, etc.). Sinon ça fausse la manière dont je traite ma chaîne, comme je joue avec les longueurs

@ GurneyH : Tu peux mettre un coup de débugger pour le -1000 - 0 stp parce que chez moi ça marche bien et je vois pas du tout d'où ça vient :euh:

Pour les nombres égaux c'est réglé, j'édite

GurneyH

21 février 2010 à 5:15:57

Citation : Pouet_forever

GurneyH : Tu peux mettre un coup de débugger pour le -1000 - 0 stp parce que chez moi ça marche bien et je vois pas du tout d'où ça vient

/* Cas où a < b */
	if (len_a < len_b) {
		SWAP_PTR(a, b)
	}

que tu as changé en

/* Cas où a < b */
	if (len_a < len_b) {
		int tmp_len = len_a;
		len_a = len_b;
		len_b = tmp_len;
		*c++ = '-';
		SWAP_PTR(a, b)
	}

Dans ta fonction soustraction.

Maintenant, addition et soustraction fonctionner bien, même pour les nombres relatifs.

Zeste de Savoir, le site qui en a dans le citron !

<< 1 2 3 >>

zBigInt

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.

× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.

zBigInt

Solutions

zBigInt

Supprimer

Modérer

Signaler le message aux modérateurs