[PDF] T.P. dinformatique no 4 CORRIGE

View - Download T.P. dinformatique no 4 CORRIGE

Previous PDF

Next PDF

MP 18-19 Feuille Info n

o04 :RécursivitéDu 21/11/18 au 28/11/18

T.P. d"informatique n

o4

Récursivité

Solution

CORRIGE

Exercice 1.

C oefficientsbinomiaux

On rappelle que les coefficients binomiaux vérifient :n p = 0sin < poup <0,n 0 =n n = 1sin2Net, pour tout couple d"entiers(n;p)avecn >0, on an p =n1 p1 +n1 p 1.

Ecrire une fonction réc ursivebinomd"arguments deux entiersnetpet retournant le coefficient binomialn

p = 0 2.

Estimer la complexi téde cet algorithme.

Solution1defb inom(n,p):2ifn

Le jeudes tours de Hanoïest constitué deNpièces (des disques percés) que l"on peut déplacer sur trois tiges

numérotées 0, 1 et 2;

lesNpièces sont toutes de tailles distinctes numérotées de 1 àN(dans l"ordre de taille croissante, i.e. la pièce

n o1 est la plus petite, la noNla plus grande).

Dans l"état initial, lesNpièces sont sur la tige no0 (dans l"ordre de taille décroissant de bas en haut).Le jeu consiste à déplacer les pièces de la tige no0 à la tige no2.

Le joueur doit obéir aux deux règles suivantes : i.les pièces ne peuvent être déplacées qu"une par une d"une tige à une autre;

ii.une pièce ne peut être posée que sur une pièce de plus grande taille (ou éventuellement sur le socle!)

Quest. 1.NotonsH(N)le nombre de coups minimal pour réussir le jeu de Hanoi àNpièces : a.déterminerH(1); b.trouver une relation de récurrence liantH(N)etH(N+ 1); c.en déduire la valeur deH(N), pour toutNentier.

Quest. 2.On décide de représenter une position du jeu par une liste nomméetourselle-même composée de 3

piles. 1 Ainsi en position initiale, par exemple pourN= 5,tours=[[5,4,3,2,1],[],[]].

a.Résoudre le problème à la main pourN= 2,N= 3. Est-ce en adéquation avec leH(N)correspondant?

b.Ecrire une fonctioninitialisequi prend en argument l"entierNet qui crée la variable globaletoursdans la

position initiale.

c.Ecrire une fonctionverifiequi prend en argument une pile et qui rendTruesi les éléments de la pile sont

dans l"ordre décroissant etFalsesinon.

d.Ecrire une fonctiondeplacequi prend en argument deux piles ditesdepartetarriveeet qui déplace la pièce

du haut de la piledepartvers la pilearrivee. Elle enverra un message d"erreur à l"aide de la fonctionprintsi

la pile d"arrivée est désordonnée (à l"aide de la fonctionverifie).

e.Ecrire une fonction récursive nomméeHanoi, recevant trois arguments :n,ietj, permettant de déplacern

pièces de la tige n oià la tige noj.

Solution1defi nitialise(N):2globalt ours3tours=[[nf orn i nr ange(N,0,-1)],[],[]]1defv erifie(pile):2fori i nr ange(len(pile)-1):3ifp ile[i]0:3arrivee.append(depart.pop())4print(tours)5ifn ot(verifie(arrivee)):6print("erreur")1defH anoi(n,i,j):2ifn >=1:3k=3-i-j# numt igei ntermediaire4Hanoi(n-1,i,k)5deplace(tours[i],tours[j])6Hanoi(n-1,k,j)1initialise(5)2Hanoi(5,0,2)3print(tours)Exercice 3.A lgorithmede Horner

On considère un polynômePdont les coefficients sont stockés dans un tableaua.P=nX k=0a kXk. On veut écrire une fonction recevant comme paramètres le tableauaet le flottant (ou entier)xet renvoyantnX k=0a kxk 1.

