Partage

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

<< 1 ... 24 25 26 ... 55 >>

25 avril 2009 à 20:45:31

Titre : zStrsearch
Mois : mai 2009
Sujet : Chaines de caractères (encore !)

Bonjour à tous.

On va rester dans l'esprit de l'exercice précédent, et donc j'espère que vous aimez les chaînes de caractères; vous allez en rebouffer pour cet exercice-là !

Après avoir fait des statistiques, nous allons nous pencher sur un autre problème que l'on rencontre très fréquemment en informatique : la recherche d'une sous-chaine dans une chaine. Il existe une fonction dans la bibliothèque standard, strstr() , qui permet de faire ceci.

Je vous propose dans cet exercice donc de coder un programme qui s'en inspire. Il existe plusieurs algorithmes pour cela, certains moins naïfs et plus performants que d'autres. Ce que je vous propose, c'est d'essayer de coder cette fonction à votre manière en premier lieu, et ensuite vous pouvez partir à la pêche à l'algorithme sur le net, sachant que nous ne faisons pas un concours de l'algorithme le plus efficace ici. Que l'on parle de complexité, oui. Qu'on en fasse un point central de débat, non. Donc j'aimerais qu'on évite de dire "ouais mais cet algo est nul il est en O(n^2) alors que le mien est en O(n.lg(n))" (complexité prises au pif), le but est d'abord de faire un programme qui fonctionne, et après on peut s'attaquer à chercher une manière plus rapide/élégante de traiter le problème. Le but est de permettre à un maximum de personnes de participer, ensuite le niveau d'implication dépendra des personnes. Mais si vous vous investissez un minimum, vous aurez probablement envie de voir plus loin que la méthode naïve, et je vous y encourage vivement; il existe des algos tout à fait intéressants qui méritent qu'on s'y penche dessus.

Certains diront "oui mais il existe déjà des algos pour le faire, suffit de l'adapter en C". Je vous invite bien sûr à essayer d'implémenter des algorithmes moins triviaux - j'entends par "implémenter" comprendre l'algorithme et le retranscrire de manière propre et claire en C. C'est aussi un bon exercice pour voir si on a compris l'algorithme et si on est capable d'exploiter les possibilités du C pour faire tourner correctement l'algorithme. Tout ceci doit être fait à titre personnel, c'est pourquoi j'insiste sur le fait que même s'il y a des algorithmes déjà existants, il est intéressant d'en comprendre les mécanismes. On ne peut pas réinventer la roue à chaque fois, de temps en temps on peut bien s'appuyer sur une base existante.

Pour cet exercice, le choix de la méthode d'entrée de la chaîne à analyser est à votre convenance. La seule contrainte que j'impose est de ne pas utiliser de caractères accentués. Sinon, normalement il ne devrait pas y avoir de souci avec les minuscules/majuscules/ponctuations.

En ce qui concerne la sortie, votre programme devra retourner la première position TOUTES LES POSITIONS VALIDES dans la chaîne où votre pattern (ce que vous recherchez) apparait.

Exemple :
On recherche "foo" dans la chaîne "blafoobarblofoohaha".
Le programme devra retourner quelque chose du genre :

Occurences en position :
4, 13

Edit : sortie console

La mise en forme de la sortie est également à votre convenance. Le plus important est que vous retourniez la première position valide TOUTES LES POSITIONS VALIDES (de manière lisible, si possible

).

Dans le cas où il n'y a pas d'occurence trouvée, un simple message suffira :

Aucune occurence trouvée.

Pour éviter que des petits malins n'aient envie d'utiliser strcmp() ou toute autre fonction déjà existante (n'est-ce pas yno :-°

), on ne devra pas utiliser les fonctions de string.h .

Dernier point : l'envoi des réponses à "réponse" n'est désormais plus d'actualité - système de gestion un peu trop lourd, pas de possibilités d'avoir des commentaires d'autres codeurs... Vous êtes donc tous invités à poster votre code directement sur le topic, avec des balises secret. Toutefois "réponse" reste en fonction pour ceux qui auraient peur de poster en public. Je les y invite cependant car c'est toujours plus constructif d'avoir divers avis. J'en profite pour demander aux participants de faire un effort sur la lisibilité et la clarté de leur code, afin que nous n'ayions pas à décrypter ce que vous avez posté. C'est un effort salutaire autant pour les lecteurs que pour les posteurs.

