Fonction récursive
Contents
1. 2009 2010 Formation continue Algorithmique Fonction r cursive Racine carr e 2 E Version it rative du calcul de la racine carr e 0 Fonction racine it Entree A en reel delivre reel 1 Debut variable X en reel X 1 TantQue Abs X X A gt 0 001 Faire X X A X 2 FinFaire delivre X Fin 2 3 4 6 T 3 Ann e univ 2009 2010 Formation continue Algorithmique Fonction r cursive Racine carr e 3 E Version r cursive du calcul de la racine carr e 0 Fonction racine_rec_est Entree A en reel Entree x delivre reel 1 Debut variable res en Reel Si Abs x x A lt 0 001 Alors res X Sinon res racine _rec_est A x A x 2 FinSi delivre res PE LOUP 9 Fin 10 Fonction racine rec Entree A en reel delivre reel 11 Debut 12 delivre racine_rec_est A 1 13 Fin Ann e univ 2009 2010 Formation continue Algorithmique Fonction r cursive Factorielle 1 E On peut crire la factorielle de X par une suite f 1 f n _ On a X f_ Sous cette forme f d pend de f et de n et la suite f n est pas r currente d ordre 1 puisque n inter vient dans le calcul 1 On peut toutefois d finir deux suites n et F avec dr 0 e 1 n 1 ni 1 FET HA ou encore n F 0 1 et n F 1 ni 1 n Fi 1 qui est une suite r currente d ordre 1 E Rappel la factorielle de n not e n vaut 1 2 n 1 n Ann e univ 2009 2010 Formation2. Remarque les instructions Permuter a b et CAN Permuter b a sont strictement quivalentes me m V rifier le bon d roulement du programme en 23 1 compl tant le tableau ci contre Pour chaque cel 8 1 2 lule donnez les valeurs de a b c CD Ann e univ 2009 2010 Formation continue Algorithmique Raisonnement par r currence E Raisonnement par r currence Soit une propri t P sur IN telle que P O est vraie et l implication P n P n 1 Alors P n est vraie pour tout n de IN H Suite r currente Soit un ensemble E on note a une suite d l ments de E telle que f est connue a f a pour n gt 0 et E E La suite a avec n N est une suite r currente On dit qu elle est d ordre 1 si la fonction f ne fait intervenir que a Elle est enti rement d termin e pour tout n de IN Ann e univ 2009 2010 Formation continue Algorithmique Fonction r cursive Racine carr e 1 E La valeur de la racine carr e d un nombre A peut tre appro xim e en employant la suite r currente d ordre 1 suivante X 1 X X HAI Xn Une valeur convenable est atteinte lorsque X A lt o est une valeur tr s faible E Racine de 4 on obtient x 1 x 1 4 1 2 2 5 x 2 5 4 2 5 2 2 05 x 2 05 4 2 05 252 000609756 E Racine de 9 on obtient x 1 x 1 9 1 2 5 x 5 9 5 2 3 4 x 3 4 9 3 4 2 3 023 x 3 023 9 3 023 2 3 00008745 Ann e univ
3. continue Algorithmique Fonction r cursive Factorielle 2 E crire l algorithme de la fonction factorielle en employant la r cursivit Ann e univ 2009 2010 Formation continue Algorithmique Fonction r cursive Factorielle 3 0 Fonction factorielle rec Entree n en Entier delivre Entier 1 Debut 2 variable fn en Entier 3 Si n 0 OU n 1 Alors 4 fn 1 5 Sinon 6 fn n factorielle rec n 1 T FinSi 8 delivre fn 9 Fin Ann e univ 2009 2010 Formation continue Algorithmique Fonction r cursive Suite de Fibonacci E Soit la suite d finie par suite r currente d ordre 2 f U 1 0 1 a Md ii A On a les valeurs 1 1 2 3 5 8 13 21 34 Algorithme na f 0 Fonction fibonacci Entree n en Entier delivre Entier 1 Debut variable res en Entier Si n 0 ou n 1 Alors res 1 Sinon res fibonacci n 1 fibonacci n 2 FinSi delivre res 2 3 4 J 6 T 8 9 Ann e univ 2009 2010 Formation continue Algorithmique Suite de Fibonacci Solution na ve Fib 3 Fib 2 Fibonacci 5 Fibonacci 4 P gt PARA 5 NONE pe me on Fibonacci 1 Fibonacci 6 Fibonacci 2 Fibonacci 2 Ea T _ P gt gt EE Fibonacci 7 Fibonacci 4 Fibonacci 2 _p Fibonacci 2 lt En Fibonacci 3 Fibonacci 1 gt Fibo
4. poids autoris de la cabine serait d pass Remarque au sein du programme nous sommes oblig s de g rer le poids de la cabine Ann e univ 2009 2010 Formation continue Algorithmique Fonctions Corrig s E 1 Fonction poidsTotalAutorise Entree poidsActuel en Reel Entree poidsPassager en Reel delivre booleen 2 Debut 3 delivre poidsActuel poidsPassager lt 300 4 Fin E 0 Programme ascenseur d claration de la fonction poids TotalAutorise 5 Debut G variable cage passager en Reel re cage 0 8 passager 0 9 TantQue poidsTotalAutorise cage passager Faire 10 cage cage passager a passager lecture 12 FinFaire 13 ecriture portes fermees 14 Fin Ann e univ 2009 2010 Formation continue Algorithmique Une unique information d livr e par une fonction E est possible de d finir galement des param tres de sor ties en employant le mot clef correspondant Sortie E Exemple 0 fonction caractRectangleA Entree L en Reel Entree H en Reel Sortie aire en Reel Sortie perimetre en Reel 1 Debut 2 aire L H 3 perimetre L H 2 4 Fin 0 fonction caractRectangleB Entree L en Reel Entree H en Reel Sortie aire en Reel delivre Reel 1 Debut 2 variable perimetre en Reel 4 perimetre L H 2 3 aire L H 5 delivre perimetre 6 Fin H Un param tre effectif de sortie doit tre une variable Ann e univ 2009 2
5. 010 Formation continue Algorithmique Gestion de la cabine d ascenseur suite E 1 Fonction poidsTotalAutorise Entree ancienPoids en Reel Entree poidsPassager en Reel Sortie nouveauPoids en Reel delivre booleen 2 Debut 3 nouveauPoids poidsActuel 4 Si poidsActuel poidsPassager lt 300 Alors D nouveauPoids nouveauPoids poidsPassager 6 delivre Vrai 7 Sinon 8 delivre Faux 9 FinSi 10 Fin E 0 Programme ascenseur 11 Debut 12 variable cage passager cageMaj en Reel 13 cage 0 14 passager 0 15 TantQue poidsTotalAutorise cage passager cageMa j Faire 16 cage cageMaj 17 passager lecture 18 FinFaire 19 ecriture portes fermees Ann e univ 2009 2010 Formation continue Algorithmique Des entr es des sorties des entr es sorties E Un param tre peut jouer la fois le r le de param tre d entr e et de sortie Le param tre effectif correspondant est alors n cessairement une variable initialis e pour que son r le de sortie puisse tre accompli E Exemple Fonction doubler Entree Sortie x en Reel Debut X gt XT2 Fin E Exercice crire un programme permettant de saisir trois r els variables a b c et suite plusieurs appels une fonction permuter permettant d changer les valeurs de deux variables conduit avoir a lt b lt c quelles que soient les valeurs saisies Ann e univ 2009 2010 Formation continue Algo
6. Formation continue Fonctions et proc dures Herv Locteau Universit de Nancy 2 locteau loria fr L int r t des fonctions et des proc dures E Regrouper un ensemble d instructions au sein d un m me algorithme afin de pouvoir y faire appel autant de fois que n cessaire Int r t lisibilit et identification des erreurs r utilisation E On distingue la d finition d une fonction de son appel son utilisation E est inutile de conna tre comment est d finie une fonction une proc dure pour pouvoir y faire appel Par contre il est n cessaire de conna tre sa d claration son manuel d utilisation E Quel est son r le Quels sont les arguments fournir Quel est la valeur retourn e signification type Ann e univ 2009 2010 Formation continue Algorithmique Fonctions versus Proc dures On effectue parfois la distinction entre les fonctions et les proc dures l image des fonctions math matiques une valeur est retourn e par les fonctions algorithmiques l inverse des proc dures E Exemples ecriture bonjour constitue un appel la proc dure ecriture on lui fournit en param tre la valeur d une cha ne de caract res aucune valeur n est retourn e A lecture constitue un appel la fonction lecture aucun argument est fourni mais on crit les parenth ses syst matiquement une valeur est retourn e E On utilisera le terme fonction
7. indiff remment Ann e univ 2009 2010 Formation continue Algorithmique D finition d une fonction E Une fonction peut avoir aucun un ou plusieurs param tres E Exemple Fonction nf Entree a en Entier Entree b en Chaine delivre Reel 1 Debut variables res en Reel 3 za 2 delivre res Fin E 1 d claration prototype 2 corps 3 d finition d claration corps E Correspond la d finition d une fonction identifi e par le nom nf E Cette fonction admet deux param tres le premier doit tre un entier tandis que le second est une cha ne de caract re E Cette fonction retourne la valeur r elle d une variable E Le corps de la fonction constitue un algorithme dans lequel les variables a et b sont disponibles Ann e univ 2009 2010 Formation continue Algorithmique Fonction utilisateur Exemple complet 0 Programme SuiteArithmetique 1 Fonction terme Entree rang en Entier Entree raison en Entier Entree terme0 en Entier delivre Entier 2 Debut 3 variable val en Entier 4 val terme0 raison rang D delivre val 6 Fin 7 Debut 8 variable N u0 uN r en Entier 14 Pour N dans 0 10 Faire 9 ecriture Premier terme 15 uN terme N r u0 10 uO lecture 16 ecriture UN 11 ecriture Raison 17 ecriture 12 r e lecture 18 FinFaire 13 ecriture termes u0 u10 19 ecriture n Remarque les valeurs de N r e
8. nacci 4 Fibonacci 5 J Fibonacci 3 Fibonacci 2 gt Fibonacci 3 gt Ann e univ 2009 2010 Formation continue Algorithmique Suite de Fibonacci Solution lin aire E Principe transmettre deux valeurs cons cutives Algorithme 0 Fonction Fibo rec Entree rang en Entier Entree moins2 en Entier Entree moins1 en Entier delivre Entier 1 Debut 2 variable res en Entier 3 Si rang 0 ou rang 1 Alors 4 res moinsi 5 Sinon 6 res Fibo_rec rang 1 moins1 moins1 moins2 7 FinSi 8 Fin 9 Fonction Fibo Entree rang en Entier delivre Entier 10 Debut 11 delivre Fibo rec rang 1 1 12 Fin m crire quels sont les appels successifs Fibo_ rec pour Fibo 7 Ann e univ 2009 2010 Formation continue Algorithmique Suite de Fibonacci D roulement Fibo 7 gt Fibo_rec 7 1 1 gt Fibo_rec 6 1 1 1 gt Fibo_rec 5 2 1 2 gt Fibo rec 4 3 2 3 gt Fibo rec 3 5 3 5 gt Fibo rec 2 8 5 8 gt Fibo_rec 1 13 8 13 Ann e univ 2009 2010 Formation continue Algorithmique
9. rithmique Gestion de la cabine d ascenseur fin 1 Fonction poidsTotalAutorise Entree Sortie PoidsCabine en Reel Entree poidsPassager en Reel delivre booleen 2 Debut 3 Si PoidsCabine poidsPassager lt 300 Alors 4 PoidsCabine PoidsCabine poidsPassager D delivre Vrai Il faut m moriser ces valeurs ou les renvoyer 6 Sinon 7 imm diatement Apr s le FinSi nous ne T delivre Faux savons plus si PoidsCabine a t mis jour et 8 FinSi dji delivre PoidsCabine lt 300 y est toujours Vraie 9 Fin 0 Programme ascenseur 10 Debut LL variable cage passager en Reel 12 cage 0 13 passager 0 14 TantQue poidsTotalAutorise cage passager Faire 15 passager lecture 16 FinFaire 17 ecriture portes fermees 18 Fin Ann e univ 2009 2010 Formation continue Algorithmique Trier les valeurs de trois variables 0 Programme triVariables 1 Fonction Permuter Entree Sortie x en Reel Entree Sortie y en Reel 2 Debut 3 variable z en Reel 4 Z Y 5 Y Xx G X Z 7 Fin 8 Debut 9 variable a b cen Reel 17 Si a gt c Alors 10 a lecture 18 Permuter a c 11 b lecture 19 FinSi 12 c lecture trouver la bonne valeur de b trouver la bonne valeur de a et donc galement de c 14 Si a gt b Alors 20 Si b gt c Alors 15 Permuter a b 21 Permuter b c 16 FinSi 22 FinSi _ _ 23 Fi n saisie Instructions LANTA PLANTE 200 21241825
10. t uO sont transmises pas les variables Ann e univ 2009 2010 Formation continue Algorithmique Param tres d une fonction E Dans sa d claration ils sont appel s param tres formels E Au sein d un appel ils sont appel s param tres effectifs chaque param tre formel correspond un param tre effectif de m me type E Le nom d un param tre effectif peut tre diff rent de celui du param tre formel associ E Exemple Soit la d claration Fonction Somme Entree a en Entier Entree b en Entier delivre Entier Soit un algorithme pour lequel nous disposons des variables a b c d variables a b c d en Entier Nous pouvons avoir les appels suivants Somme a b ou Somme b a ou Somme a a ou Somme a c d Ann e univ 2009 2010 Formation continue Algorithmique Fonctions Exercices E crire la fonction poidsTotalAutorise qui accepte en entr e deux r els et retourne un bool en Le premier param tre concerne le poids actuel des passagers d un ascenseur le second celui d un nouveau passager La valeur de retour de cette fonction doit tre Vrai si le poids total avec ce nouveau passager est inf rieur 300 kg Faux sinon E crire le programme faisant appel cette fonction au sein d une boucle o une lecture clavier permet de saisir le poids d un passager On sortira de la boucle avec l affichage por tes ferm es en refusant l acc s au passager pour lequel le
Download Pdf Manuals
Related Search