Partage

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

<< 1 ... 51 52 53 ... 55 >>

14 février 2010 à 15:09:41

Citation : schadocalex

Intéréssant, je le ferais surement. Mais comment savoir à l'avance le nombre de dizaine de c ? On peut, ou on ne peut pas et c'est au fur et à mesure de l'addition ?

J'ai modifié l'exemple, qui était, très très mal choisi.

Sinon, pour ta question schadocalex, oui, tu peux connaître la taille maix de c par rapport à la taille de a et b.

Tu connais la taille maxi de c, AVANT de faire l'addition.

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

colbseton

14 février 2010 à 15:32:40

Je me suis 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

Arthurus

14 février 2010 à 15:33:59

Un topic a été créé pour les codes

Reposte le sur ce topic, et on en discutera

nepser

14 février 2010 à 16:15:59

Mince, j'ai l'impression d'être retombé en plein Epitech

J'ai une question subsidiaire pour les matheux codeurs, est-ce que vous avez un algo pour passer un nombre en base 256 à la volée:
=> 21648744541845219 , je n'évalue pas tout, parceque ça rentre pas dans un int, donc je regarde le bout et je fais des opérations petit à petit jusqu'à le transformer en base 256.

Note, c'est aussi une question importante, j'aimerai bien savoir faire ça, mais je ne vois pas comment m'y prendre pour le coup sans devoir utiliser un nombre à taille infinie.

GurneyH

14 février 2010 à 17:26:00

Citation : nepser

Mince, j'ai l'impression d'être retombé en plein Epitech
J'ai une question subsidiaire pour les matheux codeurs, est-ce que vous avez un algo pour passer un nombre en base 256 à la volée:
=> 21648744541845219 , je n'évalue pas tout, parceque ça rentre pas dans un int, donc je regarde le bout et je fais des opérations petit à petit jusqu'à le transformer en base 256.

Note, c'est aussi une question importante, j'aimerai bien savoir faire ça, mais je ne vois pas comment m'y prendre pour le coup sans devoir utiliser un nombre à taille infinie.

Vous faisiez ce genre de trucs à epitech? Le mince, c'est parce que tu trouves ce genre d'exercice ennuyeux?

Sinon, pour ta colle, j'ai ça

/* On cherche! */

Sauf grosse bourde. :-°

edit: Il y avait bien une grosse bourde :'(

. Je pense que c'est bon maintenant.
Toujours pas bon. :'(

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

Lithrein

14 février 2010 à 18:18:58

Citation : GurneyH

Le prototype des fonctions devient

void addition(char *a, char *b, char *c, int base);
void addition(char *a, char *b, char *c, int base);
void addition(char *a, char *b, char *c, int base);

Trop de copier/coller, tue le copier/coller.
ok, je sors -->[]

GurneyH

14 février 2010 à 18:27:00

Citation : Lithrein

Citation : GurneyH
Le prototype des fonctions devient
void addition(char *a, char *b, char *c, int base);
void addition(char *a, char *b, char *c, int base);
void addition(char *a, char *b, char *c, int base);
Trop de copier/coller, tue le copier/coller.
ok, je sors -->[]

Je corrige.

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

Lithrein

14 février 2010 à 18:49:42

Juste une question comme ça, on a le droit de faire joujou avec stdarg.h et d'avoir ainsi des prototypes du style:

void addition(char* dest, int base, ...)

GurneyH

14 février 2010 à 19:05:29

@lithrein:
Tu veux utiliser, stdarg, pour pouvoir passer plus de 2 valeurs à additionner, c'est ça?

Comme tu le sens.
Seulement, je te conseillerai de ne pas te compliquer la vie avec le premier exercice, et de passer pas mal de temps, sur le second.

Mais, encore, une fois, tu fais comme tu veux.

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

Lithrein

14 février 2010 à 19:07:28

D'accord, donc pour le premier je ferais simple et pour le deuxième je me compliquerais un peu plus la vie.

darkipod

15 février 2010 à 11:48:41

Merci pour la correction de Zarray1, et le temps que tu nous consacre

les exos suivants vont etre coton à faire

Adroneus

15 février 2010 à 18:48:08

Personnellement, j'ai fait en sorte que l'utilisateur n'aie pas a se préoccuper de la taille de c, et j'ai modifié les prototypes en conséquence... Je posterai ma solution plus tard, j'ai pas fait la multiplication et la gestion des nombres signés

GurneyH

16 février 2010 à 4:09:46

J'ai édité l'énoncé de zBigInt.

Pour les exercices 1b et 2 on se limitera aux bases entre 2 et 16...

Avec des bases plus importantes, on se retrouve avec des problèmes de mise en forme, qui n'apportent pas grand chose.

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

pylaterreur

17 février 2010 à 19:42:26

Bonsoir,
voici mon zSommeChiffres

int	zSommeChiffresChar(const char *src)
{
  return (*src == '\0' ? 0 : *src - '0' + zSommeChiffresChar(src + 1));
}

int	zSommeChiffres(const int nb)
{
  return (nb == 0 ? 0 : nb % 10 + zSommeChiffres(nb / 10));
}

noureddine03

18 février 2010 à 10:48:36

merci

beryann

24 février 2010 à 22:43:04

Bsr les exercices sont ils concus en fonction des chapitres du tuto de Mathieu Negra sur le C (et donc du bouquin)? ou sont ils dans le "desordre"? pour ma part ,j aimerais, en tant que débutant ,des exercices qui suivent le tuto sur le C...et a fortiori sur le C++... Beryann!!

Merkil

24 février 2010 à 22:57:01

Citation

Mathieu Negra

Oh mon dieu >_<

