Chaînes de caractères | Exercices 11-15

Enoncé exercice 11

Ecrire un programme C qui lit deux chaînes de caractères et dit si la deuxième est une rotation de la première.

Exemple : les chaines de caractères abcde, bcdea, cdeab, deabc et eabcd sont toutes les rotations possibles de la chaîne abcde.

Correction exercice 11

Dans cet exercice, on souhaite vérifier si une chaîne de caractères est obtenue à partir d’une rotation quelconque d’une autre chaîne. Pour faire ceci, on va commencer par la lecture des deux chaînes de caractères vers s et c à l’aide de deux appels à la fonction gets (lignes 9-10).

Avant d’aller plus loin dans le code, on verra tout de suite comment une rotation peut être effectuée d’une manière qui sera utile dans la réalisation du programme. Soit la chaîne 123456789. Pour avoir sa rotation qui commence par 4, il suffira de mettre la partie rouge à gauche de la partie verte. Ce qui va donner, 456789123. Qui est effectivement une des rotations de la chaîne de départ:

Dans le programme, c’est exactement ce qui a été fait. On a utilisé une boucle for de compteur i, pour sélectionner la position par laquelle on souhaite que la rotation de la chaîne c commence (ligne 13). Et on procède ensuite à mettre les deux parties de la chaîne, séparées à la position i, chacune de l’autre côté de l’autre.

Pour faire cette rotation de la chaîne de caractères c, on ne va pas altérer cette dernière, mais plutôt on va mettre le résultat dans une chaîne auxiliaire rot. On va donc commencer par parcourir la partie de c entre i et n (n étant la taille de la chaîne) à l’aide de la première boucle for de compteur j. Et on mettra chaque caractère c[j] dans sa position adéquate de rot, afin d’avoir cette partie de c au début de rot (lignes 15-16). Pour la deuxième partie entre les deux indices 0 et i, on va refaire la même démarche de façon à la mettre à la fin de rot (ligne 17-18).

Le compteur k utilisé dans ces deux dernières boucles, a été initialisé par 0 dans la première boucle for, pour pouvoir commencer le remplissage de rot depuis sa première case. Et il n’a pas été réinitialisé dans la deuxième, pour pouvoir achever le remplissage de rot à partir du point où s’est arrêtée la première boucle.

Lorsque le compteur i parcourra toute la chaîne c, on aura ainsi généré toutes les rotations possibles de c. Si une d’elles est identique à s, alors s est une rotation de c (ou encore c est une rotation de s, puisque c’est réciproque). Pour le savoir, il suffira de comparer chaque rotation générée rot avec s en utilisant la fonction strcmp (ligne 19). Dans le cas où ça arrive, on signale l’égalité en mettant la variable r, initialisée par 0, à 1. Et on interrompe la recherche en quittant la boucle avec l’instruction break (lignes 21-22).

En sortant de la boucle, on vérifie le contenu de la variable r, et on affiche le message correspondant à sa valeur (lignes 25-28).

N.B.: même si le programme marche très bien, il est facile de l’optimiser davantage. Chose qui n’a pas été visée, par souci de réduire le nombre de blocs dans le code.

Solution exercice 11
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char s[100],c[100],rot[100];
    int i,j,k,l,n,r=0;
    printf("Entrez deux chaines de caracteres de meme taille:\n");
    gets(s);
    gets(c);
    n=strlen(s);
    rot[n]='\0';
    for(i=0;i<n;i++)
    {
       for(k=0,j=i;j<n;j++,k++)
          rot[k]=c[j];
       for(j=0;j<i;j++,k++)
          rot[k]=c[j];
       if(strcmp(s,rot)==0)
       {
          r=1;
          break;
       } 
    }
    if(r==1)
       printf("La deuxieme chaine est une rotation de la premiere.\n");
    else
       printf("La deuxieme chaine n'est pas une rotation de la premiere.\n");
    system("pause");
    return 0;
}
Enoncé exercice 12

Ecrire un programme C qui permet de trouver la plus grande frontière d’une chaîne de caractères, si elle existe.

