Trois exercices sur les algorythmes

Résumé du document

Trois exercices sur les algorythmes

Extraits

[...] On a la sous-chaine a tester, e e ` donc d'apr`s l'invariant 2 on a trouv´ que la chaine contient une sous chaine ´gale a la e e e ` r´f´rence commen¸ant a l'indice index . D'apr`s l'invariant 1 c'est la premi`re ee c ` e e occurrence, le programme s'arrˆte et renvoie cette valeur correctement. e 2. Lorsque la boucle 1 se termine, on a la chaˆ et il n'existe pas de sous-chaine ´gale a e e ıne e ` celle cherch´e. On retourne donc correctement -1. e 3. Il faut v´rifier que l'on ne d´borde pas de chaine a l'int´rieur de la boucle 2. [...]

[...] La solution est typographi´e avec les caract`res usuels. e e Part I Exercice 1 Dans cet exercice, on s'int´resse ` diverses fonctions concernant les chaˆ e a ınes de caract`res. On rappelle e qu'une chaˆ de caract`re C est un tableau de caract`res termin´ par un caract`re nul. ıne e e e e e ıne Soit la chaine de caract`re c1 Bernard l'Hermite est un crabe.". Dans cette chaˆ la premi`re1 occurence de c2 ="Bernard" est ` la position donn´e par l'indice les deux occurences de e a e c3 sont respectivement en position d'indice 0 et 24. [...]

[...] e e Fonction calculant la position de la plus longue chaine de blancs 4 int posPLBlanc (char ∗chaine ) { char ∗parcours ; position et longueur de la sous chaine de blanc investigu´e e char ; int lg ; position et longueur de la plus longue chaine de blancs char ∗posPLB = int longPLB = pos = chaine ; lg = for (parcours = chaine ; ∗parcours ; ) { if (' ' = (∗parcours { if (lg lg > longPLB ) { posPLB = pos ; longPLB = lg ; } pos = parcours ; lg = } else { parcours , lg ; } } if (lg lg > longPLB ) { posPLB = pos ; longPLB = lg ; } return (longPLB ? posPLB chaine : } Code utilis´ dans le fragment 17. e 5 Dans cette seconde m´thode, la boucle interne a pour but de trouver les zones de blanc, elle e ` est suivie d'un test permettant de mettre a jour la longueur de la plus longue zone de ` blanc et de la mise a jour du pointeur pos pour examiner la suite de chaine . [...]

[...] e e ee On s'int´resse maintenant ` la recherche de la plus grande sous chaine form´e de blancs. Pour cela e a e on dispose d'une fonction de classification de caract`res estBlanc qui retourne 1 si le e caract`re est blanc, et 0 sinon. Sa d´claration est: e e int estBlanc(char); Question 4 : Ecrire une fonction qui prenne une chaine en argument et retourne la position du d´but de la premi`re occurrence de la plus longue chaine de blancs qu'elle contient. [...]

[...] e 1 1 Ceci prend la forme du code int premierSc(char*chaine,char*sousChaine){ int index= for(index= 0;chaine[index]!=0;index++){ int estEgal= int 1 et 2 Car 5 seule pris en compte lors de la correction for(j= 0;estEgal&&sousChaine[j]!='\0';j++){ estEgal= (chaine[index+j]==sousChaine[j]); } if(estEgal) return index; } return-1; } Question 2 : Faut il adapter le corps de la fonction si la d´claration est modifi´e comme suit ? e e int premierSc( char chaine[], char sousChaine[]); La r´ponse sera justifi´e en d´tails. e e e + Il n'y a aucune diff´rence, le nom du tableau de taille variable chaine se comporte comme un e pointeur sur le premier ´l´ment. De la mˆme fa¸on pour l'autre. Ici, nous avons essay´ ee e c e les deux versions, sans faire aucune autre modification. [...]