Sinon tu peux te lancer dans ces exercices selon ton niveau.
Tu te rends en première page(le sommaire), et les connaissances requises sont indiquées

GurneyH

25 février 2010 à 3:55:43

Citation : beryann

Bsr les exercices sont ils concus en fonction des chapitres du tuto de Mathieu Negra sur le C (et donc du bouquin)? ou sont ils dans le "desordre"? pour ma part ,j aimerais, en tant que débutant ,des exercices qui suivent le tuto sur le C...et a fortiori sur le C++... Beryann!!

Les exercices, que ce soient proposés par shareman, Eusebus, Arthurus ou moi-même, ne sont pas classés pas ordre de difficulté.(Dans tous les cas, si tu as terminé les 2 premiers chapitres du tuto C, tous sont accessibles, moyennant un effort plus ou moins important.)

Pour ma part, j'essaye d'alterner exercices simples et plus complexes.(Par exemple, le prochain devrait être très simple.

)

Le tuto C du site propose des TP...

Si tu cherches des exercices progressif(mais orienté algorithme), tu peux regarder du coté de France IOI.

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

Merkil

25 février 2010 à 9:29:55

Ou de Prologin

Anonyme

25 février 2010 à 10:01:49

Ou encore de Project Euler

EDIT : Regarde les liens dans la signature de GurneyH aussi.

GurneyH

27 février 2010 à 11:25:25

zBigInt : Correction

Exercice 1:

Opérations sur les entiers naturels en base 10.

On commence par l'addition
C'est cette méthode. qu'on va appliquer.
Seule différence, on va remplir notre nombre C par la gauche. Pourquoi ?
Au départ de l'addition, on ne connait pas la taille finale exacte de C. Aussi comme il est plus facile d'étendre un tableau vers la droite que vers la gauche(indice -1...), on débute par la gauche.
Du coup notre chaîne c, se retrouve à l'envers, et on peut trouver des zéros inutiles à droite du nombre.

Exemple

a = 1234, b = 9512, c = ?
a = 1234, b = 9512, c[0] = 6, retenue = 0
a = 1234, b = 9512, c[1] = 4, retenue = 0
a = 1234, b = 9512, c[2] = 7, retenue = 0
a = 1234, b = 9512, c[3] = 0, retenue = 1
a = 1234, b = 9512, c[4] = 1
on place le caractère final c[5] = '\0'
c = "64701"
on retourne la chaîne c
c = 10746

On écrit donc 3 petites fonctions

/* Supprime les zéros inutiles(pas vous !... :D)
 * 0001234 devient 1234
 * 00000   devient 0
 */
void suprZeros(char *s)
{
    int n = (int)strlen(s);
    int i;

    /* On supprime les zéros inutiles */
    for (i = n - 1; i > 0 && s[i] == '0'; i--)
        s[i] = '\0';
}


/* Retourne le chaîne s
 * 1234 -> 4321
 * abcde -> edcba
 */
void reverse(char *s)
{
    int n = (int)strlen(s);
    int i;

    for (i = 0; i < n / 2; ++i)
    {
        int tmp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = tmp;
    }
}

/* Supprime les zéros inutiles et retourne la chaîne s */
void transforme(char *s)
{
    suprZeros(s);
    reverse(s);
}

Notre fonction d'addtion:

void addition(char *a, char *b, char *c)
{
    /* Nombre de chiffres de a */
    int szA = strlen ( a );
    /* Nombre de chiffres de b */
    int szB = strlen ( b );
    /* Nombre de chiffres mini de c */
    int szC =  MAX ( szA, szB );
    /* Retenue */
    int cr = 0;

    int i;
    for ( i = 0; i <= szC || cr; i++ )
    {
        int tmp = cr;

        /* On effectue la somme de la colonne actuelle */
        if ( i < szA )
            tmp += a[szA - i - 1] - '0';
        if ( i < szB )
            tmp += b[szB - i - 1] - '0';

        /* Si la somme dépasse 10, on pose une retenue */
        cr = tmp / 10;

        if ( cr )
        {
            /* Il y a une retenue, on ne conserve que l'unité de tmp */
            tmp %=  10;
        }
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] = tmp + '0';
    }

    /* On place le caractère de fin de chaîne */
    c[i] = '\0';

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );
}

La soustraction

Avec cette méthode, il nous faut ici une fonction de comparaison, puisque dans le cas ou a < b, on doit intervertir a et b.

/* Compare les valeurs de a et b
 * Retour :
 *  1 si a > b
 * -1 si a < b
 *  0 si a = b
 */
int cmp(char *a, char *b)
{
    int sz1 = strlen(a);
    int sz2 = strlen(b);

    if (sz1 > sz2)
        return 1;
    else if (sz1 < sz2)
        return -1;
    else
        return strcmp(a, b);
}

Si a < b, on effectue -(b - a).
Le résultat sera négatif comment faire?
Simplement, on place le caractère '-' au début de notre chaîne c, et on travaille ensuite sur la chaîne à l'adresse c + 1.

Sinon, le principe reste le même : on remplit c par la gauche, on doit donc le retourner et supprimer les zéros inutiles à la fin de notre soustraction.

Exemple:

a = 1234, b = 9512

a < b -> c[0] = '-' soustraction(b, a, c + 1)

a = 9512, b = 1234, c[0] = (1)2 - 8, retenue = 1
a = 9512, b = 1234, c[1] = (1)1 - (3 + 1) = 7, retenue = 1
a = 9512, b = 1234, c[2] = 5 - (2 + 1) = 2, retenue = 0
a = 9512, b = 1234, c[3] = 8
On place le caractère final -> c[4] = '0'
c = "8728"
On retourne c
c = 8278
Puis
c = -8278

