[PDF] Feuille dexercices dinformatique – Récursivité 2019-2020 Pour

View - Download Feuille dexercices dinformatique – Récursivité 2019-2020 Pour

Previous PDF

Next PDF

MP*Feuille d"exercices d"informatique - Récursivité 2019-2020Pour chacun des programmes suivants, on prouvera la validité de la réponse

et on évaluera la complexité dans le pire cas.

Exercice 1:

Écrire un programme récursifsomchiffre(n)qui renvoie la somme des chiffres décimaux de l"entiern. Exercice 2: Écrire un programme récursifbinom(n,k)d"argumentn,k2N qui renvoie le coefficient binomial¡n k¢. On cherchera une complexité mini- male, et on fera bien attention à travailler sur des entiers.

Exercice 3 - Encore Fibonacci:

Montrer que la suite de Fibonacci vérifie

Fib(2nÅ1)AEFib(nÅ1)2ÅFib(n)2

En déduire un programme calculant les nombres de Fibonacci, et conjectu- rer sa complexité temporelle. (On ne demande pas de preuve.)

Exercice 4 - Fibonacci forever:

En exploitant la matrice 2£2 qui fait passer de (Fn,Fn¡1) à (FnÅ1,Fn), déter- miner un algorithme de complexitéO(log2n) qui calculeFn. On ne demande pas d"implémentation enPYTHON.

Exercice 5:

Écrire une version récursiveHorner(L,x) de l"algorithme de Horner, oùLest la liste croissante des coefficients etxun nombre.

Exercice 7 - Multiplication du paysan russe:

russe(a,b)qui prend en argument deux entiers naturelsa,bet qui renvoie leproduitaben n"utilisant que des additions, des multiplications par 2 et des

divisions par 2. Le programme doit être linéaire en log 2b.

Exercice 8:

Untriminoest un domino constitué de trois carrés comme ceci :. Jus- tifier qu"on peut paver un damier carré de coté 2 n(nÊ1) privé d"une case par des triminos? (Les triminos se tournent et se retournent.) Donner un al- gorithme (dans un pseudo-langage) qui prend en entrée un entiernet une couple (i,j)2[[1,2n]]2et qui renvoie un pavage du damier de côté 2nprivé de la case (i,j).

Exercice 9:

Écrire un programmepartition(n)qui renvoie le nombre de partition d"un ensemble de cardinaln. (Indication : on pourra remarquer qu"une partition de [[1,n]] est uniquement déterminée par une partieXcontenantnet une partition de [[1,n]]\X.) On ne demande pas d"évaluer la complexité.

Exercice 10 - Encore Flavius Josephus:

On dispose lesnentiers 0,1,2,...,n¡1 en cercle. On en raye un sur deux en commençant par le 1. On noteJ(n) le dernier rayé. Par exemple,J(4)AE0 etJ(5)AE2. En distinguant les casnpair etnimpair, écrire un programme récursifJosephqui renvoieJ(n).

Exercice 11 - Scribe:

Les scribes égyptiens (fait attesté en 1880 av. JC) savait écrire tout rationnel rstrictement compris entre 0 et 1 comme somme d"inverse d"entiers tous différents,i.e. rAEpX jAE01n javecnjÇnjÅ1. une liste [n0,...,np] telle queab AE1n

0Å¢¢¢Å1n

