[PDF] SUJET + CORRIGE 13 avr. 2012 Exercice 1:





Previous PDF Next PDF



CORRECTION Devoir à la maison n°2

A ce jour aucun mathématicien n'a réussi à démontrer cette conjecture. Exercice 1 : construction d'une suite de Syracuse à l'aide d'un algorithme. Un 



La suite de Syracuse [it06] - Exercice

La suite de Syracuse [it06] - Exercice. Karine Zampieri Stéphane Rivi`ere. Unisciel algoprog. Version 17 mai 2018. Table des mati`eres.



La suite de Syracuse [it06] - Exercice

La suite de Syracuse [it06] - Exercice. Karine Zampieri Stéphane Rivi`ere. Unisciel algoprog. Version 17 mai 2018. Table des mati`eres.



TP no 1 : À la découverte de Python (exercices 8 à 12)

Correction de l'exercice 11 – La suite de Syracuse aussi appelée suite de Collatz



def syracuse(Nn): u = N for i in range(1

http://maths.ac-amiens.fr/IMG/pdf/tp_syracuse.pdf



suite-de-syracuse-2.pdf

Nous proposerons en fin d'exercice une solution avec le tableur de la Graph75 (ou de la Graph 95SD) et une autre avec le tableur EXCEL® de Microsoft®. Page 2. 2.



suite-de-syracuse-2.pdf

Nous proposerons en fin d'exercice une solution avec le tableur de la Graph75 (ou de la Graph 95SD) et une autre avec le tableur EXCEL® de Microsoft®. Page 2. 2.



Assembleur Y86 premiers pas Registres Code objet

4 mars 2011 Exercice 6 (suite de Syracuse) corrigés. # Version 1 avec une simple boucle infinie. # Objectifs: test pair/impair



SUJET + CORRIGE

13 avr. 2012 Exercice 1: Suites et tableaux. (12 points) ... calcule le terme un de la suite en utilisant une boucle while. Solution: def u?while (n) :.



Exercice 1: Arbre de résolution Exercice 2: Conjecture de Syracuse

1.1 Avec quelle tête de clause le but insere(X[]

DISVE

LicenceAnn

ee :2011/2012Semestre 2

PARCOURS :Licence LIMI201 & LIMI211

UE J1MI2013 :Algorithmes et Programmes

Epreuve :Devoir surveille

Date :Vendredi 13 avril 2012

Heure :11 heures

Duree :1 heure 30

Documents : non autorisesSUJET + CORRIGE

Avertissement

{ La plupart des questions sont independantes. { Les fonctions doivent ^etre ecrites enPythonen respectant les indentations. { L'espace laisse pour les reponses est susant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement deconseille). { La note maximale est de 42=40!20=20.QuestionPointsScore

Suites et tableaux12

Tableaux et predicats10

Fonction mystere9

Complexite11

Total:42

Exercice 1: Suites et tableaux (12 points)

On considere la suite denie par :

u0= 2 u n= 3un11 (a) (2 points) Ecrire une fonction iterative qui prend comme parametre un entier naturelnet calcule le termeunde la suite en utilisant une bouclewhile.Solution: defuwhile(n) : u = 2 i = 0 whilei0 : t [0] = 2 foriinrange (1 ,n) : t [ i ] = 3t [ i1]1 returnt(e) (3 points) Ecrire une fonction qui, etant donne un entierm, calcule l'indice du premier terme de la suite superieur ou egal am(exemple : si m = 30, la fonction retournera 3 car tous les termes d'indice inferieur a 3 sont plus petits que 30).Solution: defusup(m) : u = 2 i = 0 whileuExercice 2: Tableaux et predicats (10 points) Trois exemples de tableaux pour illustrer les denitions : >>> a = [1,4,3] >>> b = [1,0,0] >>> c = [1,0,2]

Soittun tableau d'entiers de taillen.

(a) (3

1=2points)Ecrire une fonctionsansDoublons(t)qui retourneTruesi le tableau d'entiers

test sans doublons (c'est a dire sans apparition multiple d'un element),Falsesinon.

Exemples :

>>> sansDoublons(a) : True >>> sansDoublons(b) : False >>> sansDoublons(c) : TrueSolution: defsansDoublons ( t ) : foriinrange ( len ( t)1) : forjinrange ( i +1,len ( t )) : if( t [ i]==t [ j ] ) : returnFalse returnTrue(b) (1

1=2points) Donner et justier la complexite de cette fonction.Solution:Deux boucles imbriquees avec un test de sortie dans la boucle interne :

{ Pire des cas (le test est toujours faux) :Pi=n2 i=0((n1)(i+ 1) + 1) =Pi=n1 i=1i= n(n1)2 . SoitO(n2), ounest la longueur du tableau. { Meilleur des cas (le premier test est vrai) : Soit (1).(c) (3 points) Ecrire une fonctioninterne(t)qui retourneTruesi8i2[0;n[,t[i]2[0;n[ et retourneFalsesinon.

Exemples :

>>> interne(a) : False >>> interne(b) : True >>> interne(c) : TrueSolution: definterne ( t ) : foriinrange ( len ( t )) : if( t [ i ]<0)j( t [ i]>=len ( t )) : returnFalse

returnTrue(d) (2 points)test une permutation si8i2[0;n[,t[i]2[0;n[ et sitne contient pas de doublons.

Exemples :

>>> permutation(a) : False >>> permutation(b) : False >>> permutation(c) : True Ecrire une fonctionpermutation(t)qui retourneTruesitest une permutation,Falsesinon.Solution: defpermutation ( t ) : returninterne ( t ) & sansDoublons ( t )Page 3 sur 6 UE J1MI2013 : Algorithmes et Programmes Devoir surveille, Annee 2011/2012

Exercice 3: Fonction mystere (9 points)

Soit la fonctionmystere(t, k)outest un tableau d'entiers non vide etkveriant 0kt [k+1] : returnFalse returnmystere (t , k+1) (a) Soitt= [6, 9, 4, 8, 12]

i. (1 point) Que retournemystere(t, 2)(Donner la liste des appels recursifs)?Solution:mystere(t,2), mystere(t,3), mystere(t,4)!Trueii. (1 point) Que retournemystere(t, 0)(Donner la liste des appels recursifs)?Solution:mystere(t,0), mystere(t,1)!False(b) (2 points) Que fait la fonctionmysteredans le cas general?Solution:La fonctionmystere(t, k)retourneTruesi la suite d'entiers contenue dans

le tableauta partir de l'indicekest croissante et retourneFalsesinon.(c) (1 point) Quel est le nombre maximum d'appels recursifs (en fonction denetk) de la fonction

mystere(t,k)si le tableautest de longueurn?Solution:Le pire des cas correspond a l'appelmystere(t,k)pour un tableau croissant

a partir de l'indicek. Il y a dans ce casn-kappels recursifs en comptant l'appel initial.(d) (1 point) En utilisant la fonctionmystere, ecrire une fonctionestCroissant(t)qui retourne

Truesi la suite d'entiers contenue dans le tableautest croissante et retourneFalsesinon.Solution: defestCroissant ( t ) :

returnmystere (t ,0)(e) (3 points) En vous inspirant de la fonctionmystere, ecrire une fonction recursiveestDans(t,

x, k)qui retourneTruesixapparait dans le tableauta partir de l'indicek,Falsesinon.Solution: defestDans(t , x , k) : ifk>len ( t )1 : returnFalse ift [k] == x : returnTrue returnestDans(t , x , k+1)Page 4 sur 6 UE J1MI2013 : Algorithmes et Programmes Devoir surveille, Annee 2011/2012

Exercice 4: Complexite (11 points)

(a) Soit la fonctionsyr(n)ounest un entier : defsyr (n) : whilen>1 : n = n // 2 returnn i. (1 point) Donner les suites des valeurs successives prises par la variablenlors des deux appelssyr(32)etsyr(20).Solution: {syr(32): 32;16;8;4;2;1 retourne 1.

{syr(20): 20;10;5;2;1 retourne 1.ii. (2 points) Quelles sont les complexites (meilleur et pire des cas) de la fonctionsyr?Solution:

{ Meilleur des cas : (log2(n)). { Pire des cas :O(log2(n)). { Soit : (log2(n)).(b) Soit la fonctionsyrac(n)ounest un entier : defsyrac (n) : whilen>1 : ifn%2 == 0 : n = n // 2 else: n = 1 returnn i. (1 point) Donner les suites des valeurs successives prises par la variablenlors des deux appelssyrac(32)etsyrac(20).Solution: {syrac(32): 32;16;8;4;2;1 retourne 1.

{syrac(20): 20;10;5;1 retourne 1.ii. (2 points) Quelles sont les complexites (meilleur et pire des cas) de la fonctionsyrac?Solution:

{ Meilleur des cas : un nombre impair, (1). { Pire des cas : une puissance de 2,O(log2(n)).Page 5 sur 6 UE J1MI2013 : Algorithmes et Programmes Devoir surveille, Annee 2011/2012 (c) Soit la fonctionsyracuse(n)ounest un entier : defsyracuse (n) : whilen>1 : ifn%2 == 0 : n = n // 2 else: n = 3n + 1 returnn i. (1 point) Donner les suites des valeurs successives prises par la variablenlors des deux {syracuse(32): 32;16;8;4;2;1 retourne 1.

{syracuse(20): 20;10;5;16;8;4;2;1 retourne 1.Depuis 1937, les mathematiciens et les informaticiensetudient les suites des valeurs successives

prises par la variablenlors de l'appel asyracuse(n). Ils cherchent a savoir si ces suites sont toutes nies, ou bien s'il en existe des cycliques, ou bien s'il en existe qui contiennent une sous-suite strictement croissante. Ce probleme est un problemeouvert, ce qui signie que personne ne connait la reponse.

ii. (2 points) Quelles sont les complexites (meilleur et pire des cas) de la fonctionsyracuse?Solution:

{ Meilleur des cas : une puissance de 2,O(log2(n)). { Pire des cas : inconnue.(d) (2 points) Soit la fonctionsyrFor(n)ounest un entier : defsyrFor (n) : s = 0; foriinrange (n+1): s = s + syr ( i ) returns

Quelles sont les complexites (meilleur et pire des cas) de la fonctionsyrFor?Solution:Le meilleur des cas est aussi le pire des cas.

syrFor:Pi=n i=1log2(i) =log2(Qi=n i=1i) =log2(n!) soit (log2(n!)).

La suite n'etait pas demandee.

syrFor=Pi=n i=1log2(i) Pi=n i=1log2(n) n log2(n)syrFor=Pi=n i=1log2(i) 12 (Pi=n i=1log2(i) +Pi=n i=1log2(n+ 1i)) 12 (Pi=n i=1(log2(i) +log2(n+ 1i))) 12 (Pi=n i=1log2(i(n+ 1i))) 12 (Pi=n i=1log2(n)) n2 log2(n)

SoitO(nlog2(n))Soit

(nlog2(n))

Soit (nlog2(n)).Page 6 sur 6

quotesdbs_dbs46.pdfusesText_46
[PDF] la suite définie

[PDF] La Suite numérique

[PDF] La supercificie de la Terre est environ de 5,1 x 10 puissance 8 km²

[PDF] La supersitition

[PDF] la superstition

[PDF] La suprématie militaire et diplmatique

[PDF] la surface (fraction)

[PDF] la surface du globe

[PDF] La surveillance la prévision et la prévention

[PDF] la survie sur l ile p 182 francaix

[PDF] la syllabation en poésie

[PDF] La symbolique chevaleresque dans l'enluminure

[PDF] la symbolique du crane dans arts plastics (peinture,sculture)

[PDF] la symetrie !!;)

[PDF] la symetrie aciale exercice jai mis un lien