void soustraction(char *a, char *b, char *c)
{
    if (cmp(a, b) < 0)
    {
        /* |a| < |b| -> -(b - a) */
        c[0] = '-';
        soustraction(b, a, c + 1);
    }
    else
    {
        /* Nombre de chiffres de a */
        int szA = strlen ( a );
        /* Nombre de chiffres de b */
        int szB = strlen ( b );
        /* Retenue */
        int cr = 0;

        int i;
        for ( i = 0; i < szA; i++ )
        {
            /* On effecute la soustraction de la colonne actuelle */
            int tmp = a[szA - i - 1] - '0' - cr;

            if ( i < szB )
                tmp -= b[szB - i - 1] - '0';

            /* si tmp est négatif on pose la retenue */
            cr = tmp < 0;
            if ( cr )
            {
                /* Il y a une retenue on rajoute base à la valeur de tmp*/
                tmp += 10;
            }
            /* On récupère le caractère correspondant à la valeur de tmp */
            c[i] = tmp + '0';
        }

        /* On place le caractère de fin de chaîne */
        c[i] = '\0';

        /* On a rempli c par la gauche, on doit la retourner,et supprimer les
         * zéros inutiles.
         */
        transforme ( c );
    }
}

Multiplication
On utilise la méthode apprise en primaire

Seule différence notable, avec l'addition et la soustraction, on effectue plusieurs passage sur un même chiffre de c. on ne peut donc pas initialiser le chiffre courant de c à la volée.
Pour remédier à ce problème, on initialise c à zéro(en comptant le '\0' final , avant le début de l'opération à l'aide de la fonction memset

void multiplication(char *a, char *b, char *c)
{
    /* taille de a */
    int szA = strlen( a );
    /* taille de b */
    int szB = strlen ( b );
    /* taille de c */
    int szC = szA + szB;

    int i, j;

    /* On rempli z de zéro, jusqu'au caractère de fin de chaîne */
    memset ( c, 0, ( 1 + szC ) * sizeof *c );

    for ( i = 0; i < szA; i++ )
    {
        /* Retenue */
        int cr = 0;

        for ( j = 0; j < szB || cr; j++ )
        {
            /* On effecue la multiplication de b par le chiffre courant de a */
            int tmp = c[i + j] + cr;

            if ( j < szB )
            {
                tmp += ( a[ szA - i - 1] - '0') *
                       ( b[ szB - j - 1] - '0');
            }

            /* Si le produit est supérieur à 10, on pose la retenue */
            cr = tmp / 10;

            if ( cr )
            {
                /* si il y a retenue on ne conserve que l'unité du produit */
                tmp %= 10;
            }

            c[i + j] = tmp;
        }
    }

    for ( i = 0; i < szC; i++ )
    {
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] += '0';
    }

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );

}

Bonus!

La division

Encore une fois, c'est la méthode de l'école primaire qui est utilisée, je me contente donc de vous donner le code commenté.

void division(char *a, char *b, char *c)
{
    /* Reste précédent */
    char tmp[SZ_MAX];
    /* Reste courant */
    char reste[SZ_MAX] = "";

    int szA = strlen ( a );
    int i, j;

    for ( i = 0; i < szA; i++ )
    {
        for ( j = 0; reste[j] != '\0'; j++ )
            ;
        /* On abaisse le chiffre courant de a */
        reste[j] =  a[i];

        /* On place le caractère '\0' pour former une chaîne valide */
        reste[j + 1] = '\0';

        /* On initialise le chiffre courant du quotient à 0 */
        c[szA - i - 1] = 0;

        /* Dans reste contient de fois b ?
         * Le résultat va dans le chiffre courant du quotient
         */
        while ( cmp ( reste, b ) >= 0 )
        {
            c[szA - i - 1]++;
            soustraction ( reste, b, tmp);
            strcpy ( reste, tmp );
        }
        /* Si le reste est nul */
        if ( reste[0] == '0' )
        {
            /* On se replace au début de la chaîne */
            reste[0] = '\0';
        }

        /* On récupère le caractère correspondant à la valeur */
        c[szA - i - 1] +=  '0';
    }

    /* On place le caractère de fin de chaîne */
    c[i] = '\0';

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );
}

Un programme d'exemple.

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

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

#define SZ_MAX  100

/* -------------------------------------------------------------------------- */
int cmp(char const *a, char const *b)
{
    int sz1 = (int)strlen(a);
    int sz2 = (int)strlen(b);

    if (sz1 > sz2)
        return 1;
    else if (sz1 < sz2)
        return -1;
    else
        return strcmp(a, b);
}

/* Supprime les zéros inutiles(pas vous !... :D)
 * 0001234 devient 1234
 * 00000   devient 0
 */
void suprZeros(char *s)
{
    int n = (int)strlen(s);
    int i;

    /* On supprime les zéros inutiles */
    for (i = n - 1; i > 0 && s[i] == '0'; i--)
        s[i] = '\0';
}


/* Retourne le chaîne s
 * 1234 -> 4321
 * abcde -> edcba
 */
void reverse(char *s)
{
    int n = (int)strlen(s);
    int i;

    for (i = 0; i < n / 2; ++i)
    {
        int tmp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = tmp;
    }
}

/* Supprime les zéros inutiles et retourne les nombre n */
void transforme(char *s)
{
    suprZeros(s);
    reverse(s);
}



/* -------------------------------------------------------------------------- */

