ExperimentsLabs::Algorithmie

Introduction à l'algorithmie avec quelques exemples et exercices...

Introduction
Format
Structures conditionnelles
Exercices

Introduction

Un algorithme décrit un programme dans une langue donnée, et pas un langage. De ce fait, il est lisible par tous et peut ensuite être retranscrit dans n'importe quel langage de programmation. Il n'y a pas réellement de normes concernant les algorithmes : les structures, même si elles suivent un ordre logique, peuvent être écrites avec une certaine souplesse. Finalement, tout ce qui compteur, c'est que le programme fonctionne et qu'il soit facile à lire.

Format

Algorithme: <nom de l'algo>
{Description}

Constantes: MA_CONSTANTE : <type> ← Valeur

Tableaux:
    monTableau(<taille>) en <type>

Variables: 
    nomVar, autreVar : <type>
    encoreAutreVar : <autre type>

Début:
 |  <contenu>
Fin

Notes:

Ne pas oublier le trait vertical lorsque l'on écrit un algorithme sur papier : cela permet de se situer rapidement dans l'écriture. Pour un algorithme écrit dans un logiciel de traitement de texte, utiliser l'indentation (espaces ou tabulations).
Les mots clés Algorithme, Variables, Constantes, ...
Les variables sont afféctées suivant cette structure : <variable> ← <valeur>

Variables

Les variables utilisées dans le programme sont définies en début de programme, ainsi que leur type. Elles peuvent être des entiers (1, 2, 10, -20,...), des réels (1.5, -128.1587, ...), des chaines ("une chaine de caractères"), des caractères ('a', '$',..) ou des booléens (Vrai ou Faux).

Il est de bon usage d'utiliser des noms en camelCase pour les variables (maVariableEnCamelCase).

Constantes

Les constantes doivent être définies et affectées en début de programmes. Pour les noms de constantes, on utilisera des majuscules et underscores (MA_CONSTANTE)

Les tableaux

Les tableaux sont des variables contenant plusieur valeurs d'un même type. Ils doivent être déclarés avant les variables.

Note : Les indices des tableaux commencent à 1.

Représentation "graphique" d'un tableau à une dimension:

+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
Tableau: monTableau(5) en entier

Représentation "graphique" d'un tableau à deux dimensions:

+-----+-----+-----+-----+-----+
| 1,1 | 1,2 | 1,3 | 1,4 | 1,5 |
+-----+-----+-----+-----+-----+
| 2,1 | 2,2 | 2,3 | 2,4 | 2,5 |
+-----+-----+-----+-----+-----+
| 3,1 | 3,2 | 3,3 | 3,4 | 3,5 |
+-----+-----+-----+-----+-----+
Tableau: monTableau(5)(3) en entier

Représentation "graphique" d'un tableau à trois dimensions:

              +-------+-------+-------+-------+-------+
              | 1,1,3 | 1,2,3 | 1,3,3 | 1,4,3 | 1,5,3 |
              +-------+-------+-------+-------+-------+
       +-------+-------+-------+-------+-------+2,5,3 |
       | 1,1,2 | 1,2,2 | 1,3,2 | 1,4,2 | 1,5,2 |------+
       +-------+-------+-------+-------+-------+2,5,3 |
+-------+-------+-------+-------+-------+2,5,2 |------+
| 1,1,1 | 1,2,1 | 1,3,1 | 1,4,1 | 1,5,1 |------+
+-------+-------+-------+-------+-------+2,5,2 |
| 2,1,1 | 2,2,1 | 2,3,1 | 2,4,1 | 2,5,1 |------+
+-------+-------+-------+-------+-------+
| 3,1,1 | 3,2,1 | 3,3,1 | 3,4,1 | 3,5,1 |
+-------+-------+-------+-------+-------+  <-- indices: y,x,z
Tableau: monTableau(5)(3) en entier

Il n'y a aucune limite sur le nombre de dimensions.

Pour accéder à une valeur donnée, il faut utiliser le/les indexes permettant d'y arriver: monTableau(index1)(index2)....

Opérateurs arithmétiques

Les seuls opérateurs arithmétiques utilisables dans un algorithme sont :

