Partage

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

<< 1 ... 25 26 27 ... 55 >>

moustick1991

29 avril 2009 à 21:54:29

@Eusebus et Camp0us > Autant pour moi :lol:

Goost

30 avril 2009 à 1:24:55

Citation : x-spectrum

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

L'intérêt d'une fonction c'est justement.. d'avoir une fonction. En C tu peux découper ton code en fonction, chacune a donc une chose à faire, et mélanger dans une fonction algorithme et affichage ce n'est jamais bon, autant pour la maintenance que pour la rapidité d'exécution (il me semble qu'afficher les choses au fur et à mesure prend plus de temps que toutes en une fois).

Edit : par contre ne les employer que dans le main (), non plus. Je pense qu'il devrait y avoir une fonction spécifique qui gère l'affichage séparément du main () ou du reste d'ailleurs.

redskull

30 avril 2009 à 2:02:58

2 solutions pour ma part:
-une avec algorithme naif:

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

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

int main(void)
{
        char chaineaanalyser[] = "bla bla bla";
        char chainerecherche[] = "bla";
        int occurence[100] = {0};

	if(*chainerecherche)
		redskull_strstr(chaineaanalyser, chainerecherche, occurence);

        if(*occurence) {
                printf("l(es) occurence(s) se trouv(ent) en position:\n");
                int i;
                for (i=0; occurence[i]; i++)
                    printf("%d  ", occurence[i]);
        }
        else
                printf("il n'y a aucune occurence de la chaine recherché\n");

        getchar();
        return 0;
}




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

        int tailles, tailler;
        int i, j, k, l;
        l = 0;
        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){
                                        o[l] = i+1;
                                        l++;
                                }
                                j++;
                                k++;
                        }
                }
        }
}

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

        return i;
}

-une avec l'algorithme KMP:

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

int redskull_strlen(char s[]);
void kmp_tab(char r[], int t[], int l);
void kmp_recherche(char s[], char r[], int o[]);

int main(void)
{
        char chaineaanalyser[] = "bla bla bla";
        char chainerecherche[] = "bla";
        int occurence[100] = {0};
        if(*chainerecherche)
                kmp_recherche(chaineaanalyser, chainerecherche, occurence);
        if(*occurence) {
                printf("occurence(s) en position:\n");
                int i;
                for (i=0; occurence[i]; i++)
                        printf("%d  ", occurence[i]);
        }
        else
                printf("il n'y a aucune occurence de la chaine recherché\n");

        getchar();
        return 0;
}



int redskull_strlen(char s[]) //retourne la longueur de la chaine s
{
        int i=0;
        while(s[i] !='\0')
                i++;
        return i;
}

void kmp_recherche(char s[], char r[], int o[])  //recherche de la sous chaine
{

        int tailles, tailler;
        int t[100]= {0};
        int i, j, k, m;
        i = m = j =0;

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

        kmp_tab(r, t, tailler);

        while((m+i) != tailles) {
                if(s[m+i]==r[i]) {
                        i++;
                        if(i==tailler) {
                                o[j]=m+1;
                                k=t[i-1];
                                m = m+i-k;
                                i=k;
                                j++;
                        }
                }
                else if(i>0) {
                        k=t[i-1];
                        m = m+i-k;
                        i=k;
                }
                else {
                        k=-1;
                        m = m+i-k;
                }
        }

}

void kmp_tab(char r[], int t[], int l) //création du tableau des correspondance partielle
{
        int i, j;
        i=1;
        t[0] = j = 0;
        while(i!=l) {
                if(r[i]==r[j]) {
                        t[i] = j+1;
                        j++;
                        i++;
                }
                else if(j>0) {
                        j=t[j-1];
                }
                else {
                        t[i]=0;
                        i++;
                        j = 0;
                }
        }
}

P.s: je n'avais au départ pas prévu le cas de la chaine vide, je l'ai rajouté après le message de zx-spectrum

zx-spectrum

30 avril 2009 à 9:08:05

Merci redskull pour l'info algorithme kmp je connaissais pas !
--> je sais maintenant comment rendre plus performant mon algo "dit naif".
@+

Eusebus

30 avril 2009 à 11:08:48

C'était l'un des algos auxquels je pensais quand j'ai rédigé cet exo.

Mais sachez qu'il en existe encore d'autres. Avec un peu de recherche vous devriez en trouver au moins un.

Crehn

2 mai 2009 à 10:07:33

