Premier cycle - I1 Lundi 2 D´ ecembre 2002 Algorithmique Correction 1 Question

Premier cycle - I1 Lundi 2 D´ ecembre 2002 Algorithmique Correction 1 Question de compr´ ehension 1. Que fait le fonction suivante : fonction bidule (t : tableau[1..MAX] d’Entier ; nbElements : Entier) : Bool´ een D´ eclaration drapeau : Bool´ een, i : Entier d´ ebut drapeau Vrai i 1 tant que drapeau et i  nbElements faire si t[i]  t[i+1] alors drapeau Faux sinon i i+1 finsi fintantque retourner drapeau fin La fonction bidule permet de savoir si les nbElements entiers stock´ es dans t sont rang´ es en ordre croissant 2. Justifier votre r´ eponse. En effet dans l’algorithme on consid` ere tout d’abord que ce fait (represent´ e par la variable locale drapeau) est vrai. Ensuite on parcourt (par l’interm´ ediaire de la variable i) le tableau t tant que i  nbElements et que deux ´ el´ ements cons´ ecutifs soient bien rang´ e (t[i]  t[i+1]). Si cette deuxi` eme condition n’est pas r´ ealis´ ee, la variable drapeau passe alors ` a faux. Finalement on retourne la variable drapeau. 2 Questions sur les tris (7 pts) : 1. Ecrire la proc´ edure de tri par minimum successif qui permet de trier un tableau d’entiers (de 1 ` a MAX) contenant nbElements significatifs fonction indiceDuMinimum (t : tableau[1..MAX] d’Entier ; rang, nbElements : Entier) : Entier D´ eclaration i, indiceCherche : Entier d´ ebut indiceCherche rang pour i rang+1 ` a nbElements faire si t[i]  t[indiceCherche] alors indiceCherche i finsi finpour retourner indiceCherche fin 1 proc´ edure effectuerTriParMimimumSuccessif ( E/S t : tableau[1..MAX] d’Entier ; E nbEle- ments : Entier ) D´ eclaration i,indice : Entier d´ ebut pour i 1 ` a nbElements-1 faire indice indiceDuMinimum(t,i,nbElements) si i  indice alors echanger(t[i],t[indice]) finsi finpour fin 2. Expliciter son fonctionnement sur l’exemple suivant : 3 5 4 1 On peut repr´ esenter le comportement de effectuerTriParMimimumSuccessif ` a l’aide du tableau suivant : i indiceDuMinimum t 3 5 4 1 1 4 1 5 4 3 2 4 1 3 4 5 3 3 1 3 4 5 3 Question sur les structures (8 pts) : Soit la constante MAX et les types Lettre et Mot d´ efinis de la fac ¸on suivante : Constante MAX = 100 Type Lettre =  ’a’..’z’  Type Mot = structure nbLettres : Entier leMot : tableau[1..MAX] de Lettre finstructure 1. Ecrire l’algortihme concatener qui permet de concatener deux mots : Nom : concatener Rˆ ole : concatene deux variables de type Mot Entr´ ee : a,b : Mot Sortie : c : Mot D´ eclaration : i,j : Entier d´ ebut 2 c.nbLettres a.nbLettres+b.nbLettres si c.nbLettres  MAX alors c.nbLettres MAX finsi i 1 pour j 1 ` a a.nbLettres faire c.leMot[i] a.leMot[j] i i+1 finpour j 1 tant que j  b.nbLettres et i  MAX faire c.leMot[i] b.leMot[j] i i+1 j j+1 fintantque fin 2. Ecrire l’algorithme comparer qui permet de comparer deux mots : Nom : comparer Rˆ ole : compare deux variables de type Mot et retourne -1,0 ou 1 Entr´ ee : a,b : Mot Sortie : resultat : Entier D´ eclaration : i : Entier d´ ebut resultat 0 i 1 tant que resultat=0 et i  a.nbLettres et i  b.nbLettres faire si a.leMot[i]  b.leMot[i] alors resultat -1 sinon si a.leMot[i]  b.leMot[i] alors resultat 1 sinon i i+1 finsi finsi fintantque si resultat=0 et a.nbLettres   b.nbLettres alors si a.nbLettres  b.nbLettres alors resultat 1 sinon resultat -1 finsi finsi fin 3. Ecrire l’algorithme estUnPalindrome qui permet de savoir si un mot est un palindrome : Nom : estUnPalindrome Rˆ ole : d´ etermine si un mot est un palindrome Entr´ ee : a : Mot 3 Sortie : resultat : Bool´ een D´ eclaration : i,j : Entier d´ ebut resultat Vrai i 1 j a.nbLettres tant que resultat et i  j faire si a.leMot[i]=a.leMot[j] alors i i+1 j j-1 sinon resultat Faux finsi fintantque fin 4 uploads/Ingenierie_Lourd/ correction.pdf

Tags
Ingénierie entier alors resultat nbelements faire
Documents similaires
  • 24
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager