Partage

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

<< 1 ... 29 30 31 ... 55 >>

20 juillet 2009 à 14:49:28

Correction de zBrace

Avec un petit retard que je vous demande d'excuser (faute de temps), je propose ici une petite correction pour l'exercice du mois de Juin (qui a largement débordé sur le mois de Juillet) : zBrace.

Je ne vais détailler ici que l'algorithme naïf, c'est à dire celui que quasiment tout le monde a proposé ici, l'algorithme qui utilise un compteur. Cet algorithme en soi est assez simple mais je ne dis pas qu'il était évident pour les débutants de le trouver. Il fallait quand même réfléchir un peu avant de se lancer.

L'idée, c'est d'utiliser un compteur initialisé à 0, qu'on incrémente dès qu'une parenthèse ouvrante a été trouvée et qu'on décrémente dès qu'une parenthèse fermante a été reconnue. Ensuite, il suffit de vérifier à chaque itération sur la chaîne d'entrée que le compteur n'est jamais strictement négatif (< 0). Ce test permet d'éviter de valider des expressions comme ")(". À la fin, on "switch" la valeur du compteur. Si elle vaut 0, l'expression est bien parenthésée, sinon, l'expression est syntaxiquement fausse au niveau des parenthèses.

Nous allons donc écrire une fonction (appelons-la "pth") qui prend en entrée une chaîne de caractères (const char*) et qui retourne 1 si l'expression est bien parenthésée, sinon 0 (mal parenthésée). Très simplement :

int pth(const char* s)
{
    int compt = 0;

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

    return (compt == 0) ? 1 : 0;
}

Et pour tester ça rapidement :

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

int pth(const char* s)
{
    int compt = 0;

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

    return (compt == 0) ? 1 : 0;
}

void eval(const char* s)
{
    if(pth(s)) printf("Ok");
    else printf("Non");
    putchar('\n');
}

int main()
{
    eval("blabla");
    eval("(bl(a)()bl)a");
    eval(")(");
    return 0;
}

Bientôt (dès ce soir en fait :-°) l'exercice du mois de Juillet - Août, organisé par Arthurus cette fois-ci (que je remercie au passage

).

shareman

Anonyme

20 juillet 2009 à 16:23:18

Ouai cool

Sinon à la fin de la fonction on peut simplement faire
return (compt == 0); sans rien d'autre après.
Ou alors on pourrait aussi mettre juste return !compt; mais c'est peut être moins lisible...

EDIT: Ah bah okok je comprend.

shareman

20 juillet 2009 à 16:24:27

Citation : 21

mais c'est peut être moins lisible...

C'est précisément pour ça que je n'ai pas voulu utiliser ces "raccourcis".

Kushou

20 juillet 2009 à 16:43:13

Citation : shareman

Citation : 21

mais c'est peut être moins lisible...

C'est précisément pour ça que je n'ai pas voulu utiliser ces "raccourcis".

