ESMG / IC1SI - 2025-2026

Correction des Exercices d'Algorithmique

Dr KADJO Tanon Lambert
Département Mathématiques et Informatique - INP-HB / Yamoussoukro
Exercice 1 : Boucles infinies
a) TANT QUE
DEBUT
TANT QUE (VRAI) FAIRE
// corps vide
FIN TANT QUE
FIN

b) REPETER ... JUSQUE

DEBUT
REPETER
// corps vide
JUSQUE (FAUX)
FIN

c) POUR
DEBUT
POUR i DE 1 A INFINI FAIRE
// corps vide
FIN POUR
FIN

Note : En pratique, la boucle POUR ne permet pas facilement les boucles infinies; on utilise plutôt TANT
QUE (VRAI) ou REPETER ... JUSQUE (FAUX).

Exercice 2 : Codage binaire d'un entier et nombre de bits à 1

SOUS-PROGRAMME AfficherBinaire(n : entier)
VARIABLES
bits : tableau[0..31] d'entiers
nbBitsA1, i, temp : entier
DEBUT
nbBitsA1 <- 0
i <- 0
temp <- n
SI (temp = 0) ALORS
Afficher('0')
Retourner
FINSI
TANT QUE (temp > 0) FAIRE
bits[i] <- temp MOD 2
SI (bits[i] = 1) ALORS nbBitsA1 <- nbBitsA1 + 1 FINSI
temp <- temp DIV 2
i <- i + 1
FIN TANT QUE
// Afficher dans l'ordre inverse
POUR j DE i-1 A 0 (décroissant) FAIRE
Afficher(bits[j])
FIN POUR
Afficher('Nombre de bits à 1 : ', nbBitsA1)
FIN SOUS-PROGRAMME

Exemple : n = 13 → binaire = 1101, nombre de bits à 1 = 3

Exercice 3 : PGCD par l'algorithme d'Euclide

FONCTION pgcd(a : entier, b : entier) : entier
DEBUT
SI (b = 0) ALORS
Retourner a
 SINON
Retourner pgcd(b, a MOD b)
FINSI
FIN FONCTION

Version itérative
FONCTION pgcd_iter(a : entier, b : entier) : entier
VARIABLE r : entier
DEBUT
TANT QUE (b <> 0) FAIRE
r <- a MOD b
a <- b
b <- r
FIN TANT QUE
Retourner a
FIN FONCTION

Exemple : pgcd(48, 18) → pgcd(18, 12) → pgcd(12, 6) → pgcd(6, 0) → 6

Exercice 4 : Racine carrée entière par soustractions successives

FONCTION racine_entiere(n : entier) : entier
VARIABLES
impair, p : entier
DEBUT
impair <- 1
p <- 0
TANT QUE (n >= impair) FAIRE
n <- n - impair
impair <- impair + 2
p <- p + 1
FIN TANT QUE
Retourner p
FIN FONCTION

Trace pour n=51 :

51-1=50, 50-3=47, 47-5=42, 42-7=35, 35-9=26, 26-11=15, 15-13=2 → 7 soustractions → racine = 7

Exercice 5 : Calcul du coefficient binomial Cnp

Rappel de la définition récursive :
- C(n,0) = C(n,n) = 1
- C(n,p) = C(n-1,p-1) + C(n-1,p) pour 0 < p < n

Version récursive
FONCTION Cnp(n : entier, p : entier) : entier
DEBUT
SI (p = 0 OU p = n) ALORS
Retourner 1
SINON
Retourner Cnp(n-1, p-1) + Cnp(n-1, p)
FINSI
FIN FONCTION

Programme principal
VARIABLES n, p : entier
DEBUT
Afficher('Entrer n : ') Lire(n)
Afficher('Entrer p : ') Lire(p)
SI (p >= 0 ET p <= n) ALORS
 Afficher('C(', n, ',', p, ') = ', Cnp(n, p))
SINON
Afficher('Erreur : on doit avoir 0 <= p <= n')
FINSI
FIN

Exercice 6 : Date de Pâques

