Combinaison min/MAJ

Le
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
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 5
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Mickaël Wolff
Le #999115
Bonjour,


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.


Je pensais que c'était simple, mais ça m'a pris un moment avant
d'arriver à pondre un code correct... Une heure pour un problème trivial
:) Je suis vraiment rouillé.

Je suppose que ta question est pour tes devoirs... Donc je vais juste
te dire comment j'ai fait (parce que ça sert à rien de pomper bêtement).
Vu que tu ne t'intéresse qu'aux majuscules et minuscules, tu n'a que
deux possibilités. Ça ressemble furieusement au binaire ça. Donc tu peux
utiliser un entier pur stocker la position des caractères, et utiliser
le décalage de bits pour savoir si le caractère doit être en majuscule
ou en minuscule.

touipe => 000000
TouPie => 100100

L'astuce consiste à dire que « toupie » correspond à l'étape 0, et
TouPie à l'étape pow(2,2) + pow(2,5). Je te laisse deviner qu'elle sera
le nombre de résultats attendus.

Bien évidemment tu auras une limite de 32 ou 64 caractères suivant
l'architecture. Si tu veux faire des chaînes plus longues, il faudra un
autre algo.

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

Pierre Maurette
Le #999114
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


Bonjour,

L'algo, qui n'a pas trop à voir avec le C, s'impose de lui-même et il
est itératif(*):
- Si vous avez la solution - une liste de mots - pour N lettres, il
suffit pour passer à N + 1 de "concatener" les termes de la
liste-solution successivement à minuscule() et majuscule() de la lettre
suppémentaire.
- La solution pour N = 1 est évidente.

Voici une tentative en C. Il faut taper le mot en ligne de commande,
j'ai limité la taille à 10 caractères, à vous de modifier tout ça. De
même la fonction (idiote) mydebugputs() sert à afficher un nombre
correspondant au "pattern" binaire des majuscules, utile pour vérifier
l'unicité et la complétude des solutions.


#include #include #include #include #include
inline void souhappeCase(char* s, int offset)
{
assert(isalpha(s[offset]));
s[offset] = islower(s[offset]) ? toupper(s[offset]) :
tolower(s[offset]);
}

void mydebugputs(char* s)
{
int i = 0, somme = 0, power = 1;
int taille = strlen(s); //beurk
for(i = 0; i < taille; i++)
{
if(isupper(s[i]))somme += power;
power *= 2;
}
printf("%st, %un", s, somme);
}

void afficheRecurs(char* s, int index)
{
if(index >= 0){
afficheRecurs(s, index - 1);
souhappeCase(s, index);
//puts(s);
mydebugputs(s);
afficheRecurs(s, index - 1);
}
return;
}

inline void affiche(char* s, int taille)
{
mydebugputs(s);
afficheRecurs(s, taille - 1);
}

