Forums des Zéros

14 février 2010 à 15:01:48

Bonjour,

Comme d'habitude, j'ouvre un topic dédié à l'exercice du moment..

Postés vos réponses ici, merci.

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

14 février 2010 à 15:46:38

J'ai posté sur le topic, j'avais pas vu que tu redirigeais vers un autre sujet

.
Je me suis donc attelé à la fonction addition. C'est bien la première fois que j'opère sur les grands nombres

.
Je post mon code :

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

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

    for(i = len; i > 0; i--){
        if(((a[i] -'\0') + (b[i] - '\0')) > 9)
            c[i+1] += 1 + '\0';

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

}

int main(void)
{
    char *a = "10", *b = "5", *c;
    int len_a = strlen(a), len_b = strlen(b);

    c = malloc(sizeof(char) * (len_a + len_b));

    addition(a,b,c);

    printf("%s", *c);
    return 0;
}

Alors le programme bug ok, j'ai débuggé et voici ce qu'il me répond :

Program received signal SIGSEGV, Segmentation fault.
In msvcrt!ceil () (C:\Windows\system32\msvcrt.dll)

Ca vient ptète du malloc ?

PS : mon code est certainement pas très propre, mais j'essaie

14 février 2010 à 15:49:42

Et pourquoi tu veux faire un malloc?

Dans un premier temps, fais des tests avec des chaînes en dur, quitte à allouer une chaîne c très grande.

Pour les premiers exercice, ne vous cassez pas la tête avec l'allocation dynamique, vous aurez bien le temps après... :diable:

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

14 février 2010 à 15:58:43

Je reposte ma fonction car j'avais remplacé les '0', par des '\0' ...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
    #define T 100
    
