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
RECURSIVITE Exercices - Corrigés
Exercice 3 – Le compte est-il bon ? Ecrire une fonction Python « compte_a » qui reçoit comme argument une chaîne de caractères (éventuellement vide) et renvoie
TP 2 – Récursivité –Corrigé
Exercice 6 : Diagonale de Cantor. On initialise avec le numéro de (00)
Devoir maison 1 - Corrigé
Devoir maison 1 - Corrigé. M2 AIGEME année 2008-2009. Exercice 1. 1. On souhaite écrire une fonction récursive qui calcule le carré d'un entier. Pour trouver
TD de Logique 9 (Fonctions récursives)
26/11/2012 Les exercices qui ne sont pas abordés en cours seront (certainement) corrigés sur ma page personelle (voir ci-dessus). (✠) Exercice 1 ( ...
Travaux dirigés 11 : fonctions fonctions récursives 1 Fonctions
l'exercice. 1. 3. Page 4. int McCarthy(int x). { if (x > 100). { return (x-10); Il est nécessaire que ce soit corrigé en TD ou en TP. Si les étudiants sont ...
EXERCICES 1 :
11/04/2021 EXERCICE N°01 : (10.00 POINTS). Soit G une grammaire définie par G= ({A F} ... Gest récursive gauche (cas de la récursivité gauche indirecte).
Travaux Dirigés dalgorithmique no4
Écrire une fonction récursive qui calcule la somme de nombres de 1 a n si n > 0 et renvoie 0 sinon. Exercice 4. Donner un algorithme récursif pour calculer xn
Langage C : énoncé et corrigé des exercices IUP GéniE
Cette f onction donne l e mêm e résu l tat q ue l a f onction est-/acteur m ais est récursive. Exercice 18 On util isera l es t y pes suivants : t y pedef char
Corrigé de la Fiche de TD Récursivité Exercice 1
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
RECURSIVITE Exercices - Corrigés
RECURSIVITE. Exercices - Corrigés. Exercice1 - Un calcul très classique. Ecrire une fonction Python qui calcule la somme des inverses des carrés des n
Corrigés des exercices sur les fonctions récursives
Corrigés des exercices sur les fonctions Exercice 7.1.1 sous-programmes récursifs ... variation qui affecte le paramètre à chaque appel récursif.
Récursivité 1 Exercices
Récursivité. 1 Exercices. 1.1 Généralités sur les algorithmes récursifs. Exercice 2-1 Que calcule fact ? Question 1. Voici quelques lignes de code :.
SUJET + CORRIGE
SUJET + CORRIGE. Avertissement Exercice 1 : Récursivité ... Écrire une fonction python récursive terminale combRecAux(np
Récursivité
RÉCURSIVITÉ. Exercice 6.- (Nombres de Fibonacci). ´Ecrire une fonction C utilisant un algorithme récursif
La récursivité
Cliquez sur l'exercice pour y accéder. Maximum de trois entiers en récursif. Fonction ensureRange. Nombre intermédiaire entre trois entiers. Dis « Bonjour ! ».
TD 1 – Fonctions récursives primitives
Solution de l'exercice 1. On va montrer que les singletons sont récursifs primitifs car leur fonction caractéristique est récursive primitive.
Récursivité 1 Exercices - Nanopdf
Récursivité. 1 Exercices. 1.1 Généralités sur les algorithmes récursifs. Exercice 2-1 Que calcule fact ? Question 1. Voici quelques lignes de code :.
A.1 Quelques exercices corrigés
A.1 Quelques exercices corrigés. 1. 33. Mettre sous forme normale de Chomsky la grammaire définie Eliminer la récursivité gauche de la grammaire ETF.
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
Récursivité - Exercices
Récursivité 1 Contenududocumentettravailàréaliser – Le documentprésentedes exemples de fonctionsdé?niesdefaçonrécursive – L’objectifestdecomprendrelaprogrammationrécursivedequelquesfonctionspuisdechercheràen écrirepar vous-mêmesquelques-unes
RECURSIVITE Exercices - Corrigés - PanaMaths
RECURSIVITE Exercices - Corrigés Exercice1 - Un calcul très classique Ecrire une fonction Python qui calcule la somme des inverses des carrés des n premiers entiers naturels non nuls On pourra ensuite écrire un script plus complet qui après le calcul précédent évalue et affiche l’écart (en ) avec la limite de cette somme qui vaut
Searches related to récursivité exercices corrigés PDF
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
Exercice 1
On cherche à calculer la somme des entiers de 1 à n avec une fonction somme(n). 1. Écrivez une fonction avec la méthode itérative permettant de répondre au problème. 2. Écrivez une fonction récursive permettant de répondre au problème. 3. Écrivez une fonction permettant de calculer directement le résultat sans boucle ni récursion. 4.Faites le bilan...
Exercice 2
On cherche à calculer la somme des éléments d'une liste (un tableau). 1. Écrivez une fonction avec la méthode itérative permettant de répondre au problème. 2.Écrivez une fonction récursive permettant de répondre au problème. On rappelle que le premier élément d'une liste L se note L[0] et que le reste de la liste se note L[1:].
Exercice 3
Ici, on veut savoir si une chaîne de caractère est un palindrome, c'est à dire lue indifféremment de la gauche vers la droite et de la droite vers la gauche. 1. Écrivez une fonction récursive permettant de répondre au problème. On notera qu'on accède au premier élément d'une chaîne s avec s[0] et au dernier avec s[-1]. La chaine amputée de ses deux...
Exercice 5
Nous allons dessiner le fractal de Von Koch avec le module turtle. Nous allons avoir besoin de la récursivité. Nous dessinerons ensuite le flocon de Von Koch. 1. Créez une fonction récursive qui permet de dessiner le fractal de Kosh ci-dessous. Sont dessinés les fractal d'ordre 0, 1 et 2. La fonction de Koch prendra comme argument la longueur du se...
Comment faire une fonction récursive ?
1. Écrivez une fonction récursive donnant le quotient de la division euclidienne de n par d sachant que ce quotient est le même que celui de (n -d) par d, plus 1. Faites attention au cas de base. 2. Écrivez une fonction récursive donnant le reste de la division euclidienne de n par d sachant que ce reste est le même que celui de (n - d) par d.
Comment calculer une somme récursive?
# La fonction récursive pour le calcul de la somme proprement dit. def sum_sq_inv(n): if n == 1: return 1 else: return 1/n**2 + sum_sq_inv(n-1) # DEBUT DU SCRIPT # ===============
Comment résoudre les appels récursifs ?
S’assurer que, dans les appels récursifs, ..les arguments sont plus "simples" queceux avec lesquels la fonction a été appelée (ce qui signi?e essentiellement qu’ils« évoluent vers le cas de base ») Reconstituer correctement la valeur de retour de la fonction à partir du résultatdu ou des appels récursifs.
DISVE { LicenceAnn
ee :2011/2012Semestre 2PARCOURS :Licence LIMI201 & LIMI211
UE J1MI2013 :Algorithmes et Programmes
Epreuve :Devoir Surveille Terminal
Date :Lundi 11 juin 2012
Heure :8 heures 30
Duree :1 heure 30
Documents : non autorises
Epreuve de M. AlainGriffaultSUJET + CORRIGE
Avertissement
{ La plupart des questions sont independantes. { Le sujet est sans doute un peu long. { Les indentations des fonctions ecrites enPython doivent ^etre respectees. { L'espace laisse pour les reponses est susant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement deconseille).QuestionPointsScoreRecursivite9
Le tri par base11
Variante tri rapide10
Complexite10
Total:40
Exercice 1 : Recursivite (9 points)
Le nombre de combinaisonsCpnrepresente le nombre de sous-ensembles de cardinalpd'un ensemble de cardinaln. Il est deni parCpn= 1 sip= 0 ou sip=n, et parCpn=Cp1 n1+Cp n1dans le cas general. Une propriete interessante pour calculer les combinaisons est :Cpn=nCp1 n1p (a) Soit la fonctioncombRec(n,p)ounetpsont deux entiers positifs tels quepn. defcombRec(n,p): if(p == 0orn == p): return1 else: returnncombRec(n1,p1) // p i. (11=2points) Completer le tableau suivant pour simuler la pile d'execution lors de l'appel
combRec(7,3).Solution: appels successifs x combRec515 combRec6215 combRec7335 fonctionnpretour? UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 Soit les fonctionscombRecV2(n,p)etcombRecUV(n,p,u,v)ounetpsont deux entiers positifs tels quepn, etuetvdeux parametres supplementaires. defcombRecUV(n,p,u,v ): if(p == 0orn == p): return1 else: returnncombRecUV(n1,p1,un,vp) // p defcombRecV2(n,p): returncombRecUV(n,p,1 ,1) ii. (11=2points) Completer le tableau suivant an de simuler la pile d'execution lors d'un
appel acombRecV2(7,3).Solution: combRecUV514265 combRecUV627315 combRecUV731135 combRecV27335 fonctionnpuvretour? dans le second tableau, la valeur uv lors du dernier appel recursif est egal au resultat nal. C'est donc qu'il est inutile de propager le resultat jusqu'a l'appel initial. Ecrire une fonction python recursive terminalecombRecAux(n,p,u,v)qui calcule le nombre de combinaisonsCpn, et preciser l'appel initial a cette fonction dans une fonction python combRecTerm(n,p).Solution: defcombRecAux(n,p,u,v ): if(p == 0orn == p): returnu // v else: returncombRecAux(n1,p1,un,vp) defcombRecTerm(n,p): returncombRecAux(n,p,1 ,1)(c) (3 points) Ecrire une fonction python iterativecombIter(n,p), deriveeautomatiquementde la fonctioncombRecAux(n,p,u,v)qui calcule le nombre de combinaisonsCpn.Solution: defcombIter (n,p): u = 1 v = 1 whileTrue : if(p == 0orn == p): returnu // v else: # n,p ,u, v = n1,p1,un, vp u = un v = vp n = n1 p = p1Page 2 sur 8 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012Exercice 2 : Le tri par base (11 points)
Nous souhaitons trier un tableau de personnes suivant leurs dates de naissance. Nous allons etudier deux approches : La premiere utilise un algorithme de triclassiquequi utilise une fonction de com- paraison de deux personnes; et la seconde est une adaptation de l'algorithme de tri par base qui aete beaucoup utilise autrefois pour trier les cartes perforees. Dans la suite, nous supposerons que les
personnes sont stockees sous forme de tableaux. (a) (2 points) Completer la fonction pythonneAvant(P1,P2)de comparaison de deux personnes P1etP2qui retourneVraisiP1est nee avant ou le m^eme jour queP2, etFauxsinon. Cette fonctionneAvant(P1,P2)pourra ^etre utilisee dans n'importe lequel des algorithmes de tri vus en cours pour trier un tableau deNpersonnes suivant leur date de naissance. Il surade remplacer les testsT[i]<=T[j]parneAvant(T[i],T[j]).Solution:Trois solutions (un predicat, des branchements, une iteration) parmi d'autres.
# p1 et p2 sont deux tableaux de 3 entiers # p1 [0] et p2 [0] contiennent les jours de naissance # p1 [1] et p2 [1] contiennent les mois de naissance # p1 [2] et p2 [2] contiennent les annees de naissance defneAvant(p1 , p2 ): return((p1 [2]Le tri par base consiste a appliquer une suite de tris stables sur des parties de l'objet a trier. Pour
une date de naissance, il faut eectuer sequentiellement trois trisstables:1. Trier (avec un tri stable) suivant le jour de naissance.
2. Trier (avec un tri stable) suivant le mois de naissance.
3. Trier (avec un tri stable) suivant l'annee de naissance.
i. (2 points) Soit le tableau suivant de trois personnes avec leurs dates de naissances. indice012 jour142222 mois313 annee200420042001Page 3 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 Completer le tableau suivant apres chacune des trois etapes. Solution:Apres le tri stableApres le tri stableApres le tri stable jours de naissancemois de naissanceannees de naissance indice012012012 jour142222221422222214 mois313133313 ii. (2 points) Il est connu que le tri par base n'est pas correct si le tri utilise n'est passtable. Au choix, justier cette armation, ou bien simuler sur l'exemple precedent un tri parbase utilisant le tri par selection.Solution:Par exemple, la derniere etape peut donner avec un tri non stable :
Apres un tripar selection non stable.
indice012 jour221422 mois331 annee200120042004 Ce qui demontre que le tri base doit n'utiliser que des tris stables. iii. (1 point) Donner la liste des tris stables vus en cours.Solution:
deftriStable (t , clef ): # clef indice le second indice a utiliser pour le tri # N' importe lequel des 3 tris stables suivants peut etre utilise # triInsertion (t , clef ) triBulle (t , clef )# triFusion (t , clef )iv. (2 points) Completer la fonction pythontriBase(t)pour trier un tableau deNper-
sonnes suivant leurs dates de naissances. Vous pourrez utiliser (sans en donner le code) une fonctiontriStable(t,clef)qui trie un tableauta deux dimensions en fonc- tion des valeurst[i][clef]. Par exemple sitest un tableau de personnes, l'appel triStable(t,1)trie les personnes en fonction des mois de naissances.Solution: deftriBase ( t ): # t [ i ][0] est le jour de naissance de la personne t [ i ] # t [ i ][1] est le mois de naissance de la personne t [ i ] # t [ i ][2] est l 'annee de naissance de la personne t [ i ] forclefinrange (3):triStable (t , clef )v. (2 points) Donner et justier la complexite de votre algorithmetriBaseen fonction de
l'algorithme de tristableutilise.Solution:Le tri appelle un nombre de fois determine (ici 3) un algorithme de tri
stable. La complexite du tri par base est donc celle du tri stable utilise soit : { (n2) pour les tris par insertion et a bulles. { (nlog2(n)) pour le tri par fusion.Page 4 sur 8 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012Exercice 3 : Variante tri rapide (10 points)
(a) (2 points) Justier la validite de la fonction pythonpartitionner(t,g,d)suivante, dans laquelle les iterationsRepeterde l'algorithme 3 du tri rapide vu en cours sont remplaceespar des iterationsTant que.Solution:Les deux structures de programme suivantes sont equivalentes.Algorithm 1Repeter ...jusqu'a1:repeat
2:S3:untilPAlgorithm 2Tant que ...1:S
2:while:Pdo
3:S4:end whileAlgorithm 3Partitionner(t,g,d)Condition :0g < dlen(t)1
1:pivot t[g]
2:i g1
3:j d+ 1
4:while true do
5:repeat
6:j j1
7:untilt[j]<=pivot
8:repeat
9:i i+ 1
10:untilt[i]>=pivot
11:ifi < jthen
12:Echange(t;i;j)
13:else
14:returnj
15:end if
16:end while
Garantie :8kj;t[k]pivot
8k > j;t[k]pivot
Complexite :(dg)Algorithm 4TriRapideRec(t,g,d)Condition :0g < dlen(t)11:ifg < dthen
2:m Partitionner(t;g;d)
3:TriRapideRec(t;g;m)
4:TriRapideRec(t;m+ 1;d)
5:end if
Garantie :8k2[g;d[;t[k]t[k+ 1]
Complexite :
((dg)log2(dg)); O((dg)2)Algorithm 5TriRapide(t)1:TriRapideRec(t;0;len(t)1)Complexite :
(nlog2(n));O(n2) avecn=len(t)1defechange(t , i , j ):2 TMP = t [ i ]
3 t [ i ] = t [ j ]
4 t [ j ] = TMP
56defpartitionner (t ,g ,d):
7 pivot = t [ g ]
8 i = g1
9 j = d+1
10whileTrue :11 j= 112whilet [ j ]>pivot :13 j= 114 i += 1
15whilet [ i ] 17ifi 18 echange(t , i , j )
19else:
20returnj
21
22deftriRapideRec (t ,g ,d):
23ifg 24 m = partitionner (t ,g ,d)
25 triRapideRec (t ,g ,m)
26 triRapideRec (t ,m+1,d)
27
28deftriRapide ( t ):
29 triRapideRec (t ,0 , len ( t)1)
Page 5 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 (b) Soient l'algorithme du drapeau hollandais vu en cours et une ecriture possible en python. Algorithm 6Drapeau(t)Condition :8i2[0;len(t)1];t[i]2[0;2] 1:i 0 2:j i 3:k len(t)1
4:while(jk)do
5:ift[j] = 1then// 1 : Blanc
6:j j+ 1
7:else ift[j] = 0then// 0 : Bleu
8:Echange(t;i;j)
9:i i+ 1
10:j j+ 1
11:else// 2 : Rouge
12:Echange(t;j;k)
13:k k1
14:end if
15:end while
16:returni;j;k
Garantie :8l2[0;i[;t[l] = 0
8l2[i;j[;t[l] = 1
8l2]k;len(t)1];t[l] = 2
Complexite :(n);avecn=len(t)1defdrapeau( t ):
2# t est un tableau de 0, 1 ou 2
3# 0 : Bleu , 1 : Blanc , 2 : Rouge
4 i = 0
5 j = i
6 k = len ( t )1
7whilej<= k:
8ift [ j ] = 1:
9 j += 1
10else:
11ift [ j ] == 0:
12 echange(t , i , j )
13 i += 1
14 j += 1
15else:
16 echange(t , j ,k)
17 k= 1
18returni , j ,k
i. (1 1=2points) Soittun tableau d'entiers compris entre0et2. Soientgetddeux indices
tels que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauIntervalle(t,g,d)qui trie les variablest[i]pour les indicesicompris dans l'intervalle ferme [g;d], et laisse les autres variables du tableau inchangees.Vousdevez n'indiquer que les dierences avec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = dii. (1 1=2points) Soittun tableau d'entiers quelconques. Soientgetddeux indices tels
que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauPartition(t,g,d)qui retourne trois indicesi,j,ktels que8l2[0;i[;t[l]< pivot,8l2[i;j[;t[l] =pivotet8l2]k;len(t)1];t[l]> pivotoupivotest une valeur quelconque du tableau entre les indicesgetd.Vousdevezn'indiquer que les dierences avec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = d pivot = t [ g ] Les lignes 8 et 11 sont remplacees par :
ift [ j ] == pivot : ift [ j ] Page 6 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 et un algorithme ou un programme pythontriRapideDrapeau(t)qui optimisent les algorithmes 4 et 5 de tri rapide en tirant prot de la fonctiondrapeauPartition(t,g,d).Solution: deftriRapideDrapeauRec (t ,g ,d): ifg1=2points) Soittun tableau d'entiers dont toutes les valeurs sont identiques. Donner et
justier le nombre d'appels recursifs de votre algorithmetriRapideDrapeauRec(t,g,d) pour l'appeltriRapideDrapeau(t).Solution:Pour ce tableau particulier,triRapideDrapeauRec(t,0,len(t)-1)va
appelerdrapeauPartition(t,0,len(t)-1)qui retournera0,len(t),len(t)-1. Il y aura ensuite un appel recursif atriRapideDrapeauRec(t,0,-1)qui terminera aussit^ot, suivi d'un appel recursif atriRapideDrapeauRec(t,len(t),len(t)-1)qui terminera egalement aussit^ot.iii. (1 1=2points) Donner et justier les complexites de votre algorithmetriRapideDrapeau(t).Solution:
{ Meilleur des cas (toutes les valeurs sont egales) : (n). { Pire des cas (tableau trie de valeurs dierentes) :O(n2).Exercice 4 : Complexite (10 points) (a) Soit la fonctionindiceTrie(t)outest un tableau denentiers : defindiceTrie ( t ): i = 0 while(( i+1){ Nombre d'aectations :i+1ii. (1 point) Deduire les complexites en nombre d'aectations de la fonctionindiceTrie(t) en fonction den(taille du tableaut)?Solution: { Meilleur des cas : (1). { Pire des cas :O(n).(b) (2 points) Soit la fonctiontri(t,g,d)outest un tableau denentiers etgetddeux entiers
compris entre0etn-1.tri(t,g,d)utilise la fonction classiqueechange(t,i,j)de la page 5. deftri (t ,g ,d): ifg>= 0andgPage 7 sur 8 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 ift [ i ]>t [ j ] : echange(t , i , j ) Donner et justier les complexites en nombre d'aectations sur les variablest[k]de la fonctiontri(t,g,d)en fonction des parametresgetd?Solution: { Meilleur des cas : 0 aectation soit (1). Cas du tableau trie. { Pire des cas : 3(dg)2aectations soitO((dg)2). Cas du tableau trie a l'envers.(c) Soit la fonctiontriErrone(t)outest un tableau denentiers :
deftriErrone ( t ): i = indiceTrie ( t ) tri (t , i +1,len ( t)1) i. (2 points) Donner le nombre d'aectations eectuees sur la variableiet sur les variables t[k]du tableau lors d'un appel a la fonctiontriErrone(t)en fonction de la variableiquotesdbs_dbs7.pdfusesText_13
17ifi 18 echange(t , i , j )
19else:
20returnj
21
22deftriRapideRec (t ,g ,d):
23ifg 24 m = partitionner (t ,g ,d)
25 triRapideRec (t ,g ,m)
26 triRapideRec (t ,m+1,d)
27
28deftriRapide ( t ):
29 triRapideRec (t ,0 , len ( t)1)
Page 5 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 (b) Soient l'algorithme du drapeau hollandais vu en cours et une ecriture possible en python. Algorithm 6Drapeau(t)Condition :8i2[0;len(t)1];t[i]2[0;2] 1:i 0 2:j i 3:k len(t)1
4:while(jk)do
5:ift[j] = 1then// 1 : Blanc
6:j j+ 1
7:else ift[j] = 0then// 0 : Bleu
8:Echange(t;i;j)
9:i i+ 1
10:j j+ 1
11:else// 2 : Rouge
12:Echange(t;j;k)
13:k k1
14:end if
15:end while
16:returni;j;k
Garantie :8l2[0;i[;t[l] = 0
8l2[i;j[;t[l] = 1
8l2]k;len(t)1];t[l] = 2
Complexite :(n);avecn=len(t)1defdrapeau( t ):
2# t est un tableau de 0, 1 ou 2
3# 0 : Bleu , 1 : Blanc , 2 : Rouge
4 i = 0
5 j = i
6 k = len ( t )1
7whilej<= k:
8ift [ j ] = 1:
9 j += 1
10else:
11ift [ j ] == 0:
12 echange(t , i , j )
13 i += 1
14 j += 1
15else:
16 echange(t , j ,k)
17 k= 1
18returni , j ,k
i. (1 1=2points) Soittun tableau d'entiers compris entre0et2. Soientgetddeux indices
tels que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauIntervalle(t,g,d)qui trie les variablest[i]pour les indicesicompris dans l'intervalle ferme [g;d], et laisse les autres variables du tableau inchangees.Vousdevez n'indiquer que les dierences avec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = dii. (1 1=2points) Soittun tableau d'entiers quelconques. Soientgetddeux indices tels
que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauPartition(t,g,d)qui retourne trois indicesi,j,ktels que8l2[0;i[;t[l]< pivot,8l2[i;j[;t[l] =pivotet8l2]k;len(t)1];t[l]> pivotoupivotest une valeur quelconque du tableau entre les indicesgetd.Vousdevezn'indiquer que les dierences avec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = d pivot = t [ g ] Les lignes 8 et 11 sont remplacees par :
ift [ j ] == pivot : ift [ j ] Page 6 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 et un algorithme ou un programme pythontriRapideDrapeau(t)qui optimisent les algorithmes 4 et 5 de tri rapide en tirant prot de la fonctiondrapeauPartition(t,g,d).Solution: deftriRapideDrapeauRec (t ,g ,d): ifg1=2points) Soittun tableau d'entiers dont toutes les valeurs sont identiques. Donner et
justier le nombre d'appels recursifs de votre algorithmetriRapideDrapeauRec(t,g,d) pour l'appeltriRapideDrapeau(t).Solution:Pour ce tableau particulier,triRapideDrapeauRec(t,0,len(t)-1)va
appelerdrapeauPartition(t,0,len(t)-1)qui retournera0,len(t),len(t)-1. Il y aura ensuite un appel recursif atriRapideDrapeauRec(t,0,-1)qui terminera aussit^ot, suivi d'un appel recursif atriRapideDrapeauRec(t,len(t),len(t)-1)qui terminera egalement aussit^ot.iii. (1 1=2points) Donner et justier les complexites de votre algorithmetriRapideDrapeau(t).Solution:
{ Meilleur des cas (toutes les valeurs sont egales) : (n). { Pire des cas (tableau trie de valeurs dierentes) :O(n2).Exercice 4 : Complexite (10 points) (a) Soit la fonctionindiceTrie(t)outest un tableau denentiers : defindiceTrie ( t ): i = 0 while(( i+1){ Nombre d'aectations :i+1ii. (1 point) Deduire les complexites en nombre d'aectations de la fonctionindiceTrie(t) en fonction den(taille du tableaut)?Solution: { Meilleur des cas : (1). { Pire des cas :O(n).(b) (2 points) Soit la fonctiontri(t,g,d)outest un tableau denentiers etgetddeux entiers
compris entre0etn-1.tri(t,g,d)utilise la fonction classiqueechange(t,i,j)de la page 5. deftri (t ,g ,d): ifg>= 0andgPage 7 sur 8 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 ift [ i ]>t [ j ] : echange(t , i , j ) Donner et justier les complexites en nombre d'aectations sur les variablest[k]de la fonctiontri(t,g,d)en fonction des parametresgetd?Solution: { Meilleur des cas : 0 aectation soit (1). Cas du tableau trie. { Pire des cas : 3(dg)2aectations soitO((dg)2). Cas du tableau trie a l'envers.(c) Soit la fonctiontriErrone(t)outest un tableau denentiers :
deftriErrone ( t ): i = indiceTrie ( t ) tri (t , i +1,len ( t)1) i. (2 points) Donner le nombre d'aectations eectuees sur la variableiet sur les variables t[k]du tableau lors d'un appel a la fonctiontriErrone(t)en fonction de la variableiquotesdbs_dbs7.pdfusesText_13
18 echange(t , i , j )
19else:
20returnj
2122deftriRapideRec (t ,g ,d):
23ifg 24 m = partitionner (t ,g ,d)
25 triRapideRec (t ,g ,m)
26 triRapideRec (t ,m+1,d)
27
28deftriRapide ( t ):
29 triRapideRec (t ,0 , len ( t)1)
Page 5 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 (b) Soient l'algorithme du drapeau hollandais vu en cours et une ecriture possible en python. Algorithm 6Drapeau(t)Condition :8i2[0;len(t)1];t[i]2[0;2] 1:i 0 2:j i 3:k len(t)1
4:while(jk)do
5:ift[j] = 1then// 1 : Blanc
6:j j+ 1
7:else ift[j] = 0then// 0 : Bleu
8:Echange(t;i;j)
9:i i+ 1
10:j j+ 1
11:else// 2 : Rouge
12:Echange(t;j;k)
13:k k1
14:end if
15:end while
16:returni;j;k
Garantie :8l2[0;i[;t[l] = 0
8l2[i;j[;t[l] = 1
8l2]k;len(t)1];t[l] = 2
Complexite :(n);avecn=len(t)1defdrapeau( t ):
2# t est un tableau de 0, 1 ou 2
3# 0 : Bleu , 1 : Blanc , 2 : Rouge
4 i = 0
5 j = i
6 k = len ( t )1
7whilej<= k:
8ift [ j ] = 1:
9 j += 1
10else:
11ift [ j ] == 0:
12 echange(t , i , j )
13 i += 1
14 j += 1
15else:
16 echange(t , j ,k)
17 k= 1
18returni , j ,k
i. (1 1=2points) Soittun tableau d'entiers compris entre0et2. Soientgetddeux indices
tels que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauIntervalle(t,g,d)qui trie les variablest[i]pour les indicesicompris dans l'intervalle ferme [g;d], et laisse les autres variables du tableau inchangees.Vousdevez n'indiquer que les dierences avec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = dii. (1 1=2points) Soittun tableau d'entiers quelconques. Soientgetddeux indices tels
que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauPartition(t,g,d)qui retourne trois indicesi,j,ktels que8l2[0;i[;t[l]< pivot,8l2[i;j[;t[l] =pivotet8l2]k;len(t)1];t[l]> pivotoupivotest une valeur quelconque du tableau entre les indicesgetd.Vousdevezn'indiquer que les dierences avec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = d pivot = t [ g ] Les lignes 8 et 11 sont remplacees par :
ift [ j ] == pivot : ift [ j ] Page 6 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 et un algorithme ou un programme pythontriRapideDrapeau(t)qui optimisent les algorithmes 4 et 5 de tri rapide en tirant prot de la fonctiondrapeauPartition(t,g,d).Solution: deftriRapideDrapeauRec (t ,g ,d): ifg1=2points) Soittun tableau d'entiers dont toutes les valeurs sont identiques. Donner et
justier le nombre d'appels recursifs de votre algorithmetriRapideDrapeauRec(t,g,d) 24 m = partitionner (t ,g ,d)
25 triRapideRec (t ,g ,m)
26 triRapideRec (t ,m+1,d)
2728deftriRapide ( t ):
29 triRapideRec (t ,0 , len ( t)1)
Page 5 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 (b) Soient l'algorithme du drapeau hollandais vu en cours et une ecriture possible en python. Algorithm 6Drapeau(t)Condition :8i2[0;len(t)1];t[i]2[0;2] 1:i 0 2:j i3:k len(t)1
4:while(jk)do
5:ift[j] = 1then// 1 : Blanc
6:j j+ 1
7:else ift[j] = 0then// 0 : Bleu
8:Echange(t;i;j)
9:i i+ 1
10:j j+ 1
11:else// 2 : Rouge
12:Echange(t;j;k)
13:k k1
14:end if
15:end while
16:returni;j;k
Garantie :8l2[0;i[;t[l] = 0
8l2[i;j[;t[l] = 1
8l2]k;len(t)1];t[l] = 2
Complexite :(n);avecn=len(t)1defdrapeau( t ):
2# t est un tableau de 0, 1 ou 2
3# 0 : Bleu , 1 : Blanc , 2 : Rouge
4 i = 0
5 j = i
6 k = len ( t )1
7whilej<= k:
8ift [ j ] = 1:
9 j += 1
10else:
11ift [ j ] == 0:
12 echange(t , i , j )
13 i += 1
14 j += 1
15else:
16 echange(t , j ,k)
17 k= 1
18returni , j ,k
i. (11=2points) Soittun tableau d'entiers compris entre0et2. Soientgetddeux indices
tels que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauIntervalle(t,g,d)qui trie les variablest[i]pour les indicesicompris dans l'intervalle ferme [g;d], et laisse les autres variables du tableau inchangees.Vousdevezn'indiquer que les dierences avec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = dii. (11=2points) Soittun tableau d'entiers quelconques. Soientgetddeux indices tels
que 0g < d(len(t)1).Ecrire un algorithme ou bien un programme python drapeauPartition(t,g,d)qui retourne trois indicesi,j,ktels que8l2[0;i[;t[l]< pivot,8l2[i;j[;t[l] =pivotet8l2]k;len(t)1];t[l]> pivotoupivotest une valeur quelconque du tableau entre les indicesgetd.Vousdevezn'indiquer que les dierencesavec l'algorithme 6 ou avec le programme pythondrapeau.Solution:Les lignes 4, 5 et 6 sont remplacees par :
i = g j = i k = d pivot = t [ g ]Les lignes 8 et 11 sont remplacees par :
ift [ j ] == pivot :ift [ j ]Page 6 sur 8
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2011/2012 et un algorithme ou un programme pythontriRapideDrapeau(t)qui optimisent les algorithmes 4 et 5 de tri rapide en tirant prot de la fonctiondrapeauPartition(t,g,d).Solution: deftriRapideDrapeauRec (t ,g ,d): ifg
pour l'appeltriRapideDrapeau(t).Solution:Pour ce tableau particulier,triRapideDrapeauRec(t,0,len(t)-1)va
appelerdrapeauPartition(t,0,len(t)-1)qui retournera0,len(t),len(t)-1. Il y aura ensuite un appel recursif atriRapideDrapeauRec(t,0,-1)qui terminera aussit^ot, suivi d'un appel recursif atriRapideDrapeauRec(t,len(t),len(t)-1)qui terminera egalement aussit^ot.iii. (11=2points) Donner et justier les complexites de votre algorithmetriRapideDrapeau(t).Solution:
{ Meilleur des cas (toutes les valeurs sont egales) : (n). { Pire des cas (tableau trie de valeurs dierentes) :O(n2).Exercice 4 : Complexite (10 points) (a) Soit la fonctionindiceTrie(t)outest un tableau denentiers : defindiceTrie ( t ): i = 0 while(( i+1){ Pire des cas :O(n).(b) (2 points) Soit la fonctiontri(t,g,d)outest un tableau denentiers etgetddeux entiers
compris entre0etn-1.tri(t,g,d)utilise la fonction classiqueechange(t,i,j)de la page 5. deftri (t ,g ,d): ifg>= 0andg{ Pire des cas : 3(dg)2aectations soitO((dg)2). Cas du tableau trie a l'envers.(c) Soit la fonctiontriErrone(t)outest un tableau denentiers :
deftriErrone ( t ): i = indiceTrie ( t ) tri (t , i +1,len ( t)1) i. (2 points) Donner le nombre d'aectations eectuees sur la variableiet sur les variables t[k]du tableau lors d'un appel a la fonctiontriErrone(t)en fonction de la variableiquotesdbs_dbs7.pdfusesText_13[PDF] algorithme récursif maternelle
[PDF] algorithme récursif factorielle
[PDF] algorithme itératif
[PDF] exercice récursivité algorithme
[PDF] exercices corrigés récursivité python
[PDF] exercices récursivité
[PDF] exercice algorithme avec solution recursivité
[PDF] fonction récursive exercice corrigé python
[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