Voici ma solution (naïve ? je ne sais pas): (je n'ai pas encore regarde les réponses du topic)

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

#define    BUF_SIZE    16

size_t foo_strlen(const char *str);
void mult_strstr(size_t *hits, const char *s1, const char *s2);

size_t foo_strlen(const char *str) {
    size_t i = 0;
    for(i = 0; str[i] != '\0'; i++) {;}
    return i;
}

void mult_strstr(size_t *hits, const char *s1, const char *s2) {
    /* Init. */
    size_t i = 0;
    size_t j = 0;
    size_t cur_token = 0;
    size_t str_len = foo_strlen(s1);
    size_t token_len = foo_strlen(s2);
    
    /* Operate. */
    for(i = 0; i < str_len; ++i) {
        if(s1[i] == s2[j]) {
            ++j;
            if(j == token_len) {
                hits[cur_token] = i - j + 2;
                ++cur_token;
                j = 0;
            }
        } else {
            j = 0;
        }
    }
}

int main(void) {
    size_t i = 0;
    size_t hits[BUF_SIZE] = {0};
    mult_strstr(hits, "foolooolofoooloolofooooolooloflolfololfo", "foo");
    for(i = 0; hits[i] != 0; ++i) {
        printf("%u\n", hits[i]);
    }
    
    printf("\n%u occurence(s).\n", i);
    return EXIT_SUCCESS;
}

EDIT: Meh. L'algorithme ne fonctionne pas dans tous les cas apparemment, je corrigerai ça.

SpiritOfDoc

2 mai 2009 à 14:52:11

Bonjour,

J'ai fais un petit programme simple pour cette exercice sous FreeBSD (Je ne pense pas qu'il marchera sous Windows). Je donnerai également un lien vers un zip des sources, et un lien vers les sources, pour pouvoir les lire sans télécharger quoi que ce soit.

Pour l'utilisation du programme c'est assez simple:
./mai2009 "Un petit sapin est present dans les montagnes tandis qu'un lapin se cache dans son terrier" "es"
J'ai mi en place 2 algo, un bête et méchant et un deuxième un petit peu moins bête.
./mai2009 -algo 2 "Un petit sapin est present dans les montagnes tandis qu'un lapin se cache dans son terrier" "es"
Il y a aussi la possibilité d'ajouter un mode dit "Verbose" :
./mai2009 -v algo 1 "Un petit sapin est present dans les montagnes tandis qu'un lapin se cache dans son terrier" "es"
./mai2009 -v algo 2 "Un petit sapin est present dans les montagnes tandis qu'un lapin se cache dans son terrier" "es"

Pour le code en lui même, je vais présenter ma deuxième solution :

Si la chaine à match est "un", je commencerai à chercher un n. Par conséquent, il ne faut plus commencer à 0 dans la "longue" chaine, mais à l'indice du "n". Si jamais je trouve une correspondance du caractère "n", je regarde si la chaine à une correspondance à la première lettre de la chaine à match ("u") à l'indice correct (i - (strlen(s2) - 1)). Et si seulement cela correspond, je fais un my_strncmp. Sinon on continue a avancer. Cette "algo" permet simplement de limiter le nombre d'appelle à my_strncmp. Il part aussi du principe que l'on ne peut pas commencer à chercher le mot à matcher si l'indice de lecture est présent dans un mot qui match dejà, et donc il fait les sauts d'indice en conséquence.

void	my_basicup(const char	*s1,
		   const char	*s2,
		   const int	v)
{
  int	len_s2 = my_strlen(s2) - 1;
  int	len_s1 = my_strlen(s1) - 1;
  int	i = len_s2 - 1;

  while (s1[++i])
    if ((i - len_s2) > len_s1 - len_s2)
      return ;
    else if (s1[i] == s2[len_s2] && s1[i - len_s2] == s2[0])
    {
     if (!my_strncmp(&s1[i - len_s2], s2, len_s2 + 1))
      {
	print_result(i - len_s2);
        i += len_s2;
	if ((i - len_s2) > len_s1 - len_s2)
	  return ;
      }
    }
}

Pour avoir accès aux fichiers des sources : fichier source
Pour avoir accès à un zip des sources : fichier zip

