M1102-TD7 Exercice 1

Dans cet exercice un mot est défini comme une suite non vide de lettres (minuscules ou majuscules), de chiffres et ou de caractère “souligné” ‘_’ (underscore).

Ecrire la fonction CompterMots () de profil :
[Algo]fonction CompterMots (Chaine : in string) renvoie entier_naturel;[/Algo]
Les prédicats suivants sont supposés exister :
[Algo]fonction IsUpper (Car : in caractere) renvoie booleen;
fonction IsLower (Car : in caractere) renvoie booleen;
fonction IsDigit (Car : in caractere) renvoie booleen;
fonction IsSpace (Car : in caractere) renvoie booleen;
[/Algo]

Remarques :

  1. Il ne s’agit pas d’identifier complètement les mots mais seulement de les compter.Or il y a autant de mots que de débuts de mots ! Il suffit donc de compter les débuts de mots.

    Le début d’un mot peut être défini comme une lettre (majuscule ou minuscule), un chiffre ou un ‘_’, précédé par un caractère qui n’est aucun de ces caractères.

  2. Un mot peut commencer au rang 0. Il ne faut donc pas commencer la boucle de traitement au caractère de rang 1. On ne peut pas non plus comparer le premier caractère (de rang 0) avec son prédécesseur.

Il y a donc deux possibilités : soit traiter à part le premier caractère, ce qui est lourd, soit comparer le caractère courant avec son prédécesseur, qui aura été mémorisé dans une variable intermédiaire et qui, pour le rang 0, aura correctement été initialisé.

Comme nous l’avons signalé dans plusieurs exercices précédents, il y a deux approches algorithmiques extrêmement différentes, qui apparaissent clairement dans le cœur des deux algorithmes de haut niveau ci-dessous :

Approche caractère/caractère [Algo]
….
Se_positionner_en_debut_de_chaine;
pour (chaque_caractere_de_la_chaine)
faire
si (c_est_un_debut_de_mot)
Compter_le_mot;
fsi
Passer_au_caractere_suivant;
ffaire
….[/Algo]
Dans cet approche, la chaîne est vue comme une simple suite de caractères, qui sont donc traités séquentiellement.

Approche mot/mot [Algo]
….
boucle
Se_positionner_en_debut_de_mot;
si (fin_de_ligne) sortie;
Compter_le_mot;
Passer_a_la_fin_du_mot;
fboucle
….[/Algo]
Dans ce cas, la fonction superpose à la structure physique du tableau vu comme une “suite de caractères”, une structure logique de “suite de mots”.

A faire Ecrire les deux variantes de cette fonction.

M1102-TD7 Exercie1 Corrigé

[Algo]
fonction isupper (Car : in caractere) renvoie booleen
debut
renvoie (‘A’ <= Car ET_ALORS Car <= ‘Z’);
fin

fonction islower (Car : in caractere) renvoie booleen
debut
renvoie (‘a’ <= Car ET_ALORS Car <= ‘z’);
fin

fonction isdigit (Car : in caractere) renvoie booleen
debut
renvoie (‘0’ <= Car ET_ALORS Car <= ‘9’);
fin

fonction CarDeMot (Car : in caractere) renvoie booleen
debut
renvoie (islower (Car) OU_SINON isupper(Car) OU_SINON isdigit (Car) OU_SINON Car vaut ‘_’);
fin

//approche mot/mot
//fonction CompterNbMots (Chaine : in string) renvoie entier_naturel
//debut
// declarer Cpt : entier_naturel;
// Cpt <- 0;
// declarer i : entier_naturel;
// i <- 0;
//
// boucle
// //on se positionne sur le début du prochain mot
// tant_que ((i < taille (Chaine)) ET_ALORS (NON CarDeMot (Chaine [i])))
// faire
// i <- i + 1;
// ffaire
// si (i vaut taille (Chaine)) sortie;
//
// //si on ne sort pas, c’est qu’on est sur le debut d’un mot
// Cpt <- Cpt + 1;
//
// //on passe le mot courant
// tant_que (i < taille (Chaine) ET_ALORS CarDeMot (Chaine [i]))
// faire
// i <- i + 1;
// ffaire
// fboucle
//
// renvoie Cpt;
//fin

//approche caractere/caractere
fonction CompterNbMots (Chaine : in string) renvoie entier_naturel
debut
declarer Cpt : entier_naturel;
Cpt <- 0;
declarer EstDansMot : booleen;
EstDansMot <- faux;

