Logo GNT
Actualités Tests & Guides Bons Plans
GTA 6 iPhone 17 Copilot Switch 2 Temu ChatGPT Tesla
OVH Cloud OVH Cloud
Entraide Développement Développement Langage C Combinaison min/MAJ

Combinaison min/MAJ

43 réponses
Avatar
spongebof
Bonjour,

Je cherche un algorithme à implémenter en C qui soit capable à partir
d'un mot de X caractères de trouver toutes les écritures possibles pour
0 à X majuscule(s) présente(s) dans ce mot.

Exemple pour le mot 'test':

test
tesT
teSt
teST
tEst
tEsT
tESt
tEST
Test
TesT
TeSt
TeST
TEst
TEsT
TESt
TEST

Merci
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
1 2 3 4 5
Avatar
Antoine Leca
En news:473b1123$0$27287$, Mickaël Wolff va escriure:


int variant_init(variant * v, const char * s)
{
memset(v, '', sizeof *v) ;
v->size = strlen(s) ;



Problème potentiel lorsque strlen() retourne une valeur supérieure à
UNIT_MAX (en supposant par exemple que size_t est un type plus grand
que unsigned.)


Je suppose que tu voulais dire UINT_MAX.


Oui.

Mais est-ce que je suppose mal de considérer size_t comme un
unsigned int ?


Oui (tu supposes mal).

Où size_t est à la discretion de l'implémentation est n'est pas
inscrit dans le marbre normatif ?


C'est exactement cela.
Et pour prendre deux exemples :
- certains compilateurs pour DOS ou OS/2 16 bits en modèle "huge"
utilisaient unsigned long (32 bits) pour size_t, avec tout un système
roccoco de pointeurs s'auto-ajustant et permettant de manipuler des
structures de plus de 64 Ko ;
- la plateforme Win64 a des pointeurs sur 64 bits, et des entiers et aussi
des long sur 32 bits ; et il est concevable de faire un compilateur pour
cette plateforme avec size_t sur 64 bits.


*(next+pos) = step & 1 << pos ? toupper(first->str[pos]) :



Bzzz. str est un char*, str[pos] est éventuellement signé ;
toupper() attend un int avec soit la valeur EOF, soit une valeur
représentable comme unsigned char. Bisbille.

Le mieux est d'utiliser des unsigned char partout dans ton programme
(et d'expliquer pourquoi).


Effectivement, c'est ce que dit le man. Je n'avais même pas fait
attention à ce qu'il attende un entier. C'est d'ailleurs bizarre.
Pourquoi attend-il un entier alors que les chaînes ASCII sont stockées
dans des tableaux de char ?


Parce que les Américains ne voient pas la différence de toute façon, parce
que les char signés cela ne concernait au départ que les PDP-11 des
Américains (les machines IBM avaient des chars non signés du fait de
l'EBCDIC), et parce que comme c'est *nix qui a les préférences des gens
chargés à la fois de la normalisation et du compilateur de référence (GCC
pour le moment), par défaut char est souvent signé.
Au résultat, patatras.


Antoine




Avatar
Antoine Leca
En news:fhfddu$oc4$, Antoine Leca va escriure:
En news:473b1123$0$27287$, Mickaël Wolff va
escriure:
[Utiliser des unsigned char * quand on fait appel à <ctype.h>]

Effectivement, c'est ce que dit le man. Je n'avais même pas fait
attention à ce qu'il attende un entier. C'est d'ailleurs bizarre.
Pourquoi attend-il un entier alors que les chaînes ASCII sont
stockées dans des tableaux de char ?


Parce que les Américains ne voient pas la différence de toute façon,
parce que les char signés cela ne concernait au départ que les PDP-11
des Américains (les machines IBM avaient des chars non signés du fait
de l'EBCDIC), et parce que comme c'est *nix qui a les préférences des
gens chargés à la fois de la normalisation et du compilateur de
référence (GCC pour le moment), par défaut char est souvent signé.
Au résultat, patatras.


Complément à la réponse d'hier soir que j'ai écrit en courant.

Le paragraphe ci-dessus explique pourquoi en C on utilise par défaut des
char (signés), alors que la plupart du temps on veut probablement utiliser
des unsigned char.

Je dois rajouter après relecture qu'une autre raison est pour la symétrie de
contruction de l'ensemble, par défaut les int sont signés, les long sont
signés, les short sont signés, il est donc raisonnable d'attendre que les
char (qui ne sont que des entiers encore plus petits que short) soient
signés. Ce n'est pas seulement un simple souci d'esthétisme, au départ cela
facilite l'apprentissage du langage ; et le fait que l'on ai besoin parfois
d'avoir des unsigned char, et que selon les compilateurs ce soit parfois
l'un parfois l'autre, complique furieusement l'apprentissage du langage.


Maintenant, la question de Mickaël ne portait pas (si je relis bien) sur le
signe de char, mais plutôt sur le fait de savoir pourquoi les fonctions de
<ctype.h> utilise des arguments de type int, avec des valeurs correspondant
au type unsigned char.

Premier élément de réponse, les int sont utilisés car en C, les expressions
de taille inférieure sont de toute manière converties en int ; et en fait,
dans les premiers compilateurs C (avant la norme ANSI et spécifiquement les
prototypes), il était impossible d'avoir un argument de type char tout
court.

Deuxième élément de réponse, en plus des caractères, ces fonctions savent
traiter la valeur EOF. Cela est dû à la compatibilité avec les fonctions de
<stdio.h>, en particulier fgetc(). Historiquement, EOF vaut une valeur
négative (normalement -1), et il est impossible de changer cela, trop de
code utilise l'idiome
if( (c = fgetc(xxx)) < 0 )
/* fin de fichier ou erreur */
Et bien sûr, si on veut (ou on doit) manipuler l'ensemble des valeurs
possibles du type caractères (retour aux caractères accentués évoqués
ci-dessus), il faut alors que les caractères soit représentés par des
valeurs positives, ce qui requiert l'utilisation de unsigned char. CQFD.


Au résultat, la norme spécifie que les caractères lus ou manipulés par
toupper() et cie doivent avoir des valeurs correspondant au type unsigned
char, bien obligée.
Mais la norme a décidé de ne pas bannir le caractère signed par défaut de
char (concession faite à l'implémentation dominante, cf. supra), et a aussi
décidé de ne pas toucher aux prototypes historiques des fonctions qui
manipulent des chaînes de caractères, à commencer par le type de argv[],
laissant char*.

Le résultat global n'est pas très cohérent, et c'est bien la conclusion à
laquelle Mickaël était arrivé.


Antoine


Avatar
espie
Tiens, je me repond a moi-meme, on peut faire le travail en place, et
eviter un probleme subtil.


#include <stdio.h>
#include <ctype.h>

void
enumere(char *m, int i)
{
if (m[i] == 0)
puts(m);
else {
m[i] = tolower(m[i]);
enumere(m, i+1);
if (m[i] != toupper(m[i])) {
m[i] = toupper(m[i]);
enumere(m, i+1);
}
}
}


int
main()
{
/* necessaire pour eviter une chaine constante */
char mot[] = "court-circuit";

enumere(mot, 0);
return 0;
}
Avatar
Charlie Gordon
"Antoine Leca" a écrit dans le message de news:
fheu6g$vvt$
En news:473ad468$0$25918$, Vincent Guichard va
escriure:
void PrintSolutionN(char * mot, int len, long index)


Pourquoi un long pour index ?


Pour traiter plus de caactères si sizeof(long) > sizeof(int) ?
Mais cela marche encore mieux avec un unsigned long.

sol[i] = toupper(mot[i]);


:-( (cf. autres messages)


sol[i] = toupper((unsigned char)mot[i])

Mais il faudrait aussi tester isalpha((unsigned char)mot[i]) pour éviter de
produire des doublons pour les caractères qui ne sont pas des lettres.

int N = strlen(mot);


:-(


Effectivement, il faudrait mettre size_t N = strlen(mot);
mais c'est bien moins grave que d'avoir oublié d'inclure <string.h>

long total = 1<<N;


Pourquoi un long ici ?


Plutot unsigned long total = 1UL << N;

et il faudrait aussi un test sur ``N < sizeof(unsigned long) * CHAR_BIT'',
pour éviter le comportement indéfini du << pour une valeur trop grande.
D'ailleurs ce test n'est pas strictement suffisant pour les puristes
extrémistes, mais on va dire que ca va quand meme.

int index;


... et un int ici (alors même que le prototype de PrintSolutionsN attend
un
long pour index).


Il faudrait indéniablement utiliser le même type que pour N, long ou
unsigned long.

printf("Analyse pour %s: %ld solutions.n", mot, total);



%lu si on prend unsigned long pour le type de total et index.

for(index=0; index < total; index++)


Avec un mot de 15 lettres, total peut valoir INT_MIN (surprise) et cela va
faire une boucle infinie.
Avec un mot de 16 lettres ou plus, total peut valoir 0, donc l'algorithme
va
faire les 32768 premières possibilités (jusque là OK), index va passer de
INT_MAX à INT_MIN (ou bien erreur de débordement) et donc s'arrêter là.

Si tu as des int de 32 bits, les limites sont plus loin mais les
comportements sont les mêmes avec des mots de 31 ou 32+ lettres.


Oui, c'et pourquoi je préconise unsigned long.

--
Chqrlie.


Avatar
Charlie Gordon
"Vincent Guichard" a écrit dans le message de
news: 473ad468$0$25918$
Bonjour,

si la récursion n'est pas le thème du devoir, tu peux aussi compter de 0 à
2^N-1 et mettre une majuscule à l'emplacement i du mot lorsque le bit i de
l'index est à 1 et une minuscule lorsqu'il est à 0.


Voici une version plus complete du meme algorithme, qui support les mots
avec des caractères non alphabétiques, inclut les bon headers, utilise des
types plus cohérents et fait plus de tests.
De plus il faut éviter de poster du code indenté avc des tabs sur Usenet.

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

const char *progname;

void print_word_case(const char *mot, unsigned long mask)
{
char *sol = strdup(mot);
size_t i;

if (!sol) {
fprintf(stderr, "%s: plus de memoiren", progname);
exit(EXIT_FAILURE);
}

for (i = 0; sol[i] != ''; i++) {
if (isalpha((unsigned char)sol[i])) {
if (mask & 1) {
sol[i] = toupper((unsigned char)sol[i]);
} else {
sol[i] = tolower((unsigned char)sol[i]);
}
mask >>= 1;
}
}
printf("%sn", sol);
free(sol);
}

int main(int argc, char * argv[])
{
int i;

progname = argv[0];
if (argc < 2) {
fprintf(stderr, "usage: %s mot ...n", progname);
return EXIT_FAILURE;
}

for (i = 1; i < argc; i++) {
const char *p, *mot = argv[i];
unsigned long mask, total;

total = 1;
for (p = mot; *p != ''; p++) {
if (isalpha((unsigned char)*p)) {
total <<= 1;
}
}
if (total == 0) {
fprintf(stderr, "%s: le mot '%s' a trop de lettresn",
progname, mot);
return EXIT_FAILURE;
}
printf("Analyse pour '%s': %lu solution%s.n",
mot, total, "s" + (total < 2));
for (mask = 0; mask < total; mask++) {
print_word_case(mot, mask);
}
}
return EXIT_SUCCESS;
}

--
Chqrlie.

Avatar
espie
In article <473c97d8$0$12488$,
Charlie Gordon wrote:
void print_word_case(const char *mot, unsigned long mask)
{
char *sol = strdup(mot);
[...]

free(sol);
}


Je suis surpris, d'habitude tu utilises des fonctions portables, ce
que strdup n'est pas...

Avatar
Charlie Gordon
"Marc Espie" a écrit dans le message de news:
fhi805$2goe$
In article <473c97d8$0$12488$,
Charlie Gordon wrote:
void print_word_case(const char *mot, unsigned long mask)
{
char *sol = strdup(mot);
[...]

free(sol);
}


Je suis surpris, d'habitude tu utilises des fonctions portables, ce
que strdup n'est pas...


strdup n'est pas standard mais elle est portable : c'est une fonction Posix
qu'il est trivial de reimplementer sur les plateformes ou elle n'est pas
disponible:

char *strdup(const char *str) {
size_t size;
char *p;
if (!str)
return NULL;
size = strlen(str) + 1;
p = malloc(size);
if (!p)
return NULL;
return memcpy(p, str, size);
}

C'est un tel scandale que l'ANSI, puis l'ISO n'aient pas inclus cette
fonction dans la libc que je refuse de cesser de l'utiliser alors que
pratiquement toutes les plateformes la supportent. Bien sur M$ l'affuble
d'un underscore initial aussi stupide que laid, mais c'est bien coherent
avec le reste de leur environnmement.

--
Chqrlie.

PS: En revanche, tu n'es pas pres de me voir utiliser strncpy ;-)


Avatar
espie
In article <473cadc3$0$26500$,
Charlie Gordon wrote:
"Marc Espie" a écrit dans le message de news:
fhi805$2goe$
In article <473c97d8$0$12488$,
Charlie Gordon wrote:
void print_word_case(const char *mot, unsigned long mask)
{
char *sol = strdup(mot);
[...]

free(sol);
}


Je suis surpris, d'habitude tu utilises des fonctions portables, ce
que strdup n'est pas...


strdup n'est pas standard mais elle est portable : c'est une fonction Posix
qu'il est trivial de reimplementer sur les plateformes ou elle n'est pas
disponible:

char *strdup(const char *str) {
size_t size;
char *p;
if (!str)
return NULL;


YUCK
Grosse connerie: un pointeur nul n'est PAS une chaine valide.
Toutes les implementations qui `verifient' les pointeurs et essaient
de faire un truc sense avec en presence d'un pointeur nul ont le gros
defaut de permettre l'ecriture de code non portable (j'ai deja corrige
du code linux qui segfaultait ailleurs grace a un strcmp(NULL, "qqchose") )


size = strlen(str) + 1;
p = malloc(size);
if (!p)
return NULL;
return memcpy(p, str, size);
}

C'est un tel scandale que l'ANSI, puis l'ISO n'aient pas inclus cette
fonction dans la libc que je refuse de cesser de l'utiliser alors que
pratiquement toutes les plateformes la supportent. Bien sur M$ l'affuble
d'un underscore initial aussi stupide que laid, mais c'est bien coherent
avec le reste de leur environnmement.


Je ne suis pas d'accord avec toi. strdup pose de reels petits problemes
de portabilite. C'est une des rares fonctions qui melange allocation
memoire et manipulation de chaines... elle a aussi le gros defaut
d'avoir un flou artistique sur la fonction d'allocation memoire utilisee.
En particulier, je connais des implementations qui utilisent malloc()
en C et new en C++...D'ou big probleme avec le free() resultant.

Pour pouvoir l'inclure dansla norme, il aurait fallu que cette fonction
soit non-ambigue.

Ce qui n'est pas trop comprehensible, c'est qu'on n'ait pas dans la
norme une fonction de nom similaire et possedant une semantique bien
definie... apres tout, ils ne se sont pas genes pour index -> strchr.

Enfin si, je vois une semie- bonne raison: les fonctions de string.h sont
(globalement) valables pour les implementations `freestanding', tandis
que malloc(), non...



Avatar
Charlie Gordon
"Marc Espie" a écrit dans le message de news:
fhicbr$2i6d$
In article <473cadc3$0$26500$,
Charlie Gordon wrote:
"Marc Espie" a écrit dans le message de news:
fhi805$2goe$
In article <473c97d8$0$12488$,
Charlie Gordon wrote:
void print_word_case(const char *mot, unsigned long mask)
{
char *sol = strdup(mot);
[...]

free(sol);
}


Je suis surpris, d'habitude tu utilises des fonctions portables, ce
que strdup n'est pas...


strdup n'est pas standard mais elle est portable : c'est une fonction
Posix
qu'il est trivial de reimplementer sur les plateformes ou elle n'est pas
disponible:

char *strdup(const char *str) {
size_t size;
char *p;
if (!str)
return NULL;


YUCK
Grosse connerie: un pointeur nul n'est PAS une chaine valide.
Toutes les implementations qui `verifient' les pointeurs et essaient
de faire un truc sense avec en presence d'un pointeur nul ont le gros
defaut de permettre l'ecriture de code non portable (j'ai deja corrige
du code linux qui segfaultait ailleurs grace a un strcmp(NULL,
"qqchose") )


N'est-on pas sensé tester le résultat de strdup de toute façon? Alors
pourquoi planter délibérément? Mais en fait tu as sans doute raison, le
test sur NULL n'est bienvenu que si la sémantique de strdup est définie pour
un argument NULL, comme c'est le cas pour free et realloc. Comme cela ne
semble pas être le cas pour strdup dans Posix, un bon gros undefined
behaviour est peut-etre préférable.

size = strlen(str) + 1;
p = malloc(size);
if (!p)
return NULL;
return memcpy(p, str, size);
}

C'est un tel scandale que l'ANSI, puis l'ISO n'aient pas inclus cette
fonction dans la libc que je refuse de cesser de l'utiliser alors que
pratiquement toutes les plateformes la supportent. Bien sur M$ l'affuble
d'un underscore initial aussi stupide que laid, mais c'est bien coherent
avec le reste de leur environnmement.


Je ne suis pas d'accord avec toi. strdup pose de reels petits problemes
de portabilite. C'est une des rares fonctions qui melange allocation
memoire et manipulation de chaines... elle a aussi le gros defaut
d'avoir un flou artistique sur la fonction d'allocation memoire utilisee.
En particulier, je connais des implementations qui utilisent malloc()
en C et new en C++...D'ou big probleme avec le free() resultant.


Quel rapport avec le C ? Que des plateformes definissent strdup de facon
délirante ne doit pas pénaliser les autres. Posix définit de façon claire
que la copie est allouée avec malloc, c'est une erreur d'utiliser new.

Pour pouvoir l'inclure dansla norme, il aurait fallu que cette fonction
soit non-ambigue.


C'est plutot le contraire: l'avoir incluse dans la norme aurait permis que
la définition en fût précise et figée. C'est la faute de l'ANSI en fin de
compte.

Ce qui n'est pas trop comprehensible, c'est qu'on n'ait pas dans la
norme une fonction de nom similaire et possedant une semantique bien
definie... apres tout, ils ne se sont pas genes pour index -> strchr.


Pourquoi un autre nom alors que strdup est là et utilisée ?
Pour strchr, ils ont dû penser que le préfixe str était important pour une
fonction de chaine, et que de sacrifier le mot index pour cet usage était
inacceptable.

Un autre "oubli" est la comparaison "case-insensitive" connue sous les noms
de stricmp et strcasecmp. La définition est bien sur un peu approximative à
cause des caractères non-ASCII, mais il est naturel de calquer les choix sur
ceux de <ctype.h> et de les "localiser" le cas échéant (bien que j'aurais
préféré qu'on évite de normaliser quoi que ce soit pour le support de la
localisation).

Enfin si, je vois une semie- bonne raison: les fonctions de string.h sont
(globalement) valables pour les implementations `freestanding', tandis
que malloc(), non...


Fausse excuse.

--
Chqrlie.




Avatar
Mickaël Wolff

Complément à la réponse d'hier soir que j'ai écrit en courant.


[snip]

Le résultat global n'est pas très cohérent, et c'est bien la conclusion à
laquelle Mickaël était arrivé.


Merci pour tout ces éclaircissements ! Tout ceci me fait penser qu'au
final, il est plus intelligent d'utiliser des wchar en lieu et place des
char. Non ? (même si en fait, les wchar sont des int déguisés).

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org

1 2 3 4 5