void addition(char* a, char* b, char* c)
{
    int i, len = strlen(a);

    for(i = len; i > 0; i--){
        if(((a[i] -'0') + (b[i] - '0')) > 9)
            c[i+1] += 1 + '0';

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

}

int main(void)
{
    char *a = "10", *b = "5", c[T];
    
    addition(a,b,c);
    printf("%s",c);

    return 0;
}

Je segfault plus, mais j'ai un caractère bizarre qui s'affiche

14 février 2010 à 16:04:32

i = len

len n'appartient pas à ton tableau, ça va jusqu'à len-1.
b fait 1 caractère et a en fait 2 et toi tu commences à 3 ... ya pas un problème ? lol

14 février 2010 à 16:14:18

Oui exact pour le len - 1, je sais pas trop ce que j'ai fais m'enfin.
Je vais d'abord commencer par définir mes chaînes a et b de la même taille, ce sera ptète plus simple.

char *a = "10", *b = "05", c[T];

J'ai aussi changé ces lignes, au lieu de += j'ai mi = et vice versa.

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

Résultat :

#5

C'est pas vraiment un #, mais c'est un caractère bizarre

darkipod

17 février 2010 à 14:50:36

.
juste une petite reflection comme cela :
la multiplication doit peux t'on se servir de la fonction "addition" ? en sachant que par exemple : 65 * 10 c'est additionné 10 fois le nombre 65
ou bien doit t'on faire comme la fonction "addition" posé l'operation :
65
*10
___
00
65
___
650

idem pour la division en se servant de la "soustraction". :-°

17 février 2010 à 16:02:18

J'ai modifié un peu mon code, alors il sait gérer les additions sans retenue et à condition que les chaînes soit de la même taille

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

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

        for (i = len - 1; i >= 0; i--) // on parcours à l'envers      
        {  
                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 = "005", *b = "005", c[T] = "";

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

        return 0;
}

Avec la retenue, le programme bug, à la ligne surlignée. Je travaillerai plus tard sur les chaînes de longueur différente.

Merci de votre aide

17 février 2010 à 17:06:58

@darkipod :
Oui, tu peux utiliser les fonctions addition et soustraction, pour multiplier et diviser. Même si je trouve plus intéressant d'utiliser la technique de multiplication apprise en primaire.

Pour la division, j'ai trouvé que trop de problèmes ce posaient. Mais si vous vous sentez le courage, rien ne vous empêches de l'ajouter.

@colb_seton:

a[i-1]

avec i >= 0. aie...

Pour éviter le problème, une solution c'est de parcourir tes tableaux dans le sens inverse.

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

17 février 2010 à 17:15:19

Citation : GurneyH

@colb_seton:
a[i-1]
avec i >= 0. aie...

Pour éviter le problème, une solution c'est de parcourir tes tableaux dans le sens inverse.

for (i = len - 1; i >= 0; i--) // on parcours à l'envers

17 février 2010 à 17:34:22

Dans le sens inverse que ce que tu fais. :-°

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

meteor2

17 février 2010 à 17:39:07

Est-ce qu'on a le droit de gérer les chaînes de caractères en les convertissants en int, en les additionants puis reconvertir en chaine?
Ou c'est pas du tout le but?

17 février 2010 à 17:46:58

Le but est de multiplier des très grands entiers, genre
"145794561234567894561231203456789001265".
Pour faire tenir ça dans un entier, c'est difficile.

Non, il faut faire les opérations directement sur les chaînes.

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

darkipod

17 février 2010 à 17:56:42

Bon un premier jet pour l'addition :

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

#define taille 100
#define base 10

void addition(char *a,char *b,char *c)
{
    /*fonction qui "additionne a et b", le resultat est c*/
    int i=strlen(a);//chaines a et b de même longueur
    char cc[taille*taille]={'0'};//chaine temporaire pour le resultat
    int k;
    int cx;
    int retenue=0;
    strcpy(cc,"");//a priori taille maximum de la chaine ?sinon bug
    strcpy(c,"");
    for (k=i-1;k>=0;k--)
    {
        cx=a[k]+b[k]-'0'-'0'+retenue;//transfert char --> int
        if (cx>=base)
        {
            retenue = cx / base;
            cx= cx % base;
        }
        else
        {
            retenue=0;
        }
        cc[k]=cx+'0';//transfert int --> char

    }
    if (retenue !=0)
    {
        c[0]=retenue+'0';
    }
    strcat(c,cc);
}

int main (void)
{

    char a[taille]="11777";
    char b[taille]="99888";
    char c[taille*taille];
    addition(a,b,c);
    printf("%s\n",c);
    return 0;
}

j'ai le meme soucis que colbseton il faut que les chaines soient de la meme taille

17 février 2010 à 18:49:20

Voilà un essai pour l'addition mais un truc que je ne comprends pas me turlupine, je ne vois pas comment corriger l'erreur que m'indique valgrind.
Autrement, la longueur des chaînes n'importe pas.

Les erreurs que m'indiquent valgrind (j'ai adapté les numéros de lignes) :

valgrind --track-origins=yes ./a.out
==3010== Memcheck, a memory error detector                                     
==3010== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.       
==3010== Using Valgrind-3.5.0-Debian and LibVEX; rerun with -h for copyright info
==3010== Command: ./a.out                                                        
==3010==                                                                         
==3010== Conditional jump or move depends on uninitialised value(s)              
==3010==    at 0x402596F: strcat (mc_replace_strmem.c:174)                       
==3010==    by 0x80486C4: addition (exo1.c:35)                                   
==3010==    by 0x8048862: main (exo1.c:83)                                       
==3010==  Uninitialised value was created by a heap allocation                   
==3010==    at 0x4024C1C: malloc (vg_replace_malloc.c:195)                       
==3010==    by 0x804863A: addition (exo1.c:22)                                   
==3010==    by 0x8048862: main (exo1.c:83)                                       
==3010==                                                                         
==3010== Conditional jump or move depends on uninitialised value(s)              
==3010==    at 0x402596F: strcat (mc_replace_strmem.c:174)                       
==3010==    by 0x80486E1: addition (exo1.c:38)                                   
==3010==    by 0x8048862: main (exo1.c:83)                                       
==3010==  Uninitialised value was created by a heap allocation                   
==3010==    at 0x4024C1C: malloc (vg_replace_malloc.c:195)                       
==3010==    by 0x804865F: addition (exo1.c:26)                                   
==3010==    by 0x8048862: main (exo1.c:83)                                       
==3010==                                                                         
1034
==3010==
==3010== HEAP SUMMARY:
==3010==     in use at exit: 0 bytes in 0 blocks
==3010==   total heap usage: 2 allocs, 2 frees, 10 bytes allocated
==3010==
==3010== All heap blocks were freed -- no leaks are possible
==3010==
==3010== For counts of detected and suppressed errors, rerun with: -v
==3010== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 13 from 8)

