Exercice 1 : Tri de
Shell
Traduire la fonction TRI_SHELL définie ci-dessous en C.
Ecrire un programme pour tester la fonction TRI_SHELL.
procédure TRI_SHELL(T,N)
| (* Trie un tableau T d'ordre N par la méthode
| de Shell en ordre croissant. *)
| résultat: entier tableau T[100]
| donnée: entier N
| entier SAUT, M, K
| booléen TERMINE
| en SAUT ranger N
| tant que (SAUT>1) faire
| | en SAUT ranger SAUT divent 2
| | répéter
| | | en TERMINE ranger vrai
| | | pour M variant de 1 à N-SAUT faire
| | | | en K ranger M+SAUT
| | | | si (T[M]>T[K]) alors
| | | | | PERMUTER(T[M],T[K])
| | | | | en TERMINE ranger faux
| | | | fsi
| | | fpour
| | jusqu'à TERMINE
| ftant (* SAUT <= 1 *)
fprocédure (* fin TRI_SHELL *)
Remarque: L'algorithme a été développé par D.L.Shell en 1959. En comparant d'abord des éléments très éloignés, l'algorithme a tendance à éliminer rapidement les grandes perturbations dans l'ordre des éléments. La distance entre les éléments qui sont comparés est peu à peu réduite jusqu'à 1. A la fin du tri, les éléments voisins sont arrangés.
Correction exercice 1: Tri de Shell
Traduire la fonction TRI_SHELL définie ci-dessous en C.
Ecrire un programme pour tester la fonction TRI_SHELL.
procédure TRI_SHELL(T,N)
| (* Trie un tableau T d'ordre N par la méthode
| de Shell en ordre croissant. *)
| résultat: entier tableau T[100]
| donnée: entier N
| entier SAUT, M, K
| booléen TERMINE
| en SAUT ranger N
| tant que (SAUT>1) faire
| | en SAUT ranger SAUT divent 2
| | répéter
| | | en TERMINE ranger vrai
| | | pour M variant de 1 à N-SAUT faire
| | | | en K ranger M+SAUT
| | | | si (T[M]>T[K]) alors
| | | | | PERMUTER(T[M],T[K])
| | | | | en TERMINE ranger faux
| | | | fsi
| | | fpour
| | jusqu'à TERMINE
| ftant (* SAUT <= 1 *)
fprocédure (* fin TRI_SHELL *)
Remarque: L'algorithme a été développé par D.L.Shell en 1959. En comparant d'abord des éléments très éloignés, l'algorithme a tendance à éliminer rapidement les grandes perturbations dans l'ordre des éléments. La distance entre les éléments qui sont comparés est peu à peu réduite jusqu'à 1. A la fin du tri, les éléments voisins sont arrangés.
Correction exercice 1: Tri de Shell
#include <stdio.h>
main()
{
/* Prototypes
des fonctions appelées */
void
TRI_SHELL(int *T, int N);
void LIRE_TAB
(int *TAB, int *N, int NMAX);
void ECRIRE_TAB
(int *TAB, int N);
/* Variables
locales */
int T[100]; /*
Tableau d'entiers */
int DIM; /*
Dimension du tableau */
/* Traitements
*/
LIRE_TAB (T,
&DIM, 100);
printf("Tableau donné : \n");
ECRIRE_TAB (T,
DIM);
TRI_SHELL(T,
DIM);
printf("Tableau trié : \n");
ECRIRE_TAB (T,
DIM);
return 0;
}
void TRI_SHELL(int *T, int N)
{
/* Trie un
tableau T d'ordre N par la méthode de Shell */
/* Prototypes
des fonctions appelées */
void
PERMUTER(int *A, int *B);
/* Variables
locales */
int SAUT, M, K;
int TERMINE;
/* Traitements
*/
SAUT = N;
while
(SAUT>1)
{
SAUT /= 2;
do
{
TERMINE=1;
for
(M=0; M<N-SAUT; M++) /* Attention aux
indices! */
{
K=M+SAUT;
if (*(T+M) > *(T+K))
{
PERMUTER(T+M,T+K);
TERMINE=0;
}
}
}
while(!TERMINE); /* Attention: utiliser la négation de */
} /* la condition employée en lang
algorithmique */
}
void PERMUTER(int *A, int *B)
{
int AIDE;
AIDE = *A;
*A = *B;
*B = AIDE;
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
. . .
}
void ECRIRE_TAB (int *TAB, int N)
{
. . .
}
Exercice 2:
Déterminer le maximum de N éléments d'un tableau TAB d'entiers de trois façons différentes:
a) la fonction MAX1 retourne la valeur maximale
b) la fonction MAX2 retourne l'indice de l'élément maximal
c) la fonction MAX3 retourne l'adresse de l'élément maximal
Ecrire un programme pour tester les trois fonctions.
Correction exercice 2:
Déterminer le maximum de N éléments d'un tableau TAB d'entiers de trois façons différentes:
a) la fonction MAX1 retourne la valeur maximale
b) la fonction MAX2 retourne l'indice de l'élément maximal
c) la fonction MAX3 retourne l'adresse de l'élément maximal
Ecrire un programme pour tester les trois fonctions.
Correction exercice 2:
Déterminer
le maximum de N éléments d'un tableau TAB d'entiers de trois façons
différentes:
a) la
fonction MAX1 retourne la valeur maximale
int MAX1(int *TAB, int N)
{
int MAX,I; /* variables d'aide */
MAX=*TAB;
for (I=1; I<N; I++)
if (MAX < *(TAB+I))
MAX = *(TAB+I);
return MAX;
}
b) la fonction MAX2 retourne l'indice de l'élément
maximal
int MAX2(int *TAB, int N)
{
int I,MAX; /*
variables d'aide */
MAX=0;
for (I=1; I<N; I++)
if (*(TAB+MAX) < *(TAB+I))
MAX = I;
return MAX;
}
c) la
fonction MAX3 retourne l'adresse de l'élément maximal
int *MAX3(int *TAB, int N)
{
int *MAX, *P;
/* pointeurs d'aide */
MAX=TAB;
for (P=TAB; P<TAB+N; P++)
if (*MAX < *P)
MAX=P;
return MAX;
}
Ecrire un
programme pour tester les trois fonctions:
#include <stdio.h>
main()
{
/* Prototypes
des fonctions appelées */
int MAX1 (int
*TAB, int N);
int MAX2 (int
*TAB, int N);
int *MAX3(int
*TAB, int N);
void LIRE_TAB
(int *TAB, int *N, int NMAX);
void ECRIRE_TAB
(int *TAB, int N);
/* Variables
locales */
int T[100]; /*
Tableau d'entiers */
int DIM; /* Dimension du tableau */
/* Traitements
*/
LIRE_TAB (T,
&DIM, 100);
printf("Tableau donné : \n");
ECRIRE_TAB (T,
DIM);
printf("MAX1 : %d \n", MAX1(T,DIM)
);
printf("MAX2 : %d \n",
T[MAX2(T,DIM)] );
printf("MAX3 : %d \n", *MAX3(T,DIM)
);
return 0;
}
int MAX1(int *TAB, int N)
{
. . .
}
int MAX2(int *TAB, int N)
{
. . .
}
int *MAX3(int *TAB, int N)
{
. . .
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
. . .
}
void ECRIRE_TAB (int *TAB, int N)
{
. . .
}
Exercice 3 : Tri par sélection
Ecrire la fonction TRI_SELECTION qui trie un tableau de N entiers par la méthode de sélection directe du maximum (voir exercice 7.14). La fonction fera appel à la fonction PERMUTER (définie dans le cours) et à la fonction MAX3 (définie dans l'exercice précédent).
Ecrire un programme pour tester la fonction TRI_SELECTION.
Correction exercice 3 : Tri par sélection
#include <stdio.h>
main()
{
/* Prototypes
des fonctions appelées */
void
TRI_SELECTION(int *T, int N);
void LIRE_TAB
(int *TAB, int *N, int NMAX);
void ECRIRE_TAB
(int *TAB, int N);
/* Variables
locales */
int T[100]; /*
Tableau d'entiers */
int DIM; /* Dimension du tableau */
/* Traitements */
LIRE_TAB (T,
&DIM, 100);
printf("Tableau donné : \n");
ECRIRE_TAB (T,
DIM);
TRI_SELECTION(T, DIM);
printf("Tableau trié : \n");
ECRIRE_TAB (T,
DIM);
return 0;
}
void TRI_SELECTION(int *T, int N)
{
/* Prototypes
des fonctions appelées */
void
PERMUTER(int *A, int *B);
int *MAX3(int
*TAB, int N);
/* Variables
locales */
int I; /* rang à partir duquel T n'est pas trié */
/* Tri par
sélection directe du maximum */
for (I=0 ; I<N-1 ; I++)
PERMUTER(T+I, MAX3(T+I,N-I) );
}
int *MAX3(int *TAB, int N)
{
. . .
}
void PERMUTER(int *A, int *B)
{
. . .
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
. . .
}
void ECRIRE_TAB (int *TAB, int N)
{
. . .
}
Exercice 4 :
Ecrire la fonction INSERER qui place un élément X à l'intérieur d'un tableau qui contient N éléments triés par ordre croissant, de façon à obtenir un tableau à N+1 éléments triés par ordre croissant. La dimension du tableau est incrémentée dans la fonction INSERER.
Ecrire un programme profitant des fonctions définies plus haut pour tester la fonction INSERER.
Correction exercice 4 :
#include <stdio.h>
main()
{
/* Prototypes
des fonctions appelées */
void
INSERER(int X, int *T, int *N);
void LIRE_TAB
(int *TAB, int *N, int NMAX);
void ECRIRE_TAB
(int *TAB, int N);
/* Variables
locales */
int T[100]; /*
Tableau d'entiers */
int DIM; /* Dimension du tableau */
int A; /* Nombre à insérer */
/* Traitements
*/
LIRE_TAB (T,
&DIM, 100);
printf("Tableau donné : \n");
ECRIRE_TAB (T,
DIM);
printf("Introduire le nombre à insérer :
");
scanf("%d", &A);
INSERER(A, T,
&DIM);
printf("Tableau résultat : \n");
ECRIRE_TAB (T,
DIM);
return 0;
}
void INSERER(int X, int *T, int *N)
{
/* Variables
locales */
int I;
/* Insertion de
X dans le tableau T supposé trié: */
/* Déplacer les
éléments plus grands que X d'une */
/* position
vers l'arrière. */
for (I=*N ;
I>0 && *(T+I-1)>X ; I--)
*(T+I) =
*(T+I-1);
/* X est copié
à la position du dernier élément déplacé */
*(T+I)=X;
/* Nouvelle
dimension du tableau: */
(*N)++; /*
Attention aux parenthèses ! */
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
. . .
}
void ECRIRE_TAB (int *TAB, int N)
{
. . .
}
Exercice 5: Tri par insertion
Ecrire la fonction TRI_INSERTION qui utilise la fonction INSERER pour trier par ordre croissant les éléments d'un tableau à N éléments.
Ecrire un programme pour tester la fonction TRI_INSERTION.
Méthode: Trier le tableau de gauche à droite en insérant à chaque fois l'élément I+1 dans le tableau (déjà trié) des I premiers éléments.
Correction exercice 5: Tri par insertion
#include <stdio.h>
main()
{
/* Prototypes
des fonctions appelées */
void
TRI_INSERTION(int *T, int N);
void LIRE_TAB
(int *TAB, int *N, int NMAX);
void ECRIRE_TAB
(int *TAB, int N);
/* Variables
locales */
int T[100]; /*
Tableau d'entiers */
int DIM; /* Dimension du tableau */
/* Traitements
*/
LIRE_TAB (T,
&DIM, 100);
printf("Tableau donné : \n");
ECRIRE_TAB (T,
DIM);
TRI_INSERTION(T, DIM);
printf("Tableau trié : \n");
ECRIRE_TAB (T,
DIM);
return 0;
}
void TRI_INSERTION(int *T, int N)
{
void
INSERER(int X, int *T, int *N);
/* Variables
locales */
int I; /* indice courant */
/* Tri de T par
insertion */
I=1;
while (I<N)
INSERER(*(T+I), T, &I);
}
void INSERER(int X, int *T, int *N)
{
. . .
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
. . .
}
void ECRIRE_TAB (int *TAB, int N)
{
. . .
}
Exercice 6 :
Ecrire la fonction RANGER qui arrange le contenu de ses deux paramètres X et Y de façon à ce que le contenu de X soit plus petit que celui de Y. RANGER retourne la valeur logique 1 si un échange a eu lieu, sinon 0.
Correction exercice 6 :
int RANGER(int *X, int *Y)
{
int AIDE;
if (*X>*Y)
{
AIDE = *X;
*X = *Y;
*Y = AIDE;
return 1;
}
else
return 0;
}
Exercice 7 : Tri par propagation
Ecrire la fonction TRI_BULLE qui trie un tableau de N éléments entiers par ordre croissant en appliquant la méthode de la bulle (tri par propagation - voir exercice 7.15). Employer la fonction RANGER de l'exercice ci-dessus.
Ecrire un programme pour tester la fonction TRI_BULLE.
Correction exercice 7 : Tri par propagation
#include <stdio.h>
main()
{
/* Prototypes
des fonctions appelées */
void LIRE_TAB
(int *TAB, int *N, int NMAX);
void
TRI_BULLE(int *T, int N);
void ECRIRE_TAB
(int *TAB, int N);
/* Variables
locales */
int T[100]; /*
Tableau d'entiers */
int DIM; /* Dimension du tableau */
/* Traitements
*/
LIRE_TAB (T,
&DIM, 100);
printf("Tableau donné : \n");
ECRIRE_TAB (T,
DIM);
TRI_BULLE(T,
DIM);
printf("Tableau trié : \n");
ECRIRE_TAB (T,
DIM);
return 0;
}
void TRI_BULLE(int *T, int N)
{
/* Prototypes
des fonctions appelées */
int RANGER(int
*X, int *Y);
/* Variables
locales */
int I,J; /* indices courants */
int FIN; /* position où la dernière permutation a eu
lieu */
/* permet
de ne pas trier un sous-ensemble déjà trié. */
/* Tri de T par
propagation de l'élément maximal */
for (I=N-1 ; I>0 ; I=FIN)
{
FIN=0;
for (J=0; J<I; J++)
if (RANGER(T+J, T+J+1)) FIN = J;
}
}
int RANGER(int *X, int *Y)
{
. . .
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
. . .
}
void ECRIRE_TAB (int *TAB, int N)
{
. . .
}
Exercice 8 : Fusion de tableaux triés
Ecrire la fonction FUSION qui construit un tableau FUS trié par ordre croissant avec les éléments de deux tableaux A et B triés par ordre croissant. Pour deux tableaux de dimensions N et M, le tableau FUS aura la dimension N+M. (Méthode: voir exercice 7.13)
Ecrire un programme qui teste la fonction FUSION à l'aide de deux tableaux lus au clavier et triés à l'aide de TRI_BULLE.
Correction exercice 8 : Fusion de tableaux triés
#include <stdio.h>
main()
{
/* Prototypes
des fonctions appelées */
void FUSION(int
*A, int *B, int *FUS, int N, int M);
void
TRI_BULLE(int *T, int N);
void LIRE_TAB
(int *TAB, int *N, int NMAX);
void ECRIRE_TAB
(int *TAB, int N);
/* Variables
locales */
/* Les tableaux
et leurs dimensions */
int A[100],
B[100], FUS[200];
int N, M;
/* Traitements
*/
printf("*** Tableau A ***\n");
LIRE_TAB (A,
&N, 100);
printf("*** Tableau B ***\n");
LIRE_TAB (B,
&M, 100);
TRI_BULLE(A,
N);
printf("Tableau A trié : \n");
ECRIRE_TAB (A,
N);
TRI_BULLE(B,
M);
printf("Tableau B trié : \n");
ECRIRE_TAB (B,
M);
FUSION(A,B,FUS,N,M);
printf("Tableau FUS : \n");
ECRIRE_TAB
(FUS, N+M);
return 0;
}
void FUSION(int *A, int *B, int *FUS, int N, int M)
{
/* Variables
locales */
/* Indices
courants dans A, B et FUS */
int
IA,IB,IFUS;
/* Fusion de A
et B dans FUS */
IA=0, IB=0; IFUS=0;
while ((IA<N) && (IB<M))
if (*(A+IA)<*(B+IB))
{
*(FUS+IFUS)=*(A+IA);
IFUS++;
IA++;
}
else
{
FUS[IFUS]=B[IB];
IFUS++;
IB++;
}
/* Si A ou B
sont arrivés à la fin, alors */
/* copier le
reste de l'autre tableau. */
while (IA<N)
{
*(FUS+IFUS)=*(A+IA);
IFUS++;
IA++;
}
while (IB<M)
{
*(FUS+IFUS)=*(B+IB);
IFUS++;
IB++;
}
}
void TRI_BULLE(int *T, int N)
{
/* Prototypes
des fonctions appelées */
int RANGER(int
*X, int *Y);
. . .
}
int RANGER(int *X, int *Y)
{
. . .
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
. . .
}
void ECRIRE_TAB (int *TAB, int N)
{
. . .
}
1 commentaires:
joya shoes 414t9vlmtw724 joyaskodanmark,joyaskonorge,joyaskorstockholm,joyacipo,zapatosjoya,joyaschoenen,scarpejoya,chaussuresjoya,joyaschuhewien,joyaschuhedeutschland joya shoes 436j1vopma501
Enregistrer un commentaire