p. Examiner sa complexité en tempsetenespace. (Onfera attentionàla gestiondesrationnels; mieuxvaut travailler avec des couples d"entiers premiers entre eux.)

Écrire aussi une version itérative.

1 MP*Feuille d"exercices d"informatique - Récursivité 2019-2020Indications Exercice 1.On fera décroître le nombre de chiffres. Exercice 2.On utilise la formule de récurrenceà n k! AE nk n¡1 k¡1! valable sikÊ

1. Et on fait bien attention à d"abord effectuern£Ã

n¡1 k¡1! avant de diviser par k!

Exercice 4.On aµ1 1

n

AEµFnÅ1Fn

F Exercice 6.On ne touche pas àx, qui sert jusqu"à la fin. Exercice 7.Il faut passer des exposants au produit et des produits aux sommes. Exercice 8.Utiliser une méthode "diviser pour régner". Exercice 9.Le plus difficile est d"écrire une relation de récurrence. On aura aussi besoin de programmer les coefficients binomiaux : une fonction récur- sive est pratique. Exercice 10.Regarder ce qui se passe après un tour complet. Exercice 11.Un algorithme glouton convient : prendre le plus petit entiern tel que 1n

Éab

. Puisque Python ne gère pas naturellement les fractions, il faut utiliser des couples (a,b) d"entiers.2 MP*Feuille d"exercices d"informatique - Récursivité 2019-2020Solutions Exercice 1.On note¾(n) la somme des chiffres den. Alors¾ÃX kÊ0a k10k! AE a

0ž(X

kÊ1a k10k) car¾(10a)AE¾(a). D"où un invariant pour le programme

suivant.1defsomchiffre(n):2ifn<10:3return(n)4else:5return(n%10 + somchiffre(n//10))La pile d"appels récursifs contient autant de termes quena de chiffres dé-

cimaux. À chaque appel, on effectue un nombre fixé d"opérations. Donc la complexité est enO(lnn). (En effet, siC(n) désigne le nombre d"opérations Une récurrence (relativement) immédiate donne le résultat.)

Exercice 2.Le programme est facile.1defbinom(n,k):2ifn

0. La correction vient de la formuleÃ

n k! AE nk n¡1 k¡1! . Enfin, cette même for- mule prouve par récurrence surkque la complexité est enO(k), car la pile d"éxécution se vide enkétapes, et on a un nombre finie fixé d"opérations

élémentaires à chaque étape.

Exercice 3.On implémente les formules, qui se démontrent par récurrence.

Attention à bien mettre le casnAE2 dans l"initialisation.1deffibor(n):2ifn==0:3return(0)4elifn==1:5return(1)6elifn==2:7return(1)8elifn%2==0:9r=fibor(n//2)10return(r*(fibor(n//2 + 1) + fibor(n//2¡1)))11else:12return(fibor(n//2 + 1)**2 + fibor(n//2)**2)Si on noteC(n) le nombre d"opérations élémentaires effectuées pour l"argu-

mentn, on aC(n)ÉC(bn/2¡1c)ÅC(bn/2c)ÅC(bn/2Å1c)Å3. Il est délicat de prouver queC(n)AEO(nln23)... C"est en tout cas hors d"atteinte vu le pro- gramme. Exercice 4.On applique l"algorithme d"exponentiation rapide au calcul deµ1 1 n Exercice 5.Il renvoie la décomposition deaen basebsous forme de liste, le terme en commençant par les poids faibles. Correction : on démontre par récurrence surpque renvoie la liste ["1,...,"p] où"k2[[0,b¡1]]. C"est vrai sipAE1. Si c"est vrai au rangp¡1, alors en notantaAE"0b0Å"1b1Å¢¢¢Å"pbp, on aa0AEa//bAE

1b0Å"2b1Å¢¢¢Å"pbp¡1eta%bAE"0. Alorsexo(a,b)AE["0]Åexo(a0,b), (avec

la syntaxe dePYTHON), ce qui conclut. Exercice 6.SiLAE[a0,a1,...,an], l"idée est de supprimeranet de remplacer a

n¡1paran¡1Åanx.1defHorner(L,x):2ifle n(L) == 0:return03elifle n(L) == 1:returnL[0]4else:5n =len(L)6L[n¡2] + = L[n¡1]*x7L.pop()8returnHorner(L,x)3

MP*Feuille d"exercices d"informatique - Récursivité 2019-2020Exercice 7.Onchangelesproduitsensommesdansl"algorithmed"exponen-

tiation rapide.1defrusse(a,b):2ifa == 0:3return04elifa%2 == 0:5returnrusse(a//2, b + b)6else:7returnrusse(a//2, b+b) + bTerminaison : à chaque appel récursif,aest divisé par 2. C"est un entier na-

turel, il finit donc par atteindre la valeur 0 et le programme s"arrête. Complexité dans le pire cas : Puisqueaest changé enba/2cà chaque ap- pel récursif, il perd exactement un chiffre binaire à chaque appel. On a donc ba/2cÅ1 appels récursifs qui chacun utilise au plus trois opérations élémen- taires. La complexité est enO(log2n), soit une complexité linéaire en la taille. Exercice 8.L"idée est simple : c"est possible sinAE1 (on a déjà un trimino) et si on sait faire pour des carrés de côté 2 n¡1alors on divise le carré de côté 2n en 4 carrés égaux. La case manquante est dans un des 4 carrés. On enlève un n"a plus qu"à appliquer la récursivité...

Exercice 9.On commence par calculern!.1deffact(n):2ifn == 0:3return14returnn*fact(n¡1)On en déduit un programme calculant les coefficients binomiaux

n k! pour

0ÉkÉn.1defbinomial(n,k):2returnfact(n)//(fact(k)*fact(n¡k))On utilise enfin la formule de récurrence :pnÅ1AEnX

kAE0Ã n k! p kqui se prouve en remarquant qu"une partition de [[1,nÅ1]] est uniquement déterminée par une partie de [[1,n]] (celle qui sera dans la même partie quenÅ1) et d"une

partition du complémentaire.1defpartition(n):2ifn == 0:3return14s = 05forkinr ange(n):6s += binomial(n¡1,k)*partition(k)7returnsExercice 10.Après avoir fait un tour complet, on renumérote les survivants :

on en déduit le survivant récursivement. On trouveJ(2p)AE2J(p) etJ(2pÅ

1)AE2J(p)Å2.1defJoseph(n):2ifn==1:3return04elifn%2==0:5return(2*Joseph(n//2))6else:7return(2*Joseph(n//2)+2)Vu quenest divisé par deux à chaque étape, on va appeler récursivement la

fonction de l"ordre de ln

2nfois. Vu qu"on ne fait qu"un nombre fixé d"opé-

ration à chaque fois, cela donne une complexité temporelle enO(lnn), soit linéaire en la taille den. Exercice 11.Le premier programme permet de passer du couple (a,b) au couple (a0,b0) tel quea/bAEa0/b0¡1/nd"ajouternà la listeL, avec le bon n.1defscribe_rec(a,b,L):2ifa == 0:3returna,b,L4q = b//a5ifb%a == 0: 4

MP*Feuille d"exercices d"informatique - Récursivité 2019-20206returnscribe_rec(q*a¡b, q*b, L+[q])7else:8returnscribe_rec((q+1)*a¡b , (q+1)*b , L+[q+1])9

10defscribeR(a,b):11returnscribe_rec(a,b,[])[2]Donnons une version itérative.

1defscribe2(a,b):2n = 13L = []4whilea >0:5whilen*a < b:6n = n+17a,b = n*a¡b, n*b8L.append(n)9returnLTerminaison : puisquena¡b2[[0,a¡1]], le dénominateur décroît stricte-

ment et reste un entier positif tant qu"il est non nul : il tombe donc sur 0 en un temps fini. Complexité : La complexité en espace ne dépend que de la taille de la liste Lpuisqu"on n"utilise qu"un nombre fixé de variables. Mais puisqu"au signe prèsna¡best le quotient deaparb, le nombre d"itération dans la boucle while - qui va donner le nombre de terme dansL- est unO(lnb) d"après le théorème de Lamé (et puisque 0ÇaÇbpar hypothèse). En temps, c"est la même chose, puisqu"on ne fait qu"un nombre fixé d"opérations par étapes. Correction : notonsa0,b0les arguments etak,bk,[n1,...,nk] les valeurs de a,b,Là lakeétape. Montrons queakb kÅkX pAE11n pest un invariant de boucle. Mais siak6AE0,akÅ1AEnkÅ1ak¡bk,bkÅ1AEnkÅ1bk, doncakb kAEakÅ1b kÅ1Å1n kÅ1.

Or cet invariant vaut

a0b

0à l"entrée et à la sortie,akest nul.5

quotesdbs_dbs15.pdfusesText_21

[PDF] seuil de rentabilité cours pdf

[PDF] méthode des couts variables exercices corrigés

[PDF] exercice seuil de rentabilité corrigé pdf

[PDF] levier opérationnel calcul

[PDF] représentation graphique du seuil de rentabilité

[PDF] calcul du seuil de rentabilité avec plusieurs produits

[PDF] indice de sécurité calcul

[PDF] exercice seuil de rentabilité bts

[PDF] choix d'investissement exercices

[PDF] rentabilité des investissements cours

[PDF] calcul drci+formule

[PDF] calcul de rentabilité d'un investissement industriel

[PDF] etude de rentabilité d'une entreprise

[PDF] ratio de rentabilité commerciale

[PDF] rentabilité financière d'une entreprise