Série 9
Tableaux et chaînes de caractères

Création du projet sous QTCreator

Afin de vous inciter à vous familiariser avec QTCreator, une façon simplifiée de configurer cet outil vous est proposé dans cette série. Inspirez-vous de la vidéo de la semaine 4 en utilisant cette fois l'archive serie9.zip.

Exercice 1 : Générateur automatique de lettres (fonctions et chaînes de caractères, niveau 1)

Le but de cet exercice est d'écrire un programme nommé lettre.cc, qui constituera un générateur automatique (très simpliste) de lettres.

1. Écrivez tout d'abord une fonction genereLettre (sans argument, et sans valeur de retour). Cette fonction devra simplement produire la sortie suivante à l'écran : (ne vous occupez pas de la mise en évidence)

   Bonjour chère Mireille,
   Je vous écris à propos de votre cours.
   Il faudrait que nous nous voyons le 18/12 pour en discuter.
   Donnez-moi vite de vos nouvelles !
   Amicalement, John.
   

   Invoquez (appelez) simplement la fonction genereLettre depuis la fonction principale main, compilez votre programme et assurez vous de son fonctionnement correct.

2. Modifiez maintenant la fonction genereLettre, de manière à rendre paramétrables les parties mises en évidence dans le texte précédant. Il vous faudra pour cela passer un certain nombre d'arguments à la fonction, de manière à spécifier :
   • La formulation adaptée pour l'entrée en matière (chère pour un destinataire féminin, et cher pour un destinataire masculin). Ce choix devra être fait en fonction de la valeur d'un argument booléen (masculin ou feminin) ou énuméré (sexe).
   • Le nom du destinataire, nommé par exemple destinataire
   • Le sujet de la lettre (paramètre nommé sujet)
   • La date du rendez-vous sous forme de deux paramètres entiers, l'un pour le jour et l'autre pour le mois
   • La formule de politesse (paramètre politesse)
   • et le nom de l'auteur (auteur).
   La fonction aura donc 7 paramètres.

   Invoquez la fonction au moins deux fois de suite depuis le main, en paramétrant les appels de sorte à produire la lettre précédente, et la réponse ci-dessous :

   Bonjour cher John,
   Je vous écris à propos de votre demande de rendez-vous.
   Il faudrait que nous nous voyons le 16/12 pour en discuter.
   Donnez-moi vite de vos nouvelles !
   Sincèrement, Mireille.
   

Note : On ne vous demande pas de faire saisir les différents arguments au clavier par l'utilisateur, juste d'appeler deux fois la fonction avec les bons arguments dans le main.

Exercice 2 : Segmentation en mots (string, niveau 2)

Cadre

On s'intéresse ici au problème de la segmentation d'un texte en mots. Le but est de trouver, l'un après l'autre, les différents «mots» d'un texte ; un «mot» étant défini comme une séquence de caractères ne contenant pas de «séparateur». Pour simplifier, on considérera ici que le seul caractère séparateur est l'espace (i.e. ' ').

Par exemple, le texte « heuu bonjour, voici ma chaîne ! » aura comme «mots» : «heuu», «bonjour,» (y compris la virgule ici), «voici», «ma», «chaîne» et «!».

Fonction nextToken

Dans le fichier token.cc, prototypez puis définissez la fonction :

bool nextToken(string const& str, int& from, int& len)

dont le rôle sera d'identifier (par la position de départ et la longueur) le prochain mot à partir de la position from dans la chaîne str. Elle indiquera de plus, par sa valeur de retour, si elle a trouvé un mot ou non.

Cette fonction modifiera donc les arguments from et len de sorte qu'ils déterminent la position du premier caractère du mot trouvé et sa longueur, pour autant qu'un tel mot existe (et dans ce cas la fonction devra retourner true).

Dans le cas où il n'existe plus de mot à partir de from dans str, le résultat retourné par cette fonction nextToken sera false (et les valeurs modifiées de from et len ne seront plus significatives).