void addition(char const *a, char const *b, char *c)
{
    /* Nombre de chiffres de a */
    int szA = strlen ( a );
    /* Nombre de chiffres de b */
    int szB = strlen ( b );
    /* Nombre de chiffres mini de c */
    int szC =  MAX ( szA, szB );
    /* Retenue */
    int cr = 0;

    int i;
    for ( i = 0; i <= szC || cr; i++ )
    {
        int tmp = cr;

        /* On effectue la somme de la colonne actuelle */
        if ( i < szA )
            tmp += a[szA - i - 1] - '0';
        if ( i < szB )
            tmp += b[szB - i - 1] - '0';

        /* Si la somme dépasse 10, on pose une retenue */
        cr = tmp / 10;

        if ( cr )
        {
            /* Il y a une retenue, on ne conserve que l'unité de tmp */
            tmp %=  10;
        }
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] = tmp + '0';
    }

    /* On place le caractère de fin de chaîne */
    c[i] = '\0';

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );
}



void multiplication(char const *a, char const *b, char *c)
{
    /* taille de a */
    int szA = strlen( a );
    /* taille de b */
    int szB = strlen ( b );
    /* taille de c */
    int szC = szA + szB;

    int i, j;

    /* On rempli z de zéro, jusqu'au caractère de fin de chaîne */
    memset ( c, 0, ( 1 + szC ) * sizeof *c );

    for ( i = 0; i < szA; i++ )
    {
        /* Retenue */
        int cr = 0;

        for ( j = 0; j < szB || cr; j++ )
        {
            /* On effecue la multiplication de b par le chiffre courant de a */
            int tmp = c[i + j] + cr;

            if ( j < szB )
            {
                tmp += ( a[ szA - i - 1] - '0') *
                       ( b[ szB - j - 1] - '0');
            }

            /* Si le produit est supérieur à 10, on pose la retenue */
            cr = tmp / 10;

            if ( cr )
            {
                /* si il y a retenue on ne conserve que l'unité du produit */
                tmp %= 10;
            }

            c[i + j] = tmp;
        }
    }

    for ( i = 0; i < szC; i++ )
    {
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] += '0';
    }

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );

}



void soustraction(char const *a, char const *b, char *c)
{
    if (cmp(a, b) < 0)
    {
        /* |a| < |b| -> -(b - a) */
        c[0] = '-';
        soustraction(b, a, c + 1);
    }
    else
    {
        /* Nombre de chiffres de a */
        int szA = strlen ( a );
        /* Nombre de chiffres de b */
        int szB = strlen ( b );
        /* Retenue */
        int cr = 0;

        int i;
        for ( i = 0; i < szA; i++ )
        {
            /* On effecute la soustraction de la colonne actuelle */
            int tmp = a[szA - i - 1] - '0' - cr;

            if ( i < szB )
                tmp -= b[szB - i - 1] - '0';

            /* si tmp est négatif on pose la retenue */
            cr = tmp < 0;
            if ( cr )
            {
                /* Il y a une retenue on rajoute base à la valeur de tmp*/
                tmp += 10;
            }
            /* On récupère le caractère correspondant à la valeur de tmp */
            c[i] = tmp + '0';
        }

        /* On place le caractère de fin de chaîne */
        c[i] = '\0';

        /* On a rempli c par la gauche, on doit la retourner,et supprimer les
         * zéros inutiles.
         */
        transforme ( c );
    }
}



void division(char const *a, char const *b, char *c)
{
    /* Reste précédent */
    char tmp[SZ_MAX];
    /* Reste courant */
    char reste[SZ_MAX] = "";

    int szA = strlen ( a );
    int i, j;

    for ( i = 0; i < szA; i++ )
    {
        for ( j = 0; reste[j] != '\0'; j++ )
            ;
        /* On abaisse le chiffre courant de a */
        reste[j] =  a[i];

        /* On place le caractère '\0' pour former une chaîne valide */
        reste[j + 1] = '\0';

        /* On initialise le chiffre courant du quotient à 0 */
        c[szA - i - 1] = 0;

        /* Dans reste contient de fois b ?
         * Le résultat va dans le chiffre courant du quotient
         */
        while ( cmp ( reste, b ) >= 0 )
        {
            c[szA - i - 1]++;
            soustraction ( reste, b, tmp);
            strcpy ( reste, tmp );
        }
        /* Si le reste est nul */
        if ( reste[0] == '0' )
        {
            /* On se replace au début de la chaîne */
            reste[0] = '\0';
        }

        /* On récupère le caractère correspondant à la valeur */
        c[szA - i - 1] +=  '0';
    }

    /* On place le caractère de fin de chaîne */
    c[i] = '\0';

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );
}

int main ( void )
{
    char const *a = "123456012457984546412354565787987846100123456789629";
    char const *b = "9517534286421972213546";
    char c[SZ_MAX];

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

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

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

    multiplication(a, b, c);
    printf("%s * %s = %s\n\n", a, b, c);

    division(a, b, c);
    printf("%s / %s = %s\n\n", a, b, c);

    return 0;
}

Exercice 2

Opérations sur les entiers naturels dans une base b, avec 2 >= b <= 16.

On commence par traiter le changement de base.
Le seul changement par rapport au travail en base 10, sont l'apparition de ces 2 fonctions

char const *s_num = "0123456789abcdef";

/* Retourne le caractère correspondant à un nombre entre 0 et 15
 * n = 15 -> f
 * n = 9  -> 9
 */
int getCharNum ( int n )
{
    return s_num[n];
}

/* Retourne le nombre correspondant à un caractère
 * c = f -> 15
 * c = 9 ->  9
 */
int getNumChar ( int c )
{
    return strchr ( s_num, c ) - s_num;
}

A noter l'utilisation de la fonction strchr.

La fonction addtition devient