Algorithme de calcul selon la méthode de l'énoncé :
VARIABLES
annee, a, b, c, d, e, n : entier
jour, mois : entier
DEBUT
Afficher('Entrer l\'année : ') Lire(annee)
a <- annee MOD 19
b <- annee MOD 4
c <- annee MOD 7
d <- (19 * a + 24) MOD 30
e <- (2 * b + 4 * c + 6 * d + 5) MOD 7
n <- 22 + d + e
// Correction si n > 31 (on passe en avril)
SI (n > 31) ALORS
jour <- n - 31
mois <- 4 // Avril
SINON
jour <- n
mois <- 3 // Mars
FINSI
// Corrections spéciales
SI (d = 29 ET e = 6 ET jour = 26 ET mois = 4) ALORS
jour <- 19
FINSI
SI (d = 28 ET e = 6 ET a > 10 ET jour = 25 ET mois = 4) ALORS
jour <- 18
FINSI
Afficher('Pâques ', annee, ' : ', jour, '/', mois)
FIN

Exemple : Pour 2024 → a=10, b=0, c=1, d=14, e=5 → n=41 → 41-31=10 avril 2024 ✓

Exercice 7 : Moyenne pondérée

Coefficients : Système=5, Algo=3, HTML=3, Java=4, BDD=4 (Total=19)

1) Algorithme pour un candidat

VARIABLES
NOTES : tableau[1..5] de réels
COEFF : tableau[1..5] d'entiers <- {5, 3, 3, 4, 4}
somme, somme_coeff, moyenne : réel
i : entier
DEBUT
somme <- 0
somme_coeff <- 0
POUR i DE 1 A 5 FAIRE
somme <- somme + NOTES[i] * COEFF[i]
somme_coeff <- somme_coeff + COEFF[i]
FIN POUR
moyenne <- somme / somme_coeff
SI (moyenne >= 10) ALORS
Afficher('Admis, Moyenne = ', moyenne)
SINON
Afficher('Ajourné, Moyenne = ', moyenne)
FINSI
FIN
2) Extension pour 30 candidats
VARIABLES
NOTES : tableau[1..30][1..5] de réels
COEFF : tableau[1..5] d'entiers <- {5, 3, 3, 4, 4}
somme, somme_coeff, moyenne : réel
i, j : entier
DEBUT
POUR j DE 1 A 30 FAIRE
Afficher('Candidat ', j, ' :')
somme <- 0 somme_coeff <- 0
POUR i DE 1 A 5 FAIRE
somme <- somme + NOTES[j][i] * COEFF[i]
somme_coeff <- somme_coeff + COEFF[i]
FIN POUR
moyenne <- somme / somme_coeff
SI (moyenne >= 10) ALORS
Afficher('Admis, Moy = ', moyenne)
SINON
Afficher('Ajourné, Moy = ', moyenne)
FINSI
FIN POUR
FIN

Exercice 8 : Déplacement d'un pion sur un damier

CONSTANTE TAILLE <- 8
VARIABLES
damier : tableau[1..8][1..8] de caractères
ligne, colonne, mouvement : entier
nouvelle_ligne, nouvelle_col : entier
valide : booléen
DEBUT
// Initialisation du damier
POUR i DE 1 A 8 FAIRE
POUR j DE 1 A 8 FAIRE
damier[i][j] <- 'O'
FIN POUR
FIN POUR

// Saisie de la position initiale avec contrôle

REPETER
Afficher('Ligne (1-8) : ') Lire(ligne)
JUSQUE (ligne >= 1 ET ligne <= 8)
REPETER
Afficher('Colonne (1-8) : ') Lire(colonne)
JUSQUE (colonne >= 1 ET colonne <= 8)
damier[ligne][colonne] <- 'X'

// Saisie du mouvement
REPETER
Afficher('Mouvement (0=HG,1=HD,2=BG,3=BD) : ') Lire(mouvement)
JUSQUE (mouvement >= 0 ET mouvement <= 3)

// Calcul nouvelle position

SI (mouvement = 0) ALORS nouvelle_ligne <- ligne-1 nouvelle_col <- colonne-1
FINSI
SI (mouvement = 1) ALORS nouvelle_ligne <- ligne-1 nouvelle_col <- colonne+1
FINSI
SI (mouvement = 2) ALORS nouvelle_ligne <- ligne+1 nouvelle_col <- colonne-1
FINSI
SI (mouvement = 3) ALORS nouvelle_ligne <- ligne+1 nouvelle_col <- colonne+1
FINSI

