Partage

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

<< 1 ... 26 27 28 ... 55 >>

9 mai 2009 à 21:53:41

zx-spectrum ==>

for (j = i; j < i+len2 ; j++)
{
    if (chaine1[j]==chaine2[j-i]) trouve++;
    else
    {
        i=i+len2;
        /*break; equivalent pour i = i+ len2;*/
    }
}

Supposons quelen2 = 5
Au premier tour :i = j = 0

if (chaine1[j]==chaine2[j-i]) trouve++;
else
{
    i=i+len2;
    /*break; equivalent pour i = i+ len2;*/
}

Supposons quechaine1[0] != chaine2[0-0]
Donci = i + len2 = 0 + 5 = 5

On retourne toujours dans la boucle car :j < i+len2
Puis : if (chaine1[j]==chaine2[j-i]) trouve++;
Orj = 1 eti = 5
Donc on teste :if (chaine1[1]==chaine2[1-5])
chaine[-4] n'existe pas.

Enfin, quand j'exécute ton code, j'obtiens une erreur de violation d'accès. (A la ligne 33)

Tosh ==>

J'ai testé avec ton code :

int main(void)
{
  char sousChaine[] = "fofo";
  char chaine[] = "fofofo";
  printf ("Occurences trouvées : %d\n", zStrsearch (sousChaine, chaine));

  return 0;
}

Occurence trouvée en : 1
Caractères lus : 8
Occrences trouvées : 1

Alors, qu'il faut trouver 2 occurrences : fofofo et fofofo

Cette erreur vient du fait que :

if (test == longueurS)
{
    printf ("Occurence trouvée en : %d\n", i + 1);
    test = 0;
    occurences++;
    i += longueurS - 1;
}

Voilà, dès que tu trouves la première occurence tu fais :i += 4 - 1 donc i = 3 .
Donc tu te trouves au caractère fofofo.
C'est normal donc que tu ne trouves pas la deuxième occurrence.

Je redonne mes solutions :
La première (Je pense qu'elle utilise l'algorithme de KMP mais je ne suis pas sûr) :

void findString(const char* str, const char* underStr)
{
    int i = 0, j = 0, back = 0, strike = 0, done = 0;
    for (i = 0 ; str[i] != '\0' ; i++)
    {
        if (str[i] == underStr[0])
	{
	    for (j = 1 ; underStr[j] != '\0' && !strike ; j++)
            {
	        if (str[i+j] == underStr[0] && !done)
		{
		    back = i+j;
		    done = 1;
	        }
		else if (str[i+j] != underStr[0] && !done)
		    back = i+j+1;

		if (str[i+j] != underStr[j])
		    strike = 1;
            }
            if (!strike)
	        printf("%d  ", i);
			
            i = back > i ? back-1 : i;
	}
	strike = 0;
        done = 0;
    }
}

La deuxième (La solution naïve) :

void findString(const char* str, const char* underStr)
{
    int i = 0, j = 0, strike = 0;
    for (i = 0 ; str[i] != '\0' ; i++)
    {
        if (str[i] == underStr[0])
	{
	    for (j = 1 ; underStr[j] != '\0' && !strike ; j++)
	    {
		if (str[i+j] != underStr[j])
	            strike = 1;
            }
            if (!strike)
                printf("%d  ", i);
	}
	strike = 0;
    }
}

RaSaN20

14 mai 2009 à 20:03:29

une bonne idée je participe

Tosh

14 mai 2009 à 23:03:00

Ah, merci HighTam.

J'ai édité mon code, mais du coup l'algorithme est moins performant.

zx-spectrum

19 mai 2009 à 10:21:53

Citation : HighTam

zx-spectrum ==>
for (j = i; j < i+len2 ; j++)
{
    if (chaine1[j]==chaine2[j-i]) trouve++;
    else
    {
        i=i+len2;
        /*break; equivalent pour i = i+ len2;*/
    }
}
Supposons quelen2 = 5
Au premier tour :i = j = 0
if (chaine1[j]==chaine2[j-i]) trouve++;
else
{
    i=i+len2;
    /*break; equivalent pour i = i+ len2;*/
}
Supposons quechaine1[0] != chaine2[0-0]
Donci = i + len2 = 0 + 5 = 5

On retourne toujours dans la boucle car :j < i+len2
Puis : if (chaine1[j]==chaine2[j-i]) trouve++;
Orj = 1 eti = 5
Donc on teste :if (chaine1[1]==chaine2[1-5])
chaine[-4] n'existe pas.