Une frontière d’une chaîne de caractère, est une sous chaîne qui apparait au début et à la fin de la chaîne.

Exemples : aab est une frontière de aabbaab, bab est une frontière de babab et ab n’a pas de frontière.

Correction exercice 12

Le programme va commencer par la lecture de la chaîne de caractères entrée par l’utilisateur vers s. Une fois la chaîne est prête, on peut directement passer à la recherche de la plus grande frontière de cette chaîne. Comme on peut déduire des exemples donnés dans l’énoncé, la chaîne elle-même n’est pas considérée comme frontière. Donc si n est la taille de la chaîne, une frontière si elle existe peut atteindre au maximum la taille n-1.

L’algorithme adopté ici, consiste à choisir à chaque fois une sous chaîne de s qui va d’une position i jusqu’à la fin de la chaîne, et la comparer avec la sous chaîne de même taille qui commence à la première case de s, comme montré sur la figure suivante :

Une fois le i sélectionné, on effectue alors la comparaison mentionnée en-dessus. Pour ça, on va s’aider d’une variable front initialisé par 1, et qu’on va mettre à 0 si on trouve un seul caractère de différence entre les deux sous chaînes comparée (lignes 13-19).

Pour effacer toute ambiguïté en ce qui concerne la mise en œuvre de cette comparaison, le compteur j parcourt la sous chaîne à la fin de s, et k celle au début.

Juste après chaque comparaison, on vérifie la valeur de la variable front. Si elle est toujours égale à 1, ça veut seulement dire qu’aucune différence entre les deux sous chaînes n’a été détectée. Du coup, elles sont identiques. Et de plus, elles constituent la plus grande frontière de s. Dans ce cas, on affiche une d’elles et on arrête la recherche en utilisant un break (lignes 20-26).

Dans l’éventualité qu’aucune frontière n’existe, on doit transmettre un message à l’utilisateur. La difficulté est de pouvoir repérer quand est ce que ceci est arrivé. La méthode la plus simple est de vérifier la valeur du compteur i après la sortie de sa boucle for. Si elle est égale à n, ça veut dire que la boucle a allé jusqu’au bout sans qu’elle trouver aucune frontière (lignes 28-29). Car autrement, l’instruction break aura arrêté ses itérations (ligne 25).

Solution exercice 12
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char s[100];
    int i,j,k,n,front;
    printf("Entrez une chaine de caractere:\n");
    gets(s);
    n=strlen(s);
    for(i=1;i<n;i++)
    {
       front=1;
       for(k=0,j=i;j<n;k++,j++)
          if(s[j]!=s[k])
          {
             front=0;
             break;
          }
       if(front==1)
       {
          for(j=i;j<n;j++)
             printf("%c",s[j]);
          printf("\n");
          break;
       }
    }
    if(i==n)
       printf("Cette chaine n'a pas de frontiere.\n");
    system("pause");
    return 0;
}
Enoncé exercice 13

Ecrire un programme C qui lit deux caractères et un entier n. Puis calcule et affiche la nième chaîne de Fibonacci basée sur ces deux caractères.

La nième chaîne de Fibonacci Sn est obtenue en concaténant Sn-1 avec Sn-2, en mettant Sn-1 devant Sn-2.

Exemple :

S0=b
S1=a
S2=ab
S3=aba
S4=abaab
S5=abaababa
S6=abaababaabaab

Correction exercice 13

Pour faire cet exercice, on va utiliser trois chaînes de caractères a, b et c pour contenir les trois termes qui rentrent dans le calcul des chaînes de Fibonacci, à savoir Sn, Sn-1 et Sn-2.

Même si on sait d’avance que l’utilisateur va introduire deux caractères, on va les lire chacun en tant que chaîne de caractères vers a et b (lignes 8-11). On demande et on lit ensuite le rang n de la chaîne de Fibonacci recherchée (lignes 12-13).

Pour arriver à la chaîne de rang n, il faudra calculer toutes les chaînes de rangs inférieurs. Pour faire ceci, on va exploiter une boucle for de compteur i allant de 2 jusqu’à n (ligne 14).

