Algorithmique

Ressources

Algorithmique - Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique

By: CREPIN, Ludivine. Editions ENI. ISBN: 978-2-409-04184-6, 978-2-409-04202-7.

https://eds-p-ebscohost-com.bnf.idm.oclc.org/eds/results?sid=0098f5b8-3586-4afe-bc01-42b775ba1cb5@redis&vid=0&sdb=edspub&tid=3000EP&bquery=algorithmique+techniques&bdata=JmRiPWVkc3B1YiZsYW5nPWZyJnR5cGU9NDQmc2VhcmNoTW9kZT1BbmQmc2l0ZT1lZHMtbGl2ZQ==

C’est quoi l’algorithmique ?
  • L’algorithmique est la base de la programmation, mais aussi de l'intelligence et de l'analyse, de la compréhension, de la résolution de problème dans tous les domaines.
  • L’algorithmique est la science qui s’occupe de tous les calculs.
  • En arithmétique on distingue 4 opérations fondamentales : l’addition, la soustraction, la multiplication et la division; les autres opérations ne sont que des combinaisons de celles-ci.
  • ⇒ Si un calcul vous parait difficile vous pouvez repérer chaque opérations simples qui se trouvent dans le calcul et voir comment chacune de ses opérations sont reliées entre elles : c’est comprendre la succession d’opération, c’est donc retrouver l’algorithme.
  • L'algorithme, tout comme la programmation c'est de la création, il faut être créatif. Donc un algorithme ou un programme fait par une personne ne sera pas le même que fait par une autre personne.
    Alors, si chacun a le sien, s'il peut y avoir plusieurs solutions, laquelle est la bonne laquelle choisir ? Quelles sont les critères :
    • la rapidité d'exécution,
    • le fait que ça fonctionne dans plusieurs cas d’usage,
    • le fait que si ça tombe en panne le programme à la capacité de se remettre tout seul à fonctionner,
    • le fait qu'il ne prend pas de ressources mémoire
    • le fait qu'il soit lisible, c'est-à-dire que si une autre personne que vous doit faire des modifications, il faut pas que ce soit complètement incompréhensible.

Le principe de base

  1. Identifier les informations à manipuler
    1. données initiales
    1. résultats attendus
  1. Quel mode de calcul (ou comment) va permettre d’obtenir le résultat à partir d’un paramètre (données initiales)
  1. Coût d’exécution du calcul
    1. ressources en mémoire
    1. ressources en temps : le nombre d’opérations de base effectuées par l’ordinateur pour calculer le résultat
Entrée-sortie, variables

Variable

  • elle a un nom qui ne change pas
  • elle a un type qui ne change pas
  • elle a une valeur qui peut éventuellement changer en évoluant au cours de l’exécution du programme
    • par exemple une boulangerie où on achète du pain
      • nom du pain : pain_nom / chaîne de caractère / baguette
      • prix fixe du pain : pain_tarif / nombre entier / 1
      • coefficient appliqué en fonction des saisons : coef_hiver / nombre flotant / 0.5
      • le nombre de pain acheté : achat_nombre / nombre flottant / 1.5
      • le montant total des achats : achat_total / nombre flottant / 1.5
      • le porte monnaie de l’acheteur : wallet_acheteur / nombre flottant / 10 / 10 - 1.3 = 8.7
      • la date de l’achat : achat_date / date / 20240923

Type d’une variable

  • int / entier - nombre entier : 0 / -5 / 222
  • float / reel - nombre flottant : 0,2 / -3.14
  • string / chaine- chaîne de caractère : “Bonjour et bienvenue”
  • liste ou un tableau : [chat, chien, oiseau, poisson] ou [2, 4, 6, 8, 10] ou [1.3, -3.6, 4]
  • bouléen / booleen : elle n’a que 2 valeurs possibles : true (vrai) ou false (faux)
    • par exemple 2 > 7 ⇒ false ou 10 > 7 ⇒ true
  • date - date : (2024, 9, 24)