+ : Effectue une addition.
- : Effectue une soustraction
* : Effectue une multiplication
/ : Effectue une division
% : Retourne le modulo: le reste de la division euclidienne de nombre1 / nombre2

Structures conditionnelles

Si... Sinon...

Si <expression>:
Alors: 
    <instructions>
Sinon: 
    <instructions>
Fsi

Cas

Cas <identificateur>
  <val 1>: <insrtuctions>
  <val 2>: <instructions>
  <val x...>: <instructions>
  défault: <instructions>
FinCas

Pour

Pour <compteur> ← <valInit> à <valFin> par <pas> faire:
    <instruction>
FPour

Attention :

la variable de compteur DOIT être définie en début d'algo
il ne faut pas écrire dessus.

Tant que

Tant que <expression logique est vraie> faire:
    <instructions>
Ftq

Répéter tant que

Répéter
    <instructions>
Tant que <expression logique est vraie>

Note : Les instructions de la boucle sont éxécutées au moins une fois.

Exemple de suivi de variables

Soit l'algorithme suivant:

Algorithme : exerciceAffectations

Constante : SEUIL : réel ← 13,25

Variables : 
    valA, valB : réels
    compteur : entier
    mot, tom : chaines

Début
    valA ← 0,56
    valB ← valA
    valA ← valA x (10,5 + SEUIL)
    compteur ← 1
    compteur ← compteur + 10
    mot ← « bonjour »
    tom ← « au revoir! »
Fin

Le tableau de suivi variables peut être écrit comme suit:

Ligne	valA	valB	compteur	mot	tom
11	0.56	null	null	null	null
12	0.56	0.56	null	null	null
13	13.3	0.56	null	null	null
14	13.3	0.56	1	null	null
15	13.3	0.56	11	null	null
16	13.3	0.56	11	"bonjour"	null
17	13.3	0.56	11	"bonjour"	"au revoir !"

Exercices

1 - Calcul de prix TTC