void addition ( char *a, char *b, char *c, int base )
{
    /* Nombre de chiffres de a */
    int szA = strlen ( a );
    /* Nombre de chiffres de b */
    int szB = strlen ( b );
    /* Nombre de chiffres mini de c */
    int szC =  MAX ( szA, szB );
    /* Retenue */
    int cr = 0;

    int i;
    for ( i = 0; i <= szC || cr; i++ )
    {
        int tmp = cr;

        /* On effectue la somme de la colonne actuelle */
        if ( i < szA )
            tmp += getNumChar ( a[szA - i - 1] );
        if ( i < szB )
            tmp += getNumChar ( b[szB - i - 1] );

        /* Si la somme dépasse la base, on pose une retenue */
        cr = tmp / base;

        if ( cr )
        {
            /* Il y a une retenue, on ne conserve que l'unité de tmp */
            tmp %=  base;
        }
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] = getCharNum ( tmp );
    }

    /* On place le caractère de fin de chaîne */
    c[i] = '\0';

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );
}

A vous de comparer avec la version précédente.

Les nombre relatifs
Avant d'effectuer une opération, on va définir le signe du résultat. Ensuite, il est toujours possible de se ramener à une opération sur les entiers naturels.

Par exemple, pour une soustraction
-a - (-b) = b - a
a - (-b) = a + b
- a - b = -(a + b)

Il nout faut également une fonction de comparaison entre nombres relatifs

/* Compare les valeurs absolues de a et b
 *  1 si |a| > |b|
 * -1 si |a| < |b|
 *  0 si |a| = |b|
 */
int cmpValeurAbs ( char *a, char *b )
{
    /* Nombre de chiffres de a */
    int szA = strlen ( a );

    /* Nombre de chiffres de b */
    int szB = strlen ( b );

    if ( a[0] == '-' )
        a++;
    if ( b[0] == '-' )
        b++;

    if ( szA > szB )
        return 1;
    else if ( szA < szB )
        return -1;
    else
        return strcmp ( a, b );
}


/* Compare les valeurs de a et b
 *  1 si a > b
 * -1 si a < b
 *  0 si a = b
 */
int cmp ( char const *a, char const *b )
{
    /* sgn. 1 positif, -1 négatif */
    int sgn;

    /* Si a < 0 et b > 0 alors a > b */
    if ( a[0] == '-' && b[0] != '-' )
        return -1;

    /* Si a > 0 et b < 0 alors a > b */
    if ( a[0] != '-' && b[0] == '-' )
        return 1;

    if(a[0] == '-')
        sgn = -1;
    else
        sgn = 1;
  

    return cmpValeurAbs ( a, b ) * sgn;
}

Au final, on obtient:

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

#define SZ_MAX  100

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

/* -------------------------------------------------------------------------- */
char const *s_num = "0123456789abcdef";

/* Retourne le caractère correspondant à un nombre entre 0 et 15
 * n = 15 -> f
 * n = 9  -> 9
 */
int getCharNum ( int n )
{
    return s_num[n];
}

/* Retourne le nombre correspondant à un caractère
 * c = f -> 15
 * c = 9 ->  9
 */
int getNumChar ( int c )
{
    return strchr ( s_num, c ) - s_num;
}


/* Compare les valeurs absolues de a et b
 *  1 si |a| > |b|
 * -1 si |a| < |b|
 *  0 si |a| = |b|
 */
int cmpValeurAbs ( char const *a, char const *b )
{
    /* Nombre de chiffres de a */
    int szA = strlen ( a );

    /* Nombre de chiffres de b */
    int szB = strlen ( b );

    if ( a[0] == '-' )
        a++;
    if ( b[0] == '-' )
        b++;

    if ( szA > szB )
        return 1;
    else if ( szA < szB )
        return -1;
    else
        return strcmp ( a, b );
}


/* Compare les valeurs de a et b
 *  1 si a > b
 * -1 si a < b
 *  0 si a = b
 */
int cmp ( char const *a, char const *b )
{
    /* sgn. 1 positif, -1 négatif */
    int sgn;

    /* Si a < 0 et b > 0 alors a > b */
    if ( a[0] == '-' && b[0] != '-' )
        return -1;

    /* Si a > 0 et b < 0 alors a > b */
    if ( a[0] != '-' && b[0] == '-' )
        return 1;

    sgn = a[0] == '-' ? -1 : 1;

    return cmpValeurAbs ( a, b ) * sgn;
}




/* Supprime les zéros inutiles(pas vous !... :D)
 * 0001234 devient 1234
 * 00000   devient 0
 */
void suprZeros ( char *s )
{
    int n = strlen ( s );
    int i;

    for ( i = n - 1; i > 0 && s[i] == '0'; i-- )
        s[i] = '\0';
}


/* Retourne le chaîne s
 * 1234 -> 4321
 * abcde -> edcba
 */
void reverse ( char *s )
{
    int n = strlen ( s );
    int i;

    /* On parcourt la première moitié de s */
    for ( i = 0; i < n / 2; ++i )
    {
        /* On échange le contenu de s[i] et s[s - i - 1] */
        int tmp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = tmp;
    }
}

/* Supprime les zéros inutiles et retourne les nombre n */
void transforme ( char *s )
{
    suprZeros ( s );
    reverse ( s );
}



/* -------------------------------------------------------------------------- */
#define MAX(a, b)((a) >= (b) ? a : b)