Si vous voulez d'autres précisions, si vous avez des questions, n'hésitez pas.

Sur ce, bon courage et bon code !

EDIT : modification de l'objectif (cf majuscules en GRAS)

Yno

25 avril 2009 à 21:06:41

Une solution naïve :

#include <stdio.h>
#include <string.h>

size_t my_strstr (const char *text, const char *str)
{
    size_t n = 0;
    size_t len = strlen (str);
    while (strncmp (&text[n], str, len) != 0)
        n++;
    return n;
}

int main (void)
{
    char *text = "fobarfooOgaoyBarloOl";
    char *str = "foo";
    printf ("Premiere occurence a '%s' dans '%s' en position %u\n",
            str, text, my_strstr (text, str));
    return 0;
}

edit: onoes je suis spotted. Bon j'vais éditer ça. N'empêche Eusebus, tes éditions fourbes pour rajouter de la difficulté c'est mal.

Tiens en plus mon code est trop mauvais, la fonction ne s'arrête pas tant qu'une occurrence n'a pas été trouvée.

Eusebus

25 avril 2009 à 21:12:47

C'est ça de vouloir poster un code à tout prix juste après que j'ai tout juste posté l'énoncé... Soi-dit en passant c'est vrai qu'en les utilisant c'est beaucoup plus simple mais c'est moins ludique aussi. :-°

Edit : marre des erreurs de typo, ce soir. :pirate:

dldk-g

25 avril 2009 à 22:01:50

Ma participation (algorithme naïf):

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

#define NO_OCC -1

/* Recherche la première occurence de ct dans cs */
int naive_strstr (const char *cs, const char *ct)
{
    const char * const p = cs;
    const char * const t = ct;
    unsigned i;

    while (*cs)
    {
        for (ct = t, i = 0; *cs && *cs == *ct; cs++, ct++, i++)
        {
            if (!*(ct + 1))
                return cs - p - i + 1;
        }
        cs++;
    }

    return NO_OCC;
}


int main (void)
{
    const char* text = "fobfooOgaoyBarloOl";
    const char* str = "foo";
    int first_occ = naive_strstr(text, str);

    if (first_occ == NO_OCC)
        printf("Aucune occurence trouvee.\n");
    else
        printf("La premiere occurence se trouve en position %d.\n", first_occ);

    return EXIT_SUCCESS;
}

Yno

25 avril 2009 à 22:19:24

Plouf :

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

int do_nothing (int c)
{
    return c;
}

int strneq (const char *s1, const char *s2, size_t n, int case_sens)
{
    size_t i = 0;
    int (*fun)(int) = (case_sens ? do_nothing : tolower);
    while (i < n && s1[i] && s2[i]) {
        if (fun (s1[i]) != fun (s2[i]))
            return 0;           /* combo breaker */
        i++;
    }
    return (i == n ? 1 : 0);
}

size_t my_strlen (const char *str)
{
    size_t n = 0;
    while (str[n])
        n++;
    return n;
}

int my_strstr (const char *text, const char *str, int case_sens)
{
    size_t n = 0;
    size_t len = my_strlen (str);
    while (text[n]) {
        if (strneq (&text[n], str, len, case_sens))
            return n;           /* string spotted */
        n++;
    }
    return -1;                  /* fail */
}

int main (void)
{
    char *text = "fobarfoOOogaoyBarloOl";
    char *str = "foo";
    printf ("Premiere occurence a '%s' dans '%s' en position %d\n",
            str, text, my_strstr (text, str, 0));
    return 0;
}

Retour :

Premiere occurence a 'foO' dans 'fobarfoOOogaoyBarloOl' en position 5

Bonus : possibilité d'être case sensitive ou pas.
Mais à part ça c'est toujours le même algorithme.