Euh d'une part la forme ternaire c'est un truc super illisible, et d'autre part c'est une bonne habitude à prendre (le return !compt; ou return (compt == 0);). Si tu veux mettre un truc plus lisible (mais si ça l'est grandement), tu le mets en commentaire.

shareman

20 juillet 2009 à 16:53:54

Justement pas, la forme ternaire est ici très sémantique (elle traduit de manière transparente les explications que j'ai données). De toute façon, c'est vraiment sans importance ici. Je peux changer si vous aimez chipoter pour ça, ça m'est égal.

Arthurus

20 juillet 2009 à 17:03:08

Moi je pense qu'il faut peut être un moment donné passer le cap du "Oh non, le ternaire c'est illisible".

C'est très pratique, il a été inventé pour rendre le code compact (et non illisible).

Kushou

20 juillet 2009 à 17:18:19

Citation : Arthurus

Moi je pense qu'il faut peut être un moment donné passer le cap du "Oh non, le ternaire c'est illisible".

C'est très pratique, il a été inventé pour rendre le code compact (et non illisible).

Euh c'est illisible, même si c'est pratique.

Anonyme

20 juillet 2009 à 17:23:54

Nan mais il est vrai que le ternaire est moins lisible qu'un if else par exemple.
C'est plus compact et c'est cool, j'aime bien.

Dans le code plus haut, le ternaire est inutile, mais rend le code plus compréhensible.

Donc moi je pense que le mieux serait de mettre :
return !compt; /* On renvoie l'inverse de compt, si compt a une valeur autre que 0 on renvoie 0 sinon si compt est égal à 0 alors on renvoie 1 */

Et oui au lieu de modifier le code pour le rendre plus compréhensible on pourrait très bien le commenter, non ?

Ou alors faire des commentaires à part, en mentionnant le numéro de la ligne (car les commentaires des fois rendent le code illisible aussi ^^)

Kushou

20 juillet 2009 à 17:26:31

Citation : 21

Nan mais il est vrai que le ternaire est moins lisible qu'un if else par exemple.
C'est plus compact et c'est cool, j'aime bien.

Dans le code plus haut, le ternaire est inutile, mais rend le code plus compréhensible.

Donc moi je pense que le mieux serait de mettre :
return !compt; /* On renvoie l'inverse de compt, si compt a une valeur autre que 0 on renvoie 0 sinon si compt est égal à 0 alors on renvoie 1 */

Et oui au lieu de modifier le code pour le rendre plus compréhensible on pourrait très bien le commenter, non ?

Ou alors faire des commentaires à part, en mentionnant le numéro de la ligne (car les commentaires des fois rendent le code illisible aussi ^^)

On notera juste d'après ton commentaire que !0 = 0 = 1 :p.

bluestorm

20 juillet 2009 à 17:29:42

Et si vous arrêtiez de discuter sur ce topic, et alliez plutôt créer un autre topic sur la sémantique du retour de booléens en C ?

J'ai hésité à le faire moi-même il y a 5 posts, et ben j'aurais du, vous n'êtes pas capables de vous gérer vous-mêmes.

Kushou

20 juillet 2009 à 17:53:26

Citation : bluestorm

Et si vous arrêtiez de discuter sur ce topic, et alliez plutôt créer un autre topic sur la sémantique du retour de booléens en C ?

J'ai hésité à le faire moi-même il y a 5 posts, et ben j'aurais du, vous n'êtes pas capables de vous gérer vous-mêmes.

« Oui papa... »

Naimar_Jean

20 juillet 2009 à 19:04:43

Il y aura un exo de Juillet finalement ?

Kushou

20 juillet 2009 à 19:08:32

Citation : frager50

Il y aura un exo de Juillet finalement ?

Oui oui, c'est en préparation par arthurus

Naimar_Jean

20 juillet 2009 à 19:17:05

Nikel !

Arthurus

20 juillet 2009 à 19:27:47

Titre : zGrep
Mois : Juillet-Aout
Sujet : récupération des paramètres du main, algo sur les chaînes, manipulation de fichier, analyse séquentielle.

Enoncé

Le but de cet exercice est de pouvoir faire des recherches de chaînes dans des fichiers.
C'est à dire qu'on prendra un mot donné, et on testera s'il existe dans un fichier ou pas.
Nous donnerons le nombre d'occurrence de ce mot dans ce fichier.
Ainsi que la ligne et la colonne où se trouve chaque occurrence.

Illustration

Soit le fichier "texte.txt" suivant :

Bonjour,
Un jour un personnage nomme Arthurus a
propose un exercice pour traiter : les chaines, 
les fichiers, les argv[] ...
Enfin, esperons que ce ne sera pas trop dur pour les zeros.
Bon courage a tous, et bon codage ;)

On va chercher le mot "les" dans ce fichier en passant en paramètre le mot en question, et le nom du fichier :

./zGrep les texte.txt

Résultat :

Trouvé 4 fois.
Occurrence 1 -> ligne 3, colonne 36
Occurrence 2 -> ligne 4, colonne 1
Occurrence 3 -> ligne 4, colonne 15
Occurrence 4 -> ligne 5, colonne 50

Précisions et conventions :

On se fiera essentiellement aux fonctions ispunct(), isspace(), isalpha(), isalnum() de la lib ctype.h
Un séparateur est un caractère non alphanumérique.
Nous appellerons un mot : le plus grand ensemble de caractères alphanumériques concaténés.
Par exemple dans : "Bonjour, je suis un gros zéro."
"Bonjour" "je" "suis" "un" "gros" "zéro" sont des mots.
Donc dans notre exercice nous allons nous restreindre uniquement à la recherche de mot tel qu'on vient de le définir.
Une ligne est un ensemble de mot qui finit soit par '\n' soit par EOF.
Une colonne commence à 1 en début de ligne et s'incrémente à chaque caractère.
La colonne d'un mot est la colonne où se trouve son premier caractère.
Par exemple : Dans "Hello, World!", "World" se situe à la colonne 8.
Nous chercherons un seul et unique mot à la fois.
On ne prendra pas en compte la recherche de sous mots. Par exemple, dans la phrase : "Hello, World !", "llo" n'y appartient pas
On fera une recherche sensible à la casse.
C'est à dire que "Bonjour" et "bonjour" sont deux mots différents.
Pour récupérer les paramètres passés au programme, nous utiliserons : argv[].
Toutes les fonctions de la lib string.h et ctype.h (et toutes les autres libs) sont permises.
Le fait de considérer un caractère accentué comme séparateur ou pas est laissé au choix...
Aucune imposition sur ce détail

EDIT : Après mure réflexion, je supprime la grammaire, car ça pourrait faire peur aux zéros, et leur faire croire que l'exo est difficile.

Anonyme

20 juillet 2009 à 19:33:39

Encore des chaînes...
Bon, je me lance !

Anonyme

20 juillet 2009 à 19:57:18

J'ai pas compris le rapport avec argv[] quelqu'un peut m'expliquer ?

Citation : Arthurus

Pour récupérer les paramètres passés au programme, nous utiliserons : argv[].

Ça j'ai pas bien saisie le truc là

GuilOooo

20 juillet 2009 à 20:15:56

Citation : 21

J'ai pas compris le rapport avec argv[] quelqu'un peut m'expliquer ?

Citation : Arthurus

Pour récupérer les paramètres passés au programme, nous utiliserons : argv[].
Ça j'ai pas bien saisie le truc là

Un tutoriel en parle sur ce site. C'est une manière classique de passer des informations à un programme en console.

J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.

GurneyH

20 juillet 2009 à 20:20:44

Citation : GuilOooo

Citation : 21

J'ai pas compris le rapport avec argv[] quelqu'un peut m'expliquer ?

Citation : Arthurus

Pour récupérer les paramètres passés au programme, nous utiliserons : argv[].
Ça j'ai pas bien saisie le truc là

Un tutoriel en parle sur ce site. C'est une manière classique de passer des informations à un programme en console.

Je pense que la question de 21 était de savoir ce qu'on récupérait comme argument, pas la méthode...
Sans précision, je pense qu'il s'agit de la chaîne à rechercher et du chemin du fichier à analyser.
@Arthurus, c'est bien cà ? Et merci c'est sympa comme exercice...

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

Arthurus

20 juillet 2009 à 20:21:35

Oui, Je fais un edit.

rz0

20 juillet 2009 à 20:44:51

Pourquoi juste string.h ? Autoriser toute la lib standard paraît sain.

Arthurus

20 juillet 2009 à 20:48:58

Citation : rz0

Pourquoi juste string.h ? Autoriser toute la lib standard paraît sain.

Ouais... Mais je pense que c'est sous entendu qu'il n y a pas de contrainte... Je l'aurai dit sinon.

J'ai mentionné string.h histoire de donner une petite indication.

rz0

20 juillet 2009 à 20:51:35

Dans ce cas là, je pense que ce serait bien de conseiller ctype.h aussi, histoire de pas se faire chier avec les classes de caractères, ponctuation et autre.

Arthurus

20 juillet 2009 à 20:55:14

Citation : rz0

Dans ce cas là, je pense que ce serait bien de conseiller ctype.h aussi, histoire de pas se faire chier avec les classes de caractères, ponctuation et autre.

OK -> edit

Anonyme

21 juillet 2009 à 1:00:41

Si j'ai bien compris, si nous recherchons le mot "les" (comme dans l'exemple) alors dans la chaine "aalesaa" on ne doit pas le détecter, mais dans celle ci "_les." oui ?
Bon et sinon le problème c'est les caractères bien relou du genre 'û' et compagnie, on les prend on compte ou pas ?
Car le mot "les" sera trouvé dans la chaine "àlesî" ou pas.