void multiplication ( char const *a, char const *b, char *c, int base )
{
    /* Signe de a */
    int sgnA = a[0] == '-' ? -1 : 1;
    /* Signe de b */
    int sgnB = b[0] == '-' ? -1 : 1;
    /* Signe de c */
    int sgnC = sgnA * sgnB;
    /* taille de a */
    int szA;
    /* taille de b */
    int szB;
    /* taille de c */
    int szC;

    int i, j;

    /* A est négatif ? */
    if ( sgnA < 0 )
        a++;
    /* B est négatif ? */
    if ( sgnB < 0 )
        b++;
    /* C est négatif ? */
    if ( sgnC < 0 && a[0] != '0' && b[0] != '0' )
    {
        /* C est négatif !*/
        c[0] = '-';
        c++;
    }

    szA = strlen ( a );
    szB = strlen ( b );
    szC = szA + szB;

    /* On rempli z de zéro, jusqu'au caractère de fin de chaîne */
    memset ( c, 0, ( 1 + szC ) * sizeof *c );

    for ( i = 0; i < szA; i++ )
    {
        /* Retenue */
        int cr = 0;

        for ( j = 0; j < szB || cr; j++ )
        {
            /* On effecue la multiplication de b par le chiffre courant de a */
            int tmp = c[i + j] + cr;

            if ( j < szB )
            {
                tmp += getNumChar ( a[ szA - i - 1] ) *
                       getNumChar ( b[ szB - j - 1] );
            }

            /* Si le produit est supérieur à la base, on pose la retenue */
            cr = tmp / base;

            if ( cr )
            {
                /* si il y a retenue on ne conserve que l'unité du produit */
                tmp %= base;
            }

            c[i + j] = tmp;
        }
    }

    for ( i = 0; i < szC; i++ )
    {
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] = getCharNum ( c[i] );
    }

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );

}
void doSub ( char const *a, char const *b, char *c, int base )
{
    /* Nombre de chiffres de a */
    int szA = strlen ( a );
    /* Nombre de chiffres de b */
    int szB = strlen ( b );
    /* Retenue */
    int cr = 0;

    int i;
    for ( i = 0; i < szA; i++ )
    {
        /* On effecute la soustraction de la colonne actuelle */
        int tmp = getNumChar ( a[szA - i - 1] ) - cr;

        if ( i < szB )
            tmp -= getNumChar ( b[szB - i - 1] );

        /* si tmp est négatif on pose la retenue */
        cr = tmp < 0;
        if ( cr )
        {
            /* Il y a une retenue on rajoute base à la valeur de tmp*/
            tmp += base;
        }
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] = getCharNum ( tmp );
    }

    /* On place le caractère de fin de chaîne */
    c[i] = '\0';

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );

}


void soustraction ( char const *a, char const *b, char *c, int base )
{
    if ( a[0] == '-' && b[0] == '-' )
    {
        /* -a - (-b) = b - a */
        soustraction ( b + 1 , a + 1 , c, base );
    }
    else  if ( a[0] != '-' && b[0] == '-' )
    {
        /* a - (-b) = a + b */
        addition ( a, b + 1, c, base );
    }
    else if ( a[0] == '-' && b[0] != '-' )
    {
        /* - a - b = -(a + b) */
        c[0] = '-';
        addition ( a + 1, b, c + 1, base );
    }
    else
    {   /* a - b */
        if ( cmpValeurAbs ( a, b ) >= 0 )
            doSub ( a, b, c, base );
        else
        {
            /* a < b on effectue -(b - a) */
            c[0] =  '-';
            doSub ( b, a, c + 1, base );
        }
    }
}

void doAdd ( char const *a, char const *b, char *c, int base )
{
    /* Nombre de chiffres de a */
    int szA = strlen ( a );
    /* Nombre de chiffres de b */
    int szB = strlen ( b );
    /* Nombre de chiffres mini de c */
    int szC =  MAX ( szA, szB );
    /* Retenue */
    int cr = 0;

    int i;
    for ( i = 0; i <= szC || cr; i++ )
    {
        int tmp = cr;

        /* On effectue la somme de la colonne actuelle */
        if ( i < szA )
            tmp += getNumChar ( a[szA - i - 1] );
        if ( i < szB )
            tmp += getNumChar ( b[szB - i - 1] );

        /* Si la somme dépasse la base, on pose une retenue */
        cr = tmp / base;

        if ( cr )
        {
            /* Il y a une retenue, on ne conserve que l'unité de tmp */
            tmp %=  base;
        }
        /* On récupère le caractère correspondant à la valeur de tmp */
        c[i] = getCharNum ( tmp );
    }

    /* On place le caractère de fin de chaîne */
    c[i] = '\0';

    /* On a rempli c par la gauche, on doit la retourner,et supprimer les
     * zéros inutiles.
     */
    transforme ( c );
}

void addition ( char const *a, char const *b, char *c, int base )
{
    if ( a[0] != '-' && b[0] != '-' )
    {
        /* a + b */
        doAdd ( a, b, c, base );
    }
    else if ( a[0] == '-' && b[0] == '-' )
    {
        /* -a + (-b)  = -(a + b) */
        c[0] = '-';
        doAdd ( a + 1, b + 1, c + 1, base );
    }
    else if ( a[0] == '-' && b[0] != '-' )
    {
        /* -a + b = b - a */
        soustraction ( b, a + 1, c, base );
    }
    else
    {
        /* a + (-b) = a - b */
        soustraction ( a, b + 1, c, base );
    }
}