Algorithme: CalculTTC
{Calcule le prix TTC à partir d'un prix HT donné}

Constantes: 
    TAUX_TVA : entier ← 20

Variables: prixHT : réel

Début:
    Ecrire ("Quel est le prix HT ?")
    Lire (prixTH)
    Ecrire ("Le prix TTC est ", prixHT * (1 + TAUX_TVA/100), '€')
Fin

2 - Permutation de valeurs

Algorithme: permutationAB
{Permute les valeurs A et B demandées à l'utilisateur}

Variables: valA, valB, pivot : entier

Début:
    Ecrire ("Donnez moi A...")
    Lire (valA)
    Ecrire ("Donnez moi B...")
    Lire (valB)
    pivot ← valA
    valA ← valB
    valB ← pivot
    Ecrire ("Les valeurs permutées sont : A=", valA, "et B=", valB)
Fin

Ligne	valA	valB	pivot
7	null	null	null
8	10	null	null
9	10	null	null
10	10	5	null
11	10	5	10
12	5	5	10
13	5	10	10

3 - Pizzas

Pour deux pizzas dont on donne un prix et un diamètre, déterminer quelle pizza est la plus rentable.

Algorithme: meilleurePizza
{Pour deux pizzas données, choisir la meilleure offre}

Constantes: PI : réel ← 3.14

Variables: pizADiam, pizAPx, pizARap, pizBDiam, pizBPrix pizBRap: rééls

Début:
    Ecrire ("Quel est le prix de la pizza A ?")
    Lire (pizAPx)
    Ecrire ("Quel est son diamètre ?")
    Lire (pizADiam)
    Ecrire ("Quel est le prix de la pizza B ?")
    Lire (pizBPx)
    Ecrire ("Quel est son diamètre ?")
    Lire (pizBDiam)
    #Comparaison surfaces/prix
    pizARap ← ((PI * (pizADiam/2) * (pizADiam/2)) / pizAPx)
    pizBRap ← ((PI * (pizBDiam/2) * (pizBDiam/2)) / pizBPx)
    Si ( pizARap > pizBRap ) Alors:
        Ecrire ("La pizza A est la plus intéressante")
    Sinon:
        Si ( pizARap < pizBRap ) Alors:
            Ecrire ("La pizza B est la plus intéressante")
        Sinon:
            Ecrire ("Les deux offres sont valables... Choisissez suivant vos goûts !")
        Finsi
    Finsi
Fin

4 - Reçu avec mention

Affiche une mention suivant la note donnée : "Reçu avec mention" si supérieure à 12, "Passable" si supérieure à 10 et "Insuffisant" dans les autres cas.

Algorithme: recuAvecMention
{Affiche la mention pour une note donnée}

Variables: note: réel

Début:
    Ecrire ("Qelle est la note ?")
    Lire (note)
    Si (note <= 10 ) Alors:
        Ecrire ("Insuffisant")
    Sinon:
        Si (note  < 12 ) Alors:
            Ecrire ("Passable")
        Sinon:
            Ecrire ("Reçu avec mention")
        Finsi
    Finsi
Fin

5 - M/Mme

Ce programme doit retourner un titre complet suivant le titre abrégé donné :

Monsieur pour M

Madame pour Mme

Mademoiselle pour Mlle

Madame, Monsieur pour les autres cas.

Réaliser des algorithmes utilisant les méthodes Si et Cas.

Avec des Si

Algorithme: M_Mme
{Affiche une particule suivant le titre donné}

Variables: titre : chaine

Début:
    Ecrire ("Quel est votre titre ?")
    Lire (titre)
    Si (titre = "M") Alors:
        Ecrire ("Monsieur")
    Sinon:
        Si (titre = "Mme") Alors:
            Ecrire ("Madame")
        Sinon
            Si (titre = "Mlle") Alors:
                Ecrire ("Mademoiselle")
            Sinon:
                Ecrire "Monsieur, Madame"
            Fsi
        Fsi
    Fsi
Fin

Avec Cas

Algorithme: mMme
{Affiche une particule suivant le titre donné}

Variables: titre : chaine

Début:
    Ecrire ("Quel est votre titre ?")
    Lire (titre)
    Cas titre:
        "M":
            Ecrire "Monsieur"
        "Mme":
            Ecrire "Madame"
        "Mlle":
            Ecrire "Mademoiselle"
        défaut:
            Ecrire "Madame, Monsieur"
    Fcas
Fin

6 - Exercice sur les boucles

Chaque année, une machine perd 10% de sa valeur d'achat. Calculer la valeur de la machine au bout de 5 ans

Algorithme: perteDeValeur
{Calcule la valeur d'une machine au bout de 5 ans.}

Constantes: NB_ANNEES : entier ← 5

Variables:
    valeur: réel
    compteur: entier

Début
    Ecrire ("Quelle est la valeur de la machine ?")
    Lire (valeur)
    Pour compteur ← 1 à NB_ANNEES par 1 faire:
        valeur ← valeur * 0.9
    FPour
    Ecrire ("Valeur après ", NB_ANNEES, " ans : ", valeur)
Fin

Test pour une machine de valeur 100000

Valeur initiale: 100 000
compteur=1: 90000
compteur=2: 81000
compteur=3: 72900
compteur=4: 65610
compteur=5: 59049

Calculer le nombre d'années nécessaires pour que la machine perde la moitié de sa valeur.

Algorithme: moitieValeur
{Calcule le temps nécéssaire pour qu'une machine perde la moitié de sa valeur.}

Variables:
    valeurInit, valeurActuelle : réels
    compteur: int

Début
    compteur ← 0
    Ecrire ("Quelle est la valeur de la machine ?")
    Lire (valeur)
    valeurActuelle ← valeurInit
    Répéter:
        valeurActuelle ← 0.9 * valeurActuelle
        compteur ← compteur +1
    Tant que (valeurActuelle > (valeurInit/2))
    Ecrire ("Il faut ", compteur, " années pour que la machine perde la moitié de sa valeur")
Fin

7 - Secondes en J/H/M/S

L'utilisateur entre une durée en secondes. Le programme doit afficher cette durée en jours/heures/minutes/secondes.

Algorithme: secondesVersJHMS
{Convertit des secondes en Jours/Heures/Minutes/Secondes}

Variables: 
    sInitiales, secondes, minutes, heures, jours, sMod, mMod, hMod, jMod: entier

Constantes:
    MINUTE ← 60
    HEURE ← 60*60
    JOUR ← 60*60*24 

Début
    Ecrire ("Nombre de secondes ?")
    Lire sInitiales
    
    # Calcul des jours
    jMod ← sInitiales % JOUR
    jours ← (sInitiales - jMod) / JOUR

    # Calcul des heures
    hMod ← jMod % HEURE
    heures ← (jMod - hMod) / HEURE

    # Calul des minutes
    mMod ← hMod % MINUTE
    minutes ← (hMod - mMod) / MINUTE

    # Secondes restantes
    secondes ← mMod

    Ecrire (sInitiales, " secondes = ", jours, "J, ", heures, "H ", minutes, "M ", secondes, "S")
Fin

8 - Tableaux

Faire un algorithme qui demande à l'utilisateur d'entrer 5 caractères dans un tableau. Le programme devra afficher cette liste en sens inverse.

Algorithme: inverseTableau

Tableaux:
    liste (5) en caractère

Variables: 
    compteur : entier

Début
    Pour compteur ← 1 à 5 par 1 faire:
        Ecrire("Quel est le caractère ", compteur, " ?")
        Lire( liste(compteur) )
    FPour
    
    # Affiche le contenu du tableau en partant du dernier caractère
    Pour compteur ← 5 à 1 par -1 faire:
        Ecrire ("Le caractère ", compteur, "est : ", liste( compteur ))
    FPour
Fin

9 - Valeur max dans un tableau

L'utilisateur entre 5 entiers dans un tableau, et l'algorithme affichera la valeur max contenue dans le tableau.

Algorithme: valeurMax

Tableaux:
    liste (5) en entier

Variables: 
    compteur, max: entiers

Début
    Pour compteur ← 1 à 5 par 1 faire:
        Ecrire("Entrez un nombre")
        Lire( liste(compteur) )
    FPour
    
    # Affectation de max à la valeur du premier élément du tableau
    max ← liste(1)
    # Recherche de la valeur max
    Pour compteur ← 2 à 5 par 1 faire:
        Si (liste(compteur) > max) Alors:
            max ← liste(compteur)
        Fsi
    FPour

    Ecrire ("La valeur max du tableau est ", max)
Fin

10 - Triage - Recherche du minimum

L'utilisateur va entrer 5 entiers dans un tableau et le programme devra les trier par ordre croissant

Algorithme: triMini
{Tri par recherche du minimum}

Tableaux:
    liste (5) en entier

Variables: 
    compteur1, compteur2, min, pivot, index: entiers

Début
    Pour compteur1 ← 1 à 5 par 1 faire:
        Ecrire("Entrez un nombre")
        Lire( liste(compteur) )
    FPour
    
    # Recherche de la valeur min
    Pour compteur1 ← 1 à 4 par 1 faire:
        min ← liste(compteur1)
        Pour compteur2 ← (compteur1 + 1) à 5 par 1 faire:
            Si (liste(compteur2) < min) Alors:
                min ← liste(compteur2)
                index ← compteur2
            Fsi
        FPour
        # Permutation
        pivot ← liste(compteur1)
        liste(compteur1) ← liste(index)
        liste(index) ← pivot
    FPour
    
	# Affichage
    Pour compteur1 ← 1 à 5 par 1 faire:
        Ecrire (liste(compteur1), ", ")
    FPour
Fin

Exemple en JS:

var liste=[3,9,7,12,4,5]

function tri(liste){
  console.log(liste.length)
    var min, i, j, pivot, index;
    for(i=0; i <= liste.lenght-1; i++){
        min=liste[i];
        index=i;
        for(j=i+1; j <= liste.lenght-1; j++){
            if(liste[j] < min){
                min=liste[j];
                index=j
            }
        }
        // Permutation
        pivot = liste[i];
        liste[i] = liste[index];
        liste[index] = pivot;
        console.log(liste[i]);
    }
    console.log(liste);
}

tri(liste);

11 - Triage - Tri à bulle