void
remove_zero (char * num, size_t len) {
    while ('0' == num[0]) {
        size_t i;
        for (i = 0 ; i < len ; ++i)
            num[i] = num[i+1];
    }
}

void
addition (char * dest, char * a, char * b) {
    size_t len_a, len_b;
    size_t len_dest;
    size_t i;
    int res, ret;
    char * cpa = NULL, * cpb = NULL;

    len_a = strlen(a), len_b = strlen(b);
    len_dest = (len_a > len_b) ? len_a+1 : len_b+1;
    res = ret = 0;

    if ((cpa = malloc(len_dest)) == NULL){
        perror("Error : Memory Allocation");
        return;
    }
    if ((cpb = malloc(len_dest)) == NULL){
        perror("Error : Memory Allocation");
        free(cpa);
        return;
    }
    
    /* On remplit de 0 les chaines pour qu'elles aient la meme longueur */
    for (i = 0 ; i < len_dest-(len_a+1) ; ++i)
        strcat(cpa, "0");
    strcat(cpa, a);
    for (i = 0 ; i < len_dest-(len_b+1) ; ++i)
        strcat(cpb, "0");
    strcat(cpb, b);
   
    for (i = len_dest-1 ; i > 0 ; --i) {
        res = cpa[i-1]+cpb[i-1]-2*'0'+ret, ret = 0;
        if (res > 9) {
            ret = res/10;
            res = res%10;
        }
            dest[i] = res+'0';
        if (1 == i) {
                dest[i-1] = ret+'0';
        }
    }

    free(cpa), cpa = NULL;
    free(cpb), cpb = NULL;
    remove_zero(dest, len_dest);

}

17 février 2010 à 18:57:14

J'ai toujours ce fichu problème,