On se donne une v aleurréelle xet un tableauacontenont les coefficients du polynômeP. Evaluer le nombre

d"additions et de multiplications de réels effectués en cas de programmation "naïve"

2.Versionitérative Justifier que l"algorithme de Horner est correct et l"implémenter.

On posey0=anet, pouriallant de 1 àn,yi=x yi1+anialorsynvautP(x). Déterminer le nombre d"additions et de multiplications lors de l"appel de cette fonction

3.Versionrécursive. On transforme un peu l"écriture. En notantPj(x) =nX

k=ja kxkj, on veut calculerP0(x).

On a :Pn(x) =anet, sij < n,Pj(x) =aj+x:Pj+1(x).

Traduire cet algorithme en un programme récursif.

Solution1defH ornerI(a,x):2n= l en(a)- 1 3y= a [n]4fori i nr ange(1,n+1):5y= x *y+a[n-i]6return(y)1defH ornerR(a,x):2ifl en(a)= =1 :3return(a[0])4else: 5return(a[0]+ x * HornerR(a[1:],x))

2

Exercice 4.Le flo conde V onK och

Le flocon de Von Koch est une célèbre figure fractale obtenue de la façon suivante : à tout segment[A;B]orienté

deAversB, on associe la ligne briséeAA1A2A3BoùA1etA3partagent le segment initial en trois parts égales

et où le triangleA1A2A3est équilatéral.

On applique alors cette transformation à un segment initial, puis on l"applique à chacun des 4 segments obtenus,

puis à chacun des 16 segments obtenus et ainsi de suite... Ce qui donne la figure ci-dessous.Ecrire une fonction récursive recevant pour paramètres deux pointsaetbet traçant la ligne de Von Koch associée.

Pour faire des calculs sur les coordonnées des points, il est conseillé de stocker les coordonn{ees[x;y]dans un

tableaunumpy.array

En rassemblant les trois lignes de Von Koch à partir des trois segments d"un triangle équilatéral, on obtient ce

type de figure :Solution

1importm atplotlib.pyplota sp lt2importn umpya sn p3

4k= 0 .5/np.sqrt(3)5xm, s euil= 1 00, 3 6

7deff locon(a,b):8d= n p.sqrt((b[0]-a[0])**2+ ( b[1]-a[1])**2)

9ifd < s euil:10plt.plot([a[0],b[0]],[a[1],b[1]]," b-")

11else: 12a1= ( 2*a+b)/313a3=( a+2*b)/314a2=( a+b)/2+ k *np.array([a[1]-b[1],b[0]-a[0]])

15flocon(a,a1)16flocon(a1,a2)17flocon(a2,a3)18flocon(a3,b)1a= np.array([0,0])2b= n p.array([xm,0])3c= n p.array([xm/2,-xm*np.sqrt(3)/2])

4ax=plt.gca()5ax.set_xticks([]);a x.set_yticks([])6plt.axis("equal")7flocon(a,b)8flocon(b,c)9flocon(c,a)10plt.show()3

quotesdbs_dbs46.pdfusesText_46

[PDF] Le fluor

[PDF] le fmi et la banque mondiale vus par un caricaturiste correction

[PDF] le foie dans le corps humain

[PDF] le foie humain et l'alcool

[PDF] le folioscope

[PDF] Le fonctionnement d'un velo

[PDF] Le fonctionnement d'une lampe

[PDF] Le fonctionnement d'une trottinette

[PDF] le fonctionnement d'une troupe de théatre au XVIIeme siecle

[PDF] Le fonctionnement d'usage

[PDF] le fonctionnement de certaines centrales géothermiques corrigé

[PDF] Le fonctionnement de l'ONU

[PDF] Le fonctionnement de la justice

[PDF] le fonctionnement de la justice (valeurs, acteurs)

[PDF] Le fonctionnement du coeur