edit: Hey vous avez vu ? Ma variable 'case_sens' est colorée n'importe comment !

zx-spectrum

25 avril 2009 à 22:35:40

Merci Eusebus, pour ce nouvel exo.

@+

IATGOF

25 avril 2009 à 22:56:49

Citation : Yno

edit: Hey vous avez vu ? Ma variable 'case_sens' est colorée n'importe comment !

Oui parfois la coloration syntaxique fail très fort. Essayes par exemple dans mettre un commentaire sur la même ligne qu'une directive de préprocesseur:

#include <stdio.h> /* ok mickey */

int main(void)
{
   puts("Ce programme ne sert à rien "
        "(sauf à faire planter la coloration syntaxique)");
   return 0;
}

Et sinon, la fonction do_nothing c'était vraiment histoire de montrer que tu sais faire un pointeur sur fonction... :-°

Yno

25 avril 2009 à 23:33:44

En vrai jl'ai fait pour ne pas dupliquer un morceau de code dans ma fonction, ici l'utilité réelle est minime, mais c'est un exemple simple d'usage courant des pointeurs de fonctions.

GurneyH

26 avril 2009 à 9:39:02

Salut,

Une autre version naïve...

#include <stdio.h>

int my_strcmp(const char *s1, const char *s2)
{
    int res;
    if (*s2)
    {
        while (*s1 && *s2 && *s1++ == *s2++);
        res = *(--s1) - *(--s2);
    }
    else
    {
        res = *s1 - *s2;
    }
    return res;
}





char *my_strstr(const char *haystack, const char *needle)
{
    int flag = 1;
    const char *res = NULL;
    const char *copy = haystack;

    while (*copy && flag)
    {
        flag = my_strcmp(copy, needle);
        copy++;
    }

    if (!flag)
    {
        res = --copy;
    }

    return (char *)res;
}


int zStrSearch(const char *haystack, const char *needle)
{
    const char *occ = haystack;
    int cpt = 0;

    while(occ)
    {
        occ = my_strstr(occ, needle);
        if (occ != NULL)
        {
            printf("Une occurence a la position %d\n", 1 + occ - haystack);
            occ++;
            cpt++;
        }
        else
        {
            if (!cpt)
            printf("Pas d'occurence.\n");
        }
    }
    return cpt;
}



int main(void)
{
    const char *meule = "blafoobarblofoohaha";
    const char *aiguille = "foo";

    printf("%d occurences trouvees\n", zStrSearch(meule, aiguille));

    return 0;
}

EDIT : correction du problème de la chaîne vide (dans my_strcmp)...J'avais un beau UB... :-°

Merci ZX!

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

Camp0us

26 avril 2009 à 16:10:22

Solution donnant le nombre d'occurences :

#include <stdio.h>

int main(void)
{
        const char ch_orig[] = "blafoobarblofoohaha",
                   ch_rech[] = "foo";

	size_t i = 0, j = 0,
               cpt = 0, nbre = 0,
               size = 0, length = 0;

	size = sizeof(ch_rech) / sizeof(*ch_rech) - 1;

	for(i = 0; ch_orig[i] != '\0'; i++, cpt++)
	{
		if(ch_orig[i] == ch_rech[j])
		{
			j++;
			length++;
			if(size == length)
			{
				printf("La %de occurence se trouve en position %d\n", nbre + 1, cpt - size + 2);
				nbre++;
			}
		}
		else
		{
			if(length != 0)
				i--, cpt--;

			j = 0;
			length = 0;
		}
	}
	if(0 == nbre)
		puts("Aucune occurence trouvee.");

	return 0;
}

redskull

26 avril 2009 à 22:01:20

Ma tentative:

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

int redskull_strstr(char s[], char r[]);
int redskull_strlen(char s[]);

int main(void)
{
        char chaineaanalyser[] = "chaine de test";
        char chainerecherche[] = "e tes";
        int premiereoccurence = 0;

        premiereoccurence = redskull_strstr(chaineaanalyser, chainerecherche) +1;

        if(premiereoccurence)
                printf("la première occurence se trouve en position %d\n", premiereoccurence);
        else
                printf("il n'y a aucune occurence de la chaine recherché\n");

        getchar();
        return 0;
}