Par exemple, si l'on appelle nextToken avec " heuu bonjour, voici ma chaîne ! " dans str et 0 dans from, la fonction retournera true (oui, elle a trouvé un mot : «heuu») et aura modifié from à 1 (ce mot trouvé commence à la position 1) et len à 4 (le mot trouvé a une longueur de 4 caractères).

Si on l'appelle avec la même chaîne, mais 6 dans from, la fonction retournera true (oui, elle a trouvé un mot : «bonjour,») et aura laissé from à 6 (ce mot trouvé commence à la position 6) et len à 8.

Si par contre, on appelle nextToken, toujours avec la même chaîne, mais 32 dans from, elle retournera alors false (non, elle n'a pas trouvé de mot à partir de la position 32).

Application

Depuis le main du programme, vous demanderez à l'utilisateur d'entrer une chaîne de caractères au clavier, et afficherez (en faisant des appels successifs à la fonction nextToken) l'ensemble des mots de la chaîne entrée, à raison de un mot par ligne, placés entre apostrophes.

Utilisez l'exemple de fonctionnement ci-après pour vérifier la validité de votre programme ; faites en particulier attention à ce que les apostrophes entourent les mots sans qu'il y ait d'espace entre les deux.

Vérifiez également que le programme se comporte correctement même lorsque la chaîne entrée se termine par une suite d'espaces.

	Pour lire une ligne entière, utilisez : getline(cin, ligne_a_lire); où ligne_a_lire est une string.
	Ne pas utiliser :  cin >> ligne_a_lire; qui ne lit qu'un seul mot (c'est-à-dire s'arrête au premier blanc (espace) rencontré).

Exemple de fonctionnement :

Entrez une chaîne :  heuu bonjour, voici ma chaîne !  
Les mots de " heuu bonjour, voici ma chaîne !  " sont:
'heuu'
'bonjour,'
'voici'
'ma'
'chaîne'
'!'

Exercice 3 : Placement sans recouvrement (tableaux, niveau 2)

Le but de cet exercice est de placer sans recouvrement des objets rectilignes sur une grille carrée. Cela pourrait être par exemple une partie d'un programme de bataille navale.

Dans le fichier recouvrement.cc :

1. Définissez une constante globale entière non-signée, nommée DIM et de valeur 10. Elle représentera la taille de la grille (carrée).

2. Prototypez et écrivez une fonction :

   bool remplitGrille(array<array<bool, DIM>, DIM>& grille,
   		   unsigned int ligne, unsigned int colonne,
                      char direction, unsigned int longueur);
   

   dont le rôle est de vérifier si le placement dans une grille (voir ci-dessous) d'un objet de dimension longueur est possible, en partant de la coordonnée (ligne,colonne) et dans la direction définie par direction (Nord, Sud, Est ou Ouest).
   
   Si le placement est possible, la fonction devra de plus effectuer ce placement (voir ci-dessous la description de la grille).

   La fonction devra indiquer (par la valeur de retour) si le placement a pu être réalisé ou non.

3. Dans le main()
   • Définissez une variable nommée grille, de type array<array<bool, DIM>, DIM>.
     La valeur true dans une case [i][j] de cette grille représente le fait qu'un (bout d')objet occupe la case de coordonnées (i, j).
   • Utilisez la fonction précédente pour remplir interactivement la grille, en demandant à l'utilisateur de spécifier la position, la taille et la direction des objets à placer.
     Indiquez à chaque fois à l'utilisateur si l'élément a pu ou non être placé dans la grille.
     Le remplissage se termine lorsque l'utilisateur entre une position/coordonnée strictement inférieure à 0.
   • Terminer alors en "dessinant" la grille : afficher un '.' si la case est vide et un '#' si la case est occupée.

• Dans l'interface utilisateur, pour indiquer les positions, utilisez au choix soit les coordonnées du C++ : 0 à DIM-1 (plus facile), soit les coordonnées usuelles (1 à DIM, un peu plus difficile) , MAIS dans tous les cas utilisez les indices de 0 à DIM-1 pour votre tableau (aspect programmeur).
• Pensez à effectuer des tests de validité sur les valeurs entrées (débordement du tableau).
• pour représenter la direction, vous pouvez soit utiliser un caractère ('N' pour nord. 'S' pour sud, etc..., plus facile), soit un type enuméré (plus difficile : pensez à l'interface avec l'utilisateur).
• N'oubliez pas d'initialiser la grille en tout début de programme !