Donc comment faire, il est normal de ne pas détecter la chaine "les" dans "àlesça" mais c'est pas normal de la rater dans "£les§" je pense.

Je dis ça car j'ai vérifié avec la lib ctype.h et la fonction (ou macro je sais pas) isalpha donne des choses un peu au hasard avec les ï et î Ö etc.

Donc doit on prendre en compte ces maudit caractères ?

Arthurus

21 juillet 2009 à 1:04:32

Citation : 21

Si j'ai bien compris, si nous recherchons le mot "les" (comme dans l'exemple) alors dans la chaine "aalesaa" on ne doit pas le détecter, mais dans celle ci "_les." oui ?
Bon et sinon le problème c'est les caractères bien relou du genre 'û' et compagnie, on les prend on compte ou pas ?
Car le mot "les" sera trouvé dans la chaine "àlesî".

Donc doit on prendre en compte ces maudit caractères ?

En fait ce détail j'ai volontairement pas voulu en parler, car je ne veux pas entrer dans le détail de la version d'ASCII utilisée.

Dans je laisse ce détail arbitraire...

Un accent par exemple est au choix soit séparateur soit non...

Je fais un edit pour cette précision

Al3xx

21 juillet 2009 à 1:05:21

Exercice intéressant, j'espère ne pas faire hurler la moitié des programmeurs du forum si jamais ils lisent le code que je ferai