int redskull_strstr(char s[], char r[])
{

        int tailles, tailler;
        int i, j, k;

        tailles = redskull_strlen(s);
        tailler = redskull_strlen(r);

        for(i=0; i<tailles;i++) {
                if(s[i] == r[0]) {
                        j=i;
                        k=0;
                        while(s[j]==r[k]) {
                                if(k == tailler - 1)
                                        return i;
                                j++;
                                k++;
                        }
                }
        }

        return -1;
}

int redskull_strlen(char s[])
{
        int i=0;
        while(s[i] !='\0')
                i++;

        return i;
}

glator

27 avril 2009 à 16:33:17

Ma version (naïve si j'ai bien compris

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

int main()
{
    char chaine[200] = "", rech[200] = "";
    int t_chaine = 0, t_rech = 0, i = 0, a = 1, nb = 0;

    puts("Chaine (sans accents): ");
    fgets(chaine, 200, stdin);
    puts("Mot a rechercher: ");
    fgets(rech, 200, stdin);

    while (chaine[t_chaine])
        t_chaine++;

    while (rech[t_rech])
        t_rech++;

    while (i <= t_chaine-t_rech+1)
    {
        if (chaine[i] == rech[0])
        {
            a = 1;
            while (chaine[i+a] == rech[a] && chaine[i+a] != '\0')
                a++;
            if (a == t_rech)
            {
                nb++;
                if(nb == 1)
                    puts("\nOccurences:");
                printf("%d ", i+1);
            }
        }
        i++;
    }
    printf("\n%d occurences.", nb);
    return 0;
}

Par contre je me demande si le temps gagné en ne testant pas les t_rech-1 derniers caractères n'est pas perdu en calculant t_rech et t_chaine (j'ai du mal a expliquer ca clairement)...

Elle affiche les occurrences et leur nombre, mais est case sensitive (d'ailleurs, comment ne pas l'être sans utiliser tolower()?).

EDIT: remplacement de gets par fgets

Eusebus

27 avril 2009 à 17:16:38

gets() detected

Citation : man gets - Section BOGUES

N’utilisez jamais gets(). Comme il est impossible de savoir à l’avance combien de caractères seront lus par gets(), et comme celui-ci écrira tous les caractères lus, même s’ils débordent du tampon, cette fonction est extrèmement dangereuse à utiliser. On a déjà utilisé ce dysfonctionnement pour créer des trous de sécurité. UTILISEZ TOUJOURS fgets() À LA PLACE DE gets().

VOTRE ATTENTION S'IL VOUS PLAIT

En ayant modifié l'objectif de l'exercice que je m'étais fait au départ, j'ai complètement modifié l'exercice qui est devenu assez trivial et qui a un intérêt limité. Je me suis donc permis de modifier l'énoncé et de le remettre dans la forme que je voulais, je demande à tous de le relire, et bien sûr de poster vos codes. Désolé pour le désagrément.

Et d'ailleurs l'énoncé reprend du sens parce qu'en effet, dans l'état où je l'avais posté il n'y avait pas 36000 manières de faire. Maintenant, le défi est plus intéressant je trouve. :pirate:

0xdeadc0de

27 avril 2009 à 20:40:15

Bon, jme lance :-°

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

void searchStr(const char *chaine, const char *chaineArechercher)
{
    int i = 0, j = 0, nbrOcc = 0, temp = 0, auMoins1Carac = 0;

    for( i = 0; chaine[i] != '\0'; i++)
    {
        if(chaine[i] == chaineArechercher[j])
        {
            j++;
            if(!auMoins1Carac)
            {
                auMoins1Carac = 1;
                temp = i;
            }

            if(chaineArechercher[j] == '\0')
            {
                nbrOcc++;
                printf("Occurence numero %d trouvee au caractere %d\n", nbrOcc, temp+1);
                j = 0;
                auMoins1Carac = 0;
            }
        }
        else
        {
            auMoins1Carac = 0;
            temp = 0;
            j = 0;
        }
    }

    if(!nbrOcc)
    {
        puts("Aucune occurence trouvee\n");
    }
}