int main(int argc, char *argv[])
{
if(argc != 2){
/* usage */
return EXIT_SUCCESS;
}
int curseur;
int taille = strlen(argv[1]);
assert(taille < 11);
for(curseur = 0; curseur < taille; curseur++){
if(! isalpha(argv[1][curseur])){
fprintf(stderr, "Le mot ne doit contenir que des lettres
!");
return EXIT_SUCCESS;
}
//argv[1][curseur] = tolower(argv[1][curseur]);
}
affiche(argv[1], taille);
return EXIT_SUCCESS;
}

(*) je ne suis pas sûr du vocabulaire. Je dirais que le raisonnement
est itératif, et le traitement POURRA être récursif.


--
Pierre Maurette

espie
Le #999113
In article Pierre Maurette
L'algo, qui n'a pas trop à voir avec le C, s'impose de lui-même et il
est itératif(*):
- Si vous avez la solution - une liste de mots - pour N lettres, il
suffit pour passer à N + 1 de "concatener" les termes de la
liste-solution successivement à minuscule() et majuscule() de la lettre
suppémentaire.
- La solution pour N = 1 est évidente.

(*) je ne suis pas sûr du vocabulaire. Je dirais que le raisonnement
est itératif, et le traitement POURRA être récursif.


Non, il s'agit bien d'une recursion, au sens mathematique du terme.

Note qu'un vrai matheux dirait que la solution pour N=0 est evidente...

Apres, faut voir ce qu'on veut comme resultat, si c'est juste afficher
tous les mots possibles, il y a des facons super-simples de faire en
juste quelques lignes de code:


#include #include #include
void
construit(const char *m, char *b, int i)
{
if (m[i] == 0) {
b[i] = 0;
printf("%sn", b);
} else {
b[i] = tolower(m[i]);
construit(m, b, i+1);
b[i] = toupper(m[i]);
construit(m, b, i+1);
}
}


int
main()
{
char *buffer;
const char *mot = "example";
int N = strlen(mot);

buffer = malloc(N+1);
if (!buffer)
exit(1);

construit(mot, buffer, 0);
exit(0);
}

Vincent Guichard
Le #999112
Bonjour,

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

Vincent Guichard

#include #include
void PrintSolutionN(char * mot, int len, long index)
{
char * sol = (char*)malloc(len+1);
int i;
for(i=0; i<len; i++)
{
if(index&(1<<i))
sol[i] = toupper(mot[i]);
else
sol[i] = tolower(mot[i]);
}
printf("Solution n°%ld:t%sn", index, sol);
free(sol);
}

int main(int argc, char * argv[])
{
if(argc!=2) return EXIT_FAILURE;
char * mot = argv[1];
int N = strlen(mot);
long total = 1<<N;
int index;
printf("Analyse pour %s: %ld solutions.n", mot, total);
for(index=0; index < total; index++)
{
PrintSolutionN(mot, N, index);
}
return EXIT_SUCCESS;
}
Antoine Leca
Le #998974
En news:, Pierre Maurette va escriure:
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.


L'algo, qui n'a pas trop à voir avec le C, s'impose de lui-même et il
est itératif(*):
<snip>


Oui.

Voici une tentative en C.
<snip mode d'emploi>

<snip #include>
inline void souhappeCase(char* s, int offset)
{
assert(isalpha(s[offset]));


Pourquoi cet assert() ? le programme n'est pas susceptible de traiter un mot
comme 'casse-pied' ?

Par ailleurs, isalpha a un comportement indéfini ici (par exemple lorsque
char est signed).


s[offset] = islower(s[offset]) ? toupper(s[offset])
: tolower(s[offset]);

void afficheRecurs(char* s, int index)
{
if(index >= 0){
afficheRecurs(s, index - 1);
souhappeCase(s, index);
//puts(s);
mydebugputs(s);
afficheRecurs(s, index - 1);
}


Non. Si la lettre ne change pas dans l'appel à souhappeCasse() (cas d'un
tiret, ou d'un caractère accentué bas-de-casse dont la capitale n'est pas
disponible dans le jeu de caractère actuel, disons par exemple un ß), tu vas
afficher deux fois la même forme, et ce n'est pas correct.


int main(int argc, char *argv[])
<snip init>

for(curseur = 0; curseur < taille; curseur++){
if(! isalpha(argv[1][curseur])){


Manque un appel à setlocale() avant cette ligne.

fprintf(stderr, "Le mot ne doit contenir que des lettres!");
return EXIT_SUCCESS;


Ce doit être un succès pour tromper l'ennemi...


Enfin, ton implémentation modifie la chaîne en place, ce qui suppose qu'il
existe une bijection entre les capitales et les bas-de-casses, ce qui n'est
pas obligatoirement le cas (par exemple ÿ en iso-8859-1).


Antoine


Pierre Maurette
Le #998973
En news:, Pierre Maurette va escriure:
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.


L'algo, qui n'a pas trop à voir avec le C, s'impose de lui-même et il
est itératif(*):
<snip>


Oui.

Voici une tentative en C.
<snip mode d'emploi>

<snip #include>
inline void souhappeCase(char* s, int offset)
{
assert(isalpha(s[offset]));


Pourquoi cet assert() ? le programme n'est pas susceptible de traiter un mot
comme 'casse-pied' ?


C'est exactement ça. Ce n'est pas un programme, mais une "tentative en
C". Le assert() et le test dans le main() - qui ont presque du luxe dns
ce genre de réponse - sont clairs, on ne traite que des chaines de
caractères alphabétiques.


Par ailleurs, isalpha a un comportement indéfini ici (par exemple lorsque
char est signed).


s[offset] = islower(s[offset]) ? toupper(s[offset])
: tolower(s[offset]);

void afficheRecurs(char* s, int index)
{
if(index >= 0){
afficheRecurs(s, index - 1);
souhappeCase(s, index);
//puts(s);
mydebugputs(s);
afficheRecurs(s, index - 1);
}


Non. Si la lettre ne change pas dans l'appel à souhappeCasse() (cas d'un
tiret, ou d'un caractère accentué bas-de-casse dont la capitale n'est pas
disponible dans le jeu de caractère actuel, disons par exemple un ß), tu vas
afficher deux fois la même forme, et ce n'est pas correct.


D'où le assert() dans souhappeCase(), voir plus haut.

int main(int argc, char *argv[]) <snip init>
for(curseur = 0; curseur < taille; curseur++){
if(! isalpha(argv[1][curseur])){


Manque un appel à setlocale() avant cette ligne.

fprintf(stderr, "Le mot ne doit contenir que des lettres!");
return EXIT_SUCCESS;


Ce doit être un succès pour tromper l'ennemi...


Je renvoie EXIT_SUCCESS après une "erreur" traitée, plus exactement
quand la ligne de commandes ne correspond pas à ce que le programme
attend et que c'est affiché. C'et à mon sens une sortie normale du
programme.


Enfin, ton implémentation modifie la chaîne en place, ce qui suppose qu'il
existe une bijection entre les capitales et les bas-de-casses, ce qui n'est
pas obligatoirement le cas (par exemple ÿ en iso-8859-1).


Si vous le dites... Mais je vous rappelle quand même et à nouveau que
le ÿ ne passe pas le test initial dans le main(), et l'assert()
redondant.

--
Pierre Maurette



Mickaël Wolff
Le #998972

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.


C'est un peu ce que j'ai proposé cette nuit. À croire que personne n'a
lu mon message :-/ Alors que ça m'intéresse d'avoir des avis sur mon
code pourri.

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

Antoine Leca
Le #998971
En news:473abf4b$0$11444$, Mickaël Wolff va escriure:
typedef struct _variant {
unsigned int size ;
char * str ;
} variant ;

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


if(v->size > sizeof(unsigned int)*8 - 1)
return -1 ;



Intéressant. Tu limites la taille à N-1 (N le nombre de bits dans un entier,
je néglige ici les cas particuliers du genre char sur 9 bits), alors que ton
algorithme devrait pouvoir être utilisé avec une lettre de plus. Je sais
bien que tel que tu l'as programmé il va probablement avoir des soucis si on
augmente la taille d'un, mais à mon sens c'est justement cela qui est
intéressant, non ?


*(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).


int main(int argc, char ** argv)
[...]


result = malloc(variant.size * sizeof(char)) ;



Mmmh... et un malloc() sans vérifier le retour, un !


Antoine


Antoine Leca
Le #998970
En news:473ad468$0$25918$, Vincent Guichard va
escriure:
void PrintSolutionN(char * mot, int len, long index)


Pourquoi un long pour index ?

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


:-( (cf. autres messages)

int N = strlen(mot);


:-(

long total = 1<<N;


Pourquoi un long ici ?

int index;


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

printf("Analyse pour %s: %ld solutions.n", mot, total);
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.

Antoine

Mickaël Wolff
Le #998969
Tout d'abord, merci d'y avoir jeté un ½il !


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. Mais est-ce que je suppose
mal de considérer size_t comme un unsigned int ? Où size_t est à la
discretion de l'implémentation est n'est pas inscrit dans le marbre
normatif ?


if(v->size > sizeof(unsigned int)*8 - 1)
return -1 ;



Intéressant. Tu limites la taille à N-1 (N le nombre de bits dans un entier,
je néglige ici les cas particuliers du genre char sur 9 bits), alors que ton
algorithme devrait pouvoir être utilisé avec une lettre de plus. Je sais
bien que tel que tu l'as programmé il va probablement avoir des soucis si on
augmente la taille d'un, mais à mon sens c'est justement cela qui est
intéressant, non ?


Au départ, j'utilisais effectivement tout les bits de l'entier, mais
j'avais un problème lorsque je faisais 1 << 32 :) Donc j'ai décidé de
limité arbitrairement, pour éviter un plantage et y revenir plus tard,
si c'est intéressant.

En ce qui concerne les char ne correpondant pas à un octet, je n'y
avais effectivement pas pensé.

*(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 ?

int main(int argc, char ** argv)
[...]


result = malloc(variant.size * sizeof(char)) ;



Mmmh... et un malloc() sans vérifier le retour, un !


Ça arrive de laisser passer une bêtise comme ça :p

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



Publicité
Poster une réponse
Anonyme