M1102 TD6 exercice 2

Ecrire la fonction CompterDoublons () présentée ci-dessous. Les “règles du jeu” (les spécifications) sont les suivantes :

  1. un doublon est une suite de deux caractères consécutifs (deux éléments dont les rangs diffèrent d’une unité) identiques.
  2. un doublon est une suite de deux caractères consécutifs identiques.
  3. trois caractères consécutifs identiques constituent deux doublons.
  4. les doublons de caractères d’espacement  sont comptabilisés : par exemple un espace suivi d’une tabulation (ou l’inverse) est un doublon.

M1102-TD6 Exercie2 Corrigé

[Algo]
fonction isspace (C : in caractere) renvoie booleen
debut
renvoie (C vaut ‘ ‘ OU_SINON C vaut ‘\t’ OU_SINON C vaut ‘\n’);
fin

fonction CompterDoublonsV2 (Chaine : in string) renvoie entier_naturel
debut

si (taille(Chaine) < 2) renvoie 0;

declarer Compt : entier_naturel;
Compt <- 0;

pour (i variant_de 1 a taille (Chaine) – 1)
faire
si ((Chaine [i] vaut Chaine [i-1]) OU_SINON (isspace (Chaine [i]) ET_ALORS isspace (Chaine [i-1])))
Compt <- Compt + 1;
fsi
ffaire
renvoie Compt;
fin

algorithme Nb_de_Doublons
debut

boucle
// Saisie

declarer LigneLue : string;
afficher (“Entrer une string (ligne vide pour sortir) : “);
saisir (LigneLue);

si (taille (LigneLue) vaut 0) sortie;

// La ligne traitée est non vide

// Comptage

declarer NbreDoublons : entier_naturel;

NbreDoublons <- CompterDoublonsV2 (LigneLue);

// Affichage
afficher (LigneLue);
ligne_suivante;
afficher (“Nombre de doublons : “, NbreDoublons);
ligne_suivante;
fboucle
fin
[/Algo]

M1102 TD6 exercice 3

Ecrire la fonction CompterDoublons () présentée ci-dessous. Les “règles du jeu” (les spécifications) sont les suivantes :

  1. un doublon est une suite de deux caractères consécutifs identiques.
  2. trois caractères consécutifs identiques constituent deux doublons.
  3. les caractères d’espacement doivent être ignorés :
    • il ne faut pas compter les doublons de caractères d’espacement,
    • deux caractères identiques séparés par un nombre quelconque de caractères d’espacement, forment un doublon.

M1102-TD6 Exercie3 Corrigé

[Algo]
fonction isspace (C : in caractere) renvoie booleen
debut
renvoie (C vaut ‘ ‘ OU_SINON C vaut ‘\t’ OU_SINON C vaut ‘\n’);
fin

fonction CompterDoublonsV3 (Chaine : in string) renvoie entier_naturel
debut

si (taille(Chaine) < 2) renvoie 0;

declarer Compt : entier_naturel;
Compt <- 0;

declarer CarPrec : caractere;
CarPrec <- Chaine [0];

pour (i variant_de 1 a taille (Chaine) – 1)
faire
si (isspace (Chaine [i])) continue;
si (CarPrec vaut Chaine [i])
Compt <- Compt + 1;
fsi
CarPrec <- Chaine [i];
ffaire
renvoie Compt;
fin

algorithme Nb_de_Doublons
debut

boucle
// Saisie

declarer LigneLue : string;
afficher (“Entrer une string (ligne vide pour sortir) : “);
saisir (LigneLue);

si (taille (LigneLue) vaut 0) sortie;

// La ligne traitée est non vide

// Comptage

declarer NbreDoublons : entier_naturel;

NbreDoublons <- CompterDoublonsV3 (LigneLue);

// Affichage
afficher (LigneLue);
ligne_suivante;
afficher (“Nombre de doublons : “, NbreDoublons);
ligne_suivante;
fboucle

fin
[/Algo]

M1102 TD6 exercice 4

Lorsque le motif dépasse deux caractères, il devient lourd et maladroit de mémoriser individuellement les caractères qui composent le motif. Il est préférable de considérer que l’on cherche une sous-chaine (de 2, 3 lettres ou plus) dans une chaîne (ou un sous-tableau dans un tableau).

Ecrire la fonction FindSubstrInStr() qui renvoie le rang de la première apparition d’une sous-chaîne dans une chaîne de caractères, à partir d’un rang de début de recherche, tous trois passés en paramètres. Plus précisément, elle renvoie le rang du premier caractère de la sous-chaîne dans la chaîne.