int main(void)
{
    char chaine[] = "abcdfoo123mlkfoodbz";
    char chaineAtrouver[] = "foo";

    searchStr(chaine, chaineAtrouver);

    return EXIT_SUCCESS;
}

moustick1991

28 avril 2009 à 0:06:44

Je participe

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

int str_search(const char search [] ,const char str[]);
int main(int argc, char *argv[])
{
  char search[] = "foo" , in[] = "blafoobarblofoohaha",nb_occ;  
    
  if((nb_occ = str_search(search,in)) == 1)
     {printf("Desole , aucune occurence trouve\n");}
  else
     {printf("\nnombre d'occurences : %d\n",nb_occ);}     
  
  getch();	
  return 0;
}

int str_search(const char search [] ,const char str[])
{
     int i = 0 ,i2 = 0, taille = 0 , nb_occ = 1 ;
     
     while(search[taille] != '\0')
     {taille++;}
     
     if(taille)
     {
     while(str[i] != '\0')
     {
             if(search[i2] == str[i])
               {i2++;}
             else
               {i2 = 0;}  
             
             if(i2 == taille)
             {printf("occurence %d : pos%d\n",nb_occ,i-taille+2);
              i2 = 0 , nb_occ++;}
       i++;}
       }
    else 
    {nb_occ = 0;}

    return nb_occ;
}

HighTam

28 avril 2009 à 1:02:17

Ma solution :

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

Une petite explication de l'algorithme utilisé :
Prenons une chaîne "S": ABC ABCDAB ABCDABCDABDE
Avec la chaîne à rechercher "P" : ABCDABD

On commence la vérification :

v
ABC ABCDAB ABCDABCDABDE
ABCDABD
^

L'algorithme démarre en testant la correspondance des caractères les uns après les autres. Ainsi, à la quatrième étape, on a un espace en "S" et la lettre 'D' en "P", la correspondance n'est pas possible.

v
ABC ABCDAB ABCDABCDABDE
ABCDABD
   ^

Plutôt que de recommencer avec à la position 1 de "S", l'algorithme remarque qu'aucun 'A' n'est présent dans "S" entre les positions 1 et 3. En conséquence, pour avoir testé tous les caractères précédents, l'algorithme sait qu'il n'a aucune chance de trouver le début d'une correspondance s'il vérifie à nouveau. De ce fait, l'algorithme avance jusqu'au caractère suivant, avec la position 4 de "S" et la position 0 de "P"

----v
ABC ABCDAB ABCDABCDABDE
    ABCDABD
    ^

A cette étape, la vérification échoue parce qu'à la position 10 de "S" il y a un espace alors qu'il faut avoir la lettre 'D'. De même, au lieu de recommencer à la position 5 de "S" l'algorithme se souvient qu'il n'y a pas de 'A' jusqu'à la position 8 donc il démarre de le position 8 :

--------v
ABC ABCDAB ABCDABCDABDE
        ABCDABD
        ^

Déjà, entre la version montrée ci-dessus et cette version :

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

