1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Lycéen
    Inscrit en
    juin 2017
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 27
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Lycéen
    Secteur : Enseignement

    Informations forums :
    Inscription : juin 2017
    Messages : 1
    Points : 0
    Points
    0

    Par défaut Exercice en C de combinaison de chiffres

    Bonjour tout le monde, alors voila, je commence a apprendre le langage C et du coup j'essaie de faire des exercices.
    J'ai recupéré des exercices de l'ecole 42 et tente de les comprendre et aussi de les refaires.
    Actuellement il y en a un qui calcule des chiffres qui me pose probleme.
    Je comprends bien le code, mais comment fonctionne il ?
    Voici l'ennoncé de l'exercice:

    Écrire une fonction qui affiche, dans l’ordre croissant, toutes les différentes combinaisons
    de trois chiffres différents dans l’ordre croissant - oui, la répétition est
    volontaire.
    • Cela donne quelque chose comme ça :
    012, 013, 014, 015, 016, 017, 018, 019, 023, ..., 789
    • 987 n’est pas là car 789 est déjà présent
    • 999 n’est pas là car ce nombre ne comporte pas exclusivement des chiffres différents
    les uns des autres
    Voici le code que j'ai trouvé:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    #include <unistd.h>
     
    void    putchar(char c)
    {
        write(1, &c, 1);
    }
     
    void    count(void)
    {
        int a;
        int b;
        int c;
     
        a = '0';
        b = '1';
        c = '2';
        while (a <= '9')
        {
            while (b <= '9')
            {
                while (c <= '9')
                {
                    putchar(a);
                    putchar(b);
                    putchar(c);
                    putchar(' ');
                    c++;
                }
                b++;
                c = b + 1;
            }
            a++;
            b = a;
        }
    }
     
    int     main(void)
    {
        count();
        return (0);
    }
    Et ce que je comprends:
    Ok on initialise 3 varibles a 0, 1, 2
    Mais ensuite comment on fait pour que quand on execute le code, par exemple 021 il ne l'affiche pas !?
    Je ne comprends pas la logique qui arrive que le code affiche bien les 3 chiffres mais quand une même combinaison des trois chiffres existe deja, qu'elle ne s'affiche pas !
    Par exemple on va avoir 012 mais 021 lui ne va pas s'afficher !!! :O
    Nom : 179418ex04.jpg