La valeur de retour est obligatoirement dans l’intervalle [0, taille (Chaine)[ si la sous-chaîne est présente. On choisira donc de renvoyer la valeur taille (Chaine) si la sous-chaîne n’a pas été trouvée.

M1102-TD6 Exercie4 Corrigé

[Algo]
fonction TrouveCarDansStr (Caract : in caractere,
Chaine : in string,
Debut : in entier_naturel) renvoie entier_naturel
debut
declarer i : entier_naturel;
i <- Debut;
tant_que (i < taille(Chaine) ET_ALORS Caract ne_vaut_pas Chaine [i])
faire
i <- i +1;
ffaire
renvoie i;
fin

fonction FindSubInStr (SsChaine : in string, Chaine : in string, Debut : in entier_naturel) renvoie entier_naturel
debut

//on se demande s’il y a la place pour faire la recherche
si (taille (SsChaine) + Debut >= taille (Chaine)) renvoie taille (Chaine);

//peut-on accéder à l’élément en position 0 de la sous-chaine? non => on sort
si (taille (SsChaine) vaut 0) renvoie taille (Chaine);

declarer i : entier_naturel;
i <- Debut;

declarer j : entier_naturel;
j <- 0;

boucle
//on cherche la première occurence de SsChaine [0] dans Chaine à partir de la position i
i <- TrouveCarDansStr (SsChaine [0], Chaine, i);

//cas 0: si la recherche a échouée (on ne peut pas trouver le sous-motif), alors on sort
si (i vaut taille (Chaine)) sortie;

//si on ne sort pas, l’assertion SsChaine [0] vaut Chaine [i] est vraie
//cas 1 : on se demande alors si on peut placer la sous-chaine entre la position i et la fin de la chaine sans faire de
//débordement de case. Si ce n’est pas le cas, on sort de la boucle
si (i + taille (SsChaine) > taille (Chaine)) sortie;

//cas 2: on peut lancer la recherche
//on parcourt donc le reste de la sous-chaine
j <- 1;
tant_que (j < taille (SsChaine) ET_ALORS Chaine [i + j] vaut SsChaine [j])
faire
j <- j +1;
ffaire

//si on a atteint la fin de la sous-chaine, on sort de la boucle
si (j vaut taille (SsChaine)) sortie;

//si on ne sort pas, on prépare la prochaine recherche
i <- i + 1;
fboucle

si (j ne_vaut_pas taille (SsChaine))
i <- taille (Chaine);
fsi
renvoie i;
fin
//astuce : même si le test ligne 34 (cas 0) est juste, il est couvert par celui en ligne 39 (cas 1)
//on pourrait donc s’en passer 🙂

algorithme TestFindSubInStr
debut
boucle
// Saisie

declarer LigneLue : string;
afficher (“Entrer une string (ligne vide pour sortir) : “);
saisir (LigneLue);

si (taille (LigneLue) vaut 0) sortie;

// La ligne traitée est non vide

declarer SousChaine : string;
boucle
afficher (“Entrer la sous-chaine cherchee : “);
saisir (SousChaine);
si (taille (SousChaine) ne_vaut_pas 0) sortie;
fboucle

declarer Pos : entier_naturel;
afficher (“Entrer la position à partir de laquelle vous souhaitez faire la recherche : “);
saisir (Pos);

declarer PosCherchee : entier_naturel;
PosCherchee <- FindSubInStr (SousChaine, LigneLue, Pos);

// Affichage
si (PosCherchee < taille (LigneLue))
afficher (“On trouve le motif \””, SousChaine, “\” dans la chaine “, LigneLue);
afficher (” pour la première fois à partir de la position “, Pos, ” en position “, PosCherchee);
sinon
afficher (“On ne trouve pas le motif \””, SousChaine, “\” dans la chaine “, LigneLue, ” a partir de la position “, Pos);
fsi
ligne_suivante;
fboucle
fin
[/Algo]

M1102-TD5 Exercice 1

Le but de cet exercice est d’afficher le nombre d’occurrences de chaque élément d’un petit ensemble de valeurs dans une collection. Ici, on comptera le nombre de voyelles contenues dans une chaîne de caractères. Pour cela :

  1. initialiser les compteurs ;
  2. pour chaque valeur de la collection (chaque caractère de la chaîne), balayer complètement le petit ensemble (l’ensemble des voyelles) et incrémenter le bon nombre d’occurrence quand il le faut ;
  3. calculer le nombre total d’occurrence des éléments de l’ensemble (le nombre total de voyelles) ;
  4. afficher le nombre d’occurrences de chacun des éléments de l’ensemble (de chacune des voyelles) ainsi que leur fréquence relative (au nombre total d’éléments de l’ensemble (de voyelles)) ;
  5. on pourra utiliser les fonctions ComptCaract() et/ou TrouveCarDansStr ().

M1102-TD5 Exercie1 Corrigé

[Algo]
fonction TrouveCarDansStr (Caract : in caractere,
Chaine : in string,
Debut : in entier_naturel) renvoie entier_naturel
debut
declarer i : entier_naturel;
i <- Debut;
tant_que (i < taille(Chaine) ET_ALORS Caract ne_vaut_pas Chaine [i])
faire
i <- i +1;
ffaire
renvoie i;
fin

fonction ComptCarac (Caract : in caractere,
Chaine : in string) renvoie entier_naturel
debut
declarer Cpt : entier_naturel;
Cpt <- 0;

declarer Pos : entier_naturel;
Pos <- 0;

boucle
Pos <- TrouveCarDansStr (Caract, Chaine, Pos);
si (Pos vaut taille (Chaine)) sortie;
Cpt <- Cpt + 1;
Pos <- Pos + 1;
fboucle

renvoie Cpt;
fin

algorithme ComptagePetitEnsemble
debut
declarer KStrVoy : constante string <- "aeiouy";

declarer TabCpt : tableau_de taille (KStrVoy) entier_naturel;

declarer Chaine : string;
afficher ("Veuillez saisir une chaine de caractères : ");
saisir (Chaine);

//comptage
pour (i variant_de 0 a taille (KStrVoy) -1)
faire
TabCpt [i] <- ComptCarac (KStrVoy [i], Chaine);
ffaire

//nb total d’occurence
declarer Somme : entier_naturel;
Somme <- 0;
pour (i variant_de 0 a taille (TabCpt) – 1)
faire
Somme <- Somme + TabCpt [i];
ffaire

//affichage final
pour (i variant_de 0 a taille (KStrVoy) -1)
faire
afficher ("Le caractère ", KStrVoy [i], " apparait ", TabCpt [i], " fois en absolu et ", TabCpt [i]*100 / Somme, "% en relatif");
ligne_suivante;
ffaire
fin
[/Algo]

M1102 TD5 Exercice 2

Ecrire les prédicats suivants :
[Algo]
fonction IsUpper (Car : in caractere) renvoie booleen;
fonction IsLower (Car : in caractere) renvoie booleen;
fonction IsDigit (Car : in caractere) renvoie booleen;
[/Algo]

Ces prédicats renvoient vrai si le caractère qui leur est passé en paramètre est respectivement une majuscule, une minuscule ou un chiffre décimal (de '0' à '9').
Ecrire le prédicat IsSpace (), qui renvoie vrai si le caractère passé en paramètre est un caractère d’espacement (espace, tabulation ou retour à la ligne).

M1102-TD5 Exercie2 Corrigé

[Algo]
fonction TrouveCarDansStr (Caract : in caractere,
Chaine : in string,
Debut : in entier_naturel) renvoie entier_naturel
debut
declarer i : entier_naturel;
i <- Debut;
tant_que (i < taille(Chaine) ET_ALORS Caract ne_vaut_pas Chaine [i])
faire
i <- i +1;
ffaire
renvoie i;
fin

algorithme ComptagePetitEnsemble
debut
declarer KStrVoy : constante string <- "aeiouy";

declarer TabCpt : tableau_de taille (KStrVoy) entier_naturel;
pour (i variant_de 0 a taille (TabCpt) – 1)
faire
TabCpt [i] <- 0;
ffaire

declarer Chaine : string;
afficher ("Veuillez saisir une chaine de caractères : ");
saisir (Chaine);

//comptage
pour (i variant_de 0 a taille (Chaine) -1)
faire
declarer Pos : entier_naturel;
Pos <- TrouveCarDansStr (Chaine [i], KStrVoy, 0);
si (Pos vaut taille (KStrVoy)) continue;
TabCpt [Pos] <- TabCpt [Pos] + 1;
ffaire

//nb total d’occurence
declarer Somme : entier_naturel;
Somme <- 0;
pour (i variant_de 0 a taille (TabCpt) – 1)
faire
Somme <- Somme + TabCpt [i];
ffaire

//affichage final
pour (i variant_de 0 a taille (KStrVoy) -1)
faire
afficher ("Le caractère ", KStrVoy [i], " apparait ", TabCpt [i], " fois en absolu et ", TabCpt [i]*100 / Somme, "% en relatif");
ligne_suivante;
ffaire
fin
[/Algo]