Il y a une différence :
- Si le nombre de boucle qu'effectue la deuxième est 25, le nombre de boucle qu'effectue la première est 11
(Pas dans tous les cas : J'ai testé pour le cas où : "S" = ABC ABCDAB ABCDABCDABDE et "P" = ABCDABD)

Je ne sais pas si c'est la bonne implémentation de l'algorithme. Corrigez-moi s'il y a des fautes

zx-spectrum

28 avril 2009 à 21:21:37

Bonjour, pour contribuer à ma façon à ce forum, voici ma solution :

#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);
    if (len2 !=0) /*dans le seul cas ou la chaine contient rien*/
    {
        for (i=0;i<(len1-len2)+1;i++)
        {
            trouve = 0;
            for (j=i;j<i+len2;j++)
            {
                if (chaine1[j]==chaine2[j-i]) trouve++;
            }

            if (trouve == len2)
            {
                nb_occurence ++ ;
                printf ("en position N.: %d\n",i+1);
            }
        }
    }
    return nb_occurence;
}
int main(void)
{
    char chaine[]="ZxHello word ! Zx-Spectrum soluce, exercice may 2009. Easy soluce by Zx";
    char ch[]="Z";

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

Ce qui me donne à l'execution :
exemple n°1 : ch <-- "Zx"

ZxHello word ! Zx-Spectrum soluce, exercice may 2009. Easy soluce by Zx
-->Z<--
en position N.: 1
en position N.: 16
en position N.: 70
nous avons 3 occurence(s) trouvee(s)
Process returned 0 (0x0)   execution time : 0.015 s
Press any key to continue.

exemple n°2 : ch <--""
La plus part de vos programmes ne traitent pas ce cas! Je sais faut être débile pour rechercher une chaine vide ! Mais si par exemple l'utilisateur se trompe dans la saisie, le résultat reste cohérent.

ZxHello word ! Zx-Spectrum soluce, exercice may 2009. Easy soluce by Zx
--><--
nous avons 0 occurence(s) trouvee(s)
Process returned 0 (0x0)   execution time : 0.218 s
Press any key to continue.

exemple n°3 : ch<--"soluce"

ZxHello word ! Zx-Spectrum soluce, exercice may 2009. Easy soluce by Zx
-->soluce<--
en position N.: 28
en position N.: 60
nous avons 2 occurence(s) trouvee(s)
Process returned 0 (0x0)   execution time : 0.218 s
Press any key to continue.

Ensuite j'ai privilégié la lisibilité Maximale du code : "pas de contraction" dans l'ecriture , pour un maximum de compréhension !
@+

moustick1991

29 avril 2009 à 0:15:22

Citation : zx-spectrum

La plus part de vos programmes ne traitent pas ce cas! Je sais faut être débile pour rechercher une chaine vide ! Mais si par exemple l'utilisateur se trompe dans la saisie, le résultat reste cohérent.

En effet !!!

Merci de le rappeler , code modifié en conséquence ...

HighTam

29 avril 2009 à 1:09:11

==> moustick1991, julax, Camp0us :
J'ai effectué un petit test avec vos solutions :

Chaîne initiale : "fofofolile"
Chaîne à rechercher : "fofolile"

Et le résultat que j'obtiens :

Aucune occurrence trouvee.

Même avec la première solution que j'ai proposé c'est la même chose :

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

Une petite explication (pour ma solution):

v
fofofolile
fofolile
^

On commence la vérification et on remarque qu'il n'y a pas correspondance à la position 4. Normalement, pendant la vérification, l'algorithme remarque qu'il y a un 'f' à la position 2 mais aussi il remarque de nouveau qu'il y a un 'f' à la position 4, donc, au lieu de recommencer la vérification de la position 2 il la recommence de la position 4, ce qui est faux.

----v
fofofolile
    fofolile
    ^

Donc, il faut remplacer ma première solution solution par celle ci :

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

Où utiliser la plus simple mais moins optimisée :

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

moustick1991

29 avril 2009 à 2:20:12

Ha oui !

Je n'avais pas prévu ça non plus (décidément je ne prévois pas grand chose ... :-°

) . Bon , je réessaye :

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

int str_search(const char search [] ,const char str[]);
int main(int argc, char *argv[])
{
  char search[] = "fofo" , in[] = "fofofolile",nb_occ;  
    
  if((nb_occ = str_search(search,in)) == 0)
     {printf("Desole , aucune occurence trouve\n");}
  else
     {printf("\nnombre d'occurences : %d\n",nb_occ);}     
  
  getch();	
  return 0;
}

int str_search(const char search [] ,const char str[])
{
     int i = 0 ,i2 = 0, taille = 0 , nb_occ = 0 ;
     
     while(search[taille] != '\0')
     {taille++;}
     
     if(taille)
     {
          while(str[i] != '\0')
          {
                 while(search[i2] == str[i+i2])
                              {
                                  if(i2 == taille-1)
                                  {printf("occurence %d : pos%d\n",nb_occ+1,i+1);        
                                   i2 = 0 , nb_occ++ ;
                                   break;}       
                               i2++; }
            i2 = 0;     
            i++;}
      
      }
      return nb_occ;
      }

