Accueil     Soft. MacOSX     Soft. MacOS/PC     PHP     ROMS GBA     TP d'info     TI-92     DBZ-GT     Martingales     Galeries     Liens     @  

Correction Partiel 2001 Nov. Prog&Algo

Ex 1.1 : A faire...
Vide(Creer(E))= Vrai
Vide(Ajouter(E,X))= Faux
Ajouter(E,X)= ajoute un element en queue de E
Supprimer(Ajouter(E,X),Y)= Y apprtient a E, X n'apprtient plus a E. taille de E inchangé
Cardinal(Creer(E))= 0
Cardinal(Ajouter(E,X),Y)= Cardinal(E) + 1
Cardinal(Supprimer(E,X))= Cardinal(E) - 1 (E∫0)
Pred(Succ(E))= E (Si E n'est pas le dernier de l'ensemble)
Succ(Pred(E))= E (Si E n'est pas le premier de l'ensemble)

Ex 1.2 :
typedef int Element; /* Je met int de maniere arbitraire, on peut aussi mettre float, ou autre chose... */
typedef struct Cellule {
Element valeur;
struct Cellule * suivant;
struct Cellule * precedent;
} Cellule;
typedef struct Cellule * Ensemble;

Ex 1.3 :
Avantages: mémoire illimité, pas besoin de connaitre la taille de l'ensemble (a l'inverse d'un tableau) on peut donc ajoute autant d'elements que l'on veut !
Inconvenients: impossible d'acceder directement a une valeur donne, on est oblige de parcourir la liste chainee pour cela (perte de temps)

Ex 1.4 :
X n'appartient pas a E.

Ex 1.5 :
/* pour APPARTIENT, il faut preciser que l'Ensmble E n'est pas classe dans un ordre croissant ou decroissant */
/* BOOL : Booleen */
BOOL Appartient(E:Ensemble,X:Element) { /* ITERATIF */
while(E!=NULL) {
if (E->valeur==X)
return(VRAI);
E=E->suivant;
}
return(FAUX);
}
BOOL Appartient(E:Ensemble,X:Element) { /* RECURSIF */
if (E==NULL)
return(FAUX);

if (E->valeur==X)
return(VRAI);

return(Appartient(E->suivant,X));
}


Nat Cardinal(E:Ensemble) { /* ITERATIF */
Nat compt=0;
while(E!=NULL) {
compt++;
E=E->suivant;
}
return(compt);
}
Nat Cardinal(E:Ensemble) { /* RECURSIF */
if (E==NULL)
return(0);
else
return(Appartient(E->suivant)+1);
}

Ex 1.6 :
/* E est trie dans l'ordre croissant */
BOOL Appartient(E:Ensemble,X:Element) { /* RECURSIF */
if (E==NULL)
return(FAUX);

if (E->valeur>X)
return(FAUX);

if (E->valeur==X)
return(VRAI);

return(Appartient(E->suivant,X));
}

©2002 All Rights Reserved to Didier STRAUS www.Software-DS.com

Ex 1.7 :
Ensemble Min(E:Ensemble) { /* ITERATIF, on suppose E non vide */
Ensemble M;
M=E->valeur;
E=E->suivant;
while(E!=NULL) {
if ((E->valeur)<(M->valeur))
M=E;
E=E->suivant;
}
return(M);
}

Ex 1.8 :
Ensemble Min(E1,E2:Ensemble) { /* ITERATIF, on suppose E non vide */
if (E1==NULL)
return(E2);
if ((E1->valeur) < (E2->valeur))
return(Min(E1->suivant,E1));
/* else */
return(Min(E1->suivant,E2));
}

Ex 1.9 :
Ajouter(E1,E2:Ensemble){

while(E1->suivant!=NULL){
E1=E1->suivant;
}

E1->suivant=Min(E2); /* Min de 1.7 */
E1->suivant->suivant=NULL;
}

©2002 All Rights Reserved to Didier STRAUS www.Software-DS.com

Ex 1.10 :
Effacer(E:Ensemble){
Ensemble P;

P=Min(E);
P->precedent->suivant=P->suivant;
P->suivant->precedent=P->precedent;
free(P);
}

Ex 1.11 :
Tri_Selection(E:Ensemble){
Ensemble E2;
Creer(E2);

while(Cardinal(E)!=0){
Ajouter(E2,E);
Effacer(E);
}
E=E2;
}

©2002 All Rights Reserved to Didier STRAUS www.Software-DS.com

Ex 1.12 :
Oui, le tri rapide consiste a diviser un tableau en 2 sous tableau et a trier
les 2 sous tableau par rapport a un pivot.

Ex 1.13 :
Union:
Si E1 est vide, on recopie E2 dans E
Si E2 est vide, on recopie E1 dans E

Si E1 et E2 non vide:
E1 et E2 sont trie tous les 2, donc on va recopier la valeur de E1 dans E
s'il n'y a pas de valeurs plus petite que E1 dans E2 (si c'est le cas, on
recopira ces valeurs dans E puis on copira la valeur de E1 dans E)
Les valeurs recopier seront supprimer
Algo iteratif:
tant que !vide(E1) et !vide(E2) faire
si vide(E1) alors
si !Appartient(E,Val(E2)) alors ajouter(E,val(E2));
supprimer(E2);
sinon si vide(E2) alors
si !Appartient(E,Val(E1)) alors ajouter(E,val(E1));
supprimer(E1);
sinon si Val(E1)<Val(E2) alors
si !Appartient(E,Val(E1)) alors ajouter(E,val(E1));
supprimer(E1);
sinon
si !Appartient(E,Val(E2)) alors ajouter(E,val(E2));
supprimer(E2);
fin tant que

Ex 1.14 :
Inter:
Si E1 est vide, E=NULL , on a fini
Si E2 est vide, E=NULL , on a fini

Si E1 et E2 non vide:
on prend la valeur de tete de E1, on rechercher si elle existe dans E2, si c'est le cas on
la memorise dans E2 et on la supprime de E1.
(Pour une meilleur optimisation, on n'utilise pas la fonction Appartient !)
Algo iteratif:
si vide(E1) ou vide(E2) alors
E=NULL
sinon
tant que !vide(E1)
si (Val(E1)==Val(E2) alors
ajouter(E,Val(E1));
supprimer(E1);
supprimer(E2);
sinon si (Val(E1)<Val(E2) alors
supprimer(E1);
sinon
supprimer(E2);
fin tant que

Ex 1.15 :
typedef int Element; /* Je met int de maniere arbitraire, on peut aussi mettre float, ou autre chose... */
typedef struct Cellule {
Element valeur;
int nb; /* nombre de fois */
struct Cellule * suivant;
struct Cellule * precedent;
} Cellule;
typedef struct Cellule * Multi_Ensemble;

Ex 1.16 :
int c;
Element E
Liste K,M
K=L
tant que K->suivant∫NULL faire
E=K->Valeur;
c=0;
M=L
tant que M->suivant∫NULL faire
si M->valeur==E alors
c=c+1;
fin tant que
ajouter(MU,E,c);
fin tant que


Cette correction est ma correction, elle ne vous permet pas d'avoir un 20/20 mais une bonne note.
©2002 All Rights Reserved to Didier STRAUS www.Software-DS.com





Haut de la page - Page précédente - Page générée en 0.00977 sec.
Recherche personnalisée
 

1815782 visiteurs.   ©2001-2019 All Rights Reserved to Software-DS.com
Made with a mac  
Confidentialité