void division ( char const *a, char const *b, char *c, int base )
{
    /* Signe de a */
    int sgnA = a[0] == '-' ? -1 : 1;
    /* Signe de b */
    int sgnB = b[0] == '-' ? -1 : 1;
    /* Signe de c */
    int sgnC = sgnA * sgnB;

    /* A est négatif ? */
    if ( sgnA < 0 )
        a++;
    /* B est négatif ? */
    if ( sgnB < 0 )
        b++;

    if ( cmpValeurAbs ( a, b ) < 0 )
    {
        /* Le quotient de la division est nul. */
        strcpy ( c, "0" );
    }
    else
    {
        /* Reste précédent */
        char tmp[SZ_MAX];
        /* Reste courant */
        char reste[SZ_MAX] = "";

        int szA = strlen ( a );
        int i, j;

        if ( sgnC < 0 )
        {
            /* C est négatif */
            c[0] = '-';
            c++;
        }

        for ( i = 0; i < szA; i++ )
        {
            for ( j = 0; reste[j] != '\0'; j++ )
                ;
            /* On abaisse le chiffre courant de a */
            reste[j] =  a[i];

            /* On place le caractère '\0' pour former une chaîne valide */
            reste[j + 1] = '\0';

            /* On initialise le chiffre courant du quotient à 0 */
            c[szA - i - 1] = 0;

            /* Dans reste contient de fois b ?
             * Le résultat va dans le chiffre courant du quotient
             */
            while ( cmp ( reste, b ) >= 0 )
            {
                c[szA - i - 1]++;
                soustraction ( reste, b, tmp, base );
                strcpy ( reste, tmp );
            }
            /* Si le reste est nul */
            if ( reste[0] == '0' )
            {
                /* On se replace au début de la chaîne */
                reste[0] = '\0';
            }

            /* On récupère le caractère correspondant à la valeur */
            c[szA - i - 1] = getCharNum ( c[szA - i - 1] );
        }

        /* On place le caractère de fin de chaîne */
        c[i] = '\0';

        /* On a rempli c par la gauche, on doit la retourner,et supprimer les
         * zéros inutiles.
         */
        transforme ( c );

    }
}


int main ( void )
{
    char const *a = "ecf6a45353af75bd";
    char const *b = "d354eb363fa6ee5";
    char c[SZ_MAX];
    int base = 16;

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

    soustraction(a, b, c, base);
    printf("%s - %s = %s\n\n", a, b, c);

    soustraction(b, a, c, base);
    printf("%s - %s = %s\n\n", b, a, c);

    multiplication(a, b, c, base);
    printf("%s * %s = %s\n\n", a, b, c);

    division(a, b, c, base);
    printf("%s / %s = %s\n\n", a, b, c);

    return 0;
}

Il ne vous reste plus qu'à coder une petite lib de manipulation de grands nombres. C'est une bonne occasion pour s'attaquer à la gestion d'erreurs, à l'allocation dynamique, etc...
On peut également réfléchir à une manière efficace de stocker nos grands nombres.

Il y a de quoi s'exercer. :lol:

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

Pouet_forever

27 février 2010 à 11:41:17

Sympa, merci.

Je pense que desfois tu fais des calculs que tu pourrais éviter.

(bon c'est un détail on s'en fou :-°

)

C'est dommage, j'ai pas eu le temps de faire la division/multiplication.

GurneyH

27 février 2010 à 11:44:12

Citation : Pouet_forever

Sympa, merci.
Je pense que desfois tu fais des calculs que tu pourrais éviter. (bon c'est un détail on s'en fou )

C'est dommage, j'ai pas eu le temps de faire la division/multiplication.

Rien ne t'empêche de les faire.

L'autre topic est toujours là pour ça.

Il y a surement des calculs qu'on peut éviter, mais ça m'a semblé plus simple de mettre tous les cas. Cependant il y a toujours moyen de corriger la correction :'(

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

Pouet_forever

27 février 2010 à 11:46:22

Citation : GurneyH

Cependant il y a toujours moyen de corriger la correction .

Oui, mais non.

Je veux pas te faire modifier la correction juste parce que moi j'aurais fait différemment. Chacun fait comme il le souhaite.

Lithrein

27 février 2010 à 11:48:56

Toujours, une aussi bonne correction, bien expliqué et très simple à comprendre.

Citation : Pouet_forever

C'est dommage, j'ai pas eu le temps de faire la division/multiplication.

+1, je pense que tu devrais adapter le temps pour faire les exercices en fonction de la difficulté de l'exercice, en l'occurrence peu ont essayé l'addition (la soustraction et la multiplication) avec les différentes bases et peu ont fini le premier exercice (d'ailleurs il ne me semble pas qu'il y en est.)

Autrement, merci pour cette correction.

Lithrein.

GurneyH

27 février 2010 à 11:56:56

Citation : Lithrein

Toujours, une aussi bonne correction, bien expliqué et très simple à comprendre.

Citation : Pouet_forever

C'est dommage, j'ai pas eu le temps de faire la division/multiplication.

+1, je pense que tu devrais adapter le temps pour faire les exercices en fonction de la difficulté de l'exercice, en l'occurrence peu ont essayé l'addition (la soustraction et la multiplication) avec les différentes bases et peu ont fini le premier exercice (d'ailleurs il ne me semble pas qu'il y en est.)

Autrement, merci pour cette correction.
Lithrein.

Je pense rester sur une base de 15 jours.
Ce n'est pas parce que la correction est postée qu'on ne peut plus donner sa solution, c'est l'avantage du topic séparé.
D'ailleurs je serai curieux de voir ta multiplication avec l'algo de karatsuba.

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

candide

27 février 2010 à 16:36:08

Citation : GurneyH

zBigInt : Correction

Je suis pas trop convaincu par ton zExo. Prenons par exemple le cas de la fonction d'addition. Supposons que bous voulions calculer <math>\(2^{2010}\)</math> (ie 2 exposant 2010). Il suffit d'itérer ta fonction d'addition 2010 fois :

1+1=2=<math>\(2^{1}\)</math>
2+2=4=<math>\(2^{2}\)</math>
4+4=8=<math>\(2^{3}\)</math>
etc

Ton code s'adapte-t-il facilement à ce problème corrélatif ?

GurneyH

27 février 2010 à 17:47:51

Citation : candide

Citation : GurneyH

