Algorithmique
1er cours (13/09/2023) :
Introduction :
L’algorithmique est une suite de raisonnement et d’opérations qui fournit une solution
(sortie) à certains problèmes (entrée). Un peu comme une recette (instructions pour un
savoir faire sans expliquer la théorie)… La définition dépend des personnes même si la
définition reste mieux mathématiquement.
Un langage fortement typé est un langage dans lequel les variables doivent être définies au
tout début (contraire de faiblement typé).
Le premier ordinateur électronique est d’ailleurs apparu pendant la 2nde guerre mondiale qui
a réussi à décoder ENIGMA.
Notion d’algorithme :
Le langage algorithmique est un compromis entre un langage naturel et un langage de
programmation.
Ces algorithmes est une suite d’instructions compréhensibles et lisibles dans l’ordre, qui
sont souvent accompagnés d’un lexique qui indique pour chaque variable, son type et son
rôle avec des critères à respecter comme une entête et un corps.
Variables :
Une variable est une entité qui contient un identifiant (nom), une valeur et un type.
On ne peut en faire que trois choses :
- Obtenir son contenu
- Affecter un (nouveau) contenu
- Modifier son type
Pour proposer de définir une variable, on écrit : Variable <- lire()
Opérateurs :
Un opérateur peut être mathématique mais aussi booléens (et, ou, OuExclusif)
Dans une division euclidienne, mod correspond au reste et div correspond au résultat.
Ces opérateurs ont les mêmes règles de priorités qu’en mathématiques. Pour les booléens,
l’ordre est : non, et, ouExclusif, ou.
Les parenthèses sont donc utiles comme dans l’exemple 2 != 2 qui change de tout au tout si
on en met ou non.
Structures de contrôle :
Les structures d’instruction permet de conditionner l’exécution d’un algorithme, comme les
instructions conditionnelles (si…alors, sinon, FinSi,…), la structure car, les itérations (pour,
FinPour, tant que, répéter jusqu’à, …)
Les tableaux :
Un tableau est un regroupement de variables qui ont chacune un type commun.
Un peu par exemple faire un tableau répertoriant 10 entiers/emplacements (un tableau
commence généralement par l’index 0).
Les fonctions et procédures :
Une fonction est un bloc de code que l’on peut réutiliser est qui donne sortie comparé à une
procédure.
On peut prendre comme exemple une fonction qui s’appelle elle-même un certain nombre
de fois pour fournir un résultat.
Les différents algorithmes :
Algorithme d’Euclide :
Cet algorithme sert à calculer le PGCD.
Exemple de pgcd: pgcd (12, 15) = 3
pgcd (12, 30) = 6
Nom : Algorithme d’Euclide
Données : 2 nombres
Résultat / Sortie : Le PGCD des deux nombres fournies
Principe : On divise la première valeur par la deuxième via une division euclidienne, on
obtiendra donc un quotient et un reste. On divise ensuite le quotient et le reste obtenu et
ainsi de suite jusqu’à obtenir un reste qui est égal à 0. On affiche alors le quotient.
Début
Ecrire ( « Entrez A »)
A <- lire()
Ecrire ( « Entrez B »)
B <- lire()
Auxiliaire <- A
Si A < B
A <- B
B <- Auxiliaire
Fin Si
Répéter
Reste <- A mod B
A <- B
B <- Reste
Jusqu’à ce que Reste = 0
Retourner B
Fin
Algorithme d’Eratosthène :
Cet algorithme permet de donner les nombres premiers entre 1 et une valeur que l’on
définit. Et ce sans multiplication et division mais avec des additions.
Nom : Algorithme d’Eratosthène
Données : 1 nombre entier.
Résultat / Sortie : Tout les nombres premiers entre 1 et le nombre choisie
Principe : On prend le premier nombre premier entre 1 et le nombre choisie, puis on l’ajoute
en boucle pour voir tout les nombres qui ne sont pas premiers jusqu’à atteindre ou dépasser
notre variable. Puis on recommence le même principe avec le second nombre premier dans
l’ordre et ainsi de suite jusqu’à notre variable.
Début
Tab : tableau [1 … N] booléen
Si N <= 1 alors :
Ecrire (« Aucun nombre premier »)
Sinon faire:
Tab[1] <- 0
Pour i de 2 à N faire
Tab[i] <- 1
Fin pour
Pour i de 1 à N faire :
Si Tab[i] = 1 alors :
NombreABarrer <- i + i
Répéter :
Tab[NombresABarrer] <- 0
NombresABarrer <- NombreABarrer + i
Jusqu’à ce que NombreAbarrer > N
Fin si
Fin pour
Pour i de 1 à N faire :
Si Tab[i] = 1
Ecrire (i)
Fin si
Fin pour
Fin si
FIN
Algorithme de décomposition :
Nom : Algorithme de décomposition
Données : La valeur N
Résultat / Sortie : L’affichage de la décomposition du nombre en question
Principe : Divisions successives de 2 jusqu’à N pour trouver la décomposition en nombre
premier sans les savoir au début.
Début
Ecrire (« Entrez la valeur de N »)
N <- Lire ()
Réponse <- N + ‘=’
Diviseur <- 2
Tant que (N != 1) faire :
Si (N mod diviseur = 0) alors :
N <- N div Diviseur
Si N != 1 alors :
Réponse <- Réponse + Diviseur + «*»
Sinon :
Réponse <- Réponse + Diviseur
Fin si
Sinon :
Diviseur <- Diviseur + 1
Fin si
Fin tant que
Ecrire (Réponse)
FIN
Algorithme des sommes :
Nom : Algorithme des sommes
Données : La valeur N
Résultat / Sortie : Ecrire le résultat de la somme de tout les entiers naturels de 1 à N
Principe : Additionner tout les nombres entre 1 et N en descendant N jusqu’à atteindre 0.
Début
Ecrire (« Entrez la valeur N »)
N <- lire()
Réponse <- N
Si N = 0 alors :
Ecrire (Réponse)
Sinon :
Tant que (N != 0) faire :
N <- N - 1
Réponse <- Réponse + N
Fin Tant que
Fin si
Ecrire (‘’Somme =’’, réponse)
Fin
OU
Début
Ecrire (« N ? »)
N <- lire()
Somme <- N * (N+1) / 2
Ecrire (Somme)
Fin
Algorithme de conversion en binaire et Hexadécimal :
Début
Tab : Tableau [0,…, Max] Entiers
Ecrire (« Entrez la valeur de N »)
N <- lire()
i <- 0
Tant que N != 0 alors :
Tab [i] <- N mod 2
N <- N div 2
i <- i + 1
Fin tant que
Tant que i != 0 faire :
i <- i – 1
Ecrire (Tab [i])
Fin tant que
FIN
Début
Tab : Tableau [A,B,C,D,E,F] caractère
Ecrire (« Entrez la valeur de N »)
N <- lire()
Quotient <- N
Reste <- 0
NB_Hexa <- ‘’ ’’
Tant que Quotient > 0 faire :
Reste <- Quotient mod 16
Quotient <- Quotient div 16
Si Reste >= 10 alors :
NB_Hexa <- Tab [Reste – 10] + NB_Hexa
Sinon :
NB_Hexa <- str(Reste) + NB_Hexa
Fin si
Fin Tant que
Retourner NB_Hexa
FIN
On veut un algorithme pour calculer la valeur rapproché de e-x avec x >= 0
On analyse le problème :
Pour tout x appartenant à R :
e-x = ∑infn = 0 (-1)n xn/(n!) = ∑Maxn=0 (-1)n xn/(n!) + ∑+infn = Max+i (-1)n xn/(n!)
Algorithme puissances :
Fonction Puissance (x : réel, n : entier) : réel.
Début
Aux <- 1
Si n = ! 0 alors :
Pour i de 1 à n faire :
Aux <- Aux * x
Fin pour
Fin si
Retourner Aux
Fin
Algorithme Factorielle :
Fonction factorielle (n : entier) : entier
Début
Aux <- 1
Si n != 0 alors :
Pour i de 1 à n faire :
Aux <- Aux * i
Fin pour
Fin si
Retourner Aux
Fin
Algorithme exponentielle valeur approchée :
Début
Ecrire (« x ? »)
x <- lire()
Ecrire (« Ꜫ ? »)
Ꜫ <- lire()
Terme <- 1
Somme <- 0
n <- 1
Tant que Terme > Ꜫ faire :
Somme <- Somme + Terme
Terme <- Puiss (-x, n) / Facto (n)
n <- n + 1
Fin tant que
Ecrire (« L’approximation est : », somme)
Fin
OU
Début
Ecrire (« x ? »)
x <- lire()
Ecrire (« Ꜫ ? »)
Ꜫ <- lire()
Terme <- 1
Somme <- 0
n <- 1
Tant que Terme > Ꜫ faire :
Somme <- Somme + terme
Terme <- Terme * -1 * x / (n + 1)
n <- n + 1
Fin tant que
Ecrire (« L’approximation est : », somme)
Fin
Algorithme résolution polynôme second degrés :
Début
Ecrire (« a ? »)
A <- lire()
Ecrire (« b ? »)
B <- lire()
Ecrire (« c ? »)
C <- lire()
Si A = 0 alors :
Ecrire (« Ce n’est pas un polynôme du second degrès)
Fin si
Delta <- B*B-4*A*C
Si Delta = 0 alors :
X1 <- (-1 * B)/(2 * A)
Ecrire (« La solution de l’équation est : », X1)
Fin si
Si Delta > 0 alors :
X1 <- ((-1 * B) + sqrt(Delta))/(2*A))
X2 <- ((-1 * B) - sqrt(Delta))/(2*A))
Ecrire (« Les solutions de l’équation sont : », X1, X2)
Fin si
Si Delta < 0 alors :
X1 <- ((-1 * B) + « i »,sqrt(Delta))/(2*A))
X2 <- ((-1 * B) – « i »,sqrt(Delta))/(2*A))
Ecrire (« Les solutions de l’équation sont : », X1, X2)
Fin si
Fin
