Exercice langage C : travailler avec les tableaux
Exercice (1) : Entrelacement de tableaux :
Écrivez une fonction prenant pour paramètres deux tableaux d'entiers A et B de même taille, ainsi que leur taille. Cette fonction devra allouer un nouveau tableau R dont la taille sera le double de celle de A ou B. R sera ensuite construit de la façon suivante:
- Le premier élément de
Rsera le premier élément deA, - le deuxième élément de
Rsera le premier élément deB, - le troisième élément de
Rsera le deuxième élément deA, - etc...
La fonction renverra un pointeur sur le premier élément de R.
Solution :
int *entrelacement(int *A, int *B, int taille)
{
int *R = new int[taille * 2];
for (int i=0; i<taille; i++) {
R[i * 2] = A[i];
R[i * 2 + 1] = B[i];
}
return R;
}
Exercice (2) : maximum et minimum des valeurs d'un tableau :
Ecrire un programme qui détermine la plus grande et la plus petite valeur dans un tableau d'entiers A. Afficher ensuite la valeur et la position du maximum et du minimum. Si le tableau contient plusieurs maxima ou minima, le programme retiendra la position du premier maximum ou minimum rencontré.
Solution :
#include
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int N; /* dimension */
int I; /* indice courant */
int MIN; /* position du minimum */
int MAX; /* position du maximum */
/* Saisie des données */
printf("Dimension du tableau (max.50) : ");
scanf("%d", &N );
for (I=0; I<N; I++)
{
printf("Elément %d : ", I);
scanf("%d", &A[I]);
}
/* Affichage du tableau */
printf("Tableau donné :\n");
for (I=0; I<N; I++)
printf("%d ", A[I]);
printf("\n");
/* Recherche du maximum et du minimum */
MIN=0;
MAX=0;
for (I=0; I<N; I++)
{
if(A[I]>A[MAX]) MAX=I;
if(A[I]<A[MIN]) MIN=I;
}
/* Edition du résultat */
printf("Position du minimum : %d\n", MIN);
printf("Position du maximum : %d\n", MAX);
printf("Valeur du minimum : %d\n", A[MIN]);
printf("Valeur du maximum : %d\n", A[MAX]);
return 0;
}
Exercice (3) : insérer une valeur dans un tableau trié :
Un tableau A de dimension N+1 contient N valeurs entières triées par ordre croissant; la (N+1)ième valeur est indéfinie. Insérer une valeur VAL donnée au clavier dans le tableau A de manière à obtenir un tableau de N+1 valeurs triées.
Solution :
#include
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int VAL; /* valeur à insérer */
int N; /* dimension */
int I; /* indice courant */
/* Saisie des données */
printf("Dimension N du tableau initial (max.50) : ");
scanf("%d", &N );
for (I=0; I<N; I++)
{
printf("Elément %d : ", I);
scanf("%d", &A[I]);
}
printf("Elément à insérer : ");
scanf("%d", &VAL );
/* Affichage du tableau */
printf("Tableau donné : \n");
for (I=0; I<N; I++)
printf("%d ", A[I]);
printf("\n");
/* Déplacer les éléments plus grands que */
/* VAL d'une position vers l'arrière. */
for (I=N ; (I>0)&&(A[I-1]>VAL) ; I--)
A[I]=A[I-1];
/* VAL est copié à la position du dernier */
/* élément déplacé. */
A[I]=VAL;
/* Nouvelle dimension du tableau ! */
N++;
/* Edition des résultats */
printf("Tableau résultat :\n");
for (I=0; I<N; I++)
printf("%d ", A[I]);
printf("\n");
return 0;
}
Exercice (4) : fusion de deux tableaux triés :
Problème: On dispose de deux tableaux A et B (de dimensions respectives N et M), triés par ordre croissant. Fusionner les éléments de A et B dans un troisième tableau FUS trié par ordre croissant.
Méthode: Utiliser trois indices IA, IB et IFUS. Comparer A[IA] et B[IB]; remplacer FUS[IFUS] par le plus petit des deux éléments; avancer dans le tableau FUS et dans le tableau qui a contribué son élément. Lorsque l'un des deux tableaux A ou B est épuisé, il suffit de recopier les éléments restants de l'autre tableau dans le tableau FUS.
Solution :
#include
main()
{
/* Déclarations */
/* Les tableaux et leurs dimensions */
int A[50], B[50], FUS[100];
int N, M;
int IA, IB, IFUS; /* indices courants */
/* Saisie des données */
printf("Dimension du tableau A (max.50) : ");
scanf("%d", &N );
printf("Entrer les éléments de A dans l'ordre croissant :\n");
for (IA=0; IA<N; IA++)
{
printf("Elément A[%d] : ", IA);
scanf("%d", &A[IA]);
}
printf("Dimension du tableau B (max.50) : ");
scanf("%d", &M );
printf("Entrer les éléments de B dans l'ordre croissant :\n");
for (IB=0; IB<M; IB++)
{
printf("Elément B[%d] : ", IB);
scanf("%d", &B[IB]);
}
/* Affichage des tableaux A et B */
printf("Tableau A :\n");
for (IA=0; IA<N; IA++)
printf("%d ", A[IA]);
printf("\n");
printf("Tableau B :\n");
for (IB=0; IB<M; IB++)
printf("%d ", B[IB]);
printf("\n");
/* Fusion des éléments de A et B dans FUS */
/* de façon à ce que FUS soit aussi trié. */
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 IA ou IB sont arrivés à la fin de leur tableau, */
/* 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++;
}
/* Edition du résultat */
printf("Tableau FUS :\n");
for (IFUS=0; IFUS<N+M; IFUS++)
printf("%d ", FUS[IFUS]);
printf("\n");
return 0;
}
Exercice (5) : tri d'un tableau par sélection du maximum :
Problème: Classer les éléments d'un tableau A par ordre décroissant.
Méthode: Parcourir le tableau de gauche à droite à l'aide de l'indice I. Pour chaque élément A[I] du tableau, déterminer la position PMAX du (premier) maximum à droite de A[I] et échanger A[I] et A[PMAX].
Exemple:
Solution :
#include
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int N; /* dimension */
int I; /* rang à partir duquel A n'est pas trié */
int J; /* indice courant */
int AIDE; /* pour la permutation */
int PMAX; /* indique la position de l'élément */
/* maximal à droite de A[I] */
/* Saisie des données */
printf("Dimension du tableau (max.50) : ");
scanf("%d", &N );
for (J=0; J<N; J++)
{
printf("Elément %d : ", J);
scanf("%d", &A[J]);
}
/* Affichage du tableau */
printf("Tableau donné :\n");
for (J=0; J<N; J++)
printf("%d ", A[J]);
printf("\n");
/* Tri du tableau par sélection directe du maximum. */
for (I=0; I<N-1; I++)
{
/* Recherche du maximum à droite de A[I] */
PMAX=I;
for (J=I+1; J<N; J++)
if (A[J]>A[PMAX]) PMAX=J;
/* Echange de A[I] avec le maximum */
AIDE=A[I];
A[I]=A[PMAX];
A[PMAX]=AIDE;
}
/* Edition du résultat */
printf("Tableau trié :\n");
for (J=0; J<N; J++)
printf("%d ", A[J]);
printf("\n");
return 0;
}
Exercice (6) : tri d'un tableau par propagation (bubble sort) :
Problème: Classer les éléments d'un tableau A par ordre croissant.
Méthode: En recommençant chaque fois au début du tableau, on effectue à plusieurs reprises le traitement suivant: On propage, par permutations successives, le plus grand élément du tableau vers la fin du tableau (comme une bulle qui remonte à la surface d'un liquide).
Exemple:
Implémenter l'algorithme en considérant que:
* La partie du tableau (à droite) où il n'y a pas eu de permutations est triée.
* Si aucune permutation n'a eu lieu, le tableau est trié.
Solution :
#include
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int N; /* dimension */
int I; /* rang à partir duquel A est trié */
int J; /* indice courant */
int AIDE; /* pour la permutation */
int FIN; /* position où la dernière permutation a eu lieu. */
/* permet de ne pas trier un sous-ensemble déjà trié. */
/* Saisie des données */
printf("Dimension du tableau (max.50) : ");
scanf("%d", &N );
for (J=0; J<N; J++)
{
printf("Elément %d : ", J);
scanf("%d", &A[J]);
}
/* Affichage du tableau */
printf("Tableau donné :\n");
for (J=0; J<N; J++)
printf("%d ", A[J]);
printf("\n");
/* Tri du tableau par propagation de l'élément maximal. */
for (I=N-1 ; I>0 ; I=FIN)
{
FIN=0;
for (J=0; J<I; J++)
if (A[J]>A[J+1])
{
FIN=J;
AIDE=A[J];
A[J]=A[J+1];
A[J+1]=AIDE;
}
}
/* Edition du résultat */
printf("Tableau trié :\n");
for (J=0; J<N; J++)
printf("%d ", A[J]);
printf("\n");
return 0;
}
Exercice (7) : Entrelacement de tableaux :
Cet exercice a pour but de vérifier les points techniques suivants :
- Utilisation simple de tableaux.
- Un algorithme simple sur un tableau : recherche de l'indice du plus grand élément.
Travail à Faire :
Ecrire un programme qui demande à l'utilisateur de saisir 10 entiers stockés dans un tableau.
Le programme doit ensuite afficher l'indice du plus grand élément.
Solution :
#include
using namespace std;
const int N=10;
int main()
{
int t[N],i,indice;
for(i=0;i<N;i++){cout<<"Tapez un entier ";cin>>t[i];}
indice=0;
for(i=1;i<N;i++)
if(t[indice]<t[i])indice=i;
cout<<"L'indice du plus grand élément est : "<<indice<<endl;
return 0;
}