Récursivité Récursivité
Une fonction est récursive si elle s'appelle elle- à ce que le problème avec la solution triviale puisse ... Récursivité: Fibonacci et Hanoï.
Exercices sur la technique diviser pour régner Chapitre 7 ÉNONCÉS
b) Sachant que la solution générale de l'équation de récurrence. T (n) ? { l'efficacité de la partie non récursive de l'algorithme ?
Calcul des nombres de Fibonacci [cx03] - Exercice
Calcul des nombres de Fibonacci [cx03] - Exercice 1.3 Algorithme récursif terminal . ... Validez votre fonction avec la solution. Solution Python.
IFT2015 5 Techniques de récursion
Sept 27 2011 avec solution T(n) = ?(2n). 5.2 Récursion terminale. On peut toujours transformer une boucle en un algorithme récursif ... Exercice 5.1.
Récursivité des actions [rc] Exercices de cours
Exercices de cours Déduisez une fonction récursive factoriel(n) qui calcule et renvoie le factoriel de n ... Validez votre algorithme avec la solution.
Exemples dalgorithmes récursifs 1 Des exercices sur les suites
Par exemple algo1Rtrous.sce désigne la traduction de l'algorithme 1 sous SCILAB
Corrigé de la Fiche de TD Récursivité Exercice 1
écrire (n '*'
Calcul des nombres de Fibonacci [cx03] - Exercice
1.3 Algorithme récursif terminal . Cet exercice analyse la complexité de la suite de Fibonacci. ... Validez votre fonction avec la solution.
Puissance ni`eme dun nombre [rc02] - Exercice
Validez votre algorithme avec la solution. Solution alg. @[pgpuissance.alg]. Algorithme pgpuissance. Variable x : Réel. Variable n : Entier.
SUJET + CORRIGE
Jun 16 2014 Le but de l'exercice est l'écriture d'un algorithme de tri de tableaux ... La figure 1 montre qu'un même tableau peut être dessiné avec des ...
Récursivité - AlloSchool
1 Algorithmes récursifs 1 1La multiplication du paysan russe La méthode du paysan russe est un très vieil algorithme de multiplication de deux nombres entiers déjà décrit (sous une forme légèrement di?érente) sur un papyrus égyptien rédigé vers 1650 av J -C Il s’agissait de la
Corrigés des exercices sur les fonctions récursives
Corrigés des exercices sur les fonctions récursives Exercice 7 1 1 sous-programmes récursifs Pour chacun des sous-programmes nous donnerons les paramètres en précisant le paramètre sur lequel porte la récurrence le cas de base (valeur de ce paramètre pour lequel le calcul s’arrête) et la
Algorithmique et Programmation 1 Feuille de TD La récursivité
Exercice 2 Élever un nombre ?ottant à une puissance entière 1 ÉcrireenCamlunefonctionquiàpartird’unentierpositifnetd’un?ottantxrenvoielavaleurde x n Avantd’écrirecettefonctionélaborerunalgorithmequicalculecettevaleurdefaçonrécursive
Comment définir un algorithme récursif?
Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même. Dans le cadre de ce cours, nous ne nous intéresserons qu’aux programmes et algorithmes récursifs. Mais la notion de définition récursive est beaucoup plus générale : en mathématiques : définition de l’exponentielle : ? x ? R, f 0 ( x) = f ( x) et f (0) = 1.
Qu'est-ce que la récursivité solution?
Fiche TD N° 01.2 : La Récursivité solution . 1. Qu’est ce que la récursivité ? Tout objet est dit récursif s’il se définit à partir de lui-même Ainsi, une fonction est dite récursive si elle comporte, dans son corps, au moins un appel à elle-même 2.
Quel est l’algorithme d’une fonction récursive de dérivation?
Voici (une esquisse) de l” algorithme d’une fonction récursive de dérivation (nommée ici derivee ). sinon si … 2.2.4. Exemple 3 : Les tours de Hanoï ¶ Et voici un algorithme récursif pour résoudre le problème des tours de Hanoi. Cet algorithme est celui d’une fonction nommée hanoi à trois paramètres
Comment prouver la terminaison d'un algorithme récursif ?
Dans le cas des algorithmes récursifs, ces méthodes sont spécifiques. Pour prouver la terminaison d'un algorithme récursif, la méthode la plus usuelle est la suivante: chacun des ensembles dans lesquels les paramètres prennent leurs valeurs sont équipés d'une relation d'ordre.
Parcours :Licence LIMI201 & LIMI211
Code UE :J1MI2013Epreuve :Algorithmes et ProgrammesDate :Lundi 16 juin 2014Heure :16 heures 30
Duree :2 heures
Documents : non autorisesEpreuve de M. AlainGriffaultCollegeSciences
etTechnologiesSUJET + CORRIGEAvertissement
A chaque question, vous pouvez au choix repondre par un algorithme ou bien par un programme python. Les inden tationsdes f onctions ecritesen Pythondoivent ^etre res- pectees. L'espace laiss ep ourles r eponsese stsusan t(sauf si v ousutilisez ces feuilles comme brouillon, ce qui est fortement deconseille).QuestionPointsScoreLe tri par tas28
Suite de Padovan12
Total:40
Exercice 1 : Le tri par tas (28 points)
Le but de l'exercice est l'ecriture d'un algorithme de tri de tableaux base sur la notion detas. Les questions se suivent logiquement, mais beaucoup sont independantes. (a) Des fonctions elementairesp ourse d eplacerdans un tableau. indice01234567T[indice]52601915
(a) Vision tabulaire[0] : 5 [1] : 2 [3] : 0 [7] : 5[4] : 1[2] : 6 [5] : 9[6] : 1 (b) Vision arborescenteFigure1 { Deux vues dierentes d'un m^eme tableau
La gure 1 montre qu'un m^eme tableau peut ^etredessineavec des casescontigues, ou bien avec des cases
disperseesdans unearborescence. Avec la vuecontigue, on utilise generalement une variableiquiparcourt
les indices du tableau. Avec la vuearborescente, on peut evidemment utiliser une variableiquiparcourtles
indices du tableau, mais on utilise egalement trois fonctions qui permettent de suivre lesliens bidirectionnels
(reels ou virtuels) de l'arborescence: {gauche(indice)represente les lienspointille du haut vers le basde l'arborescence. Par exemple, dans la gure 1b,gauche(1)=3,gauche(4)=9etgauche(2)=5. {droite(indice)represente les liensen trait plein du haut vers le basde l'arborescence. Par exemple, dans la gure 1b,droite(1)=4,droite(3)=8etdroite(0)=2. {pere(indice)represente les liensdu bas vers le hautde l'arborescence. Par exemple, dans la gure 1b,pere(4)=1,pere(7)=3etpere(2)=0. Par contrepere(0)n'est pas deni, et sa valeur (null,-1,0,...) importe peu car jamais utilisee dans cet exercice. UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014Voici un algorithme et un programmePython, de complexites en temps et en espace de (1), possibles pour
la fonctiongauche(indice).Gauche(i){
retourner 2*i+1; }defgauche( i ): return2i+1 i. (1 p oint) Ecrire un programmePythonou un algorithmedroite(i)qui retourne un entierdtel qu'il existe un lienen trait plein du haut vers le basreliant les indicesiad. Les complexites en temps et en espace doivent ^etre en (1).Solution:
defdroite ( i ): return2( i+1)ii.(1 p oint) Ecrire un programmePythonou un algorithmepere(i)qui retourne un entierptel qu'il existe un liendu bas vers le hautreliant les indicesiap. Les complexites en temps et en espace doivent ^etre en (1).Solution:
defpere ( i ): return( i1)//2(b)Construction d'un tas apartir d'un tab leau.Denition 1Un tas est un tableau d'entiers tel que pour tous les indicesistrictement positifs, la valeur
deT[i]est inferieure ou egale a celle deT[pere(i)]Le but de cette partie de l'exercice est d'eectuer la transformation representee par la gure 2.[0] : 5
[1] : 2 [3] : 0 [7] : 5[4] : 1[2] : 6 [5] : 9[6] : 1 (a) Vue arborescente du tableau initial[0] : 9 [1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 6 [5] : 5[6] : 1 (b) Tas obtenu par constructionFigure2 { Construction d'un tas
i. (3 p oints) Ecrire un programmePythonou un algorithmeestunTas(T)qui retourneVraisi le tableauTest un tas,Fauxsinon.
La complexite en temps doit ^etre en
(1);O(n) avecn=longueur(T), et celle en espace doit ^etre en (1).Solution:
defestUnTas(T): foriinrange (1 , len (T)): ifT[ pere ( i )]Solution:
defmaximum(T, i , limite ): assert(0<=iandiT[ i ] = T[ j ]
T[ j ] = aux
Completer l'arborescence avec les valeurs du tableau apres l'appelentasserRecursif(T,0,8)Solution : [0] : 5 [1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 9 [5] : 6[6] : 1 (a) Avant entasser[0] : 9 [1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 6 [5] : 5[6] : 1 (b) Apres entasserFigure3 { Entasser(T,0,8)iv.(3 p oints)La fonction entasserRecursif(T,i,limite)est recursive terminale.
Ecrire un programmePythonou un algorithme iteratifentasser(T,i,limite)equivalent.Solution:
defentasser (T, i , limite ): iMax = maximum(T, i , limite ) whileiMax!= i : echange (T, i , iMax) i = iMaxiMax = maximum(T, i , limite )v.(1 p oint)Donner les complexit esen tem pset en espace (meilleur des cas e tpire des cas) d ev otre
algorithmeentasser(T,i,limite).Page 3 sur 7
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014Solution:
Les complexites sont :
en temps en (1) ;O(log2(n)) avecn=longueur(T),en espace en (1). vi.(4 p oints)L'algorithme entasser(T,i,limite)echange des valeurs du tableau de haut en bas,en
suivant une branche de l'arborescence. Cela a pour eet de fairedescendredes petites valeurs, et defairemonterles grandes valeurs. Il est donc possible de construire un tas, en iterant cet algorithme sur
les indices decroissants du tableau. En utilisantentasserRecursif(T,i,limite)ouentasser(T,i,limite), ecrire un programmePython ou un algorithmeconstruireTas(T)qui transforme un tableau en un tas.Solution:
defconstruireTas (T): #for i in range( len (T)1,1,1): peut etre optimise en foriinrange (( len (T)1)//2,1,1):entasser (T, i , len (T))vii.(1 p oint)Donner les complexit esen temps et en espace ( meilleurdes cas et pire des cas) de v otre
algorithmeconstruireTas(T).Solution:
Si l'on utilise l'algorithme iteratif pourentasser, les complexites sont : en temps en ( n) siTest deja un tas,O(nlog2(n)) avecn=longueur(T), en espace en (1). (c)T rid'un tas.Le but de cette partie de l'exercice est d'eectuer la transformation representee par la gure 4.[0] : 9
[1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 6 [5] : 5[6] : 1 (a) Tas initial[0] : 0 [1] : 1 [3] : 2 [7] : 9[4] : 5[2] : 1 [5] : 5[6] : 6 (b) Vue arborescente du tableau trieFigure4 { Tri d'un tas
i. (4 p oints)Dans un tas, la v aleurmaximale est ala racine de l'arborescence, donc enT[0]. Dans le tableau trie, cette valeur doit ^etre enT[len(T)-1]. Il sut donc d'echanger ces deux valeurs pourprogresser vers la solution. Une fois cette echange fait, si l'on exclut la derniere valeur du tableau, le tas
est peu change. En faitentasser(T,0,len(T)-1)va creer un nouveau tas pour les valeurs du tableau dont les indices sont inferieurs alimite = len(T)-1. Il sut donc d'iterer ces deux etapes (echange, entasser) pour trier un tas. Ecrire un programmePythonou un algorithmetrierTas(T)qui transforme un tas en un tableau trie en ordre croissant.Solution:
deftrierTas (T): foriinrange ( len (T)1,0,1): echange (T,0 , i ) entasser (T,0 , i )Page 4 sur 7 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014 ii. (1 p oint)Donner les complexit esen temps et en espace (meilleur des cas et pire d escas) de v otre algorithmetrierTas(T).Solution:
Si l'on utilise l'algorithme iteratif pourentasser, les complexites sont : en temps en ( n) si toutes les valeurs deTsont egales,O(nlog2(n)) avecn=longueur(T), en espace en (1). (d)T rid'un tableau al'aide de tas. i. (3 p oints) Ecrire un programmePythonou un algorithmetriParTas(T)qui trie un tableau d'entiers Ten construisant d'abord un tas, puis en le triant.Solution:
deftriParTas (T): construireTas (T)trierTas (T)ii.(1 p oint)Donner les complexit esen temps et en espace (meilleur des cas et pire d escas) de v otre
algorithmetriParTas(T).Solution:
Si l'on utilise l'algorithme iteratif pourentasser, les complexites sont :quotesdbs_dbs22.pdfusesText_28[PDF] algorithme récursif exemple
[PDF] fonction recursive langage c
[PDF] fonction récursive exercice corrigé
[PDF] recursivite java
[PDF] la récursivité en algorithme exercice corrigé
[PDF] leo traduction
[PDF] récursivité python exercices corrigés
[PDF] exercices récursivité python
[PDF] récursivité algorithme exercice corrigé
[PDF] écrire un discours en allemand
[PDF] variable réelle définition économie
[PDF] carte shom pdf
[PDF] instructions nautiques pdf
[PDF] carte marine shom gratuite