// Vérification validité
SI (nouvelle_ligne < 1 OU nouvelle_ligne > 8 OU
nouvelle_col < 1 OU nouvelle_col > 8) ALORS
Afficher('Mouvement impossible : sortie du damier!')
SINON
 damier[ligne][colonne] <- 'O'
damier[nouvelle_ligne][nouvelle_col] <- 'X'
// Affichage du damier
POUR i DE 1 A 8 FAIRE
POUR j DE 1 A 8 FAIRE
Afficher(damier[i][j], ' ')
FIN POUR
Afficher('\n')
FIN POUR
FINSI
FIN

Exercice 9 : Chiffre de César

1) Codage de EXAMEN avec décalage de 4
E → I, X → B, A → E, M → Q, E → I, N → R
EXAMEN codé avec décalage 4 = IBEQIR

2) Programme d'encodage
VARIABLES
CHAINE_A_CODER : tableau de caractères
LONGUEUR_CHAINE, DECALAGE : entier
i, code : entier
c : caractère
DEBUT
Afficher('Longueur de la chaîne : ') Lire(LONGUEUR_CHAINE)
Afficher('Décalage : ') Lire(DECALAGE)
DECALAGE <- DECALAGE MOD 26
// Saisie et validation (majuscules uniquement)
POUR i DE 1 A LONGUEUR_CHAINE FAIRE
REPETER
Lire(c)
SI (c < 'A' OU c > 'Z') ALORS
Afficher('Saisir une majuscule!')
FINSI
JUSQUE (c >= 'A' ET c <= 'Z')
CHAINE_A_CODER[i] <- c
FIN POUR
// Encodage
Afficher('Résultat : ')
POUR i DE 1 A LONGUEUR_CHAINE FAIRE
c <- CHAINE_A_CODER[i]
SI (c >= 'A' ET c <= 'Z') ALORS
code <- (ORD(c) - ORD('A') + DECALAGE) MOD 26
Afficher(CHR(ORD('A') + code))
SINON
Afficher(c) // Caractère non alphabétique inchangé
FINSI
FIN POUR
FIN

3) Programme de décodage
// Décodage : décalage inverse
POUR i DE 1 A LONGUEUR_CHAINE FAIRE
c <- CHAINE_A_DECODER[i]
SI (c >= 'A' ET c <= 'Z') ALORS
code <- (ORD(c) - ORD('A') - DECALAGE + 26) MOD 26
Afficher(CHR(ORD('A') + code))
SINON
Afficher(c)
FINSI
FIN POUR
Exercice 10 : Tri bulle
1) Algorithme du tri bulle
PROCEDURE TriBulle(T : tableau[1..n] de numériques, n : entier)
VARIABLES i, j : entier temp : numérique echange : booléen
DEBUT
POUR i DE 1 A n-1 FAIRE
echange <- FAUX
POUR j DE 1 A n-i FAIRE
SI (T[j] > T[j+1]) ALORS
temp <- T[j]
T[j] <- T[j+1]
T[j+1] <- temp
echange <- VRAI
FINSI
FIN POUR
SI (NON echange) ALORS Retourner FINSI // Optimisation
FIN POUR
FIN PROCEDURE

2) Déroulement sur [45, 11, 2, 0, 3, 2, 0, 17, 11]

Tableau initial : [45, 11, 2, 0, 3, 2, 0, 17, 11]
Passe 1 : [11, 2, 0, 3, 2, 0, 17, 11, 45]
Passe 2 : [2, 0, 3, 2, 0, 11, 11, 17, 45]
Passe 3 : [0, 2, 2, 0, 3, 11, 11, 17, 45]
Passe 4 : [0, 2, 0, 2, 3, 11, 11, 17, 45]
Passe 5 : [0, 0, 2, 2, 3, 11, 11, 17, 45]
Passe 6 : [0, 0, 2, 2, 3, 11, 11, 17, 45] → Aucun échange, tri terminé.
Résultat final : [0, 0, 2, 2, 3, 11, 11, 17, 45]

Exercice 11 : Méthode de tri par bissection

1) Quand sait-on que le tableau est trié ?
Le tableau est trié lorsque chaque sous-intervalle de bissection ne contient qu'un seul élément. À chaque
étape, si toutes les partitions contiennent 0 ou 1 élément, le tableau est trié.