Donc on affecte une valeur à une variable

  • pain_nom ← “baguette”
  • pain_tarif ← 1.3

Les instructions ou opérations d’entrée-sortie

⭐

On décrit le comportement de l’ordinateur et non celui de l’utilisateur

  • LIRE()achat_nombre (saisir)
  • ECRIRE() achat_total (afficher)
Opérations
PROGRAMME Nom_du_programme
CONST //(ici on mettra toutes les variables constantes nécessaires au programme)
	pain_tarif <- 1 : ENTIER
VAR //(ici on mettra toutes les variables nécessaires au programme)
	pain_nom : CHAINE
DEBUT
	ECRIRE (”Saisissez le nom du pain que vous souhaitez acheter”)
	pain_nom <- LIRE()
	ECRIRE (”Vous avez choisi le pain “, pain_nom, ". Tarif : ", pain_nom x pain_tarif," euros")
FIN
Opérations arithmétiques de bases

addition, soustraction, multiplication

PROGRAMME operations
VAR
	a <- 17 : ENTIER
	b <- 2 : ENTIER
	c <- 2.5 : REEL
	resultat : REEL
DEBUT
	resultat <- a + b
	ECRIRE (”L'addition de a et b vaut : ”, resultat)
	resultat <- a - b
	ECRIRE (”La soustraction de a et b vaut : ”, resultat)
	resultat <- a x c
	ECRIRE (”La multiplication de a et c vaut : ”, resultat)
	resultat <- a / c
	ECRIRE (”La division de a par c vaut : ”, resultat)
FIN
Opérations de comparaison
PROGRAMME comparaison
VAR
	a <- 17 : ENTIER
	b <- 2 : ENTIER
	resultat : REEL
DEBUT
	resultat <- a = b
	ECRIRE (”a est-il égal à b ? ”, resultat) // FAUX
	resultat <- a ? b // différence
	ECRIRE (”a est-il différent de b ? ”, resultat) // VRAI
	resultat <- a < b
	ECRIRE (”a est-il inférieur à b ? ”, resultat) // FAUX
	resultat <- a > b
	ECRIRE (”a est-il supérieur à b ? ”, resultat) // VRAI
	resultat <- a <= b
	ECRIRE (”a est-il inférieur ou égal à b ? ”, resultat) // FAUX
	resultat <- a >= b
	ECRIRE (”a est-il supérieur ou égal à b ? ”, resultat) // VRAI
FIN
Opérations sur les chaînes
PROGRAMME chaines
VAR
	sujet : CHAINE <- "Le chat"
	verbe : CHAINE <- "ronronne"
	resultat : CHAINE
DEBUT
	//Concaténation
	resultat <- CONCATENER(sujet, verbe)
	ECRIRE (resultat) // Le chatronronne
	resultat <- CONCATENER(sujet," ", verbe)
	ECRIRE (resultat) // Le chat ronronne

	//Extraction
	resultat <- EXTRAIRE(sujet, 5, 3)
	ECRIRE (resultat) //hat
	//Longueur
	resultat <- LONGUEUR(verbe)
	ECRIRE (resultat) //8

FIN

Hello World
Exercices
#1

Donnez l’algorithme pour calculer le volume d’un rectangle dont la largeur et la longueur soit données par l’utilisateur.

Volume = Longueur × Largeur × Hauteur

PROGRAMME Volume
VAR
	x, y, h, volume : ENTIER
DEBUT
	ECRIRE("Entrez la largeur entière ")
	x <- LIRE()
	ECRIRE("Entrez la longueur entière ")
	y <- LIRE()
	ECRIRE("Entrez la hauteur entière ")
	h <- LIRE()
	volume <- x x y x h
	ECRIRE("Le volume est de", volume)
FIN
#2

Donnez deux algorithmes différents qui inversent les valeurs de deux variables. Ces valeurs sont données par l’utilisateur.

PROGRAMME Inversion
VAR
	a, b, tmp : ENTIER
DEBUT
	ECRIRE("Entrez votre première valeur ")
	a <- LIRE()
	ECRIRE("Entrez votre deuxième valeur ")
	b <- LIRE()
	tmp <- a 
	a <- b 
	b <- tmp
	ECRIRE("a vaut",a, "et b", b)
FIN


PROGRAMME Inversion2
VAR
	a, b : ENTIER
DEBUT
	ECRIRE("Entrez votre première valeur ")
	a <- LIRE()
	ECRIRE("Entrez votre deuxième valeur ")
	b <- LIRE()
	a <- a+b
	b <- a-b
	a <- a-b
	ECRIRE("a vaut",a, "et b", b)
FIN

a = 3
b = 5

a <- 3+5 / 8
b <- 8-5 / 3
a <- 8-3 / 5
Quizz
  • L’algorithmie est-elle la base commune de tous les langages de programmation ?
    • oui
    • non
  • Est-ce qu'une variable peut être un entier et un réel à la fois ?
    • Oui
    • Non
  • Quel est le type de résultat d’une comparaison ?
    • Entier
    • Réel
    • Caractère
    • Booléen
    • Chaîne de caractères

#3

Écrire l’algo qui convertit un nombre en binaire et inversement.

Conditions
Si, alors, sinon
PROGRAMME Entier_positif 
VAR  
   un_nombre : ENTIER 
DEBUT 
   ECRIRE("Entrez un entier de votre choix") 
   un_nombre <- LIRE() 
   SI un_nombre > 0 
   ALORS 
      ECRIRE("Votre entier est positif")
	 SINON 
      ECRIRE("Votre entier est négatif") 
   FINSI 
FIN

Et la valeur zéro ?

PROGRAMME Entier_positif 
VAR  
   un_nombre : ENTIER 
DEBUT 
   ECRIRE("Entrez un entier de votre choix") 
   un_nombre <- LIRE() 
   SI un_nombre > 0 
   ALORS 
      ECRIRE("Votre entier est positif")
	SINON 
      SI un_nombre < 0 
      ALORS 
         ECRIRE("Votre entier est négatif") 
      SINON 
         ECRIRE("Votre entier est nul") 
      FINSI 
   FINSI 
FIN
Cas parmi
PROGRAMME Mois_cas_parmi 
VAR 
   mois : ENTIER 
DEBUT 
   ECRIRE("Entrer un chiffre entre 1 et 6 compris") 
   mois <- LIRE() 
   CAS mois PARMI : 
      CAS : 1 
         ECRIRE("Janvier") 
      CAS : 2 
         ECRIRE("Février") 
      CAS : 3 
         ECRIRE("Mars") 
      CAS : 4 
         ECRIRE("Avril") 
      CAS : 5 
         ECRIRE("Mai") 
      PARDEFAUT 
         ECRIRE("Juin") 
   FINCASPARMI 
FIN
Conditions multiples
  • ET
    • Vérifier si une personne a entre 18 et 30 ans.
PROGRAMME age_personne
VAR
   age : ENTIER
DEBUT
   ECRIRE("Entrez votre âge :")
   LIRE(age)
   SI age >= 18 ET age <= 30 ALORS
      ECRIRE("Vous avez entre 18 et 30 ans.")
   SINON
      ECRIRE("Vous n'avez pas entre 18 et 30 ans.")
   FINSI
FIN
  • OU
    • Vérifier si une personne est soit mineure, soit âgée de plus de 65 ans.
PROGRAMME age_personne
VAR
   age : ENTIER
DEBUT
   ECRIRE("Entrez votre âge :")
   LIRE(age)
   SI age < 18 OU age > 65 ALORS
      ECRIRE("Vous êtes soit mineur, soit âgé de plus de 65 ans.")
   SINON
      ECRIRE("Vous avez entre 18 et 65 ans.")
   FINSI
FIN
Exercices
Exercice du feu tricolore
  • Si le feu est vert alors je peux passer sinon j’attends
    PROGRAMME feu_tricolore 
VAR  
   couleur : CHAINE 
DEBUT 
   ECRIRE("Entrez le couleur du feu tricolore") 
   couleur <- LIRE() 
   SI couleur = "vert" 
   ALORS 
      ECRIRE("Vous pouvez passer")
	 SINON 
      ECRIRE("Vous devez attendre") 
   FINSI 
FIN
  • Si le feu est (ou orange ou rouge) alors j’attends sinon je peux passer
    PROGRAMME feu_tricolore 
VAR  
   couleur : CHAINE 
DEBUT 
   ECRIRE("Entrez le couleur du feu tricolore") 
   couleur <- LIRE() 
   SI couleur = "orange" OU couleur = "rouge"
   ALORS 
      ECRIRE("Vous devez attendre")
	 SINON 
      ECRIRE("Vous pouvez passer") 
   FINSI 
FIN
  • 3 cas
    • Cas le feu est vert : je passe
    • Cas le feu est orange : j’attends
    • Cas le feu est rouge : j’attends
    PROGRAMME feu_tricolore 
VAR  
   couleur : CHAINE 
DEBUT 
   ECRIRE("Entrez le couleur du feu tricolore") 
   couleur <- LIRE() 
   CAS couleur PARMI : 
      CAS "vert" :
         ECRIRE("Vous pouvez passer") 
      CAS "orange" :
         ECRIRE("Vous devez attendre") 
      CAS "rouge" :
         ECRIRE("Vous devez attendre") 
      PARDEFAUT 
         ECRIRE("erreur de couleur. Les 3 couleurs possibles sont : vert, orange, rouge")
   FINCASPARMI
FIN

    ‼️ Le programme avec une itération en cas de saisie incorrecte

    PROGRAMME feu_tricolore 
VAR  
   couleur : CHAINE 
DEBUT
   REPETER
	   ECRIRE("Entrez le couleur du feu tricolore") 
	   couleur <- LIRE() 
	   CAS couleur PARMI : 
	      CAS "vert" :
	         ECRIRE("Vous pouvez passer") 
	      CAS "orange" :
	         ECRIRE("Vous devez attendre") 
	      CAS "rouge" :
	         ECRIRE("Vous devez attendre") 
	      PARDEFAUT 
	         ECRIRE("erreur de couleur. Les 3 couleurs possibles sont : vert, orange, rouge")
	   FINCASPARMI
   JUSQUA (couleur = "vert" OU couleur = "orange" OU couleur = "rouge")
FIN

Exercice calcul d’une remise

Écrivez l’algorithme qui calcule la remise suivante à un montant de type réel entré par l’utilisateur : il est accordé une remise de 5 % pour tout montant compris entre 100 et 500 € et 8 % au-delà. Pensez à tester votre script avec tous les cas possibles.

💡

Attention si on doit utiliser
= ou >= ou <=

PROGRAMME Remise
VAR
	montant : REEL
DEBUT
	ECRIRE("Entrez votre montant : ")
	montant <- LIRE()
	SI montant > 100
	ALORS
		SI montant > 500 
		ALORS
			montant = montant - (montant x 0.08)
		SINON
			montant = montant - (montant x 0.05)
		FINSI
	FINSI
	ECRIRE("Vous devez :", montant)
FIN
Exercice de tri

Écrivez l’algorithme faisant saisir à l’utilisateur trois entiers, i, j et k, et les triant par ordre croissant et les afficher pour vérifier votre tri.

PROGRAMME Tri
VAR
	x, y, z, tmp : ENTIER
DEBUT
	ECRIRE("Entrez le premier entier ")
	x <- LIRE()
	ECRIRE("Entrez le deuxième entier ")
	y <- LIRE()
	ECRIRE("Entrez letroisième entier ")
	z <- LIRE()
	SI x > y
	ALORS
		tmp = x
		x = y
		y = tmp
	FINSI
	SI y > z
	ALORS
		tmp = y
		y = z
		z = tmp
	FINSI
	SI x > y
	ALORS
		tmp = x
		x = y
		y = tmp
	FINSI
	ECRIRE(x, y, z)
FIN
Vérifier si nombre est positif ou négatif

Écrivez l’algorithme qui calcule le signe du produit de deux réels entrés par l’utilisateur sans utiliser la multiplication ni aucun autre calcul.

PROGRAMME Signe_multiplication
VAR
	a, b : ENTIER
	signe : CHAINE
DEBUT
	ECRIRE("Entrez le premier entier ")
	a <- LIRE()
	ECRIRE("Entrez le second entier ")
	b <- LIRE()
	SI a = 0 ou b = 0
	ALORS
		signe <- "nul"
	SINON
		SI a > 0 ET b > 0
		ALORS
			signe <- "positif"
		SINON
			signe <- "négatif"
		FINSI
	FINSI
	ECRIRE("Le signe est ", signe)
FIN
Boucle
Tant que
Nous pouvons comparer le TANT QUE à un SI ALORS qui se répète tant que la condition est valide. Cette structure réalise un nombre indéfini d’itérations qui va dépendre de la validité de la condition. Ces itérations ne s’arrêtent que lorsque la condition n’est plus validée.

Jeu de déplacement d'un personnage

PROGRAMME deplacement_personnage
VAR
   position, distance_max : ENTIER
DEBUT
   position <- 0        // La position de départ du personnage
   distance_max <- 10    // La position finale que le personnage doit atteindre
   
   ECRIRE("Le personnage commence à avancer...")
   
   TANTQUE position < distance_max FAIRE
      position <- position + 1
      ECRIRE("Le personnage est à la position :", position)
   FINTANTQUE

   ECRIRE("Le personnage a atteint la fin du parcours !")
FIN
Répéter
Quelle que soit la validité de la condition, les instructions du bloc sont forcément exécutées une fois.

Jeu du nombre mystère avec la boucle REPETER

Deviner un nombre

Écris un algorithme qui demande à l'utilisateur de deviner un nombre secret compris entre 1 et 10. Tant que l'utilisateur ne donne pas le bon nombre, l'algorithme doit continuer à lui demander de deviner. Une fois que l'utilisateur a trouvé le bon nombre, affiche un message de félicitations.

Étapes :

  1. Définir un nombre secret (par exemple 7).
  1. Demander à l'utilisateur de proposer un nombre.
  1. Tant que le nombre proposé n'est pas égal au nombre secret, redemander un nouveau nombre.
  1. Si l'utilisateur trouve le nombre secret, afficher "Bravo, tu as trouvé le nombre !"
PROGRAMME jeu_nombre_mystere
VAR
   nombre_mystere, nombre_saisie : ENTIER
DEBUT
   nombre_mystere <- 7  // Le nombre mystère est 7 (ou on peut utiliser une valeur aléatoire)
   
   ECRIRE("Bienvenue au jeu du nombre mystère !")
   
   REPETER
      ECRIRE("Devinez un nombre entre 1 et 10 :")
      nombre_saisie <- LIRE
      
      SI nombre_saisie < nombre_mystere ALORS
         ECRIRE("C'est plus grand ! Essayez encore.")
      SINON SI nombre_saisie > nombre_mystere ALORS.    // ici on répète une condition pour le cas où le nombre deviné serait égal au nombre mystère
         ECRIRE("C'est plus petit ! Essayez encore.")
      FINSI
   JUSQUA nombre_saisie = nombre_mystere

   ECRIRE("Félicitations ! Vous avez deviné le nombre mystère :", nombre_mystere)
FIN
Pour

Quand on connait le nombre d’itérations à faire

Nous allons afficher à l’utilisateur la table de multiplication de son choix.

PROGRAMME Table_multiplication 
   i : ENTIER 
   entree_utilisateur : ENTIER 
DEBUT 
   ECRIRE("Quelle table de multiplication voulez-vous afficher ? 
(entier entre 1 et 10)") 
   entree_utilisateur <- LIRE() 
   POUR i ALLANT de 1 à 10 AU PAS DE 1 
   FAIRE 
      ECRIRE(i," x ", entree_utilisateur," = ", entree_utilisateur x i) 
   FINPOUR 
FIN

Pour toutes les tables de multiplications

PROGRAMME Tables_multiplication 
   i, j : ENTIER  
DEBUT  
   POUR i ALLANT de 1 à 10 AU PAS DE 1 
   FAIRE 
      ECRIRE("Table de ", i)  
      POUR j ALLANT de 1 à 10 AU PAS DE 1 
      FAIRE 
         ECRIRE(i," x ",j," = ",j x i) 
      FINPOUR 
   FINPOUR 
FIN
Exercices
BOULANGERIE

Afficher tous les produits en vente de la boulangerie en ligne er si le produit commence par un C, le signaler

PROGRAMME boutique
VAR
produits : TABLEAU[1...5]: CHAINE
i : ENTIER
DEBUT
   produits <- {"baguette", "pain complet", "croissant", "chocolatine", "chouquette"}
   position <- 1
   
   ECRIRE("Voici la liste des produits")
   
   POUR i ALLANT de 1 à 5 AU PAS DE 1 
   FAIRE
	   SI SUBSTRING(produits[i], 1, 1) = "C" // Le premier 1 indique que l'extraction commence au premier caractère et le deuxième 1 indique qu'on extrait un seul caractère.
			ALORS
				ECRIRE(produits [i], ", ce produit commence par un C.")
			SINON
				ECRIRE(produits [i])
			FINSI
      
   FINPOUR 

   ECRIRE("Fin de la liste")
FIN

Inventer un exercice

Calcul de la somme des valeurs des cases d’un tableau.

1- on demande à l’utilisateur d’entrer les chiffres à additionner

2- on en fait la somme

PROGRAMME Somme_tableau 
VAR 
   tab : TABLEAU[1...12] : ENTIER 
   i, somme : ENTIER 
DEBUT 
   // Saisie des valeurs du tableau 
   POUR i ALLANT de 1 à 12 AU PAS DE 1 
   FAIRE 
      ECRIRE("Entrez la valeur ", i, " du tableau") 
      tab[i] <- LIRE() 
   FINPOUR 
   // calcul de la somme 
   somme <- tab[1]  
   POUR i ALLANT de 2 à 12 AU PAS DE 1 
   FAIRE 
         somme <- somme + tab[i] 
      FINPOUR 
   FINPOUR 
   ECRIRE("La somme du tableau est : ", somme) 
FIN
Structure et enregistrement
La structure permet de regrouper et organiser les informations liées à un achat de manière plus efficace et propre.

Programme qui demande au visiteur ce qu’il veut acheter

PROGRAMME achat_boulangerie
STRUCTURE achat 
DEBUT 
   produit : CHAINE 
   quantité : ENTIER 
FINSTRUCTURE 
VAR 
   mon_achat : achat
DEBUT 
   ECRIRE("Entrez le nom du produit que vous souhaitez acheter") 
   mon_achat.nom <- LIRE() 
   ECRIRE("Entrez la quantité du produit") 
   mon_achat.quantite <- LIRE() 
   ECRIRE("vous avez choisi : ",mon_achat.nom, " avec une quantité de ", mon_achat.quantite) 
FIN

On peut mettre un tableau dans une structure

STRUCTURE livre 
DEBUT 
   titre : CHAINE 
   editions : TABLEAU[1...5] : CHAINE 
FINSTRUCTURE
Les fonctions
Les fonctions sont le type de sous-programmes le plus utilisé aujourd’hui en informatique. Ce sont des procédures restreintes :
  • Les paramètres sont uniquement en entrée.
  • Une fonction renvoie toujours une et une seule valeur au programme qui l’appelle.

OCaml

Interpréteurs :