zBigInt : Correction

Je suis pas trop convaincu par ton zExo. Prenons par exemple le cas de la fonction d'addition. Supposons que bous voulions calculer <math>\(2^{2010}\)</math> (ie 2 exposant 2010). Il suffit d'itérer ta fonction d'addition 2010 fois :
1+1=2=<math>\(2^{1}\)</math>
2+2=4=<math>\(2^{2}\)</math>
4+4=8=<math>\(2^{3}\)</math>
etc

Ton code s'adapte-t-il facilement à ce problème corrélatif ?

Non, ce ne sera pas réalisable "facilement" (sans copie, s'entend).
Le but était de présenter une méthode générale, et la plus simple possible.

Enfin

#define SZ_MAX  1000
...
int main ( void )
{
    char a[SZ_MAX] = "1";
    char tmp[SZ_MAX];

    int i;
    for(i = 0; i < 2010; i++)
    {
        addition(a, a, tmp);
        strcpy(a, tmp);
    }

    printf("%s", a);
    return 0;
}

11756858319608366328144211980059463516388533269388238852891061625095846516657872
01389219313988102420396488667790323161880009849815923768659380153708714652861840
69108884799774720705309847797805948343221237825009914656374234773901684682052634
66543754646620671647555829638035930071615827112912503216329762066569642896280008
55097368365924433039963145572111364392987819075848504545363274099520427635383125
16819557371285932162070302575005739171689659649577870780315742126648276770395824
16809992392418982971674150955579773543990102915729349842381712924240269580817964
5981492042590997317596624652477287576606081024
Process returned 0 (0x0)   execution time : 0.062 s
Press any key to continue.

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

candide

27 février 2010 à 22:43:41

Citation : GurneyH

strcpy(a, tmp);

Si vraiment ton code est incapable d'éviter ce genre de copie (totalement inutile), tu devrais le reprendre.

Sinon, je trouve ton code compliqué (imagine le débutant qui va devoir se taper 500 lignes de code avec des fonctions qui partent dans tous les sens, des const, etc, il va vite se retrouver en surcharge cognitive le pôvre).

Voici un code basé sur une addition que j'avais écrite il y a X mois ou années, le code est un peu trop dense pour un débutant mais ça donne l'idée de l'échange de pointeurs pour éviter la recopie.

#include <stdio.h>
#include <string.h>
#define SZ_MAX  1000
void additionner(char *p, char *q, char *s)
{
  size_t np = strlen(p), nq = strlen(q), i;
  int retenue = 0;

  for (i = 0; i < np || i < nq; i++)
    {
      int x =
        retenue + (i < np ? p[i] : '0') - '0' + (i < nq ? q[i] : '0') - '0';
      s[i] = "0123456789"[x - (retenue = (x > 9)) * 10];
    }
  /* Gestion de la retenue finale et fermeture de la chaine */
  s[i] = retenue ? s[i + 1] = 0, '1' : 0;
}

int main(void)
{
  char a[SZ_MAX] = "1";
  char r[SZ_MAX] = "0";
  char *p = a, *q = r;
  int i, n = 2010;

  for (i = 0; i < n; i++)
    {
      additionner(p, p, q);
      p = q;
      q = a;
    }
  n = strlen(p);
  for (i = n - 1; i >= 0; i--)
    printf("%c", p[i]);
  printf("\n");
  return 0;
}

GurneyH

28 février 2010 à 1:12:20

Citation : candide

Si vraiment ton code est incapable d'éviter ce genre de copie (totalement inutile), tu devrais le reprendre.

Probablement...

int main(void)
{
    char a[SZ_MAX] = "1";
    char r[SZ_MAX];
    char *p = a, *q = r;
    int i, n = 2010;

    for (i = 0; i < n; i++)
    {
        char *tmp = p;
        addition(p, p, q);
        p = q;
        q = tmp;
    }

    printf("%s", p);

    return 0;
}

fonctionne également avec mon code.

Figure toi, que je me suis posé la question entre échange de pointeurs et strcpy...
C'est finalement la solution la plus simple qui l'a emporté...

Ensuite sur la longueur du code, dès le départ l'idée était de fournir un code qui pourrait fournir un code sur les entiers naturels facilement transposable au entiers relatifs...

Ainsi, si tu enlèves les commentaires

void addition(char const *a, char const *b, char *c)
{
   
    int szA = strlen ( a );
    int szB = strlen ( b );
    int szC =  MAX ( szA, szB );
    int cr = 0;

    int i;
    for ( i = 0; i <= szC || cr; i++ )
    {
        int tmp = cr;
        if ( i < szA )
            tmp += a[szA - i - 1] - '0';
        if ( i < szB )
            tmp += b[szB - i - 1] - '0';

        cr = tmp / 10;

        if ( cr )
            tmp %=  10;
        c[i] = tmp + '0';
    }
    c[i] = '\0';
    transforme ( c );
}

La fonction n'est à mon sens pas si longue que ça... Et reste beaucoup plus accessible que ta fonction. :-°

Pour les const, si tu regardes bien, ils n'apparaissent que dans le code d'exemple...
Chaque fonction est détaillée sans const.

Je suis d'ailleurs prêt à expliquer à un débutant le pourquoi de l'ajout de const.

De toutes façons, tout ne sera pas parfait(à raison d'un exercice tous les 15 jours!.
Mais si vraiment le besoin se fait sentir, je modifierai les codes de la correction.

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

<< 1 ... 51 52 53 ... 55 >>

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

zBigInt : Correction

Exercice 1:

Un programme d'exemple.

Exercice 2

zBigInt : Correction

zBigInt : Correction

Supprimer

Modérer

Signaler le message aux modérateurs