[PDF] Examen dalgorithmique Année 2015–2016. Exercice

View - Download Examen dalgorithmique

Previous PDF

Next PDF

Universit´eParisDiderotL2Informatiqu eAnn´ee2015-2016

Examend'algorithmique

jeudi14janvier2 01615h 30-18h30/Aucundocumen tautoris´e Moded'emploi :Lebar` emeestdonn´e`atitreindic atif.Laqual it´edelar´edaction desalgo rithmesetdesexplicationsserafortem entpris eencom ptepourla note.Onpeutt oujourssu pposerunequestionr´esol ueetpasser`alasuite.

Exercice1:D´eroulerde sal gor ithmes(4points)

1.Onconsid` erel'algorithmeP1ci-dessous:

DefP1(entier x):

Six==0Alors Retourner0

Sinon:

a=0 b=1 i=2 tantquei <=xfaire: aux=b b=a+b a=aux i=i+1

Retournerb

D´ecrirecequefaitl'al gorith meP1appel´eavecleparam`etre 6.Ond´ecrirapr´ecis´ ement l'´etatdesvariablesaetbaucoursde l'algorithme.

2.Onconsid` erel'algorithmeP2ci-dessous:

DefP2(x) :

Six==0ou x==1AlorsRetourner x

SinonRetourner P2(x-1)+P2(x-2)

D´ecrirecequefaitl'alg orith meP2appel´eavecleparam`etre6. Ond´ecrirapr´ecis´emen t touslesappe lsdefoncti ons.

3.Comparercesdeuxalgorit hmes.

Exercice2:Tripourdeuxv ale urs- 4points

