REPUBLIQUE DEMOCRATIQUE DU CONGO
INSTITUT SUPERIEUR D’INFORMATIQUE ET DE GESTION
I.S.I.G / GOMA
B.P 841 / GOMA
TP
ALGORITHMIQUE ET MÉTHODES DE PROGRAMMATION
LIC 2/LIAGE
GROUPE 24:
KAHINDO SYAMINYA
MUNYAGA MAMBOLEO DAVID
BEZA HAKIZA DIVINE
BUKENGE CHOYA NATHALIE
ASSANI KAZINGUFU SHALIMO
NEEMA TUNGA
1. L’algorithme de tri par insertion consiste à insérer chaque élément du tableau à trier à sa
place parmi les éléments déjà triés. Pour cela, on compare l’élément à insérer avec les
éléments précédents, et on les décale si nécessaire pour libérer la place. Le tri par insertion
est un tri stable, en place, et online. Il a une complexité en temps de O(n2) en moyenne et en
pire cas, où n est la taille du tableau. Il est efficace sur des petites entrées ou des entrées
presque triées.
Algorithme :
Commencer par considérer le premier élément du tableau comme la partie triée.
Prendre l'élément suivant de la partie non triée et l'insérer à la place correcte dans la partie
triée.
Répéter cette étape jusqu'à ce que la partie non triée devienne vide.
Complexité :
Meilleur cas : O(n) - lorsque le tableau est déjà trié.
Pire cas : O(n2) - lorsque le tableau est trié dans l'ordre inverse.
L’algorithme de tri à bulles consiste à parcourir le tableau à trier, et à échanger les éléments
consécutifs qui ne sont pas dans l’ordre. Après un premier passage, le plus grand élément se
trouve en fin de tableau. On répète le processus en s’arrêtant à l’avant-dernier élément, et
ainsi de suite. Le tri à bulles est un tri stable et en place. Il a une complexité en temps de
O(n2) en moyenne et en pire cas, où n est la taille du tableau. Il est peu performant comparé
à d’autres algorithmes de tri.
Algorithme :
Parcourir le tableau à partir du début.
Comparer les éléments adjacents et les échanger s'ils sont dans le mauvais ordre.
Répéter ces étapes jusqu'à ce que le tableau soit entièrement trié.
Complexité :
Meilleur cas : O(n) - lorsque le tableau est déjà trié.
Pire cas : O(n2) - lorsque le tableau est trié dans l'ordre inverse.
2. LES DEUX ALGORITHMES TRADUIT EN C#.NET
ALGORITHME DE TRI PAR INSERTION :
using System;
class Program
{
static void Main()
{
int[] tableau = { 5, 2, 9, 1, 5, 6 };
TriInsertion(tableau);
[Link]("Tableau trié par insertion : ");
AfficherTableau(tableau);
}
static void TriInsertion(int[] tableau)
{
int n = [Link];
for (int i = 1; i < n; ++i)
{
int cle = tableau[i];
int j = i - 1;
while (j >= 0 && tableau[j] > cle)
{
tableau[j + 1] = tableau[j];
j = j - 1;
}
tableau[j + 1] = cle;
}
}
static void AfficherTableau(int[] tableau)
{
foreach (int element in tableau)
{
[Link](element + " ");
}
[Link]();
}
}
ALGORITHMES DE TRI A BULLES :
using System;
class Program
{
static void Main()
{
int[] tableau = { 15, 12, 19, 11, 15, 16 };
TriBulles(tableau);
[Link]("Tableau trié à bulles : ");
AfficherTableau(tableau);
}
static void TriBulles(int[] tableau)
{
int n = [Link];
for (int i = 0; i < n - 1; ++i)
{
for (int j = 0; j < n - i - 1; ++j)
{
if (tableau[j] > tableau[j + 1])
{
// Échanger les éléments si ils sont dans le mauvais ordre
int temp = tableau[j];
tableau[j] = tableau[j + 1];
tableau[j + 1] = temp;
}
}
}
}
static void AfficherTableau(int[] tableau)
{
foreach (int element in tableau)
{
[Link](element + " ");
}
[Link]();
}
}
3. ALGORITHME D’UN PROGRAMME CALCULANT ET AFFICHANT LA SOMME S, DE DEUX MATRICES A
ET B. SACHANT QUE A ET B SONT DES MATRICES À 3 LIGNES ET À 3 COLONNES, ET LES ÉLÉMENTS
DES MATRICES A ET B SONT PRÉALABLEMENT SAISIS PAR L’UTILISATEUR:
ALGORITHME SOMME_MATRICES
Variables
i, j : entier
A[3][3], B[3][3], S[3][3] : réel
Début
// Saisir les éléments des matrices A et B
Pour i de 1 à 3
Pour j de 1 à 3
Ecrire "Entrez l'élément A[", i, "][", j, "] : "
Lire A[i][j]
Ecrire "Entrez l'élément B[", i, "][", j, "] : "
Lire B[i][j]
FinPour
FinPour
// Calculer la somme S
Pour i de 1 à 3
Pour j de 1 à 3
S[i][j] <- A[i][j] + B[i][j]
FinPour
FinPour
// Afficher la somme S
Ecrire "La somme S des matrices A et B est : "
Pour i de 1 à 3
Pour j de 1 à 3
Ecrire S[i][j], " "
FinPour
Ecrire "\n"
FinPour
Fin
4. CODE C++ ET ILLUSTRATION:
#include <iostream>
using namespace std;
// Déclaration de la fonction principale
int main() {
// Déclaration des matrices A, B et la somme S
int A[3][3], B[3][3], S[3][3];
// Saisie des éléments de la matrice A par l'utilisateur
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cout << "Saisir l'élément A[" << i << "][" << j << "] : ";
cin >> A[i][j];
}
}
// Saisie des éléments de la matrice B par l'utilisateur
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cout << "Saisir l'élément B[" << i << "][" << j << "] : ";
cin >> B[i][j];
}
}
// Calcul de la somme des matrices A et B
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
S[i][j] = A[i][j] + B[i][j];
}
}
// Affichage de la somme S
cout << "La somme des matrices A et B est :\n";
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cout << S[i][j] << " ";
}
cout << "\n";
}
return 0;
}
5. ALGORITHME DE COTATION
Déclarations :
pointsMaximaux = [100, 120, 80, 80, 120, 100]
Pour chaque étudiant (i de 1 à 10) :
Demander le nom de l'étudiant
totalPoints = 0
Pour chaque cours (j de 1 à 6) :
Demander la note obtenue pour le cours j
Ajouter la note au totalPoints
Calculer le pourcentage : pourcentage = (totalPoints / pointsMaximaux[j]) * 100
Déterminer la mention en fonction du pourcentage :
Si pourcentage >= 55 et pourcentage < 69 : mention = "Satisfaction"
Sinon, si pourcentage >= 70 et pourcentage < 80 : mention = "Distinction"
Sinon, si pourcentage >= 80 et pourcentage < 90 : mention = "Grande Distinction"
Sinon, si pourcentage >= 90 et pourcentage <= 100 : mention = "Très Grande Distinction"
Sinon : mention = "Échec"
Afficher le nom de l'étudiant, les notes pour chaque cours, le pourcentage et la mention
Fin Pour
TRADUCTION EN LANGAGE JAVA
import [Link];
public class CotationEtudiants {
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
// Déclarations
int[] pointsMaximaux = {100, 120, 80, 80, 120, 100};
// Boucle pour chaque étudiant
for (int etudiant = 1; etudiant <= 10; etudiant++) {
[Link]("Étudiant " + etudiant);
// Demander le nom de l'étudiant
[Link]("Saisir le nom de l'étudiant : ");
String nomEtudiant = [Link]();
// Initialiser le total des points
int totalPoints = 0;
// Boucle pour chaque cours
for (int cours = 0; cours < 6; cours++) {
// Demander la note obtenue pour le cours
[Link]("Saisir la note obtenue pour le cours " + getNomCours(cours) + " :
");
int note = [Link]();
// Ajouter la note au total des points
totalPoints += note;
}
// Calculer le pourcentage
double pourcentage = ((double) totalPoints / pointsMaximaux[0]) * 100;
// Déterminer la mention
String mention = getMention(pourcentage);
// Afficher les résultats
[Link]("Nom de l'étudiant : " + nomEtudiant);
[Link]("Total des points : " + totalPoints);
[Link]("Pourcentage : " + pourcentage + "%");
[Link]("Mention : " + mention);
// Saut de ligne pour la clarté
[Link]();
// Nettoyer le tampon d'entrée
[Link]();
}
}
static String getNomCours(int index) {
String[] cours = {"Algorithme", "Programmation Orientée Objet", "Recherche
Opérationnelle", "Pédagogie Comparée", "Système d'Exploitation", "Langage Java"};
return cours[index];
}
static String getMention(double pourcentage) {
if (pourcentage >= 55 && pourcentage < 69) {
return "Satisfaction";
} else if (pourcentage >= 70 && pourcentage < 80) {
return "Distinction";
} else if (pourcentage >= 80 && pourcentage < 90) {
return "Grande Distinction";
} else if (pourcentage >= 90 && pourcentage <= 100) {
return "Très Grande Distinction";
} else {
return "Échec";
}
}
}
REFERENCES
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms.
Mit Press.
Learn Data Structure and Algorithms. GeeksforGeeks. (n.d.).
[Link]
0x9FL33T, coma94, & Aronanol. (2014, July 9). Le tri par insertion • tutoriels • zeste de
savoir. Zeste de Savoir. [Link]
