Examen dalgorithmique PDF Examen d'algorithmique Exercice 1 :

Exercices avec Solutions

Cet ouvrage regroupe des exercices des séries des travaux dirigés et examens (avec corrigés) du module Algorithmique de la première année MI (USTHB).

Examen dalgorithmique et programmation

Les 4 exercices sont indépendants. Exercice 1. Tri de notes. On consid`ere deux liste etudiants et notes de longueur n ? N telles que pour tout entier

Langage C : énoncé et corrigé des exercices IUP GéniE

apr è s l'échange. Exercice 3 Ecrire un progra mm e q ui a ffi che l es code ASCII des l ettres et des chiff res sous l a.

SUJET + CORRIGE

UE J1BS7202 : Algorithmique et Programmation. Épreuve : Examen Pour cet exercice du fait que les indices d'un tableau T sont compris entre 0 et ...

INF201 Algorithmique et Programmation Fonctionnelle - Cours 1

Algorithmique et Programmation Fonctionnelle. Cours revoir le cours faire des exercices . ... Une feuille (A4) autorisée pour les examens (à confirmer).

cours-python.pdf

22 mars 2018 Introduction à la programmation Python pour la biologie ... 2.11 Exercices . ... Le cours est disponible en version HTML 2 et PDF 3.

INF201 Algorithmique et Programmation Fonctionnelle - Cours 1

Algorithmique et Programmation Fonctionnelle. Cours revoir le cours faire des exercices . ... Une feuille (A4) autorisée pour les examens (à confirmer).

EXAMENS

Le sujet de cette épreuve comporte obligatoirement un exercice d'algorithmique (programmation). L'épreuve est notée sur 100 points distribués entre les

Algorithmique & programmation en langage C - vol.1 - Archive

1 févr. 2019 Supports de cours vol.1 – Période 2005-2014 ... d'algorithmique et de programmation en langage C donnés à la Faculté ... 4.2.7 Exercices.

Examen dalgorithmique

Examen d'algorithmique Exercice 1 : Dérouler des algorithmes (4 points) ... l'état des variables a et b au cours de l'algorithme.

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_dbs46.pdfusesText_46

[PDF] Examen dalgorithmique Examen d'algorithmique Exercice 1 :