Exemple de fonctionnement (version facile : coordonées de 0 à 9 et lettres pour les directions) :

Entrez coord. x: 2
Entrez coord. y: 8
Entrez direction (N,S,E,O): E
Entrez taille: 2
Placement en (2,8) direction E longueur 2 -> succès
Entrez coord. x: 0
Entrez coord. y: 8
Entrez direction (N,S,E,O): S
Entrez taille: 5
Placement en (0,8) direction S longueur 5 -> ECHEC
Entrez coord. x: 0
Entrez coord. y: 9
Entrez direction (N,S,E,O): O
Entrez taille: 5
Placement en (0,9) direction O longueur 5 -> succès
Entrez coord. x: -1

Exercice 4 : LIEN PARTIE THEORIQUE : Conversions binaire <--> décimal (chaînes de caractères, niveau 1)

1. Conversion en binaire d'un nombre entier positif

Pour donner l'écriture binaire d'un nombre entier positif n, il suffit d'appliquer l'algorithme suivant :

• si n est nul, afficher 0 ;
• tant que n est strictement positif, afficher n modulo 2 (c.-à-d. le reste de la division de n par 2),
  puis diviser n par 2.

Le problème avec l'algorithme ci-dessus est qu'il affiche le nombre à l'envers. Par exemple pour 2, il affiche 01 au lieu de 10.

Il suffit simplement pour palier ce problème d'utiliser une structure de données auxiliaire dans le langage de programmation choisi (par exemple une chaîne de caractères) et d'y ajouter les symboles 0 ou 1 non pas à la fin comme le ferait un affichage standard, mais au début de la structure de données choisie. Une fois celle-ci remplie, il ne reste plus qu'à l'afficher normalement (c.-à-d. dans l'ordre usuel).

On peut aussi palier ce problème d'ordre d'affichage des bits en recourant à la version récursive suivante :

• si n est supérieur ou égal à deux, afficher l'écriture binaire de n/2;
• (puis) si n est pair afficher 0, sinon afficher 1.

2. Conversion binaire --> décimal

La conversion réciproque (binaire vers décimal positif) se fait simplement en ajoutant la puissance de 2 correspondant à chaque '1' présent dans l'écriture binaire.

On peut par exemple utiliser l'algorithme suivant :

• initialiser r à 0 et p à 1

• En allant du dernier bit au premier (sens inverse de lecture) :

  • Si le bit est à 1, augmenter r de p (r <-- r + p)

  • multiplier p par 2

3. Conversion de nombres négatifs

On peut maintenant s'intéresser aux nombres négatifs, représenté en binaire en « complément à 2 ». Pour simplifier ici, on ne fixera pas la taille de la représentation binaire, mais on ajoutera simplement le bit de signe au début (= à gauche) de l'écriture binaire minimale nécessaire pour représenter le nombre (exemples ci-dessous).

Commencez pour cela par écrire une fonction qui retourne le complément à 2 d'une écriture binaire.
Le plus simple pour cela est d'inverser tous les bits à gauche du 1 le plus à droite (et laisser le reste inchangé).

Par exemple, le complément à 2 de « 100110100 » est « 011001100 » (notez que la partie soulignée est inchangée et le reste inversé).

Une fois une telle fonction à disposition, il suffit d'appliquer les conversions précédentes si le nombre est positif (bit de signe à 0) et d'appliquer le complément à 2 à la conversion de leur opposé si le nombre est négatif.

On prêtera cependant attention au fait de rajouter un bit supplémentaire (bit de signe) au début des écritures binaires non signées.

Valeurs de test

Commencez par tester avec des valeurs simples (puissances de 2).

L'écriture binaire sans bit de signe de 42 est 101010.

L'écriture binaire signée de 42 est 0101010.

L'écriture binaire signée de -42 est 1010110.