Pour constituer un nouveau terme c, il faudra concaténer les deux derniers a et b. Afin de respecter l’ordre de concaténation, on va copier le contenu de b dans c en utilisant la fonction strcpy (ligne 16), puis on ajoute a à la fin de c à l’aide de la fonction strcat (ligne 17).

Dans l’itération qui suivra, on n’aura plus besoin que de b et c. Donc, en guise de préparation à cette itération, on va mettre b dans a et c dans b (lignes 18-19).

Après la sortie de cette dernière boucle, la nième chaîne de Fibonacci est contenue dans c. Sauf que, si le rang entré est égal à 0 ou à 1 la chaîne recherchée est soit dans a ou dans b. Il faudra donc tenir ça en considération lors de l’affichage. D’où l’utilisation de la structure de contrôle switch (lignes 21-28).

Solution exercice 13
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char a[1000],b[1000],c[1000];
    int i,n;
    printf("Entrez le premier caractere: ");
    gets(a);
    printf("Entrez le deuxieme caractere: ");
    gets(b);
    printf("Entrez un entier: ");
    scanf("%d",&n);
    for(i=2;i<=n;i++)
    {
       strcpy(c,b);
       strcat(c,a);
       strcpy(a,b);
       strcpy(b,c);
    }
    switch(n)
    {
       case 0: puts(a);
          break;
       case 1: puts(b);
          break;
       default: puts(c);
    }
    system("pause");
    return 0;
}
Enoncé exercice 14

Ecrire un programme C qui lit deux chaînes de caractères et vérifie si la deuxième est une période de la première.

Exemple : abc est une période de abcabcabc mais pas de aabcabc.

Correction exercice 14

Il y’a une multitude de méthodes qui permettent de réaliser le programme répondant à la tâche décrite dans l’énoncé. Mais la méthode adoptée ici sera peut-être la plus élégantes d’entre elles.

Après la lecture de la première chaîne de caractères vers s, on lit la période vers c (lignes 8-11). Maintenant, pour vérifier si c est une vraie période de s, il faudra bien sûr procéder à des comparaisons entre des tronçons de s avec c. Et pour ça, on va se baser sur une constatation qu’on va illustrer sur l’exemple suivant : soit la chaîne abcabcabc et la période abc. Si on associe les caractères qui devront être comparés pour assurer la vérification, on obtiendra :

Si on prend l’indice d’un caractère quelconque de s, et on calcule son modulo 3 (3 étant la taille de c), le résultat obtenu sera l’indice du caractère de c avec lequel il sera comparé.

D’après cette constatation, on va utiliser une boucle for de compteur i, pour parcourir la chaîne de caractères s. Et à chaque fois, on compare s[i] avec c[i%m]m est la taille de la chaîne c. Ces deux caractères devront être identiques pour tout i, afin que la chaîne c soit considérée une période de s. Donc, la première différence rencontrée doit être signalée en mettant la variable per, initialisée par 1, à 0, et on arrête le parcours en utilisant un break (lignes 15-20).

Cet algorithme couvre tous les cas, sauf un seul. C’est le cas où c est une concaténation de s avec une autre chaîne quelconque. Par exemple, si s est égale à abc et c à abcd. Le traitement de ce cas particulier est trop simple; après la sortie de la boucle for, on mit à 0 la variable per dans le cas où la taille de c est supérieure à celle de s (ligne 21).

Pour l’affichage, on vérifie le contenu de la variable per, et on affiche le message adéquat (lignes 22-25).

Solution exercice 14
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char s[100],c[100];
    int i,j,n,m,per;
    printf("Entrez la premiere chaine:\n");
    gets(s);
    printf("Entrez la deuxieme chaine:\n");
    gets(c);
    n=strlen(s);
    m=strlen(c);
    per=1;
    for(i=0;i<n;i++)
       if(s[i]!=c[i%m])
       {
          per=0;
          break;
       }
    if(m>n) per=0;
    if(per==1)
       printf("%s est une periode de %s.\n",c,s);
    else
       printf("%s n'est pas une periode de %s.\n",c,s);
    system("pause");
    return 0;
}
Enoncé exercice 15