J'ai néanmoins quelques petites questions.
Il est dit que les signes de ponctuation sont considérés comme des séparateurs. Quid des traits d'union et des mots composés ? Le trait d'union est-il considéré comme un séparateur ? Et pour une liste complète, peut-on considérer que tous les caractères hormis les chiffres et les lettres (majuscules, miniscules, accentuées ou non) sont des séparateurs ?

Aussi, question con, mais vu que l'organisateur de l'exercice du mois n'est pas le même que d'habitude, où envoyer nos codes ?

Merci pour les futures réponses

EDIT: semi-grilled :-°

RE-EDI : trois-quarts grilled là mais je maintiens le post pour les questions encore sans réponse.

Arthurus

21 juillet 2009 à 1:15:56

Bon d'accord...
Vu que tout le monde en parle, je suis contraint de faire un choix...
Le voici :
On se fiera essentiellement aux fonctions ispunct(), isspace(), isalpha(), isalnum() de la lib ctype.h
Comme ça on se met d'accord sur les conventions.

Pour plus de details cf :

http://www.siteduzero.com/forum-83-114 [...] ctions-c.html

Pour le code, postez le ici en secret

Al3xx

21 juillet 2009 à 2:41:29

Petite curiosité de ma part : quand prend fin l'exercice ?

Arthurus

21 juillet 2009 à 2:45:20

Citation : Al3xx