Correction TP X01 Structure de données et algorithmique.
Bonjour les développeurs , j’espère que vous allez très bien , aujourd'hui , je vais avec vous un tp qu'un ami m'a envoyer dernièrement , apparemment , il est conçu a la faculté des science saad dahleb en Algérie , Bonne lecture
Université Saad
Dahleb Blida
Faculté des Sciences
Département
d’Informatique
1ère Epreuve de Moyenne Durée
« Structures de Données et Algorithmes »
Février 2010
Exercice 1 (7 pts): On se propose
d’implémenter les algorithmes de recherche auto-adaptative appliqués à une LLC
unidirectionnelle.
1 – Rappeler en deux lignes ce
qu’est la recherche auto-adaptative (1pt)
La
recherche auto-adaptative consiste à favoriser la recherche ultérieure d’un
élément déjà recherché. A chaque fois qu’un élément est recherché, sa position
se rapproche du début.
2 – Rappeler les deux méthodes
permettant d’implémenter une technique de recherche auto-adaptative (1 pt)
La
première méthode consiste à placer l’élément recherché en tête de la
liste ; la seconde consiste à le faire monter d’un rang (s’il est 20e
par exemple, il devient 19e).
3 – Nommer les deux idées
permettant d’implémenter la recherche auto-adaptative (idée1 et idée2).
Rappeler alors le constat de Donald Knuth relatif aux deux idées. (1pt)
Si
l’on nomme les deux idées précédemment décrites idée1 et idée2 dans l’ordre où
elles ont été énoncées, selon Knuth, si on a un nombre de recherches inférieur
ou égal à n2, n étant le nombre d’éléments, la première idée est
meilleure. Au-delà de ce seuil, la seconde est meilleure.
4 – Ecrire deux fonctions C
distinctes réalisant chacune une des deux idées (une fonction C pour la
première idée et une seconde pour la seconde) appliquée à une LLC
unidirectionnelle. (2pts pour chaque fonction)
int
idee1(liste *l, int e)
{
int sortie = 0; int x;
liste p = *l; liste prec = NULL;
while ((p != NULL) &&
(sortie == 0))
if
((x = val(p)) == e)
{
aff_adr(prec,
suiv(p));
aff_adr(p,
*l);
*l
= p;
sortie
= 1;
}
else
{
prec
= p;
p = suiv(p);
}
return sortie;
}
int
idee2(liste *l, int e)
{
int sortie = 0; int x;
liste p = *l; liste prec = NULL;
while ((p != NULL) &&
(sortie == 0))
if
((x = val(p)) == e)
{if
(prec != NULL)
{
aff_val(p,
val(prec));
aff_val(prec,
x);
}
sortie
= 1;
}
else
{
prec
= p;
p
= suiv(p);
}
return sortie;
}
Exercice 2 (4pts):
On voudrait écrire une fonction C
« récursive » qui évalue un nombre écrit en binaire. La fonction aura
en entré une chaîne de caractères représentant un nombre binaire et donnera en
sortie l’équivalent décimal. Exemple : la fonction ayant en entrée la
chaîne « 11011 » donnera la valeur 27.
Ecrire la fonction C
« récursive » effectuant ce travail.
int BinToDec(char c[])
{
int
sortie = 0, n = strlen(c);
if (n != 0)
if (c[0] ==
'1')
sortie
= pow(2,n-1) + BinToDec(c+1);
else
sortie
= BinToDec(c+1);
return sortie;
}
Exercice 3 (6pts) :
1 – rappeler le principe du tri
par insertion (1pt)
Le
tri par insertion à considérer, lorsque l’itération arrive au ie
élément, que les éléments allant du premier au (i-1)e sont triés.
Ainsi, si le ie élément n’est
pas à sa place (il est plus petit que le (i-1)e), il faudra le
placer à sa place dans l’intervalle [premier, (i-1)e[.
2 – ce tri s’applique-t-il aux
LLC unidirectionnelles (0,5
pt)? aux LLC bidirectionnelles ? (0,5 pt)
Oui il s’applique aux LLC
unidirectionnelles. Pour placer l’élément à sa place dans
l’intervalle [premier, (i-1)e[, il suffira de démarrer les tests
pour savoir s’il est plus petit que les éléments de l’intervalle à partir du
début de l’intervalle et non de la fin car on ne peut aller de la fin au début,
les chaînages ayant un sens unique.
Il
s’applique également aux LLC bidirectionnelles. On peut, lors des comparaisons
nécessaires pour placer l’élément, commencer indifféremment du premier au (i-2)e
ou du (i-2)e au premier.
3 – que faudrait-il faire afin
que la fonction C qui effectue le tri s’applique sans aucune modification aussi
bien aux LLC unidirectionnelles qu’aux LLC bidirectionnelles ? (1 pt)
Etant
donné que pour la LLC
uni., il faut comparer avec le premier puis le second jusqu’au (i-2)e au besoin
et que le LLC bidi., on peut indifféremment aller du premier au (i-2)e
ou du (i-2)e au premier, il suffit de choisir la solution qui
convient aux deux à la fois, à savoir comparer avec le premier puis le second
etc. et n’opérer que des changements de valeurs et non de chaînages, le
changement de valeurs étant le même dans les deux cas alors que le changement
de chaînage est différent.
4 – Ecrire une fonction C qui
effectue ce tri et qui soit utilisable pour les deux types de listes
void
TriInsertion(liste l)
{
liste p,prec,q,s;
int x,y;
if (l != NULL)
{
prec
= l;
p
= suiv(l);
while
(p != NULL)
{
if
((x = val(p)) < val(prec))
{
//trouver
la place de l'élément
q
= l;
while
((y = val(q)) < val(p))
q
= suiv(q);
//q
pointe la place ou devrait se placer l'élément
//il
faut déplacer tous les autres
s = q;
while
(q != suiv(p))
{
y
= val(q);
aff_val(q,
x);
x
= y;
q
= suiv(q);
}
}
prec = p;
p = suiv(p);
}
}
}
Exercice 4 (3pts) :
On voudrait transformer un nombre
représenté par une chaîne de caractères en un autre nombre qui sera copié dans
la chaîne d’origine de la façon suivante :
Tous les chiffres pairs
deviennent en tête dans leur ordre d’origine et tous les chiffres impairs
seront copiés à la suite des pairs dans leur ordre inverse.
Exemple : 123456 è 246531
Ecrire une fonction C qui
transforme ainsi les chaînes-nombres en utilisant une file et une pile.
(utiliser les fonctions du modèle Pile et File sans les réécrire)
void
transforme(char c[])
{
file F; pile P;
int x;
int n = strlen(c);
int i;
for
(i = 0; i<n ; i++)
if
((c[i]-'0') % 2 == 0)
enfiler(&f,
c[i]);
else
empiler(&p,
c[i]);
i
= 0;
while
(Desenfiler(&f, &x))
c[i++]
= x;
while
(Desempiler(&p, &x))
c[i++] = x;
}
pour consulter plus d'exercices en algorithmique ou programmation langage c : par ici
le lien vers les questions de ce tp : par ici