Ecrire un programme C qui lit deux chaînes de caractères, et affiche toutes les sous chaînes de la première, qui ne sont constituées que de caractères existants dans la deuxième chaîne.

Correction exercice 15

Cet exercice présente deux défis principaux. Le premier concerne la génération de toutes les sous chaînes possibles d’une chaîne de caractères. Et le deuxième est à propos de la vérification de l’existence d’un ensemble de caractères dans une chaîne d’une manière qui soit un peu rapide.

On va commencer par la lecture des deux chaînes de caractères, consécutivement, dans s puis c et on va ensuite mettre leurs tailles dans les deux variables entières n et m (lignes 9-14).

Pour voir si un caractère d’une sous chaîne existe ou non dans c, il ne sera pas trop optimal d’aller parcourir à chaque fois la chaîne c afin de le vérifier. Une alternative sera d’utiliser un tableau d’entiers t de taille 256, qui est le nombre de caractères du langage C, pour le remplir de uns et de zéros. Le 1 dans une case d’indice i par exemple, voudra dire que le caractère dont le code ASCII est i existe dans la chaîne c. Et un 0 voudra tout simplement dire, le contraire.

Pour préparer ce tableau à l’utilisation, on va l’initialiser au départ par des zéros (lignes 15-16). Puis, on va parcourir la chaîne de caractères c, et pour chaque caractère c[i], on lui applique une conversion vers le type entier pour obtenir son code ASCII, et on mettra à 1 la case du tableau t dont l’indice correspond à ce code (lignes 17-18).

Pour générer toutes les sous chaînes possibles de s, on aura besoin de deux boucles for imbriquées. La première, de compteur i allant de 0 à n-1, qui va donner les différents débuts possibles d’une sous chaîne. Et la deuxième, de compteur j allant de i jusqu’à n-1, donnant les différentes fins possibles d’une sous chaîne commençant à i.

A l’intérieur de ces deux boucles, il sera temps de vérifier si les caractères dans l’intervalle [i,j] apparaissent tous dans c ou non. On peut bien sûr garder les choses simples et utiliser une troisième boucle pour parcourir cet intervalle, mais on pourra faire mieux.

Ce qui se passe ici, est que le i est fixe et le j varie de i à n-1. Supposant que pour un certain j, le caractère s[j] n’existe pas dans c, alors il ne sera plus nécessaire de rechercher les sous chaines qui commencent à i et qui s’étalent au-delà de ce j, puisqu’elles contiendront toujours ce caractère s[j] qui n’apparait pas dans c.

Pour exploiter cette source d’optimisation, on va quitter la boucle de compteur j chaque fois qu’on retrouve un caractère qui n’appartient pas à c. Ceci permettra de ne vérifier que le nouveau caractère ajouté à la sous chaîne d’une itération à l’autre, et qui est s[j] (lignes 23-24).

Si on dépasse ce test qui contient le break, on sera sûr que la sous chaîne entre i et j ne contient pas de caractères en dehors de c. On l’affiche alors en utilisant la boucle for de compteur k (lignes 25-26).

Solution exercice 15
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char s[100],c[100];
    int t[256];
    int i,j,k,n,m;
    printf("Entrez la premiere chaine:\n");
    gets(s);
    printf("Entrez la deuxieme chaine:\n");
    gets(c);
    n=strlen(s);
    m=strlen(c);
    for(i=0;i<256;i++)
       t[i]=0;
    for(i=0;i<m;i++)
       t[(int)c[i]]=1;
    printf("Les sous chaines obtenues:\n");
    for(i=0;i<n;i++)
       for(j=i;j<n;j++)
       {
          if(t[(int)s[j]]==0)
             break;
          for(k=i;k<=j;k++)
             printf("%c",s[k]);
          printf("\n"); 
       } 
    system("pause");
    return 0;
}