ou tout simplement , la fonction de recherche :

int str_search(const char search [] ,const char str[])
{
     int i = 0 ,i2 = 0, taille = 0 , nb_occ = 0 ;
     
     while(search[taille] != '\0')
     {taille++;}
     
     if(taille)
     {
          while(str[i] != '\0')
          {
                 while(search[i2] == str[i+i2])
                              {
                                  if(i2 == taille-1)
                                  {printf("occurence %d : pos%d\n",nb_occ+1,i+1);        
                                   i2 = 0 , nb_occ++ ;
                                   break;}       
                               i2++; }
            i2 = 0;     
            i++;}
      
      }
      return nb_occ;
      }

GurneyH

29 avril 2009 à 4:06:43

Salut,

J'avais également ce problème de la chaîne à rechercher vide, j'ai édité mon code... Encore merci !

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

Miphys

29 avril 2009 à 11:37:45

Voilà ma solution :

#include <stdio.h>

#include <stdlib.h>


size_t zStrLen(char* str)
{
    int i = 0;
    while (str[i] != '\0')
    {
        i++;
    }
    return i;
}

int zCmpSubstr(char* str, int pos, char* pattern)
{
    int i = 0;
    size_t lenPattern = zStrLen(pattern);
    for (i = 0; i < lenPattern; i++)
    {
        if (str[pos+i] != pattern[i])
            return 0;
    }
    return 1;
}

void zStrSearch(char* str, char* pattern)
{
    int i = 0;
    size_t lenDiff = zStrLen(str) - zStrLen(pattern) + 1;
    for (i = 0; i < lenDiff; i++)
    {
        if (zCmpSubstr(str, i, pattern))
        {
            printf("%d ", i);
            fflush(stdout);
        }
    }
}


int main(void)

{
    char chaine[1000] = "";
    char motif[1000] = "";

    scanf("%1000s", chaine);
    scanf("%1000s", motif);
    zStrSearch(chaine, motif);
    printf("\n");

    return 0;

}

EDIT:
Et ma solution pour l'exercice zStrstat :

#include <stdio.h>

#include <stdlib.h>
#include <ctype.h>

void zCompte(char *str)
{
    int compte[27] = {0};
    int i = 0;
    char ch = 0;
    while (str[i] != '\0')
    {
        ch = tolower(str[i]);
        if (ch >= 97 && ch <= 122)
        {
            compte[ch-97]++;
        }
        i++;
    }
    for (i = 0; i < 26; i++)
    {
        if (compte[i] != 0)
        {
            printf("%c: %d\n", i+97, compte[i]);
        }
    }
}


int main(void)

{

    char str[1000] = "";
    scanf("%1000s", str);
    zCompte(str);

    return 0;

}

Yno

29 avril 2009 à 13:01:16

Non en fait rien.

Camp0us

29 avril 2009 à 16:38:08

"HighTam" -> Exact !
Je suis donc dans l'obligation de poster un autre code

(très peu optimisé mais très condensé) :

#include <stdio.h>

int main(void)
{
	const char ch_orig[] = "fofofolile",
	           ch_rech[] = "fofolile";

	size_t i = 0, j = 0,
	       trouve = 0,
	       size = 0, length = 0;

	size = sizeof(ch_rech) / sizeof(*ch_rech) - 1;

	for(i = 0; ch_orig[i] != '\0'; i++)
	{
		for(j = i; j < i + size; j++)
		{
			length = (ch_orig[j] == ch_rech[j - i]) ? length + 1 : 0;

			if(length == size) {
				printf("Occurence en position %d\n", j - size + 1);
				length = 0, trouve++;
			}
		}
	}
	if(!trouve) puts("Aucune occurence reperee");

	return 0;
}

moustick1991

29 avril 2009 à 20:06:46

@Camp0us : Si je peux me permettre deux remarques au sujet de ton code :

