Exercice en C de combinaison de chiffres

Version imprimable

1 pièce(s) jointe(s)

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:

Citation:

É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:

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
Pièce jointe 282340

04/06/2017, 22h52
Delias

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

Citation:

Envoyé par raiden500

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

Code:

write(1, &c, 1);

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:

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:

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

09/06/2017, 15h49
Invité

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

Bonjour,

Citation:

Envoyé par raiden500

Code:

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:

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

Code:

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:

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

10/06/2017, 08h41
Sve@r

Citation:

Envoyé par Pyramidev

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

Il y a une étourderie. Il faut remplacer zone[i] < zone[i-1] par zone[i] <= zone[i-1].

Exact. 8-) De ton côté tu rajouteras le free() qui manque :D
10/06/2017, 10h49
ternel

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)
10/06/2017, 11h43
Sve@r

Citation:

Envoyé par ternel

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 8-)
16/06/2017, 00h14
Pyramidev
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:

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

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.
16/06/2017, 09h28
ternel

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.

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:

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.