Enfin, quand j'exécute ton code, j'obtiens une erreur de violation d'accès. (A la ligne 33)

je piges pas que tu trouves une erreur dans mon code, je viens "de verifier à la main mon prog" je n'ai pas d'indice négatif :

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

int lenString ( char *chaine)
/*en entrée : une chaine de caractere nommé chaine*/
/*en sortie : donne le nombre de caractere de la chaine*/
/*traitement :calcule la longueur d'une chaine*/
{
    int len =0;
    while ( chaine[len] != '\0' )
    {
        len ++ ;
    }
    return len;
}

int occurence (char *chaine1, char *chaine2)
{
    int nb_occurence =0;/*pour compter les occurences*/
    int len1,len2;/*pour les longueurs de chaines à traiter*/
    int i=0,j=0;/*compteurs de boucle de boucle*/
    int trouve;/*la chaine est identique si trouve = len2*/
    len1 = lenString(chaine1);
    len2 = lenString(chaine2);
    int z = len1-len2+1;
    if (len2 !=0) /*dans le seul cas ou la chaine contient rien*/
    {
        i=0;
        while (i< z)
        {
            trouve = 0;
            for (j=i;j<i+len2;j++)
            {
                if ((j-i) !=0) printf("%d  ",j-i);/*ligne test j-i*/
                if (chaine1[j]==chaine2[j-i]) trouve++;
                else
                {
                  /* i=i+len2; */
                  break;
                }
            }

            if (trouve == len2)
            {
                nb_occurence ++ ;
                printf ("en position N.: %d\n",i+1);
            }

            i++;
        }
    }
    return nb_occurence;
}
int main(void)
{
    char chaine[]="ZxHello word ! Zx-Spectrum soluce, exercice may 2009. Easy soluce by Zx";
    char ch[]="soluce";

    printf("%s\n-->%s<--\n",chaine,ch);
    printf("nous avons %d occurence(s) trouvee(s)",occurence (chaine,ch));
    return 0;
}

Drủby♣B75

20 mai 2009 à 6:00:18

waa c'est pas mal de proposé des exercices comme ca , Dommage je suis au debut de la

2 partie des tuto a Matheo , mais je le ferait quand j'orai ratrapée mon retard

thx

HighTam

24 mai 2009 à 15:56:41

zx-spectrum ==>
Tu as remplacé ça :

Citation : HighTam

if (chaine1[j]==chaine2[j-i]) trouve++;
else
{
    i=i+len2;
    /*break; equivalent pour i = i+ len2;*/
}

Par ça :

Citation : zx-spectrum

if (chaine1[j]==chaine2[j-i]) trouve++;
else
{
    /* i=i+len2; */
    break;
}

C'est pourquoi, ça marche maintenant !
Apparemment, contrairement à ce que tu dis :break n'est pas équivalent ài=i+len2
(/*break; equivalent pour i = i+ len2;*/ )

Je teste avecbreak et ça marche.
Et je teste aveci = i+ len2 , j'obtiens :

zx-spectrum

24 mai 2009 à 20:20:42

Merci hightam, pour ton explication
effectivement tu avais raison
@+

Eusebus

29 mai 2009 à 20:30:43

Bonjour à tous.

Comme vous avez pu le constater, j'ai été assez absent du topic ce mois-ci, mais un déménagement ça prend du temps.

Donc, je vais déjà vous proposer une correction pour l'exercice que je vous avez soumis le mois dernier. Il y a eu pas mal de participations, c'est une bonne chose. Vous ne pourrez pas dire après que vous n'êtes pas à l'aise avec les chaînes de caractères en C (du moins je l'espère :-°

) ! Rappelez-vous, il s'agissait de trouver, dans une chaîne de caractères donnée, une certaine sous-chaîne (que j'appellerai pattern dans la suite). Il y avait plusieurs possibilités, la plupart d'entre-vous ont choisi de coder ce que j'avais appelé la méthode "naïve". En effet, c'est la manière la plus "naturelle" de traiter le problème.

Elle consiste simplement à comparer un à un les caractères du pattern avec le texte de départ. On commence bien sûr au début de la chaîne, et s'il y a une concordance, on le signale, sinon on passe à la position suivante en décalant d'un caractère la position de départ de comparaison. On recommence le tout jusqu'à ce qu'on ait exploré toutes les positions exploitables. Cet algo est assez gourmant, car si on note n la taille de la chaine et m celle du pattern, cet algo est en <math>\(O((n - m + 1)m)\)</math>. En voici une implémentation possible :

#include <stdio.h>

size_t my_strlen(const char *s);