Onveut d´efinirunalg orithmedetripourdesta bleaux detaillennecon tenantque deuxvaleursdis tinctes.Oncherc he`atrierdansl'ordrecroissant. Parexem plepourletableausuiv antdetaille5 :[2,4,4,2,2],onveutobtenir [2,2,2,4,4]

1.Ecrireunalgorithm edetri bas´esurunem´ethodedecomp tage.

2.Ecrireunalgorithme quitri eletableauennefaisantqu'unseu lparcours dutableau.

1/4 Universit´eParisDiderotL2Informatiqu eAnn´ee2015-2016

Exercice3:Algorithmes sur les arbres-6points

Onconsid` eredesarbrebinairescontenantdesv aleursenti `eres danslesno euds,comme dansl'exe mpleci-dessous: Onsupp osequecesarbressont repr´esen t´es pardes structureschaˆın ´ees(commeen cours).Unnoeuddel'arbr e( typenoeud)serarepr´esent´eparunestructureayantles champsdevaleurss uivant s: - unchamp denomvaletde typeentiercontenantlavaleurstock ´ee; - unchamp denomfgetde typearbrecontenantl'adressedufil sgauche; - unchamp denomfdetde typearbrecontenantl'adressedufil sdroit. Etun arbreestun pointeur (adresse)versunnoeud(l'adresse0d´esigneunarbre vide). Lorsqu'unnoeud n'apasdefilsgauche,son champfgvaut0(etc'es tpa reilpourl efils droitav ecfd).Unnoe udq uin'anifilsgauc he,nifilsd roitestun efeuille. Siaestun arbren onvide,a->vald´esignelavaleurstock´e e`asa racine(lepremier noeuddel'arbre),a->fgd´esignel'adressedufils gauche(doncunarbre),eta->fgd´esigne l'adressedufilsdroit,etc.

1.Dessinerlastructurechaˆ ın´eer epr´esentantl'arbretestci-dessous:

2. Ecrireunalgorith meSommequi´e tantdonn´eunarbrearetournelasommedetoutes lesvaleurss tock´eesdansle snoeudsdecetarbre(et0sil'arbreestvide).

NB:S ur l'exemple ,ondoitrenvoyer36.

Profilsugg´er´e :entierSomme(arbrea)

Appliquervotrealgorithmes url'arbretest(etd´ec rireles´eventuelsappelsde fonction,ouit´erations. ..) . 2/4 Universit´eParisDiderotL2Informatiqu eAnn´ee2015-2016 3. Ecrireunalgorithm eCptFeuillequi´etant donn´eunarbrearetournelenombre defe uillesdel'arbrea.

NB:S ur l'exemple ,ondoitrenvoyer4.

Profil:entierCptFeuille(arbrea)

Quellevaleur retournevotrealgorithmesur l'arbretest?

4.Ecrireunalgorithm eCptOccqui´e tantdonn´eunarbreaetun entierxretournele

nombred'occurre ncesdexdansl'arbre deracine a.

NB:S ur l'exemple etavecx=4,ondoitrenvoyer2.

Profilsugg´er´ e:entierCptOcc(arbrea, entierx) Quellevaleur retournevotrealgorithmesur l'arbretestavecx=4?

5.Ecrireunalgorit hmeHauteurqui´e tantdonn´eunarbrearetournelahauteurde

l'arbre(lalongueurdup luslon gchemindirectentrelarac ineetu nefeuille,e tpar conventiononprendra-1commehaut eurp ourl'arbrevide).

NB:S ur l'exemple ,ondoitrenvoyer3.

Profilsugg´er´e :entierHauteur(arbrea)

Quellevaleur retournevotrealgorithmesur l'arbretest?

Exercice4:Backtrack ing- 6po ints

Ons'int ´eresseiciauxmotsconstruits`apartird'unalphabet (unensem blefinide lettres).Parexemple,si ={a,b,c},alorslesmotsaaab,abc,abbbbbaaaabsontdesmot s possibles.Lemotvideestnot´e "etil estaussiunm otpossi ble(de longueu r0).Maisl e motabbdaabn'estpaspossiblec ardn'appartientpas`a⌃. Danscetexerc ice,onpour rautilisertouteslesfonc tions classiquessurlesch aˆınesde

caract`eres:concat´enation (+), acc`esaui-`emecaract`e re(w[i]),longueu r(|w|),la r´e p´etition

d'unele ttreifois(i*'a' )...

1.Etantdonn´eu nalphabet⌃repr´esent´eparuntableauTdetaillen(T[i]estla

i-`emelettre) etunentierk,´ecrireunalgorithmequi achetousl esmots delo ngueurkpossiblesavec⌃.

NB:Av ecl' alphabet

ac,ba,bb,bc,ca,cb,cc. Appliquervotrealgorit hme`al'al phabet⌃={a,b}(doncT=[a,b]etk=3. Ond ´ecriraavecpr´ecisionle d´eroul´edel'algorithme. Profilsugg´er´e sialgorithmer´ecursif:voidGenererMot(T,k,w) o`uwestle moten coursdeconstr uction(m otvideaupremierappel).Etprofil sugg´er´epou rversion it´erative:voidGenererMot(T,k) .

2.Onrepr endlaquestionpr´ec´ed entema iscettefois,onrempla cel'argumentkpar

untableau decaract`e resm[-]delongueur kquivaimpos erunmo tifparticulier auxmotsrec herch´ es:soitm[i]estun elettrede⌃etal orstouslesmot sach´es parl'algorithmede vronta voircettelettre`a lapositioni,soitm[i]est*etalor s n'importequellelettre de peutsetrouver` alaposition i.

Ecrireunalgorithme

pourr´eso udreceprobl`eme.

NB:Av ec l'alphabe t

3/4 Universit´eParisDiderotL2Informatiqu eAnn´ee2015-2016 pr´ec´edentepourk=2. Donnerler´esul tatdel'ap plicationdevotrealgorithmepourl'alph abet⌃= {a,b,c}etm=[*,a,a,*].

3.Onmodifie leprobl`emepr´ ec´eden tendonnantuntableaud'entiers Nb[-]`ala

placedumotifm[-]:Nbvad´ ecrirelatailledess´eque ncesde lettresidentiques. Par exemple,siNbestde taille3 etqueNb[0]=3,Nb[1]=2etNb[2]=1,alorsles motsre cherch´escommencerontparunelettrer´ep´et´e etroisfois,puisuneautre(pas lamˆem e!)serar´ep´et´ee2fo is,etlemotse termineraparundernierchangemen t delet tre(sansr´ep´etiti on).Doncavec ={a,b,c}etcet ableau Nb,onobtiendrait lesmotssuivan ts:aaabba,aaabbc,aaacca,aaaccb,bbbaab,bbbaac,bbbcca,bbbccb, cccaab,cccaac,cccbba,etcccbbc. Modifierl'algorit hmepr´ec´edentpourr´esoudreceprobl`eme. Donnerler´esult atdel'ap plicationdevotrealgorithmepourl'alp habet⌃= {a,b}etNb=[2,4,3]. 4/4quotesdbs_dbs4.pdfusesText_8

[PDF] introduction générale sur l informatique

[PDF] informatique s4 smp pdf

[PDF] qcm langage c corrigé pdf

[PDF] informatique s4 pdf

[PDF] examen qcm langage c

[PDF] qcm langage c pointeur

[PDF] comment séparer les constituants d un mélange 5ème chimie

[PDF] agir sur le monde informer s'informer déformer

[PDF] informer s'informer déformer eduscol

[PDF] frise chronologique laicité en france

[PDF] chronologie laicité france

[PDF] la laicité en france

[PDF] frise chronologique laïcité

[PDF] module d'osmose inverse en pdf

[PDF] ordre de mise ? disposition bpo 210