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] 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] Exercices avec Solutions
Les Structures de Contrôle (Conditionnelles – Itératives) Exercices Corrigés d' Algorithmique – 1ére Année MI 5 EXERCICE 1 Ecrire un algorithme qui
[PDF] Algorithmique et Structures de Données POLYCOPIEDECOURS
Il constitue un manuel de cours et d'exercices sur une partie du domaine de programmation Les lecteurs ne nécessitent aucun pré requis sur les l' algorithmique
[PDF] Exercices et problèmes dalgorithmique - Adrien Poupa
Corrigés des exercices et des problèmes intervient à l'EFREI en algorithmique et structures de données, théorie des langages et techniques de compilation
[PDF] 25 ALGORITHMIQUE ET STRUCTURES DE DONNEES 1
Structures de données (enregistrements, tableaux) et algorithmes associés situations de la vie quotidienne (déroulement d'une journée, les repas, les R DALMASSO, P WITOMSKI "Analyse de Fourier et applications" Exercices corrigés
[PDF] Les tableaux 1 Exercice 1 - LIPN
Algorithmique et structures de données Ecrire les algorithmes permettant : 1 Le calcul du nombre d'occurences d'un élément donné dans un tableau
[PDF] Correction TD 05 :Structures de données indexées - LISIC
Ensuite, ce tableau est affiché par afficheTab Exercice 3 : Copie et échange a- Algorithme créeTab(n : entier) : tableau d'entier
[PDF] Algorithmique et programmation : les bases (Algo) Corrigé
d'un algorithmique, les variables, les types, les constantes, les expressions et les Exercice 8 : Cube d'un réel (avec une variable) les structures de contrôle de Pascal avec les mots-clés de fin de structure de Modula-2 ; La partie déclarations permet de déclarer les données qui sont utilisées par le programme
[PDF] Algorithmique I - École normale supérieure de Lyon
1 7 Exercices Ce polycopié rassemble les cours et travaux dirigés (avec corrigés) du module Bien sûr, il faudrait discuter d'une structure de données
[PDF] exercices corrigés d'algorithmique sur les boucles pdf
[PDF] exercices corrigés d'algorithmique sur les matrices
[PDF] exercices corrigés d'algorithmique sur les matrices pdf
[PDF] exercices corrigés d'analyse de la variance
[PDF] exercices corrigés d'analyse factorielle des correspondances
[PDF] exercices corrigés d'economie de developpement pdf
[PDF] exercices corrigés d'économie financière pdf
[PDF] exercices corrigés d'économie générale avec corrigés détaillés
[PDF] exercices corrigés d'économie générale avec corrigés détaillés pdf
[PDF] exercices corrigés d'économie générale pdf
[PDF] exercices corrigés d'économie internationale
[PDF] exercices corrigés d'économie politique pdf
[PDF] exercices corriges d'estimation
[PDF] exercices corrigés d'estimation et échantillonnage pdf
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