5`eme semestre (2006/2007) Algorithmes et structures de données : TD 4 Corrigé Types - Enregistrements - Temps d'un algorithme T(n) Exercice 4 1 Types
Previous PDF | Next PDF |
[PDF] exercices corrigés algorithmepdf
Exercice 5 1 Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et 3 jusqu'à ce que la réponse convienne corrigé - retour au cours
[PDF] Exercices avec Solutions
Exercices Corrigés d'Algorithmique – 1ére Année MI 5 EXERCICE 1 Ecrire un algorithme qui demande un nombre à l'utilisateur, puis calcule et affiche le carré
[PDF] Algorithmique - Correction du TD3
Algorithmique - Correction du TD3 IUT 1ère Année 18 décembre 2012 1 Les boucles (suite) Exercice 1 Ecrire un algorithme qui reçoit en entrée un nombre
[PDF] SUJET + CORRIGE
Écrire un algorithme sontInvOuOpp(a,b) o`u a et b sont deux nombres, qui retourne Dans cet exercice, nous allons adapter des algorithmes de tri vus en cours
[PDF] Algorithmes et structures de données : TD 4 Corrigé - LaBRI
5`eme semestre (2006/2007) Algorithmes et structures de données : TD 4 Corrigé Types - Enregistrements - Temps d'un algorithme T(n) Exercice 4 1 Types
[PDF] Algorithmique et programmation : les bases (Algo) Corrigé
avril–mai 2013 Algorithmique et programmation : les bases (Algo) Corrigé Résumé Ce document décrit les Exercice 1 : Lien entre raffinage et algorithme
[PDF] Algorithmes - Cours, examens et exercices gratuits et corrigés
Algorithmes : Exercices et corrigés Abdallah OBAYE 3 / 24 Tsdi GC2 – ISTA Agadir Les Variables Exercice 1 1 Quelles seront les valeurs des variables A et
[PDF] Algorithmes et programmation en Pascal TD corrigés
TD corrigés Deug 1 Algorithmes et programmation en Pascal Edouard On donne cette liste de propriétés (non vue en cours) avant de poser l'exercice :
[PDF] Les tableaux 1 Exercice 1 - LIPN
Algorithmique et structures de données Ingénieurs 1`ere année Correction du T D 2 Les tableaux 1 Exercice 1 Ecrire les algorithmes permettant : 1
[PDF] Exercices et problemes dalgorithmique - Numilog
proposer une correction entièrement rédigée, rigoureuse et complète de chaque ques- tion On y trouvera, pour chaque notion, des exercices visant la
[PDF] les algues du genre porphyra constituent un élément de base
[PDF] Les algues(CNED)
[PDF] Les aliments biologie
[PDF] Les aliments en anglais
[PDF] Les allégations alimentaires
[PDF] les allèles et les chrs dm ? rendre vite SVP
[PDF] les alliages
[PDF] Les Alliages: BRONZE et AVANTAGES
[PDF] Les alpes françaises entre développement et préservation du milieu
[PDF] les alphabet
[PDF] Les alpinistes et les randonneurs utilisent des aliment lyophilisés (congelés puis déshydratés) Quel intêret représente pour eux ce type d'alimen
[PDF] Les altérations de la molécule d'ADN
[PDF] Les alternances (3 eme déclinaison)
[PDF] les alternatives ? la prison
Universit´e Bordeaux 2 Licence MASS/Scico 5`eme semestre (2006/2007) Algorithmes et structures de donn´ees : TD 4 Corrig´e Types - Enregistrements - Temps d"un algorithme T(n)
Exercice 4.1Types
D´eclarer des types qui permettent de stocker :1. Un joueur de basket characteris´e par son nom, sa date de naissance, sa nationalit´e, et son
sexe type t_sexe = (masculin, feminin); type t_joueur = RECORD nom : string; nation : string; sexe : t_sexe; END;2. Une association de joueurs de basket
type t_assoc = array[1..N] of t_joueur; Remarque :Pour permettre `a l"association de croitre, c"est-`a-direavoir plus de N joueurs, il faudra allouer un tableau dynamique ou une liste...3. Une equipe de basket avec son nom, ses joueurs, ainsi que les points gagn´es et les basket
marqu´es et encaiss´es dans la saison courante. type t_equipe = RECORD nom : string; joueurs : array[1..N] of t_joueur; points : integer; basketmarque : integer; basketencaisse : integer; END; Remarque :Pour les joueurs, il vaudrait mieux allouer un tableau dynamique ou une liste...4. Un tableau de 18 equipes de basket
type t_tableau = array[1..18] of t_equipe; Exercice 4.2Je constate que la somme desnpremiers nombres impairs est ´egale `an2, c"est `a dire que1 + 3 + 5 +...+ (2n-1) =n2.1. Ecrivez lafunction sommeImpairs(n : integer) : integer;qui calcule la somme
desnnombres impairs. function sommeImpairs(n : integer) : integer;var i, somme : integer;begin somme := 0; for i := 1 to n do begin somme := somme + (2*i)-1; end; result := somme; end;2. Ecrivez lafunction carre(n : integer) : integer;qui calculen2
function carre(n : integer) : integer; begin result := n*n; end;3. Faites tourner l"appel de fonctionresultat := sommeImpairs(3);
n sommeiresult 3 0 1 1 2 4 3 94. Faites tourner l"appel de fonctionresultat := carre(3);
n result 3 95. Faites tourner l"appel de fonctionresultat := sommeImpairs(6);
2 nsommeiresult 6 0 1 1 2 4 3 9 4 16 5 256 36
6. Faites tourner l"appel de fonctionresultat := carre(6);
n result 6 367. Quelle algorithme est plus efficace? (Rappel: Si on double la valeur d"entr´ee, comment va
´evoluer le temps d"´execution de l"algorithme). Bien evidemment c"est ce dernier algorithme qui est plus efficace. On dit qu"il est de complexit´e constante - aussi appel´e O(1) - car le temps d"´ex´ecution n"est pas influenc´e par la valeur d"entr´ee de la fonction. Le premier algorithme est decomplexit´e lin´eaire - aussi appel´e O(N) car le temps d"´ex´ecution est lin´eaire en
fonction de la la valeur d"entr´ee de la fonction.Exercice 4.3Complexit´e
1. Consid´erer le tableau suivant :
type t_tableau = array[1..15] of integer;2. Ecrire la fonction
function dedans(quoi : integer) : integer; qui renvoie la position dans le tableau de l"´elementquois"il est dedans, et 0 sinon. function dedans(quoi : integer) : integer; var position : integer; var i : integer; var entree : integer; d´ebut position := 0; i := 1; tant que (i<=15 ET position = 0) faire 3 entree = tab[i];si (quoi = entree) alors position := i; fin si i := i + 1; fin tant que result := position; fin3. Faites tourner l"algorithmeresultat := dedans(31)avec le vecteur
1,3,3,7,8,12,17,18,18,26,29,31,40,44,46.
quoi positionientreeresult 310 1 1 2 3 3 3 4 7 5 8 6 12 7 17 8 18 9 18 10 26
11 29
12 31
12 13 12
4. D´eterminer la fonction de temps maximale ("worst case")T(n) pour un tableau de taille
n.T(n) = 6n + 3
Remarque :Pour etre d´emonstrative, j"avais introduit la variableentr´ee, elle n"est pas forc´ement n´ecessaire. De plus, la comparaisonposition = 0dans la condition de la boucle tant queest optionnel. Si on la met pas, le meilleur cas est aussi le pire de cas, c"est-`a-dire 4 dans tout les cas les 15 it´erations de la boucletant queseront effectu´e. 5Exercice 4.4Complexit´e
1. Vous pouvez maitenant supposer que levecteurest tri´e d"ordre croissant, c"est `a dire que
Consid´erer la fonction suivant :
function enigme(quoi : integer, n : integer) : integer; begin var inf, sup, milieu : integer; var trouve : boolean; inf := 1; sup := n; trouve := FAUX; tant que (sup >=inf ET trouve = FAUX) milieu := (inf + sup) DIV 2; si (quoi = tab[milieu]) alors trouve := VRAI; sinon si (quoi < tab[milieu]) sup := milieu -1; sinon inf := milieu + 1; fin si fin si fin tant que if (trouve = FAUX) result := 0; sinon result := milieu; fin si end2. Faites tourner cette fonctionresultat := enigme(31,15);dans un tableau avec les
valeur de1,3,3,7,8,12,17,18,18,26,29,31,40,44,46. . quoi ninfsupmilieutrouveresult 3115 1 15 FAUX 8 9 12 VRAI 12