1 : Pour moi , le sizeof est une mauvaise idée pour calculer la taille de la chaine car imagine que l'utilisateur entre lui même sa chaine dans un tableau plus grand que la chaine .... :euh:

2 : (C'est aussi applicable à la première remarque) on est sensé re-coder une fonction utilisable par n'importe qui , ce que tu as fais n'est pas une fonction ... Ceci dit , le changement n'est pas énorme .

Bonne chance

Camp0us

29 avril 2009 à 20:41:42

Citation : moustick1991

1 : Pour moi , le sizeof est une mauvaise idée pour calculer la taille de la chaine car imagine que l'utilisateur entre lui même sa chaine dans un tableau plus grand que la chaine ....

Heureusement que dans mon cas on propose pas à l'utilisateur de saisir sa chaine...
De plus ça n'a aucun rapport, si tu utilises fgets() ou scanf() d'une manière sécurisée, ça n'a aucune chance d'arriver.
Et que tu utilises sizeof() ou pas, rentrer plus de caractères que ne peut en contenir ton tableau engendrera un depassement mémoire et donc le code sera mauvais.

Citation : moustick1991

2 : (C'est aussi applicable à la première remarque) on est sensé re-coder une fonction utilisable par n'importe qui , ce que tu as fais n'est pas une fonction ... Ceci dit , le changement n'est pas énorme .

#include <stdio.h>

void fonction(void)
{
	const char ch_orig[] = "fofofolile",
	           ch_rech[] = "fofolile";

	size_t i = 0, j = 0,
	       trouve = 0,
	       size = 0, length = 0;

	size = sizeof(ch_rech) / sizeof(*ch_rech) - 1;

	for(i = 0; ch_orig[i] != '\0'; i++)
	{
		for(j = i; j < i + size; j++)
		{
			length = (ch_orig[j] == ch_rech[j - i]) ? length + 1 : 0;

			if(length == size) {
				printf("Occurence en position %d\n", j - size + 1);
				length = 0, trouve++;
			}
		}
	}
	if(!trouve) puts("Aucune occurence reperee");

}

int main(void)
{
	fonction();

	return 0;
}

Content ?

Eusebus

29 avril 2009 à 21:05:05

Citation : moustick1991

2 : (C'est aussi applicable à la première remarque) on est sensé re-coder une fonction utilisable par n'importe qui , ce que tu as fais n'est pas une fonction ... Ceci dit , le changement n'est pas énorme .

Je n'ai jamais dit une telle chose, j'ai juste dit qu'il fallait coder un programme pour réaliser l'objectif. Si son choix est de ne pas utiliser de fonction... Il en a tout à fait le droit.

robocop

29 avril 2009 à 21:28:23

Camp0us > Essaye de ne pas mettre de fonctions d'I/O dans la fonction, cela fait des effets de bords qui n'ont rien à faire là.
Affiche le résultats avec des printf dans le main, après appel de la fonction.
C'est une bonne habitude à prendre de faire des fonctions un peu près pur, même dans un langage comme le c.

Bonne continuation.

Camp0us

29 avril 2009 à 21:31:54

Citation : robocop

Camp0us > fonctions d'I/O

Comprends pas ce terme.
Cette fonction c'était pour déconner hein...

x-spectrum

29 avril 2009 à 21:40:59

bonjour

Citation : robocop

Camp0us > Essaye de ne pas mettre de fonctions d'I/O dans la fonction, cela fait des effets de bords qui n'ont rien à faire là.
Affiche le résultats avec des printf dans le main, après appel de la fonction.
C'est une bonne habitude à prendre de faire des fonctions un peu près pur, même dans un langage comme le c.

Bonne continuation.

pour Campous : I/O : Input / Output

--> Robocop : pour quelles raisons si c'est le but recherché !
Pourquoi proscrire printf , scanf...dans les fonctions ? Pourquoi les employer uniquement dans le main ?
Peux tu me donner un exemple d'incohérence pour illustrer tes propos?
Merci
@+

<< 1 ... 24 25 26 ... 55 >>

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

Supprimer

Modérer

Signaler le message aux modérateurs