P.s: J'ai décidé d'afficher {null} comme réponse à la non solution. Or ./bin "[...]" "" devrait matcher. Mais on ne sait pas dans quel cas il doit réellement match, j'ai décidé qu'il équivaudrait à une non solution. (Il n'y a aucun intérêt à chercher une chaine vide dans une chaine)

[EDIT]: lien down

coco2154

3 mai 2009 à 14:10:04

Bonjour
j'ai un problème au moment de compiler et exécuter . Il me dit que le programme est introuvable . J'ai essayer de recommencer mais il me dit toujours la meme chose .
Aidez moi svp

shareman

3 mai 2009 à 15:04:36

Bonjour,

Pour ce genre de problèmes qui ne concerne pas directement les exercices proposés ici, ouvre un nouveau topic sur le forum C, cela évitera de faire un hors-sujet et tu auras certainement plus d'aide.

ShareMan

zx-spectrum

3 mai 2009 à 19:23:41

Bonjour,
j'ai pas teste ton code spiritofdoc mais quand je vois ceci :

void	my_basicup(const char	*s1,
		   const char	*s2,
		   const int	v)
{
  int	len_s2 = my_strlen(s2) - 1;
  int	len_s1 = my_strlen(s1) - 1;
  int	i = len_s2 - 1;

  while (s1[++i])
    if ((i - len_s2) > len_s1 - len_s2)
      return ;
    else if (s1[i] == s2[len_s2] && s1[i - len_s2] == s2[0])
    {
     if (!my_strncmp(&s1[i - len_s2], s2, len_s2 + 1))
      {
	print_result(i - len_s2);
        i += len_s2;
	if ((i - len_s2) > len_s1 - len_s2)
	  return ;
      }
    }
}

a savoir deux "return" dans une fonction c'est pas une bonne pratique (je sais c'est un vieux débat !). Techniquement en C, c'est vrai c'est possible (pas forcément dans d'autres langages). Il vaut mieux rester sur le principe suivant :

un seul point d'entree 
un traitement à effectuer
un seul point de sortie

Ensuite une fonction de type void, je suis quand même étonné de voir un return !
@+

0xdeadc0de

3 mai 2009 à 22:39:45

Bon, et bien repostage de code après la remarque de HighTam

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

void searchStr(const char *chaine, const char *chaineArechercher)
{
    int y = 0, a = 0;
    int position = 0, nbrOcc = 0;

    for (y = 0; chaine[y] != '\0'; y++)
    {
        if (chaine[y] == chaineArechercher[0])
        {
            position = y+1;
            for (a = 1; chaineArechercher[a] != '\0'; a++)
            {
                if (chaineArechercher[a] != chaine[y+a])
                {
                    position = 0;
                    break;
                }
            }

        }

        if (position)
        {
            nbrOcc++;
            printf("Occurence trouvee au caractere %d\n", position);
        }
        position = 0;
    }

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

int main(void)
{
    char chaine[] = "bcdefklabcdlmbcd";
    char chaineAtrouver[] = "abcd";

    searchStr(chaine, chaineAtrouver);

    return EXIT_SUCCESS;
}

moustick1991

3 mai 2009 à 23:04:42

J'attends l'exo suivant avec impatience :lol:

.

Merci au(x) personnes qui ont créées et maintenus le post .

Camp0us

4 mai 2009 à 15:58:45

Citation : zx-spectrum

Ensuite une fonction de type void, je suis quand même étonné de voir un return !

Baf ça sert à sortir de ta fonction de la même façon qu'un break sert à sortir d'une boucle...

Citation : zx-spectrum

a savoir deux "return" dans une fonction c'est pas une bonne pratique

Je suis daccord mais c'est quand même un peu le genre de conseil que l'on donne aux débutants pour qu'ils évitent de s'embrouiller. Quand on à une certaine maîtrise du langage on peut oublier s'écarter un peu de cette pratique (sans pour autant la négliger).

zx-spectrum

4 mai 2009 à 20:26:08

bonjour

Citation : Camp0us

Citation : zx-spectrum

Ensuite une fonction de type void, je suis quand même étonné de voir un return !

Baf ça sert à sortir de ta fonction de la même façon qu'un break sert à sortir d'une boucle...
Citation : zx-spectrum

a savoir deux "return" dans une fonction c'est pas une bonne pratique

Je suis daccord mais c'est quand même un peu le genre de conseil que l'on donne aux débutants pour qu'ils évitent de s'embrouiller. Quand on à une certaine maîtrise du langage on peut oublier s'écarter un peu de cette pratique (sans pour autant la négliger).

C'est bien pour cela que je conteste ces deux procédés à savoir :
une boucle , un sous programme, obligatoirement pour une question de lisibilité de tes programmes, de bonnes pratiques à prendre, pour maintenir correctement dans le temps tes programmes, pour ceux qui commencent la programmation (ou expert), pour pouvoir traduire tes programmes dans un autre langage,.......
s'organiser de la façon suivante :

un seul point d' entrée
-->un traitement à effectuer
un et un seul point de sortie

J'invente rien de nouveau ! Ce n'est pas parce que C accepte des "instructions de saut" ( goto, break pour les boucles (tres tres tres tres mauvais !)) qu'il faut s'en servir. Ceci est mon argumentation. Elle vaut ce qu'elle vaut. Je veux bien changer d'avis si tu me démontres concrètement avec un exemple clé en main !
Par contre, je peux te prouver que tu peux t'en passer....C'est un vieux débat déjà débattu dans les anées 80........Et j'ai opté pour le clan de la lutte contre l'abus des instructions de saut

. Cela parait plus difficile au début de s'en priver, mais un gain de temps dans ton organisation future.
@+

Camp0us

4 mai 2009 à 21:18:01

Citation : zx-spectrum

Ce n'est pas parce que C accepte des "instructions de saut" ( goto, break pour les boucles (tres tres tres tres mauvais !)) qu'il faut s'en servir. Ceci est mon argumentation. Elle vaut ce qu'elle vaut.

C'est pas ce que tu défends qui est criticable, c'est le point de vue que tu y apportes.
Comment peux-tu juger qu'utiliser un break dans une boucle est "tres tres tres tres mauvais" ?!
Tu as fait un programme un jour et celui-ci comportait une erreur inexiplicable qui après de longues heures de reflexions ton amenées à decouvrir que tout était la faute du pauvre break, qui placé dans une boucle engendrait un comportement indeterminé !
Bref defendre tes opinions quand à certaines spécificité du langage C comme tu le fais est honorable mais pour ma part je n'en serais pas convaincu tant que je ne serais pas confronté à un cas du type cité plus haut. De plus je suis sûr que même un goto utilisé par un guru du C peut être bien employé.
Ces préjugés préfabriqués ne mène à rien...

Citation : zx-spectrum

Je veux bien changer d'avis si tu me démontres concrètement avec un exemple clé en main !

Ok, si tu me démontres qu'utiliser un break dans une boucle ou plusieurs return dans une fonction est catastropique :-°

(et je suis prêt à accepter que c'est si mauvais

)

bluestorm

5 mai 2009 à 11:38:01

zx-spectrum : et comment tu fais, sans opérateur ternaire de condition et en conservant la récursivité (il ne s'agit pas de changer de fonction), pour quelque chose comme cela :

int fact(int n)
{
   if (n == 1)
     return 1;
   else return n * fac(n-1);
}

glator

5 mai 2009 à 12:52:47

Citation : bluestorm

zx-spectrum : et comment tu fais, sans opérateur ternaire de condition et en conservant la récursivité (il ne s'agit pas de changer de fonction), pour quelque chose comme cela :
int fact(int n)
{
   if (n == 1)
     return 1;
   else return n * fac(n-1);
}
?

int fact(int n)
{
   int r;
   if (n == 1)
     r = 1;
   else 
     r = n * fac(n-1);
   return r;
}

Selon la logique "une seule sortie" c'est la bonne facon de faire. Mais en pratique on crée une variable à chaque appel de la fonction, ce qui est quand même cher payé pour satisfaire une bonne habitude...

zx-spectrum

5 mai 2009 à 13:00:53

Citation : glator

Selon la logique "une seule sortie" c'est la bonne facon de faire. Mais en pratique on crée une variable à chaque appel de la fonction, ce qui est quand même cher payé pour satisfaire une bonne habitude...

Merci de repondre pour moi, j'aurais pas fait mieux!
Ensuite je commence à peine à entrevoir pourquoi je vois plusieurs "return" dans une fonction, pour n'avoir jamais pris ce genre d'habitude!
@+

Goost

5 mai 2009 à 18:29:41

Mettre plusieurs return n'est pas mauvais, c'est comme tout, utilisés modérément et surtout si c'est maitrisé, ça va. Le problème se pose pour ceux qui en mettent partout à tord et à travers alors que ce n'est pas justifié.
Mais je pense que ce n'est pas l'endroit pour débattre de cela

dldk-g

5 mai 2009 à 18:43:08

Plusieurs return c'est surtout déconseillé pour les fonctions dans lesquelles on alloue et libère de la mémoire : un return mal placé et la mémoire n'est pas libéré.
Pour des petites fonctions comme bluestorm a montré c'est même mieux car on ne déclare pas de variable (c'est totalement négligeable mais bon

shareman

5 mai 2009 à 19:14:03

Je ne vois vraiment pas le problème au fait d'utiliser plusieurs return. À partir du moment où il y a une logique, ce n'est vraiment pas la peine de s'encombrer à n'utiliser qu'un return. Mais comme cela a été évoqué, il est très déconseillé de le faire quand on ne le maîtrise pas (libération de mémoire oubliée ? etc.). Cette règle s'applique en fait pour énormément d'autres concepts, voilà pourquoi, zx-spectrum, je ne comprends pas pourquoi tu sembles insister si fortement sur cette manière de coder. Je pense même que plutôt que de vouloir respecter à la lettre les règles de ce type, il faudrait avant tout produire un code logique et sémantiquement parlant.

zx-spectrum

5 mai 2009 à 23:37:53

Citation : shareMan

Cette règle s'applique en fait pour énormément d'autres concepts, voilà pourquoi, zx-spectrum, je ne comprends pas pourquoi tu sembles insister si fortement sur cette manière de coder. Je pense même que plutôt que de vouloir respecter à la lettre les règles de ce type, il faudrait avant tout produire un code logique et sémantiquement parlant.

c'est dommage que tu n'ai pas répondu sur le topic que j'ai ouvert sur ce sujet, pour eviter de polluer ce forum !

C'est justement ce que je veux savoir "s'applique à d'autres concepts" : lesquels ?

Ensuite je veux simplement "ébranler" le fait que j'ai appris la programmation comme cela il y a 20 ans à savoir : aucune utilisation "d'instructions de jump" quand on utilise un langage avec "des structures de controles complexes" qui ont un cadre de definition établis depuis bien longtemps ! Jeter un oeil sur wikipédia rubrique structure de controle, j'invente rien !

Ensuite dans tous les codes que j'ai fourni ai je produit un seul code non logique, et sémantiquement non parlant ? Il serait alors judicieux de m'en faire part ?

Tosh

7 mai 2009 à 16:43:54

Première fois que je participe à un exercice, donc vous moquez pas de mon code

(j'ai utilisé une fonction de string.h, j'espère qu'on avait le droit)

Algorythme naïf :

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

int
my_len (char *chaine)
{
  char cara = 1;
  int longueur = 0;
  while (cara != '\0')
    {
      cara = chaine[longueur];
      longueur++;
    }
  longueur--;
  return longueur;
}

int
zStrsearch (char *sousChaine, char *chaine)
{
  int longueurS = 0, longueurC = 0, occurences = 0, test = 0, calcule = 0;
  longueurS = my_len (sousChaine);
  longueurC = my_len (chaine);


  for (int i = 0; i < longueurC; i++)
    {
      for (int j = 0; j < longueurS; j++)
	{
	  calcule++;
	  if (sousChaine[j] == chaine[i + j])
	    {
	      test++;
	    }
	  else
	    {
	      test = 0;
	      j += longueurS;
	    }
	}
      if (test == longueurS)
	{
	  printf ("Occurence trouvée en : %d\n", i + 1);
	  test = 0;
	  occurences++;
	}
    }
  printf ("Caractères lus : %d\n", calcule);
  return occurences;
}

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


  return 0;
}

sortie :

Occurence trouvée en : 1
Occurence trouvée en : 3
Occurence trouvée en : 11
Occurence trouvée en : 13
Caractères lus : 28
Occurences trouvées : 4

Miphys

7 mai 2009 à 18:23:49

Citation : Tosh

Première fois que je participe à un exercice, donc vous moquez pas de mon code (j'ai utilisé une fonction de string.h, j'espère qu'on avait le droit)

Algorythme naïf :

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

int
zStrsearch (char *sousChaine, char *chaine)
{
  int longueurS = 0, longueurC = 0, occurences = 0;
  char cara = 1;

  while (cara != '\0')
    {

      cara = sousChaine[longueurS];
      longueurS++;
    }
  longueurS--;
  cara = 1;
  while (cara != '\0')
    {
      cara = chaine[longueurC];
      longueurC++;
    }
  longueurC--;
  for (int i = 0; i < (longueurC - longueurS)+1; i++)
    {
      char *S = NULL;
      S = (char *) malloc ((longueurS - 1) * sizeof (char));
      if (S == NULL)
	{
	  exit (0);
	}
      for (int j = 0; j < longueurS; j++)
	{
	  S[j] = chaine[i + j];
	}
      if (strcmp (S, sousChaine) == 0)
	{
	  occurences++;
	  printf ("Occurence n°%d trouvée en : %d\n", occurences, i + 1);
	}

      free (S);
    }
  return occurences;
}

int
main (void)
{

  char sousChaine[] = "jah";
  char chaine[] = "injahwetrustjahisall";
  printf ("Occurences trouvées : %d\n", zStrsearch (sousChaine, chaine));


  return 0;

}

Pour améliorer ton code, la première chose à faire est de le découper en fonctions. Il n'en sera que plus lisible.

HighTam

7 mai 2009 à 20:25:57

Citation : Tosh

(j'ai utilisé une fonction de string.h, j'espère qu'on avait le droit)

Citation : Eusebus

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 .

Tosh

7 mai 2009 à 20:51:10

Voilà, j'ai édité mon code :-°

.
J'ai enlevé la fonction de string.h, et j'ai fais une fonction pour mesurer la taille des chaines pour plus de clarté.

Je vais essayer d'optimiser un peu mon code (notamment regarder si il n'y pas des conditions inutiles).

Je suis toujours preneur en conseils.

Eusebus

8 mai 2009 à 15:49:37

Et sinon, personne n'est motivé pour coder autre chose que la manière naïve ?

Je n'ai vu qu'une seule tentative pour implémenter l'algo KMP, ça pourrait être intéressant de voir si d'autres personnes y arrivent.

Tosh

8 mai 2009 à 16:01:26

Mon algorithme ne compare qu'une seule fois chaque caractère de la chaine principale, je ne sais pas si c'est l'algo KMP. (je ne sais pas trop comment se code un algorithme...)

En gros, pour une chaine de 30 caractères, il fera 30 tours de boucle. (alors que l'ancien, faisait 30*(longueur de la sous chaine)

zx-spectrum

9 mai 2009 à 0:03:34

bonjour,
donc une solution avec l'algorithme de KMP :

#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*/
    {
        i=0;
        while (i< (len1-len2)+1)
        {
            trouve = 0;
            for (j=i;j<i+len2;j++)
            {
                if (chaine1[j]==chaine2[j-i]) trouve++;
                else
                {
                  i=i+len2;
                  /*break; equivalent pour i = i+ len2;*/
                }
            }

            if (trouve == len2)
            {
                nb_occurence ++ ;
                printf ("en position N.: %d\n",i+1);
                i = i+len2;
            }
            else
              {
                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;
}

remarque : en voyant ton code redskull je suis pas sur que ma solution soit celle de KMP ?

ensuite sur wikipedia il existe :
algo d'aho corasik

algo de boyer moore

Nota bene : et non j'ai toujours ma solution naive remaniée !

#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 (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 = i+len2;
            }
            else
              {
                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;
}

GurneyH

9 mai 2009 à 8:34:07

Salut,

Une autre version, avec l'algorithme Boyer-Moore simple.
Le principe consiste à précalculer les déplacement à effectuer dans la chaîne(haystack) lorsqu'il n'y a pas d'occurrence de la sous_chaîne(needle) à la position courante.

/* Algorithme de Boyer-Moore simple*/
#include <stdio.h>
#include <limits.h>

/* retourne la longueur d'une chaîne caractères */
static size_t my_strlen(char const *src)
{
    char const *cpy = src;
    while (*cpy++);

    return --cpy - src;
}


char *my_strstr(char const *haystack, char const *needle)
{
    char *res = NULL;
    int tab[UCHAR_MAX + 1];
    int i;
    int nLen = my_strlen(needle);
    int hLen = my_strlen(haystack);
    if (nLen && hLen)
    {
        for (i = 0; i < UCHAR_MAX + 1; i++)
            tab[i] = nLen;
        for (i = 0; i < nLen - 1; ++i)
            tab[(size_t)needle[i]] = nLen - 1 - i;

        while (hLen >= nLen && !res)
        {
            i = nLen - 1;
            while(haystack[i] == needle[i] && !res)
            {
                if (!i)
                    res = (char *)haystack;
                --i;
            }
            if (!res)
            {
                hLen     -= tab[(size_t)haystack[nLen - 1]];
                haystack += tab[(size_t)haystack[nLen - 1]];
            }
        }
    }
    return 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 = "blffoobarblofoohaha";
    const char *aiguille = "foo";

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

}

a++

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

<< 1 ... 25 26 27 ... 55 >>

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

Supprimer

Modérer

Signaler le message aux modérateurs