Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université Oran 1 1eme LMD/MI/S2 Faculté Des Sciences Exactes et Appliquées Dép

Université Oran 1 1eme LMD/MI/S2 Faculté Des Sciences Exactes et Appliquées Département d’informatique Module :ASD2 2019 /2020 Corrigé de la fiche sur la Récursivité 1 Corrigé de la Fiche de TD Récursivité Exercice 1 a) Déroulez les procédures récursives suivantes pour k=6 : Procédure test (↓k : entier) Début Si (k≥0) alors test (k-1); Écrire (k); fsi;Fin; Procédure essai (↓k : entier) Début Si (k≥0) alors Écrire (k); essai (k-1) ; fsi ;Fin ; Déroulement : Procédure Test : La descente : 1er appel test (6) appel test (5) et empiler (6)  appel test (4) et empiler (5) appel test(3) et empiler (4) appel test (2) et empiler (3) appel test (1) et empiler (2) appel test(0) et empiler (1) arrêt Maintenant on dépile et on affiche le contenu de la pile : 1 2 3 4 5 6 Procédure essai 1er appel essai (6)afficher (6) et appel essai (5)afficher (5) et appel essai (4) afficher (4) et appel essai (3) afficher (3) et appel essai (2) afficher (2) et appel essai (1) afficher (1) et appel essai (0)  arrêt Onaffiche : 6 5 4 3 2 1 b) L’affichage est croisant pour test car la récursivité est non terminale. Par contre il est décroissant dans essai car la recursivité est terminale c) tester (19) tester (9), empiler (1)  tester (4) ; empiler (1) ;  tester (2) ; empiler (0)  tester (1) ; empiler(0)  tester (0) ; empiler (1) Dépiler et afficher : 10011 = 19 en binaire tester (13) tester (6), empiler (1)  tester (3) ; empiler (0) ;  tester (1) ; empiler (1)  tester (0) ; empiler(1) Dépiler et afficher : 1101 = 13 an binaire La procédure tester est non terminale d) Déroulez la fonction récursive suivante et dites ce qu’elle fait fonction produit(n:entier, x :entier) : entier Début si (n > 0) alors ecrire("avant appel", n,x); produit  produit(n - 1, x) + x; ecrire ("apres appel :" , n,x);} sinon produit  0; fsi, fin Début n = 8, x = 5; écrire (n, ’*’, x, ‘=’,produit(n, x)); Université Oran 1 1eme LMD/MI/S2 Faculté Des Sciences Exactes et Appliquées Département d’informatique Module :ASD2 2019 /2020 Corrigé de la fiche sur la Récursivité 2 fin. 1er appel Produit (8,5); Elle fait le produit de n*x. L’instruction ecrire ("apres appel :" , n,x); dans la fonction produit n’est jamais exécutée. Exercice 2 a) Écrire une fonction itérative qui renvoie le reste de la division euclidienne d'un entier a par un entier b en utilisant les soustractions successives. Fonction q_it (a,b :entier) :entier Début S :entier ; S0 ; Tque a≤b faire aa-b ; s s+1 ; ftque q_it s ; fin b) Donner la fonction récursive correspondante. Fonction q_rec (a,b :entier) :entier Début Si a<b alors q_rec 0 ; Sinon Université Oran 1 1eme LMD/MI/S2 Faculté Des Sciences Exactes et Appliquées Département d’informatique Module :ASD2 2019 /2020 Corrigé de la fiche sur la Récursivité 3 q_rec  q_rec (a-b,b)+1 ; fsi fin Exemple : a=8 et b=3 Il s’agit d’une fonction non terminale, donc il y a une descente et une remontée. La descente nous permettra de faire les appels (flèches en bleues). Une fois avoir atteint le point d’arrêt, on remonte pour effectuer les calculs (flèches en rouges). Pour notre exemple, le resultat=2. Exercice 3 Fonction binomial(n : entier, p : entier) : entier Début Si (p = 0 ou p = n) alors Retourner 1 ; Sinon Retourner binomial(n – 1, p) + binomial(n – 1, p – 1) ; FinSi ; Fin Exercice 4 /*version 1 La forme itérative*/ Fonction premierc(n :entier) :entier Debut Variables i, S :entier; S←O; Pour i de 1 à n faire 1er appel q_rec (8,3) •2= 1+ q_rec( (5,3) •2= 1+ q_rec (2,3) 0 •1= Université Oran 1 1eme LMD/MI/S2 Faculté Des Sciences Exactes et Appliquées Département d’informatique Module :ASD2 2019 /2020 Corrigé de la fiche sur la Récursivité 4 S←S+(i*i) ; Fin pour Retourner S ; Fin Algorithme principal Variables A, Som : entier ; Debut Ecrire (‘Donnez la valeur de A :’) Som← premierc(A) ; /* appel de la fonction*/ Ecrire (‘la somme est :’,Som) ; Fin /*version2 La forme récursive */ Fonction premiercrecu(n :entier) :entier Debut Si n=1 Alors retourner 1 /* critère d’arrêt */ Sinon si n > 1 Alors retourner (n*n)+ premiercrecu(n-1) Finsi Finsi Fin Algorithme principal Variables A, Som : entier ; Debut Ecrire (‘Donnez la valeur de A :’) Som← premiercrecu (A) ; /* appel de la fonction récursive par le programme principal */ Ecrire (‘la somme est :’, Som) ; Fin Exercice 5 Procédure Tour_Mehdi ( ↓n : entier) Debut Si (n=0) Alors Ecrire("Salim a gagné!"); Sinon Tour_Salim(n-1); Fsi; Fin. Procédure Tour_Salim ( ↓n : entier) Debut Si (n=0) Alors Ecrire("Mehdi a gagné!"); Sinon Si (n mod 2 = 0) Alors Tour_Mehdi(n-2); Sinon Tour_Mehdi(n-1) Fsi; Université Oran 1 1eme LMD/MI/S2 Faculté Des Sciences Exactes et Appliquées Département d’informatique Module :ASD2 2019 /2020 Corrigé de la fiche sur la Récursivité 5 Fsi; Fin  Les deux procédures s'appellent mutuellement → il s'agit de procédures Récursives Croisées (indirecte) Exercice Supplémentaire : Fonction Truc (n : Entier) : Entier Début X : Entier ; Si (n<10) alors Truc  n*n Sinon X  n mod 10 ; Truc  X*X+ Truc (n div 10) Fsi ; Fin. 1-Que fait la fonction Truc ? 2- Quelle est la nature de la récursivité. Correction  la fonction Truc calcule la somme des carrés des chiffres d’un entier n donné. Ex : N= 142 alors Truc= 12+ 42+22 .  La nature de cette récursivité est non terminale car il ya des traitements à faire dans la phase de remontée (calcul de X*X) donc l’appel récursif ne termine pas la fonction. uploads/s1/ corrige-fiche-recursivite.pdf