int main(void)
{
        const char str[] = "foobarfofoobafoobarffoobfoo";
        const char pattern[] = "foo";
        size_t slen = my_strlen(str), plen = my_strlen(pattern), i, j;
        int find = 0;

        /* Parcours de la chaine */
        for(i = 0; i < slen - plen + 1; i++)
        {
                /* Parcours et comparaison du pattern */
                for(j = 0; j < plen && str[i + j] == pattern[j]; j++);

                if(j == plen)
                {
                        find = 1;
                        printf("Occurence en position %d\n", i + 1);
                }
        }

        if(!find)
                puts("Aucune occurence trouvee");

        return 0;

}

size_t my_strlen(const char *s)
{
        size_t i = 0;

        while(s[i] != '\0')
                i++;

        return i;
}

Je pense que le code est assez explicite, je vais juste expliquer la borne supérieure de i. Un petit schéma devrait suffir pour comprendre :

Exemple :

       v
FOOBARFOO
      BAR

Là on en est à la dernière position possible, simplement car à la position d'après (celle marquée par le v), notre pattern "dépasse" de la chaîne et on s'évite de traiter ces cas-là. Si vous observez bien, vous verrez qu'il y a taille("FOOBARFOO") - taille("FOO") + 1 solutions possibles (pour parler plus technique, c'est en fait l'application d'une petite formule qui donne le nombre d'entiers dans un intervalle entier [a,b] qui est b-a+1).

Alors, il est possible d'appliquer toutes sortes de petites optimisations, comme par exemple le fait de mémoriser la prochaine position en se basant sur le premier caractère (du pattern) si on le rencontre lors de notre parcours du pattern. Ce qui peut nous faire penser à la chose suivante : pour optimiser un peu notre recherche, il pourrait être bien d'utiliser les informations que l'on obtient lors d'un parcours du pattern, afin de s'affranchir de certaines positions dont on sait qu'elles ne pourront pas être valides. Un algorithme efficace que l'on peut trouver est celui de Knuth-Morris-Pratt (lien wiki), qui fait d'abord un pré-traitement du pattern (en <math>\(\theta(m)\)</math> )puis qui utilise ces infos pour progresser plus efficacement (on parcourt simplement la chaîne et on aura des sauts, opération en <math>\(\theta(n)\)</math>). On passe alors à une complexité en <math>\(\theta(n+m)\)</math> si l'on garde les notations précédemment utilisées ce qui est bien mieux que le cas précédent. Une seule personne a proposé un code pour cet algo (redskull, pour le citer), j'aurais pensé que plus de monde aurait tenté sa chance

.

Pour ceux qui veulent se frotter à cet algorithme (et je vous y encourage !), sachez qu'il n'est pas forcément évident à comprendre (ce qui explique surement pourquoi pratiquement personne ne s'y est aventuré ?), et j'avoue que vous l'expliquer serait assez long et je n'en ai malheureusement pas le temps, mais il est intéressant je trouve. Ca dépasse le cadre du vrai débutant, néanmoins je me permets d'en poster une implémentation. Je précise que je me suis grandement aidé du livre "Introduction à l'algorithmique" de Cormen, Leiserson, Rivest & Stein (souvent appelé "le Cormen" ou le "CLRS") ; excellent livre, de ce que j'en ai lu, mais qui demande de (très) bonnes bases en maths. Je propose donc cette implémentation :

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

int *prefix_fun(const char *s, const size_t len);
size_t my_strlen(const char *s);

int main(void)
{
        const char str[] = "foobarfofoobafoobarffoobfoo";
        const char pattern[] = "foo";
        size_t slen = my_strlen(str), plen = my_strlen(pattern),
            q = 0, find = 0, i;
        int *prefix = NULL; 

        /* q : nombres de caractères correspondants
         * prefix : tableau de prétraitement du pattern */

        prefix = prefix_fun(pattern, plen);

        if(prefix == NULL)
        {
                perror("malloc()");
                exit(EXIT_FAILURE);
        }

        printf("Chaine : %s\nPattern : %s\n", str, pattern);

        for(i = 0; i < slen; i++)
        {
                while(q > 0 && pattern[q] != str[i])
                        q = prefix[q - 1];

                if(pattern[q] == str[i])
                        q++;

                if(q == plen)
                {
                        printf("Occurence en position %d\n",
                                i + 2 - plen);
                        q = prefix[q - 1];
                        find = 1;
                }
        }

        if(!find)
                puts("Aucune occurence.");

        free(prefix);

        return 0;
}

size_t my_strlen(const char *s)
{
        size_t i = 0;

        while(s[i] != '\0')
                i++;

        return i;
}

/* Fonction de pré-traitement du pattern */

int *prefix_fun(const char *s, const size_t len)
{
        int *tab = malloc(len * sizeof *tab);
        size_t q, k = 0;

        if(tab != NULL)
        {
                tab[0] = 0;

                for(q = 1; q < len; q++)
                {
                        while(k > 0 && s[k] != s[q])
                                k = tab[k - 1];

                        if(s[k] == s[q])
                                k++;

                        tab[q] = k;
                }
        }

        return tab;
}

Voilà, merci à tous les participants, prochain exercice... dans pas longtemps (oui, je ne me mouille pas trop là, je sais. :p).

Anonyme

10 juin 2009 à 18:07:13

J'up pour demander quand viendra le nouvel exercice...Car ça fait fait déjà 2 semaines sans réponses.

shareman

10 juin 2009 à 18:27:23

Exercice du mois de Juin : < zBrace >

Après la longue et intéressante correction de l'exercice sur la recherche de sous-chaîne par Eusebus, je propose ici (un petit exo parce que j'ai du temps, surtout que c'est bientôt les vacances) un nouvel exercice intitulé zBrace. C'est avant tout un exercice qui demandera énormément de réflexion, en premier lieu au niveau algorithmique puis au niveau du codage même en C (mais c'est surmontable).

Objectif

L'idée de cet exercice peut se résumer en quelques mots : coder un algorithme qui vérifie qu'une expression est correctement parenthésée. Une expression désigne ici n'importe quoi, en réalité, tous les caractères sauf '(' et ')' peuvent être utilisés et ces deux derniers seront utilisés pour la représentation des parenthèses. Vous pouvez permettre à l'utilisateur de choisir les caractères de ses parenthèses (c'est plus pratique et plus générique) comme '[' ']' ou encore '{' '}'.

Voici un petit test qui devrait être facilement réalisable avec votre algorithme (d'où l'utilité de s'organiser, faites des fonctions ! (j'en profite)) :

()()(())
bien parenthésé
((()(
mal parenthésé !
)(
mal parenthésé
fmldkf(fmldk(flk)()fdmkf)(f)d
bien parenthésé
...

Sur ce coup (enfin je le dis, mais c'est pas nouveau), il faudra bien réfléchir et trouver un algorithme sûr ne permettant aucune "faille" (commencez de préférence avec papier + crayon). Le code en C doit être travaillé avant d'être posté ici, et pour qu'on comprenne facilement, par la sémantique, ce que vous essayez de faire, pensez à donner des noms explicites (mais ça, vous le faites naturellement hein :-°

).

Si vous ne l'avez pas encore remarqué, je le rappelle : vous pouvez désormais poster vos codes ici, permettant ainsi un système d'entraide plus "communautaire". Si vous avez besoin d'un ou deux tuyaux, vous pouvez également demander ici.

Bonne chance !

shareman

dldk-g

10 juin 2009 à 19:07:46

Ma solution (ne permet pas à l'utilisateur de choisir les caractères de ses parenthèses) :

/* Renvoie 1 si la chaîne est bien parenthésée
        0 sinon */
static int
bien_pth (const char *s)
{
  int nbPth = 0;

  while (*s != '\0')
    {
      if (*s == '(')
	nbPth++;
      else if (*s == ')')
	nbPth--;
      if (nbPth < 0)
	return 0;
      s++;
    }

  if (nbPth == 0)
    return 1;
  return 0;
}

Code entier pour les tests :

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

/* Renvoie 1 si la chaîne est bien parenthésée
           0 sinon */
static int
bien_pth (const char *s)
{
  int nbPth = 0;

  while (*s != '\0')
    {
      if (*s == '(')
	nbPth++;
      else if (*s == ')')
	nbPth--;
      if (nbPth < 0)
	return 0;
      s++;
    }

  if (nbPth == 0)
    return 1;
  return 0;
}

static void 
usage (const char *name)
{
  printf ("%s : << chaine >>\n", name);
  exit (EXIT_FAILURE);
}

int
main (int argc, char *argv[])
{
  if (argc != 2)
   usage (argv[0]);

  if (bien_pth (argv[1]) == 1)
    printf ("Oui\n");
  else
    printf ("Non\n");
     
  return EXIT_SUCCESS;
}

Varmin

10 juin 2009 à 19:19:38

Citation : ShareMan

C'est avant tout un exercice qui demandera énormément de réflexion, en premier lieu au niveau algorithmique puis au niveau du codage même en C (mais c'est surmontable).

Euh beaucoup de réflexion, beaucoup de réflexion... C'est un peu exagéré je trouve, car pour dire beaucoup de réflexion, il faudrait passer des heures dessus, alors que au niveau algorithmique, je dis 5 minutes au max (j'ai trouvé en peu de temps, mais je pense pas que ce sera le cas de tout le monde).
Je vais me lancer dans le code, peut être pour ce soir, cependant, je considérerais que l'entrée est formatée, comme sur france-ioi.
EDIT : (surtout que l'algo naif(je pense pas qu'il y en ait 50 000) est en O(N).)

EDIT2 : voici le code avec les tests

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

/**CONSTANTES DE L'ENNONCE**/
char expression[200];

void verifier(void)
{
   int differenceOuvranteFermante = 0;
   int i = 0;
   for(;expression[i] != '\0';i++)
	{
	   if(differenceOuvranteFermante < 0)
	   {
         printf("mal parenthese !\n");
         return;
	   }
	   if(expression[i] == '(')
	   {
	      differenceOuvranteFermante++;
	   }
	   else if(expression[i] == ')')
	   {
	      differenceOuvranteFermante--;
	   }
	}
	if(differenceOuvranteFermante == 0)
	{
	   printf("bien parenthese\n");
	   return;
	}
	printf("mal parenthese !\n");
}

int main(void)
{
   for(;;)
   {
      fgets(expression, 200, stdin);
      verifier();
   }
	return 0;
}

Et les fichiers tests

)(()( OK
)( OK
a OK
(()()())()(((()())())) OK
(()()())()(((()())()) OK
bonjour comment ça va () OK
me revoila (vraiment) OK
tu est sur (alors la)) OK
(((ex)emple)( ) )au(t())re) OK
(((ex)emple)( ) )au(t())re OK

EDIT3 : après avoir lu ton code, je viens de me rendre compte qu'il était basé sur exactement le même algorithme (sauf que j'affiche dans la fonction), bon ben cela me rassure ... Je vais me lancer dans une version permettant de choisir ses parenthèses.

EDIT4 : enfin fini, saletés de saisies non sécurisées ...

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

/**CONSTANTES DE L'ENNONCE**/
char expression[200];
char caracOuvrant;
char caracFermant;

void verifier(void)
{
   int differenceOuvranteFermante = 0;
   int i = 0;
   for(;expression[i] != '\0';i++)
	{
	   if(differenceOuvranteFermante < 0)
	   {
         printf("mal parenthese !\n");
         return;
	   }
	   if(expression[i] == caracOuvrant)
	   {
	      differenceOuvranteFermante++;
	   }
	   else if(expression[i] == caracFermant)
	   {
	      differenceOuvranteFermante--;
	   }
	}
	if(differenceOuvranteFermante == 0)
	{
	   printf("bien parenthese\n");
	   return;
	}
	printf("mal parenthese !\n");
}

int main(void)
{
   for(;;)
   {
      scanf("%c %c ", &caracOuvrant, &caracFermant);
      fgets(expression, 200, stdin);
      if(caracOuvrant == caracFermant)
      {
         printf("le caractere d'ouverture et de fermeture sont les memes\n");
      }
      else
      {
         verifier();
      }
   }
	return 0;
}

J'ai pas fait de fichiers tests, mais j'ai juste testé avec un mélange de tout, et les cas précédents en changeant les caractères. rajout d'une petite sécurité.

Eusebus

10 juin 2009 à 20:04:40

Plusieurs critiques :

- Utilisations de variables globales alors qu'il n'y a pas lieu (quelle utilité ?), c'est très moche à mon avis.
- Une boucle infinie dans le main, ça aussi c'est vraiment très moche (et tu en sors comment ?)
- Des noms de variables à rallonge qui nuisent à la lisibilité.

robocop

10 juin 2009 à 20:07:22

Jaloyan1 :
Il ne faut pas juste compter les parenthèses !
Sinon, tu valides aussi ")(", ce qui n'est pas le but.
Edit : ha non, ok, autant pour moi, tu vérifies bien que la somme n'est jamais négative.

Varmin

10 juin 2009 à 20:46:27

Citation : Eusebus

Plusieurs critiques :

- Utilisations de variables globales alors qu'il n'y a pas lieu (quelle utilité ?), c'est très moche à mon avis.

Les données fournies dans l'énoncé/entrée sont ,chez ma norme, toujours en variable globale, car ils sont constants tout au long du programme (j'appelle programme la partie qui suit la saisie les entrées).
Et surtout, cela permet de coder plus vite sans se casser la tête avec les pointeurs.
(Sans compter que si on maitrise vraiment, on a pas de problèmes avec).
Après le question de la beauté, je pense que c'est une notion subjective et donc on ne peut pas en juger. Personnellement, je trouve que bien codé, cela n'est pas particulièrement moche, pas plus que des conditions ternaires ou des pointeurs de pointeurs.

Citation : Eusebus

- Une boucle infinie dans le main, ça aussi c'est vraiment très moche (et tu en sors comment ?)

ctrl+c sous linux ou la croix sur windows.
J'ai suivi selon l'exemple de l'énoncé, il y a en aucun cas la précision de commande spécifique pour quitter, ou alors une entrée précisant le nombre de tours de boucle.
Donc l'idée de la boucle inifinie peut être envisageable.

Citation : Eusebus

- Des noms de variables à rallonge qui nuisent à la lisibilité.

Euh, je préfère avoir des noms de variables longs (c'est vrai que là j'aurais pu raccourcir, mais j'avais pas d'imagination), mais au moins tu perds pas 2 heures à déboguer, vu que dès le codage, sans compiler tu te rends compte de tes erreurs. Ce qui permet de coder plus rapidement encore (surtout que les noms de variables veulent quand même dire quelque chose).
Et surtout vive l'auto complétion de C::B (et aussi que si Mathias me voit à nommer des variables s, j,dif et ans, je risque de me faire taper sur les doigts)

Crehn

10 juin 2009 à 21:52:35

Bon voici ma version claire et propre:

#include <stdio.h>

int cb(char *s){int n=0;for(;*s;++s){if(*s==
'(')++n;if(*s==')')if(--n<0)break;}return n;}

int main(int argc, char **argv) {
    if(cb(argv[1])) {
        puts("Ok.");
    } else {
        puts("Damn.");
    }

    return 0;
}

EDIT: Hop, et encore plus petit! Fonction de 90 caractères.

Eusebus

10 juin 2009 à 22:03:27

Je maintiens que la boucle infinie est quand même à éviter très fortement si ça n'est pas dument justifié, ça ressemble surtout à du code torché à la va-vite parce que tu n'as pas daigné t'arrêter deux secondes sur quelques points, notamment une condition d'arrêt ou je ne sais quoi. D'ailleurs, on pouvait très bien s'en passer... Tu veux vraiment chipoter quand tu dis "c'est pas spécifié dans l'énoncé". C'est évident, quand même ; j'ai l'impression que tu fais de la mauvaise foi. Certaines choses coulent de source, et ça en fait partie (parce qu'avec ta façon de procéder, ton programme ne se termine pas normalement, même lorsqu'il a effectué correctement la tâche qui lui est confiée).

Je maintiens également que les globales sont à éviter aussi, leur utilisation peut parfois se justifier de manière agréable, mais là c'est clairement pas le cas. Encore de la faignantise ? Et quand je parle de "moche", je parle par rapports au usages du C, les "us et coutumes", ou encore les "bonnes pratiques" pour reprendre un terme de -ed-.

Pour info, sans variable globale et sans boucle infinie, ça m'a pris environ 5 minutes à coder lorsque Shareman a posté l'exo. Comme quoi ça ne prend pas tant de temps que ça de s'attarder à faire des trucs un peu plus clairs.

#include <stdio.h>

/* OK 0
 * KO 1 */

int check(const char *s);

int main(void)
{
        char str[BUFSIZ];

        fgets(str, sizeof str, stdin);
        str[BUFSIZ - 1] = '\0'; /* Sécurité pour la boucle for de check() */

        if(check(str) == 0)
                puts("Correct.");
        else
                puts("Incorrect.");

        return 0;
}

int check(const char *s)
{
        int cpt = 0, stop = 0;

        for(; *s && !stop; s++)
        {
                if(*s == '(')
                        cpt++;
                else if(*s == ')')
                        cpt--;
                if(cpt < 0)
                        stop = 1;
        }

        return cpt;
}

Edit : LOL Crehn. GG.

shareman

10 juin 2009 à 22:12:40

+1 Eusebus.

Et puis pour la "difficulté" dont je parle dans l'énoncé ... il faut se mettre à la place de celui qui débute vraiment en programmation. Je me rappelle il y a quelques années (quand j'ai commencé en programmation) que je n'arrivais pas à coder un algorithme qui trouve le maximum dans un tableau et maintenant j'ai du mal à croire à cette histoire (:-°). Alors si je me remets un peu dans l'ancienne situation, je vois parfaitement que ce genre d'exercices est en réalité un vrai casse-tête pour débutant. Si tu affirmes le contraire sans preuve, je vais le nier sans preuve (merci Eusebus ^^).