pour (i variant_de 0 a taille (Chaine) -1)
faire
//on identifie le debut d’un nouveau mot
si (NON EstDansMot ET_ALORS CarDeMot (Chaine [i]))
Cpt <- Cpt + 1;
EstDansMot <- vrai;
//on identifie la fin du mot courant
sinon_si (EstDansMot ET_ALORS NON CarDeMot (Chaine [i]))
EstDansMot <- faux;
fsi
ffaire
renvoie Cpt;
fin

algorithme ComptageDeMots
debut
declarer LigneLue : string;
boucle
afficher (“Entrer une ligne : “);
saisir (LigneLue);
si (0 vaut taille (LigneLue)) sortie;
afficher (LigneLue);
ligne_suivante;
afficher (“Nombre de mots de la ligne :”, CompterNbMots (LigneLue));
ligne_suivante;
fboucle
fin
[/Algo]

M1102-TD7 Exercice 2

A la définition précédente d’un mot (“un mot est défini comme une suite non vide de lettres (minuscules ou majuscules), de chiffres et ou de caractère “souligné” ‘_'”) est ajoutée une contrainte supplémentaire : un mot doit commencer par une lettre (minuscule ou majuscule).

Ecrire la fonction CompterMots () correspondante. La signature de cette fonction est inchangée par rapport à l’exercice précédent. On a donc :

[Algo]fonction CompterMots (Chaine : in string) renvoie entier_naturel;[/Algo]

M1102-TD7 Exercie2 Corrigé

[Algo]
fonction isupper (Car : in caractere) renvoie booleen
debut
renvoie (‘A’ <= Car ET_ALORS Car <= ‘Z’);
fin

fonction islower (Car : in caractere) renvoie booleen
debut
renvoie (‘a’ <= Car ET_ALORS Car <= ‘z’);
fin

fonction isdigit (Car : in caractere) renvoie booleen
debut
renvoie (‘0’ <= Car ET_ALORS Car <= ‘9’);
fin

fonction CarDeMot (Car : in caractere) renvoie booleen
debut
renvoie (islower (Car) OU_SINON isupper(Car) OU_SINON isdigit (Car) OU_SINON Car vaut ‘_’);
fin

fonction DebutMot (Car : in caractere) renvoie booleen
debut
renvoie (islower (Car) OU_SINON isupper(Car));
fin

//approche mot/mot
//fonction CompterNbMots (Chaine : in string) renvoie entier_naturel
//debut
// declarer Cpt : entier_naturel;
// Cpt <- 0;
// declarer i : entier_naturel;
// i <- 0;
//
// boucle
// //on se positionne sur le début du prochain mot
// //seul le predicat change par rapport a l’exercice 1
// tant_que ((i < taille (Chaine)) ET_ALORS (NON DebutMot (Chaine [i])))
// faire
// i <- i + 1;
// ffaire
// si (i vaut taille (Chaine)) sortie;
//
// //si on ne sort pas, c’est qu’on est sur le debut d’un mot
// Cpt <- Cpt + 1;
//
// //on passe le mot courant
// tant_que (i < taille (Chaine) ET_ALORS CarDeMot (Chaine [i]))
// faire
// i <- i + 1;
// ffaire
// fboucle
//
// renvoie Cpt;
//fin

//approche caractere/caractere
fonction CompterNbMots (Chaine : in string) renvoie entier_naturel
debut
declarer Cpt : entier_naturel;
Cpt <- 0;
declarer EstDansMot : booleen;
EstDansMot <- faux;

pour (i variant_de 0 a taille (Chaine) -1)
faire
//on identifie le debut d’un nouveau mot
si (NON EstDansMot ET_ALORS DebutMot (Chaine [i]))
Cpt <- Cpt + 1;
EstDansMot <- vrai;
//on identifie la fin du mot courant
sinon_si (EstDansMot ET_ALORS NON CarDeMot (Chaine [i]))
EstDansMot <- faux;
fsi
ffaire
renvoie Cpt;
fin

algorithme ComptageDeMots
debut
declarer LigneLue : string;
boucle
afficher (“Entrer une ligne : “);
saisir (LigneLue);
si (0 vaut taille (LigneLue)) sortie;
afficher (LigneLue);
ligne_suivante;
afficher (“Nombre de mots de la ligne :”, CompterNbMots (LigneLue));
ligne_suivante;
fboucle
fin
[/Algo]