2) Programme de la méthode (tri par bissection)

PROCEDURE TriBissection(T : tableau[1..N] de réels, debut, fin : entier,
borne_inf, borne_sup : réel)
VARIABLES milieu : réel gauche, droite : listes i : entier
DEBUT
SI (fin - debut <= 0) ALORS Retourner FINSI
milieu <- (borne_inf + borne_sup) / 2
// Partitionner autour de milieu
i_gauche <- debut
i_droite <- fin
POUR i DE debut A fin FAIRE
SI (T[i] < milieu) ALORS
Placer T[i] à gauche
SINON
Placer T[i] à droite
FINSI
FIN POUR
// Appels récursifs
TriBissection(T, debut, i_gauche, borne_inf, milieu)
TriBissection(T, i_gauche+1, fin, milieu, borne_sup)
FIN PROCEDURE

// Appel initial :
TriBissection(T, 1, N, 0, 1)
3) Extension à des réels quelconques
Pour un tableau de réels quelconques, on normalise d'abord les valeurs entre 0 et 1 :
valeur_normalisée = (x - min) / (max - min)
On applique ensuite la méthode sur les valeurs normalisées, puis on reconstruit les valeurs originales.

Exercice 12 : Algorithme Bolt (QuickSort de Hoare)

1) Pseudo-code de la procédure Echanger
PROCEDURE Echanger(Tab : tableau, i : entier, j : entier)
VARIABLE temp : numérique
DEBUT
temp <- Tab[i]
Tab[i] <- Tab[j]
Tab[j] <- temp
FIN PROCEDURE

2) Déroulement sur [9, 4, 2, 8, 5] (indices 1..5)

Bolt(Tab, 1, 5) → Partitionner(Tab, 1, 5) :
pivot = Tab[1] = 9, i = 0, j = 6
Repeter j : j=5, Tab[5]=5 ≤ 9 → stop Repeter i : i=1, Tab[1]=9 ≥ 9 → stop
i=1 < j=5 → Echanger(Tab,1,5) → Tab = [5, 4, 2, 8, 9]
Repeter j : j=4, Tab[4]=8 ≤ 9 → stop Repeter i : i=2, Tab[2]=4 < 9, i=3, Tab[3]=2 < 9, i=4, Tab[4]=8 < 9,
i=5, Tab[5]=9 ≥ 9 → stop
i=5 ≥ j=4 → test=FAUX, retourner j=4
Bolt(Tab, 1, 4) puis Bolt(Tab, 5, 5)
Résultat final trié : [2, 4, 5, 8, 9]

3) Déroulement sur [2, 4, 5, 8, 9] (déjà trié)

Bolt(Tab, 1, 5) → Partitionner(Tab, 1, 5) :
pivot = 2, i=0, j=6
Repeter j : j=5... j=4... j=3... j=2... j=1, Tab[1]=2 ≤ 2 → stop
Repeter i : i=1, Tab[1]=2 ≥ 2 → stop
i=1 = j=1 → test=FAUX, retourner j=1
Bolt(Tab, 1, 1) (trivial) puis Bolt(Tab, 2, 5) → continue récursivement
L'algo fonctionne mais est moins efficace sur un tableau déjà trié (O(n²) dans le pire cas pour cette variante).

4) Cas [2, 2, 2, 2, 2] - valeur retournée par Partitionner

pivot = Tab[1] = 2, i = 0, j = 6
Repeter j : j=5, Tab[5]=2 ≤ 2 → stop
Repeter i : i=1, Tab[1]=2 ≥ 2 → stop
i=1 < j=5 → Echanger(1,5) → Tab=[2,2,2,2,2] (inchangé)
Repeter j : j=4 → stop Repeter i : i=2 → stop
i=2 < j=4 → Echanger(2,4) → inchangé
Repeter j : j=3 → stop Repeter i : i=3 → stop
i=3 = j=3 → test=FAUX, retourner j = 3
Partitionner retourne 3 pour le premier appel sur [2,2,2,2,2].

Exercice 13 : Informations employé et temps restant avant retraite

VARIABLES
nom, prenoms, sexe : chaîne
 date_embauche, date_actuelle : date
