Examen d’algorithmique

Algorithmes : Exercices et corrigés Abdallah OBAYE 14 / 24 Tsdi GC2 – ISTA Agadir Ecrire "Catégorie Poussin" Finsi Fin On peut évidemment écrire cet algorithme de différentes façons, ne serait-ce qu’en commençant par la catégorie la plus jeune Les boucles Exercice 5 1 Variable N en Entier Debut N 0 Ecrire "Entrez un nombre entre 1

Les sous programmes - cours, examens

Exemple de problème Écrire un algorithme qui calcule et affiche la moyenne des valeurs absolues de trois nombres A,B,C, sachant qu'on n'a pas la fonction ABS Algorithme MoyValAbsolu ; Déclaration A,B,C,A1,B1,C1 : entier ; moy : réel ; Début · valeur absolue a été effectué 3 fois de la même · manière pour A, pour B et pour C

Examen d’algorithmique - IRIF

On veut d´eﬁnir un algorithme de tri pour des tableaux de taille n ne contenant que deux valeurs distinctes On cherche `a trier dans l’ordre croissant Par exemple pour le tableau suivant de taille 5 : [2,4,4,2,2],onveutobtenir [2,2,2,4,4] 1 Ecrire un algorithme de tri bas´e sur une m´ethode de comptage 2

Algorithmique et programmation - USTO-MB

une activité fondamentale en informatique La programmation peut être vue comme l'art de déterminer un algorithme (une démarche) pour résoudre un problème et d' exprimer cet algorithme au moyen d'un langage de programmation 1 2 Définitions et unités de mesure Un bit (binary digit) est un élément binaire Sa valeur est donc 0 ou 1

Brahim BESSAA - الموقع الأول للدراسة في

Exercices Corrigés d’Algorithmique – 1ére Année MI 13 EXERCICE 10 Ecrire un algorithme permettant de convertir un entier N écrit sous forme binaire en sa valeur décimale Exemple : N =10111010 après conversion on obtient valeur décimale = 186 Algorithme conversion ; Var VB,B,D,P2 :entier ; Debut

SUJET + CORRIGE - Unité de formation d’informatique

i (2 points) Ecrire un algorithme rangSelection(T,r) fortement inspir e de l’algorithme ou du programme python triSelection(T) qui r esout le probl eme de la s election Ne pas oublier de s’assurer que le rang d esir e correspond a un indice du tableau Solution: Deux solutions parmi d’autres def rangSelection (T, r ): if r=len (T):

Cours d’Algorithmique et structures de données 1

On cherche à mesurer la complexité d’un algorithme indépendamment de la machine et du langage utilisés, c-à-d uniquement en fonction de la taille des données n que l’algorithme doit traiter Par exemple, dans le cas de tri d’un tableau, n est le nombre d’éléments du

Les sous-programmes (Algo) Corrigé - ENSEEIHT

1 Algorithme Guider_robot 2 3-- Guider le robot de la salle de cours vers le secrétariat 4 5-- la définition des sous-programmes est omise 6 7 Début 8-- Sortir de la salle de cours 9 progresser(2) 10 tourner_gauche 11 progresser(3) 12 13-- Longer le couloir (jusqu’à la porte du vestibule) 14 tourner_droite 15 progresser(9) 16

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_dbs18.pdfusesText_24

[PDF] Examen d’algorithmique - IRIF