Varmin

10 juin 2009 à 22:42:34

Citation : Eusebus

Certaines choses coulent de source, et ça en fait partie (parce qu'avec ta façon de procéder, ton programme ne se termine pas normalement, même lorsqu'il a effectué correctement la tâche qui lui est confiée).

Ouai bon, on va pas se taper pour cela, je vais rajouter une condition d'arrêt. (personnellement, c'est le débogueur qui vient de me faire comprendre l'intérêt de la condition d'arrêt).

Citation : Eusebus

Je maintiens également que les globales sont à éviter aussi, leur utilisation peut parfois se justifier de manière agréable, mais là c'est clairement pas le cas. Encore de la faignantise ? Et quand je parle de "moche", je parle par rapports au usages du C, les "us et coutumes", ou encore les "bonnes pratiques" pour reprendre un terme de -ed-.

Citation : mateo21

Alors, comme les programmeurs sont de grosses feignasses (comment ça je l'ai déjà dit ?!

(c'est pas moi qui l'ai dit) ...

Harryzelmak

11 juin 2009 à 11:03:42

Citation : Eusebus

fgets(str, sizeof str, stdin);
str[BUFSIZ - 1] = '\0'; /* Sécurité pour la boucle for de check() */

Il est inutile d'ajouter soi-même le caractère nul à la fin de la chaîne, la fonction fgets le fait automatiquement.
(En plus, tu ne tiens pas compte du fait que la chaîne entrée ne va pas forcément remplir le tableau de BUFSIZ-1 caractères et que donc le caractère nul n'est pas forcément en fin de tableau)

Je ne vais pas proposer le code que j'ai réalisé parce qu'il est quasi identique à celui déjà proposé par Eusebus :-°

Eusebus

11 juin 2009 à 11:39:24

Ah oui, j'aurais du mieux RTFM, merci. (sinon effectivement il n'est pas en fin mais c'est juste en sécurité)

Anonyme

11 juin 2009 à 12:22:34

Voici mon code qui n'apporte pas grand chose d'original dans ceux déjà présentés

/* 11/07/09
By Monsieur_JaKy

But : vérifier si une expression est bien paranthésée

*/

#include <stdio.h>

static int check(const char* s)
{
    int occ = 0;
    while (*s != '\0')
    {
        if (*s == '(')
            occ++;
        else if (*s == ')')
            occ--;
        if (occ < 0)
            return 0;
        s++;
    }

    return occ == 0 ? 1 : 0;
}

int main()
{
    char s[50] = "";
    fgets(s, sizeof s, stdin);
    if (check(s) == 1)
        puts("Yes");
    else
        puts("No");

    return 0;
}

GurneyH

11 juin 2009 à 17:48:52

Bonjour à tous.

Je propose une version récursive...
Les test sont effectués dans la fonction main, selon une méthode piquée à -ed-.

#include <stdio.h>

#define NELEM(a) (sizeof(a) / sizeof(*a))

static char zBrassRec(char const *src, char open, char close, int lvl)
{
    /* Si on est à la fin de la chaîne et que le niveau d'imbrication courant
      * est nul, la chaîne est correctement parenthèsée.
      */
    if (*src == '\0')
        return !lvl ? 0 : -1;

    if (*src == open)
        lvl = zBrassRec(src + 1, open, close, lvl + 1);
    else if (*src == close)
        lvl = zBrassRec(src + 1, open, close, lvl - 1);
    else
        lvl = zBrassRec(src + 1, open, close, lvl);

    return lvl;
}



/* char zBrass(char const *src, int lvl)
 * src    : Chaîne dont on veut vérifier le parenthèsage.
 * open   : Caractère representant la parenthèse ouvrante.
 * close  : Caractère représentant la parenthèse fermante.
 * Retour : 0 si la chaîne est ok, -1 sinon.
 */

char zBrass(char const *src, char open, char close)
{
    return zBrassRec(src, open, close, 0);
}



int main(void)
{
    struct test
    {
        /* Index du test courant */
        int id;
        /* Chaîne testée */
        char s[32];
        /* type de parenthèse */
        char open, close;
        /* Résultat attendu */
        int res;
    };

    static const struct test a[] =
    {
        {1, "(",		'(', ')', -1},
        {2, "()",		'(', ')',  0},
        {3, ")",	        '(', ')', -1},
        {4, "int main(void)",	'(', ')',  0},
        {5, "[a]a[aaa())))]",	'[', ']',  0},
        {6, "a}",	        '{', '}', -1},
        {7, "int main(void){}", '{', '}',  0},
    };
    size_t i;
    int terr = 0;
    for (i = 0; i < NELEM(a) && !terr; ++i)
    {
        struct test const *const p = a + i;
        int res = zBrass(p->s, p->open, p->close);

        if (res != p->res)
        {
            printf("ERR at test %d\n", p->id);
            terr = 1;
        }
    }
    if (!terr)
    {
        puts("\nP A S S E D\n");
    }

    return 0;
}

La fonction zBrass, sert à masquer l'initialisation du niveau d'imbrication lors de l'appel de zBrassRec qui fait tout le travail.

char zBrass(char const *src, char open, char close)

exemple d'utilisation

printf("%d", zBrass("((un test !...))", '(', ')'));

a++
edit1 : problème de mise en forme.
edit2 code en secret, désolé...

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

Anonyme

11 juin 2009 à 17:53:37

Mets ta solution en secret !

Varmin

11 juin 2009 à 19:25:01

Gurneh j'ai une question, c'est pas mieux au niveau de

if (*src == '\0')
        return !lvl ? 0 : -1;

de faire plutôt

if (*src == '\0')
        return !!lvl;

J'attends ta réponse comme cela je pourrais moi aussi m'instruire et en savoir plus sur ceci.
Cordialement.

GurneyH

11 juin 2009 à 19:49:55

@Jaloyan1

Je n'emploie pas la combinaison d'opérateur !!, tu vas donc devoir attendre la réponse d'une personne plus compétente...
Tout ce que je peut te dire, c'est que j'ai choisi de renvoyer un valeur négative au cas où la chaîne est mal parenthésée... Avec !!, on ne renvoie dans tous les cas 0 ou 1...
Essaye, tu ne passes pas les tests...

a++

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

shareman

11 juin 2009 à 21:38:39

Bah au final, il suffit juste de choisir une valeur de retour pour chaque cas possible (deux ici). Gurney a choisi 0 et -1 mais avec 0 et 1, y'a pas de soucis non plus.

Jaloyan1, je ne vois pas vraiment en quoi ton alternative (qui, rigoureusement parlant, n'en est pas une puisqu'elle ne fait pas exactement la même chose) serait meilleure. Grossièrement, sauf quelconques optimisations du compilo, ta première version (celle provenant du code de Gurney) fait une "opération" (la condition) et ta seconde version en fait deux (opération "non" unaire appliquée deux fois). Mais au fond, je pense surtout que c'est profondément sans importance, surtout ici.

Varmin

12 juin 2009 à 8:00:34

Citation : ShareMan

Jaloyan1, je ne vois pas vraiment en quoi ton alternative (qui, rigoureusement parlant, n'en est pas une puisqu'elle ne fait pas exactement la même chose) serait meilleure. Grossièrement, sauf quelconques optimisations du compilo, ta première version (celle provenant du code de Gurney) fait une "opération" (la condition) et ta seconde version en fait deux (opération "non" unaire appliquée deux fois). Mais au fond, je pense surtout que c'est profondément sans importance, surtout ici.

Ben justement, je me demande si c'est meilleur, c'est pour cela que je l'ai posté.

Merci en tout cas.

HighTam

13 juin 2009 à 0:43:34

Salut à tous

Je vois que la plupart des solutions se ressemblent. La mienne aussi :

int brace(const char *str, const char start, const char end)
{
    int n = 0;
    for ( ; *str ; str++)
    {
        if (*str == start)
            n++;
        else if (*str == end)
            n--;
        if (n < 0)
            return 0;
    }
    return n == 0 ? 1 : 0;
}

A+ et au prochain exercice

Kushou

13 juin 2009 à 16:30:56

Bonjour,

Bon ben voilà une petite participation, mais je suis plutot mauvais en C (vous avez dit partout ?), donc mon code est surement moche. Pour pas faire une boucle comme tout le monde, et histoire qu'on ait de quoi discuter, j'ai décidé de faire ça en récurcif (tail-rec en plus %%). Donc le code est ici. On peut choisir les délimiteurs entre (), [] et {}, voilà. Le code est un peu plus long que celui des autres. Si j'avais réussi a faire fonctionner fflush, il auraut fait 42 lignes, c'est à souligner.

<< 1 ... 26 27 28 ... 55 >>

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

Exercice du mois de Juin : < zBrace >

Objectif

Supprimer

Modérer

Signaler le message aux modérateurs