for (; i < len; i++) 
        {
                if (((a[i+1] -'0') + (b[i+1] - '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 ('fin avant si on parle du sens de parcours du tableau)
                }

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

Est ce que mon algo est bon au moins ? Je pense que oui car c'est la façon bête et méchante de faire comme au primaire. Sauf que je parcours en partant de gauche, plutôt qu'en partant de droite.

Si j'essaie comme ça :

c[i+1] = (a[i+1] -'0') + (b[i+1] - '0') - 10 + '0'; // alors on stock le (résultat - 10)
a[i] = a[i] - '0' + ('1' - '0') + '0'; // et on ajoute la retunue  dans la case d'après

J'ai toujours un bug.

17 février 2010 à 19:07:20

@Colb-Seton:
Tu es obligé de parcourir le tableau de droite à gauche à moins que tu est renversée la chaîne ("128" =>"821"), car les retenues peuvent "se transmettre". ex : 999+1.

17 février 2010 à 19:26:11

@ Lithrein : Tu fais un malloc pour tes 2 nombres, mais quand tu fais un malloc ta mémoire n'est pas initialisée ! Ensuite tu fais un strcat sur ... n'importe quoi

Je pense que le plus simple est de parcourir les 2 chaînes en partant de la fin, d'additionner les nombres et mettre les retenues, s'il y en a, et ensuite de retourner la chaîne. Après ce n'est que mon avis

17 février 2010 à 19:58:03

Ah j'avance, je bug plus avec ce code

#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+1] -'0') + (b[i+1] - '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[] = "005", b[] = "005", c[T] = "";

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

        return 0;
}

Néanmoins, la sortie est :

00:

17 février 2010 à 20:05:01

@Pouet_forever :
Merci bien, j'ai changé les mallocs pour des callocs et tout est rentré dans l'ordre.

17 février 2010 à 20:22:02

@ Colb-Seton : Pourquoi +1 ?

if (((a[i+1] -'0') + (b[i+1] - '0')) > 9) // si l'addition est plus grande que 9

Tu vérifies que 0+0 < 9 -> faux donc tu entres dans le else et tu additionnes 5+5 ce qui te donne ... > 9 (donc le caractère juste après '9').

17 février 2010 à 20:23:14

J'avais oublié de changer la condition après avoir fait des modifs, maintenant ça marche !

Merci à vous.

meteor2

17 février 2010 à 20:35:17

Oulala, j'ai essayé de faire le tout premier exercice, et il est bien plus dur qu'il n'y parait...
J'ai réussis à faire un truc un peu à l'arrache, c'est un peu moche mais bon.

void addition(char *a, char *b, char *c)
{
    if(strlen(a) < strlen(b))  // on inverse les deux chaines si a est plus petit que b
    {
        char *temp=a;
        a=b;
        b=temp;
    }
    int i, j;
    int tailleA = strlen(a);
    int tailleB = strlen(b);

    c[0] = '0';
    strcpy(c+1, a);           
    for(i=tailleB-1,j=tailleA;  i>=0;   i--,j--) 
    {
        c[j-1] += (c[j] + b[i] -'0'-'0') / 10;       
        c[j] = ((c[j] + b[i] - '0' - '0') % 10)+'0';
    }
}

Il gère les retenues et les chaines de différentes longueurs.

Remarque : il se peut qu'il y ai un 0 en tout début de chaine, on peut facile l'enlever avec un if...

18 février 2010 à 4:44:53

Citation : Pouet_forever

Je pense que le plus simple est de parcourir les 2 chaînes en partant de la fin, d'additionner les nombres et mettre les retenues, s'il y en a, et ensuite de retourner la chaîne. Après ce n'est que mon avis

Je suis du même avis.

@meteor2: Effectivement, tu à un zéro qui traîne à gauche, et par exemple avec 1 + 99, on obtient 0:0.

@Lithrein, tu avais juste un problème avec 0 + 0 et lorsque qu'on faisait plusieurs additions à la suite.

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

#define MAX(a, b)((a) >= (b) ? (a) : (b))
#define MIN(a, b)((a) < (b) ? (a) : (b))

#define A_SIZE  100
#define B_SIZE  100

void
remove_zero (char * num, size_t len) {
    while ('0' == num[0] && len > 1) /* GurneyH -> 1 modif ici */
    {
        size_t i;
        for (i = 0 ; i < len ; ++i)
            num[i] = num[i+1];
        len--;
    }
}

void
addition (char * dest, char * a, char * b) {
    size_t len_a, len_b;
    size_t len_dest;
    size_t i;
    int res, ret;
    char * cpa = NULL, * cpb = NULL;

    len_a = strlen(a), len_b = strlen(b);
    len_dest = (len_a > len_b) ? len_a+1 : len_b+1;

    memset(dest, 0,  (1 + len_dest) * sizeof * dest); /* GurneyH -> ajout du memset */
    res = ret = 0;

    if ((cpa = calloc(len_dest, sizeof *cpa)) == NULL){
        perror("Error : Memory Allocation");
        return;
    }
    if ((cpb = calloc(len_dest, sizeof *cpb)) == NULL){
        perror("Error : Memory Allocation");
        free(cpa);
        return;
    }

    /* On remplit de 0 les chaines pour qu'elles aient la même longueur */
    for (i = 0 ; i < len_dest-(len_a+1) ; ++i)
        strcat(cpa, "0");
    strcat(cpa, a);
    for (i = 0 ; i < len_dest-(len_b+1) ; ++i)
        strcat(cpb, "0");
    strcat(cpb, b);

    for (i = len_dest-1 ; i > 0 ; --i) {
        res = cpa[i-1]+cpb[i-1]-2*'0'+ret, ret = 0;
        if (res > 9) {
            ret = res/10;
            res = res%10;
        }
            dest[i] = res+'0';
        if (1 == i) {
                dest[i-1] = ret+'0';
        }
    }

    free(cpa), cpa = NULL;
    free(cpb), cpb = NULL;
    remove_zero(dest, len_dest);

}

void testAdd(void)
{
    int i, j;
    char s_A[A_SIZE] = "";
    char s_B[A_SIZE] = "";
    char s_C[MAX(A_SIZE, B_SIZE) + 1] = "";

    char s_res[MAX(A_SIZE, B_SIZE) + 1] = "";

    for(i = 0; i <= 1000; i++)
    {
        for(j = 0; j <= 1000; j++)
        {
            sprintf(s_A, "%d", i);
            sprintf(s_B, "%d", j);
            sprintf(s_res, "%d", i + j);

            addition(s_C, s_B, s_A);
            if(strcmp(s_res, s_C))
            {
                printf("%d %d %d %s\n", i, j, i + j, s_C);
                exit(EXIT_FAILURE);
            }
        }
    }
     puts("OK!");

}



int main(void)
{
    testAdd();

    return 0;
}

Mais les callocs, sont loins d'être obligatoire.

Edit:
Après réflexion, les 2 premiers exercices sont peut-être déjà bien assez compliqués.
J'édite l'énoncé et je supprime la partie pour avancés.
Dorénavant, j'essaierai de me limiter à des exercices plus simples, avec ponctuellement un point plus ardu...

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

meteor2

18 février 2010 à 12:34:53

Citation : GurneyH

Effectivement, tu à un zéro qui traîne à gauche, et par exemple avec 1 + 99, on obtient 0:0.

Ah oui tiens, j'avais pas pensé à faire ce test...
J'ai corrigé le 0 à gauche et le problème des retenues...

void addition(char *a, char *b, char *c)
{

    if(strlen(a) < strlen(b))  // on inverse les deux chaines si a est plus petit que b
    {
        char *temp=a;
        a=b;
        b=temp;
    }
    int i, j, tailleA = strlen(a), tailleB = strlen(b);
    
    c[0] = '0';
    strcpy(c+1, a);
    for(i=tailleB-1,j=tailleA;  i>=0;   i--,j--) //on additione sans se préocuper des retenues
        c[j] += b[i]-'0';
    for(i=tailleA;i>=1;i--)  //on s'occupe des retenues
    {
        c[i-1] += (c[i] -'0')/10;
        c[i] = ((c[i]-'0')%10)+'0';
    }
    if(c[0] == '0')    //on décale la chaine vers la gauche si ya un 0 superflu
        strcpy(c,c+1);
}

18 février 2010 à 16:52:03

Citation : GurneyH

Mais les callocs, sont loins d'être obligatoire.

Je sais mais plutôt que de faire `malloc + memset` autant faire directement calloc, non ?

18 février 2010 à 17:00:15

Tu peux largement t'en passer

Regarde ce que j'ai proposé et tu verras que c'est totalement inutile

18 février 2010 à 17:14:51

Citation : Pouet_forever

Tu peux largement t'en passer
Regarde ce que j'ai proposé et tu verras que c'est totalement inutile

, je ne vois pas trop comment m'en passer, ils me servent pour que mes nombres est le même nombres de chiffres.

18 février 2010 à 17:29:45

Je met en secret

Au départ tu commences comme ça (nombres au pif) :

<math>\(a = 123 \\b = 9 \\c = 0\)</math>
Donc là tu additionnes tes nombres en partant de la fin. C'est-à-dire que pour le nombre a tu commenceras à 3 puis 2 puis 1 et pour b ce sera 9 puis rien.
A partir de là c'est simple, tu additionnes 3 et 9 > 9 donc tu poses 2 et tu ajoutes 1 à i+1. Ensuite tu fais rien + 2 + retenue ce qui donne 3. Et 1+rien = 1.
Mon équation c de fin sera égale à <math>\(231\)</math>. Mon résultat est là ! Il suffit tout simplement de retourner la chaîne <math>\(231 \rightarrow {123}\)</math>.

Et même sans faire ça tu peux simplement le faire sans retourner ta chaîne