annees_service, annees_restantes : entier
mois_restants, jours_restants : entier
DEBUT
// Saisie des données
Afficher('Nom : ') Lire(nom)
Afficher('Prénoms : ') Lire(prenoms)
Afficher('Date embauche (JJ/MM/AAAA) : ') Lire(date_embauche)
Afficher('Sexe (M/F) : ') Lire(sexe)

// Calcul de la date de retraite = date_embauche + 30 ans

date_retraite <- AjouterAns(date_embauche, 30)
date_actuelle <- DateAujourdhui()

// Calcul du temps restant

annees_restantes <- Annee(date_retraite) - Annee(date_actuelle)
mois_restants <- Mois(date_retraite) - Mois(date_actuelle)
jours_restants <- Jour(date_retraite) - Jour(date_actuelle)
// Ajustements si valeurs négatives
SI (jours_restants < 0) ALORS
mois_restants <- mois_restants - 1
jours_restants <- jours_restants + 30
FINSI
SI (mois_restants < 0) ALORS
annees_restantes <- annees_restantes - 1
mois_restants <- mois_restants + 12
FINSI

// Affichage dans un cadre

Afficher('+---------------------------------+')
Afficher('| Nom : ', nom)
Afficher('| Prénoms : ', prenoms)
Afficher('| Date d\'embauche : ', date_embauche)
Afficher('| Sexe : ', sexe)
Afficher('+---------------------------------+')

SI (sexe = 'M') ALORS prefixe <- 'Mr' SINON prefixe <- 'Mme' FINSI
Afficher(prefixe, ' ', nom, ' ', prenoms, ' est à ',
annees_restantes, ' ans ', mois_restants, ' mois et ',
jours_restants, ' jours de la retraite')
FIN

Exercice 14 : Tableau d'employés

TYPE Employe = STRUCTURE
matricule : entier
nom : chaîne
salaire : réel
etat_civil : chaîne
date_naiss : date
date_embauche : date
FIN STRUCTURE

VARIABLES
EMPLOYES : tableau[1..50] d'Employe
compteur, i, annees_service : entier
DATE_REF : date <- 01/01/2010
DEBUT
// Remplissage du tableau
POUR i DE 1 A 50 FAIRE
Lire(EMPLOYES[i].matricule, EMPLOYES[i].nom,
EMPLOYES[i].salaire, EMPLOYES[i].etat_civil,
EMPLOYES[i].date_naiss, EMPLOYES[i].date_embauche)
FIN POUR

// Comptage salaires entre 250000 et 500000

compteur <- 0
POUR i DE 1 A 50 FAIRE
SI (EMPLOYES[i].salaire >= 250000 ET EMPLOYES[i].salaire <= 500000) ALORS
 compteur <- compteur + 1
FINSI
FIN POUR
Afficher('Nb employés entre 250000 et 500000 FCFA : ', compteur)

// Liste employés avec > 20 ans de service au 01/01/2010

Afficher('Employés avec plus de 20 ans de service au 01/01/2010 :')
POUR i DE 1 A 50 FAIRE
annees_service <- Annee(DATE_REF) - Annee(EMPLOYES[i].date_embauche)
SI (annees_service > 20) ALORS
Afficher(EMPLOYES[i].nom, ' - ', annees_service, ' ans de service')
FINSI
FIN POUR
FIN

Exercice 15 : Calcul de la paie hebdomadaire

FONCTION PaieHebdomadaire(heures : réel, taux_horaire : réel) : réel
VARIABLES
paie, heures_sup : réel
DEBUT
SI (heures <= 35) ALORS
paie <- heures * taux_horaire
SINON
heures_sup <- heures - 35
paie <- (35 * taux_horaire) + (heures_sup * taux_horaire * 1.5)
FINSI
Retourner paie
FIN FONCTION

// Programme principal
VARIABLES h, t, resultat : réel
DEBUT
Afficher('Nombre d\'heures travaillées : ') Lire(h)
Afficher('Taux horaire : ') Lire(t)
resultat <- PaieHebdomadaire(h, t)
Afficher('Paie hebdomadaire : ', resultat)
FIN

Exemple : 40 heures à 2000 FCFA/h → 35×2000 + 5×3000 = 70000 + 15000 = 85000 FCFA

Dr KADJO Tanon Lambert | INP-HB / Yamoussoukro | 2025-2026