Affichages : 239
Taille : 34,7 Ko

  2. #2
    Modérateur

    Homme Profil pro
    Ingénieur électricien
    Inscrit en
    septembre 2008
    Messages
    518
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ingénieur électricien

    Informations forums :
    Inscription : septembre 2008
    Messages : 518
    Points : 1 605
    Points
    1 605

    Par défaut

    Bonsoir et Bienvenu sur developpez!

    Prends les meilleurs amis du développeur, un crayon et du papier, et réalise le programme à la main. Tu fais trois colonnes, une pour chaque variable et tu parcours ton programme, une instruction à la fois, et à chaque modification de variable tu l'écris dans la colonne correspondante. Tu comprendras rapidement comment le comptage fonctionne.

    Delias

  3. #3
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    5 927
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 5 927
    Points : 16 384
    Points
    16 384
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par raiden500 Voir le message
    Par exemple on va avoir 012 mais 021 lui ne va pas s'afficher !!! :O
    Bonjour
    Déjà même si ça a été écrit en C, ça n'a rien à voir avec le C. C'est plus un problème d'algorithmie que de langage.
    Sinon dans 021, "1" étant plus petit que "2" il a forcément été déjà affiché auparavant (via 012). C'est pour ça que quand "b" s'incrémente, "c" prend alors la valeur qui lui est immédiatement supérieure. Si par exemple on est à 149 (fin d'itération de "c") et qu'à l'itération suivante "b" passe à "5" alors "c" passe à 6 parce que les nombres 151, 152, 153, 154 et 155 ont déjà été affichés via leurs homologues 115, 125, 135, 145 et 155.
    Même principe quand "b" a fini d'itérer. "a" s'incrémente donc (pour passer de 199 à 200) et "b" repart alors immédiatement de la position "2" parce que tous les nombres 21X ont déjà été traités.

    Citation Envoyé par raiden500 Voir le message
    Bon puisqu'on est quand-même en C, voici une remarque spécifique à ce langage: Evite les nombres magiques (les nombres qui ont une valeur conventionnelle mais qui pourrait changer un jour). Utilise plutôt les macro associées
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    write(STDOUT_FILENO, &c, 1);
    Ceci dit, c'est quand-même un code un peu "bébé" que tu nous fais là. Surtout avec tes "a", "b" et "c" qui sont 3 variables distinctes alors qu'elles sont sensées représenter une collection d'éléments identiques (les digits d'un nombre). Généralement, dans ce cas là, on commence à penser plus riche et on commence à avoir l'idée d'utiliser des tableaux.
    Ce qui amène alors à la réflexion que si on a des tableaux pour représenter nos digits, non seulement on peut factoriser le traitement qui vérifie le nombre au travers de boucles mais en plus on peut étendre ce traitement à des nombres à 4, 5, 6 chiffres et au delà.

    Et donc assez rapidement on arrive à ce code un petit peu plus professionnel...
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    #include <stdio.h>
    #include <stdlib.h>
     
    unsigned long puis10(unsigned short nb) {
    	unsigned long ret;
    	unsigned short i;
    	for (i=0, ret=1; i < nb; i++)
    		ret*=10;
    	return ret;
    }
     
    short isAcceptable(unsigned long val, unsigned short nb) {
    	unsigned char *zone;
    	unsigned short i;
    	unsigned short ok;
     
    	if ((zone=malloc((nb+1) * sizeof(unsigned char))) == NULL) return -1;
     
    	sprintf(zone, "%0*lu", nb, val);
    	for (i=1, ok=1; i < nb; i++) {
    		if (zone[i] < zone[i-1]) {
    			ok=0;
    			break;
    		}
    	}
    	free(zone);
    	return ok;
    }
     
    void cpt(unsigned short nb) {
    	unsigned long val;
     
    	const unsigned long max=puis10(nb);
     
    	for (val=1; val > 0 && val < max; val++) {
    		switch (isAcceptable(val, nb)) {
    			case -1:
    				printf("Erreur évaluation (%lu)\n", val);
    				break;
    			case 1:
    				printf("%0*lu ", nb, val);
    				break;
    		}
    	}
    	fputc('\n', stdout);
    }
     
    int main(int argc, char *argv[]) {
    	cpt(strtoul(argv[1], NULL, 10));
    }

    On enregistre ce code dans un fichier "toto.c", on le compile en "toto" et on l'appelle en lui passant en paramètre le nombres de chiffres des nombres que l'on veut afficher. Ex toto 5 affichera de "00001" jusqu'à "99999"...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  4. #4
    Invité
    Invité(e)

    Par défaut

    Déjà on ne met pas 0 1 et 2 dans les variables mais '0', '1' et '2' '0' est différent de 0 c'est un caractère '0' = 40 enfin affiche ton int t'auras la valeur int de ton caractère

  5. #5
    Membre chevronné
    Avatar de Pyramidev
    Homme Profil pro
    Développeur
    Inscrit en
    avril 2016
    Messages
    468
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : avril 2016
    Messages : 468
    Points : 2 079
    Points
    2 079

    Par défaut

    Bonjour,

    Citation Envoyé par raiden500 Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
     
        a = '0';
        b = '1';
        c = '2';
        while (a <= '9')
        {
            while (b <= '9')
            {
                while (c <= '9')
                {
                    putchar(a);
                    putchar(b);
                    putchar(c);
                    putchar(' ');
                    c++;
                }
                b++;
                c = b + 1;
            }
            a++;
            b = a;
        }
    Comme l'a dit Delias, il faut que tu t'entraînes à analyser l'algorithme avec un papier et un crayon.
    Mais, à ta décharge, cet algorithme n'est pas intuitif.
    Quand on arrive à l'instruction b = a;, on a c == '9' + 2. Du coup, quand on arrive au test c <= '9', la condition est fausse donc on passe directement à b++; puis à c = b + 1;, ce qui permet de se retrouver dans une situation où b == a + 1 et c == b + 1.

    Voici un autre algorithme plus intuitif :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
        a = '0';
        b = '1';
        c = '2';
        while (a <= '7')
        {
            while (b <= '8')
            {
                while (c <= '9')
                {
                    putchar(a);
                    putchar(b);
                    putchar(c);
                    putchar(' ');
                    c++;
                }
                b++;
                c = b + 1;
            }
            a++;
            b = a + 1;
            c = b + 1;
        }
    Citation Envoyé par Sve@r Voir le message
    Code c : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    	sprintf(zone, "%0*lu", nb, val);
    	for (i=1, ok=1; i < nb; i++) {
    		if (zone[i] < zone[i-1]) {
    			ok=0;
    			break;
    		}
    	}
    Il y a une étourderie. Il faut remplacer zone[i] < zone[i-1] par zone[i] <= zone[i-1].

    A part ça, voici une implémentation optimisée dans laquelle on choisit aussi le nombre de chiffres en ligne de commande :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    #include <assert.h>
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
     
    const int cERREUR_ALLOCATION = 1;
    const int cERREUR_ARGUMENTS  = 2;
     
    void initialiserChaine(char* chaine, int nbChiffres)
    {
    	assert(nbChiffres >= 1 && nbChiffres <= 10);
    	for(int k = 0; k < nbChiffres; ++k)
    		chaine[k] = '0' + k;
    	chaine[nbChiffres] = '\0';
    }
     
    bool remplacerParChaineSuivante(char* chaine, int nbChiffres)
    {
    	assert(nbChiffres >= 1 && nbChiffres <= 10);
    	char* const premier = chaine;
    	char* const dernier = chaine + nbChiffres - 1;
    	// Etape 1 : On cherche le chiffre à incrémenter le plus à droite possible.
    	char* chiffreAIncrementer = dernier;
    	while(true)
    	{
    		const char valeurMaximale = '9' - (dernier - chiffreAIncrementer);
    		const bool incrementationPossible = (*chiffreAIncrementer < valeurMaximale);
    		if(incrementationPossible)
    			break;
    		if(chiffreAIncrementer == premier)
    			return false; // pas de chaîne suivante
    		--chiffreAIncrementer;
    	}
    	// Etape 2 : On incrémente le chiffre trouvé.
    	++(*chiffreAIncrementer);
    	// Etape 3 : On ajuste tous les éventuels chiffres qui sont à droite de celui
    	// qu'on vient d'incrémenter.
    	for(char* ptr = chiffreAIncrementer + 1; ptr <= dernier; ++ptr)
    		*ptr = *(ptr-1) + 1;
    	return true;
    }
     
    int afficherDesCombinaisonsDeChiffres(int nbChiffres) {
    	assert(nbChiffres >= 1 && nbChiffres <= 10);
    	char* chaine = malloc(nbChiffres + 1);
    	if(chaine == NULL)
    		return cERREUR_ALLOCATION;
    	initialiserChaine(chaine, nbChiffres);
    	bool onContinue;
    	do {
    		printf("%s ", chaine);
    		onContinue = remplacerParChaineSuivante(chaine, nbChiffres);
    	} while(onContinue);
    	free(chaine); // Edit 2017-06-10-12h12 : ajout de free suite à la remarque de Sve@r
    	return 0;
    }
     
    int main(int argc, char *argv[])
    {
    	if(argc < 2) {
    		printf("Erreur : pas assez d'arguments.");
    		return cERREUR_ARGUMENTS;
    	}
    	const int nbChiffres = atoi(argv[1]);
    	if(nbChiffres < 1 || nbChiffres > 10) {
    		printf("Erreur : le premier argument doit etre un nombre entre 1 et 10.");
    		return cERREUR_ARGUMENTS;
    	}
    	const int codeErreur = afficherDesCombinaisonsDeChiffres(nbChiffres);
    	if(codeErreur != 0)
    		printf("Une erreur s'est produite. Code de retour : %d.", codeErreur);
    	return codeErreur;
    }

  6. #6
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    5 927
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 5 927
    Points : 16 384
    Points
    16 384
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par Pyramidev Voir le message
    A part ça, voici une implémentation optimisée dans laquelle on choisit aussi le nombre de chiffres en ligne de commande :
    Pas mal. Tu alloues une zone dans laquelle tu remplaces les chiffres les uns par les autres. Optimisée donc parce qu'il n'y a qu'une seule allocation... (je ne compte pas les "assert" plus gadgets qu'autre chose, ni les "bool" que je n'utilise pas parce que ça m'oblige à rajouter "-std=c99" quand je compile)

    Citation Envoyé par Pyramidev Voir le message
    Il y a une étourderie. Il faut remplacer zone[i] < zone[i-1] par zone[i] <= zone[i-1].
    Exact. De ton côté tu rajouteras le free() qui manque
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  7. #7
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2007
    Messages
    5 029
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 5 029
    Points : 16 841
    Points
    16 841

    Par défaut

    Sve@r: ca te dérange tant que ça de demander à ton compilateur de respecter une norme vieille de 18 ans? (surtout que depuis, il y a le C11)
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  8. #8
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    5 927
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 5 927
    Points : 16 384
    Points
    16 384
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par ternel Voir le message
    Sve@r: ca te dérange tant que ça de demander à ton compilateur de respecter une norme vieille de 18 ans?
    Juste la flemme. Après-tout, si c'est vieux de 18 ans ça pourrait être automatiquement implicite. Remarque le compilo m'a dit que je pouvais aussi mettre "-std=c11".
    En fait je ne bosse plus en C depuis 2007 (je suis passé à Python depuis). Ce n'est pas que je n'aime pas le C mais bon, là où je suis il faut quand-même aller assez vite et donc si je peux faire en Python en 3 lignes et en 3mn ce qui me prendrait 25mn et 150 lignes en C, il n'y a pas photo.
    Donc les seuls moments où je fais du C c'est ici pour répondre aux posts. Et là, je lance une machine virtuelle Linux, je vais dans "/tmp" (parce que même en virtuel je reste propre et tout ce qui est temporaire je le fais dans "/tmp"), je tape vite fait mon code puis je lance "make" pour aller plus vite. Ceci explique donc cela
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  9. #9
    Membre chevronné
    Avatar de Pyramidev
    Homme Profil pro
    Développeur
    Inscrit en
    avril 2016
    Messages
    468
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : avril 2016
    Messages : 468
    Points : 2 079
    Points
    2 079

    Par défaut

    Maintenant que j'y pense, pour afficher, dans l’ordre croissant, toutes les différentes combinaisons de trois chiffres différents dans l’ordre croissant, le code le plus simple est :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <stdio.h>
    int main()
    {
    	for(int i = 0; i <= 7; ++i)
    		for(int j = i + 1; j <= 8; ++j)
    			for(int k = j + 1; k <= 9; ++k)
    				printf("%d%d%d ", i, j, k);
    	return 0;
    }
    Citation Envoyé par Sve@r Voir le message
    Optimisée donc parce qu'il n'y a qu'une seule allocation...
    D'ailleurs, comme la taille maximale à allouer est 11, j'aurais dû allouer directement 11 caractères dans la pile.
    Comme ça, aucune allocation dans le tas. En plus, le type de retour de afficherDesCombinaisonsDeChiffres peut devenir void.

    Le code est optimisé aussi parce que je ne parcours pas les 10 puissance nbChiffres combinaisons possibles.
    Pour aller d'une combinaison de chiffres valide à la combinaison valide suivante, j'incrémente le chiffre le plus à droite possible puis j'ajuste les chiffres plus à droite que celui que je viens d'incrémenter. Par exemple, à partir de 13789, j'incrémente le 3 qui devient un 4 puis je remplace les chiffres suivants par 567, ce qui donne 14567.
    Cela dit, je n'ai pas mesuré la vitesse d'exécution avec différents algos.

  10. #10
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2007
    Messages
    5 029
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 5 029
    Points : 16 841
    Points
    16 841

    Par défaut

    J'attire l'attension sur le mot optimiser.
    Il signifie simplement rendre optimal, c'est à dire rendre le meilleur possible.
    En lui-même, il ne signifie pas ce qu'on améliore.

    Pyramidev mentionne plusieurs axes d'optimisations.

    Ainsi, on peut optimiser la surface mémoire utilisée (en limitant la quantité de mémoire prise), la vitesse d'exécution, la durée de compilation, la fragmentation mémoire ou localité (pour améliorer la vitesse d'exécution).

    J'ajouterai que passé un certain niveau d'amélioration, il y a un compromis à faire entre ces différents axes.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  11. #11
    Membre chevronné
    Avatar de Pyramidev
    Homme Profil pro
    Développeur
    Inscrit en
    avril 2016
    Messages
    468
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : avril 2016
    Messages : 468
    Points : 2 079
    Points
    2 079

    Par défaut

    Petit up pour publier une nouvelle version du code.

    Rappel de la consigne :
    Soit nbChiffres un nombre entier entre 1 et 10 passé en argument de la ligne de commande.
    Afficher dans la sortie standard, dans l’ordre croissant, toutes les différentes combinaisons de nbChiffres chiffres différents dans l’ordre croissant.
    Par exemple, si nbChiffres == 3, l'affichage resemblera à :
    012 013 014 015 016 017 018 019 023 024 ... 678 679 689 789

    Voici la nouvelle version du code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    #include <assert.h>
    #include <ctype.h>
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    typedef struct SuiteDeChiffresDistincsCroissants {
    	char m_chaine[10+1];
    	int  m_cacheNbChiffres; //! But : optimisation : éviter d'appeler strlen.
    } SDCDC;
     
    bool SDCDC_Invariant(const SDCDC* pThis) {
    	assert(pThis != NULL);
    	if(pThis->m_cacheNbChiffres < 1 || pThis->m_cacheNbChiffres > 10)
    		return false;
    	for(int k = 0; k < pThis->m_cacheNbChiffres; ++k)
    		if(!isdigit(pThis->m_chaine[k]))
    			return false;
    	for(int k = 0; k+1 < pThis->m_cacheNbChiffres; ++k)
    		if(pThis->m_chaine[k] >= pThis->m_chaine[k+1])
    			return false;
    	return pThis->m_chaine[pThis->m_cacheNbChiffres] == '\0';
    }
     
    void SDCDC_ConstruireAvecChiffresLesPlusPetits(SDCDC* pThis, int nbChiffres) {
    	assert(pThis != NULL);
    	assert(nbChiffres >= 1 && nbChiffres <= 10);
    	for(int k = 0; k < nbChiffres; ++k)
    		pThis->m_chaine[k] = '0' + k;
    	pThis->m_chaine[nbChiffres] = '\0';
    	pThis->m_cacheNbChiffres = nbChiffres;
    	assert(SDCDC_Invariant(pThis));
    }
     
    int SDCDC_Afficher(const SDCDC* pThis, FILE* stream) {
    	assert(pThis  != NULL);
    	assert(stream != NULL);
    	return fputs(pThis->m_chaine, stream);
    }
     
    //! Par exemple, avec 4 chiffres, la dernière suite est 6789.
    //! Les autres suites ont un premier chiffre <= 5.
    bool SDCDC_SuiteSuivanteAvecMemeNbChiffresExiste(const SDCDC* pThis) {
    	assert(pThis != NULL);
    	return pThis->m_chaine[0] <= ('9' - pThis->m_cacheNbChiffres);
    }
     
    //! Par exemple, la suite de chiffres qui suit 13789 est 14567.
    void SDCDC_RemplacerParSuiteSuivanteAvecMemeNbChiffres(SDCDC* pThis) {
    	assert(pThis != NULL);
    	assert(SDCDC_SuiteSuivanteAvecMemeNbChiffresExiste(pThis));
    	char* const dernierChiffre = pThis->m_chaine + pThis->m_cacheNbChiffres - 1;
    	// Etape 1 : On cherche le chiffre à incrémenter le plus à droite possible.
    	// Par exemple, dans 13789, le chiffre à incrémenter est 3.
    	char* chiffreAIncrementer = dernierChiffre;
    	while(true)	{
    		const char valeurMaximale = '9' - (dernierChiffre - chiffreAIncrementer);
    		const bool incrementationPossible = (*chiffreAIncrementer < valeurMaximale);
    		if(incrementationPossible)
    			break;
    		--chiffreAIncrementer;
    		assert(chiffreAIncrementer >= pThis->m_chaine);
    	}
    	// Etape 2 : On incrémente le chiffre trouvé.
    	++(*chiffreAIncrementer);
    	// Etape 3 : On ajuste tous les éventuels chiffres qui sont à droite de celui
    	// qu'on vient d'incrémenter.
    	for(char* chiffreAAjuster = chiffreAIncrementer + 1; chiffreAAjuster <= dernierChiffre; ++chiffreAAjuster)
    		*chiffreAAjuster = *(chiffreAAjuster-1) + 1;
    	assert(SDCDC_Invariant(pThis));
    }
     
    void afficherDansLaSortieStandardLesCombinaisonsDeChiffresDeLExercice(int nbChiffres) {
    	assert(nbChiffres >= 1 && nbChiffres <= 10);
    	SDCDC chiffresDistincsCroissants;
    	SDCDC_ConstruireAvecChiffresLesPlusPetits(&chiffresDistincsCroissants, nbChiffres);
    	while(true) {
    		SDCDC_Afficher(&chiffresDistincsCroissants, stdout);
    		if(!SDCDC_SuiteSuivanteAvecMemeNbChiffresExiste(&chiffresDistincsCroissants))
    			break;
    		fputc(' ', stdout);
    		SDCDC_RemplacerParSuiteSuivanteAvecMemeNbChiffres(&chiffresDistincsCroissants);
    	}
    }
     
    int main(int argc, char *argv[])
    {
    	if(argc < 2) {
    		printf("Erreur : pas assez d'arguments.");
    		return 1;
    	}
    	const int nbChiffres = atoi(argv[1]);
    	if(nbChiffres < 1 || nbChiffres > 10) {
    		printf("Erreur : le premier argument doit etre un nombre entre 1 et 10.");
    		return 1;
    	}
    	afficherDansLaSortieStandardLesCombinaisonsDeChiffresDeLExercice(nbChiffres);
    	return 0;
    }
    Quelques améliorations par rapport au code que j'avais écrit en juin :
    • Erreur de conception signalée par Matthieu Vergne corrigée : remplacerParChaineSuivante ne cumule plus les deux responsabilités "vérifier s'il y a une chaîne suivante" et "remplacer par la chaîne suivante si elle existe".
    • Ajout de l'encapsulation sur la représentation des suites de chiffres.
    • Le nombre d'allocations dynamiques passe de 1 à 0.

Discussions similaires

  1. Afficher des combinaisons de chiffres
    Par sefora dans le forum Excel
    Réponses: 12
    Dernier message: 12/09/2015, 09h57
  2. combinaison de chiffres ou lettres
    Par torjancss dans le forum Excel
    Réponses: 1
    Dernier message: 05/03/2014, 19h38
  3. Combinaisons à 6 chiffres possibles parmi 20 nombres
    Par djbebop dans le forum Général Algorithmique
    Réponses: 10
    Dernier message: 14/05/2011, 15h46
  4. Combinaison de chiffre
    Par Moine dans le forum Général Algorithmique
    Réponses: 6
    Dernier message: 11/06/2008, 14h36
  5. algo pour afficher des combinaisons de chiffres
    Par m0ul3sh0t dans le forum Général Algorithmique
    Réponses: 8
    Dernier message: 29/10/2007, 23h37

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo