Programmation impérative et éléments d’algorithmique

Formation algorithmique, tutoriel & guide de travaux pratiques en pdf.

Introduction à Visual Basic

L’objectif premier de ce cours est de présenter les traits principaux de la programmation impérative. L’environnement de programmation choisi est Excel, avec un sous-ensemble de VBA (Visual Basic for Applications). Ce chapitre présente les bases du langage et permet d’Écrire des fonctions simples avec des affectations de variables et des alternatives.
Pour sérier les difcultés, nous avons choisi d’introduire les structures de contrôle en Écrivant uniquement des fonctions (chapitres 2 et 3) et les procédures ne sont introduites qu’au chapitre 4.

Introduction

On prÉsente d’abord quelques notions de base sur lesquelles s’ap-puie ce cours. Pour passer de la programmation fonctionnelle à la pro-grammation impÉrative il faut comprendre quelques diffÉrences essen-tielles : environnement d’exÉcution, diffÉrence entre les entitÉs ÉlÉmen-taires expression et instruction ; diffÉrence entre les mÉcanismes d’ex-pression de la rÉpÉtition, rÉcursion et itÉration ; diffÉrence entre les deux types de sous-programmes, procÉdures et fonctions. On insiste aussi sur l’importance de la spÉci cation d’un programme pour expli-quer comment l’utiliser et ce qui en est attendu.

Environnement

Dans le cours de programmation rÉcursive, on a dÉcrit la notion d’environnement : en Scheme, l’environnement est constituÉ de dÉ ni-tions de fonctions et de valeurs de variables, ces derniŁres ayant une valeur constante tant qu’elles sont prÉsentes dans l’environnement.
En programmation impÉrative, cette notion d’environnement est tout aussi, et mŒme peut-Œtre plus importante, avec une diffÉrence fondamentale : la valeur d’une variable n’est plus constante, elle varie pen-dant l’exÉcution du programme. Ainsi, alors qu’en programmation fonc-tionnelle, on peut seulement enrichir l’environnement (par de nouvelles dÉ nitions), en programmation impÉrative on peut Également modi er l’État prÉsent de l’environnement – on parle alors d’environnement d’exÉ-cution.

Expressions et instructions

En style purement fonctionnel, on ne fait que composer des expres-sions et tout programme est dÉcrit par une expression. En style impÉ-ratif, un programme est un enchaînement d’instructions à exÉcuter.
On manipule ici deux types d’entitÉs ÉlÉmentaires : les expressions et les instructions une expression s’Évalue en un rÉsultat (d’un certain type).
Par exemple 3+5-7 ou factorielle(5) sont des expressions en-tiŁres et X < 0 une expression boolÉenne.
une instruction dÉcrit une action de l’ordinateur. Par exemple l’ap-pel de procÉdure effacerTout et l’affectation X = X + 1 sont des instructions.

Récursion et itération

Les deux mÉcanismes permettant d’exprimer la rÉpÉtition d’opÉra-tions dans un programme sont la rÉcursion et l’itÉration (boucles).
Une mÉthode rÉcursive est fondÉe sur la dÉcomposition du traite-ment initial en traitements sur des donnÉes strictement plus pe-tites ; et il y a traitement direct des donnÉes atomiques de base. Par exemple la dÉ nition rÉcursive de la fonction factorielle sur les entiers strictement positifs est donnÉe par une rŁgle qui s’auto-applique,
f act(n) = 1 si n = 0
n × f act(n) si n > 0
Dans une mÉthode itÉrative, on initialise un environnement d’exÉ-cution, puis on exÉcute un certain nombre de fois une suite d’ins-tructions qui modi e un État de l’environnement d’exÉcution ; et l’exÉcution s’arrŒte lorsque cet État atteint un certain statut. Par exemple pour la dÉ nition itÉrative de la fonction factorielle sur les entiers strictement positifs, on peut Écrire la boucle suivante, qui effectue le produit itÉrÉ des n premiers entiers naturels :
f act(n) = Produit(i ; i allant de 1 à n)

Procédures et fonctions

Il existe deux sortes de (sous)-programmes : les fonctions et les pro-cÉdures. En programmation purement fonctionnelle on n’utilise pas de procÉdures (et inversement le style de programmation impÉrative, qui utilise des procÉdures, est quelquefois appelÉ programmation procÉdu-rale).
Fonctions et procÉdures sont de natures diffÉrentes : une fonction renvoie une valeur (sans modi er l’environnement d’exÉcution), alors qu’une procÉdure ne renvoie rien mais modifie l’environnement. Par exemple une fonction qui calcule la somme de 2 et de 3 renvoie une valeur (5) – qui peut ensuite Œtre utilisÉe (injectÉe) dans un autre calcul. En revanche une procÉdure qui af che la valeur 5 modi e l’environne-ment (par la prÉsentation d’une fenŒtre contenant 5) mais cette valeur af chÉe ne peut en aucun cas Œtre rÉutilisÉe.
Cette diffÉrence de nature se traduit au niveau de l’utilisation (ap-pel) : un appel de fonction renvoie un rÉsultat, qui est utilisÉ pour construire une expression, alors qu’un appel de procÉdure est une ins-truction.

Spécification des sous-programmes

La spÉcification d’un sous-programme dÉ nit les termes du contrat qui lie l’utilisateur et le rÉalisateur du sous-programme. La spÉci cation d’un sous-programme contient deux parties :
la signature (nom, liste et type des arguments, type du rÉsultat pour une fonction), dÉ nit la syntaxe d’emploi ; elle est donnÉe dans l’en-tŒte du sous-programme.
la sÉmantique dÉcrit ce que fait le sous-programme ; elle est expri-mÉe sous forme de commentaires, mais on s’attachera à respecter des rŁgles systÉmatiques : expliciter les hypothŁses et les erreurs dans des clauses particuliŁres, expliciter le rÉsultat de l’exÉcution du sous-programme (renvoi d’une valeur pour une fonction et mo-di cations de l’environnement d’exÉcution pour une procÉdure).

Visual Basic – Préliminaires

Types et expressions

Il y a trois types de base dans le domaine de programmation : nu-mÉrique, logique et chaîne de caractŁres. Et les expressions s’Écrivent en notation mathÉmatique habituelle.
Les types numÉriques sont les types Integer, Long (entiers longs), Byte (entiers compris entre 0 et 255), Single et Double (rÉels) avec les opÉrations habituelles (la division entiŁre est notÉe \, et l’opÉrateur « modulo » est notÉ mod).
Les constantes du type logique Boolean sont False et True et les opÉrations Not, And, Or.
Le type String est le type des chaînes de caractŁres, les constantes Étant notÉes entre guillemets anglais (« ) et l’opÉration de concatÉ-nation Étant notÉe « & ».
Les opÉrateurs binaires de comparaison =, <> , <, >, <=, >= com-parent deux valeurs numÉriques (ou deux chaînes de caractŁres) et produisent une valeur logique.

Aspects lexicaux

Visual Basic est un langage ligne : le passage à la ligne fait partie de la syntaxe du langage.
Commentaires
Les commentaires sont destinÉs au lecteur humain du programme, et ignorÉs lors de l’exÉcution. Il y a deux façons d’indiquer les commen-taires en VBA : à l’aide du mot-clÉ Rem ou à l’aide du symbole apostrophe « ’ ». Le reste de la ligne est alors ignorÉ. Un tel commentaire doit donc tenir sur une seule ligne (pour Écrire des commentaires sur plusieurs lignes il faut mettre une apostrophe au dÉbut de chaque ligne).
CaractŁre de continuation
VBA Étant un langage ligne, le changement de ligne est signi catif : par exemple les en-tŒtes des sous-programmes doivent Œtre Écrites sur une seule ligne. Si une en-tŒte (ou toute autre instruction devant tenir sur une ligne) est trop longue pour tenir sur une seule ligne physique, on peut la prolonger en insÉrant le caractŁre de continuation blanc sou-lignÉ (_), aprŁs une espace, à la n de la premiŁre ligne, et ce qui est alors Écrit sur la ligne suivante est considÉrÉ comme faisant partie de la mŒme ligne.
Function somPremEnt(ByVal n As Integer) _As Integer
Le seul endroit oé un caractŁre de continuation ne fonctionne pas de cette maniŁre est à l’intÉrieur d’une chaîne de caractŁres (string), il est alors considÉrÉ comme du texte. Pour Écrire une chaîne de caractŁres sur plusieurs lignes il faut utiliser l’opÉrateur de concatÉnation (&).
Structuration du texte
La structuration syntaxique des programmes VBA est assurÉe par un systŁme de parenthÉsage : un mot particulier vient terminer chaque instruction ou bloc d’instructions.
En gÉnÉral le mot qui sert de parenthŁse fermante est le mŒme que celui qui sert de parenthŁse ouvrante, prÉcÉdÉ de End. Par exemple End Function vient terminer une fonction, commencÉe par Function, le mot End Sub vient terminer une procÉdure, commencÉe par Sub, le mot End If vient terminer une instruction d’alternative, commencÉe par If.
Mais il y a des exceptions à cette rŁgle de formation. Par exemple Next vient terminer une boucle commencÉe par For et Loop vient ter-miner une boucle commencÉe par Do.

Fonctions en VBA

Il y a deux sortes de sous-programmes : les fonctions et les pro-cÉdures. Une fonction dÉ nie par le programmeur renvoie un rÉsultat, comme les fonctions prÉdÉ nies du tableur. Une procÉdure a pour ef-fet de modi er l’environnement d’exÉcution (par exemple colorier des cellules de la feuille de calcul).
Nous avons choisi d’Écrire les premiers programmes uniquement sous forme fonctionnelle, l’Écriture de procÉdures Étant reportÉe au cha-pitre 4. Mais les rŁgles et les conventions d’Écriture – spÉci cation, dÉ – nition, utilisation – sont semblables pour les fonctions et les procÉdures.
On explique tout d’abord dans cette section comment dÉ nir et uti-liser une fonction. On Étudiera ensuite, dans ce chapitre et le sui-vant, comment implanter les sous-programmes, c’est-à-dire construire le corps d’un sous-programme en enchaînant une suite d’instructions.

Définitions de fonctions

La syntaxe d’une dÉfinition de fonction dÉcrit le nom, les arguments et le code formant le corps de cette fonction. On insiste aussi ici sur la spÉci cation.
En-tŒte et spÉci cation
Une dÉ nition de fonction s’Écrit de la façon suivante :
L’en-tŒte de la fonction dÉcrit la signature de la fonction : nom, type des paramŁtres et type du rÉsultat :
l’ÉlÉment Private ou Public est facultatif 1 : une fonction privÉe n’est accessible qu’à l’intÉrieur du module oé elle est dÉ nie, alors qu’une fonction publique est accessible de tous les modules (voir la notion de module dans la che technique VBA). La valeur par dÉfaut est Public.
le mot Function est suivi du nom de la fonction, ici F vient ensuite la liste des paramŁtres formels avec leurs types chaque paramŁtre formel est prÉcÉdÉ du mot ByVal, qui indique que l’on transmettra la valeur du paramŁtre d’appel, (il existe en VBA d’autres modes de transmission des paramŁtres, que l’on n’Étudiera pas ici).
chaque paramŁtre formel a un nom, par exemple ici p1, et l’on indique aussi son type par As suivi du nom du type, ici t1.
les paramŁtres formels sont sÉparÉs par des virgules. en n on indique le type du rÉsultat de la fonction par As suivi du nom du type rÉsultat, par exemple ici t_res.
Il reste à donner la partie description de la spÉci cation de la fonc-tion. Cette partie est prÉsentÉe sous forme de commentaires à la suite de l’en-tŒte (ceci est une convention qui nous est propre).
la ligne Hypothèse indique les conditions d’utilisation de la fonc-tion
la ligne Erreur signale les cas oé une erreur est dÉtectÉe par la fonction
la ligne Renvoie dÉcrit la valeur renvoyÉe par la fonction, selon la valeur des paramŁtres et l’État de l’environnement.
La ligne Renvoie est obligatoire dans toute description de fonction, mais les lignes Hypothèse et Erreur n’apparaissent que lorsqu’elles ont une
1 par convention on note entre crochets les morceaux de code facultatifs raison d’Œtre.
Instruction de retour et sortie
Le corps de la fonction contient la dÉclaration des variables et les instructions. Parmi les instructions il doit toujours y avoir une instruc-tion de retour, pour renvoyer le rÉsultat de la fonction. Attention cette obligation n’est pas vÉri Ée par VBA. Pire, sans instruction de retour, la fonction retourne une valeur par dÉfaut et il n’y a donc pas d’erreur dÉtectÉe à l’exÉcution, mais en gÉnÉral cette valeur n’est pas la valeur attendue.
L’instruction de retour se note par le nom de la fonction, suivi du signe Égal (=), suivi de l’expression dont la valeur doit Œtre retournÉe en rÉsultat : le nom de la fonction sert de variable pour contenir le rÉsultat.
[Private|Public] Function F(ByVal p1 As t1) As t_res
F = <expression> ’instruction de retour
End Function
La sortie d’une dÉ nition de fonction se fait en gÉnÉral en atteignant l’ÉnoncÉ End Function. Le rÉsultat renvoyÉ est alors le contenu de la variable du nom de la fonction.
On peut aussi sortir d’une fonction en atteignant l’instruction d’Échap-pement Exit Function. Le rÉsultat renvoyÉ est alors aussi le contenu de la variable du nom de la fonction.
On dissocie donc en VB la sortie de la fonction (par Exit Function ou en atteignant End Function) et la valeur renvoyÉe par la fonction (qui est la valeur contenue, au moment de la sortie, dans la variable nom de la fonction).
Exemple 1 : somme des n premiers entiers
On commence par Écrire une fonction qui, Étant donnÉ un entier naturel n, renvoie la somme des n premiers entiers, en utilisant une formule de calcul. Le corps de la fonction est constituÉ d’une seule ins-truction : l’instruction de retour de la fonction, qui retourne la valeur de l’expression n(n + 1)/2.
Function somPremEnt(ByVal n As Integer) As Integer
’ HypothŁse : n >= 0
’ Renvoie : la somme des n premiers entiers naturels
somPremEnt = (n * (n + 1)) / 2
End Function

Appel de fonctions

Un appel de fonction est l’application d’une fonction à des arguments (on dit aussi paramŁtres effectifs ou paramŁtres rÉels) qui sont des ex-pressions. Par exemple, l’appel somPremEnt(3+2) renvoie le rÉsultat de l’application de la fonction somPremEnt avec le paramŁtre effectif 3 + 2 (dont la valeur est 5), c’est-à-dire que cet appel renvoie la valeur 15.
Un appel de fonction peut se faire soit à l’intÉrieur d’un programme VBA, soit directement dans une cellule de la feuille de calcul.
Dans un programme VBA
Un appel d’une fonction permet de former une expression dans le corps d’un programme. Dans l’exemple ci-dessous le corps de la fonc-tion sommeEnt contient deux appels à la fonction somPremEnt.
Exemple 2 : somme des entiers de n à m
Pour Écrire une fonction qui renvoie la somme n + (n + 1) + . . . + m des entiers compris entre deux entiers naturels n et m, avec n ≤ m, on calcule la diffÉrence entre la somme des m premiers entiers (rÉsultat de l’appel le la fonction somPremEnt avec l’argument m) et la somme des n − 1 premiers entiers (rÉsultat de l’appel somPremEnt(n-1)).
Function sommeEnt(ByVal n As Integer, ByVal m As Integer) _
As Integer
’ HypothŁse : 0 < n <= m
’ Renvoie : la somme des entiers compris entre n et m (inclus)
sommeEnt = somPremEnt(m) – somPremEnt(n – 1)
End Function
De mŒme dans l’expression 2 * sommeEnt(10,20)/5, l’appel de la fonction sommeEnt avec les paramŁtres effectifs 10 et 20 renvoie la va-leur 165, et l’expression vaut donc nalement 66.
Dans l’exemple prÉcÉdent, notez que les paramŁtres 10 et 20 sont sÉparÉs par une virgule : dans un appel de fonction à l’intÉrieur d’un programme VBA, les paramŁtres effectifs sont sÉparÉs par des virgules.
Dans la feuille de calcul
Pour tester les fonctions dans l’environnement Excel on peut appe-ler une fonction dans une case de la feuille de calcul. Cela peut se faire avec l’aide du « menu fonction » (entourÉ dans la gure de gauche ci-dessous). Dans la fenŒtre de dialogue qui s’ouvre alors ( gure de droite ci-dessous), on voit apparaître dans les « Fonctions personnalisÉes », la liste des fonctions dÉ nies par l’utilisateur, par exemple ici les fonctions somPremEnt et sommeEnt.
Lorque l’on sÉlectionne la fonction sommeEnt, il apparaît successi-vement plusieurs fenŒtres permettant de donner les paramŁtres effec-tifs (ici on a sÉlectionnÉ successivement la premiŁre et la deuxiŁme case de la premiŁre colonne de la feuille de calcul, et ce sont les va-leurs contenues dans ces cases qui constituent les paramŁtres effec-tifs). Finalement la formule correspondant à l’appel de fonction appa-raît dans la barre de formule =sommeEnt(L(-2)C;L(-1)C). Les para-mŁtres effectifs sont notÉs par les rÉfÉrences relatives des cellules qui les contiennent : le premier est situÉ sur la mŒme colonne, deux lignes au dessus de la case qui contient le rÉsultat de l’appel et le second sur la mŒme colonne, une ligne au dessus.
Remarque : il faut noter que lorsqu’une fonction est appelÉe dans la feuille de calcul, les paramŁtres sont sÉparÉs par des points-virgules (et non des virgules). La raison de ce changement de notation est que dans le tableur on note les nombres dÉcimaux à la française, avec des virgules (alors que c’est le point dÉcimal anglo-saxon qui est utilisÉ en Visual Basic) et il faut donc diffÉrencier le sÉparateur de paramŁtres en le notant avec un point-virgule.

Constantes et variables

Constantes et variables sont des ÉlÉments permettant de stocker et de manipuler des donnÉes. Constantes et variables ont un nom, un type et une valeur. Parmi les types manipulÉs par VBA, on retiendra dans un premier temps les nombres (integer, long, double, …) , les chaînes de caractŁres (string) et les boolÉens (boolean).
Constantes et variables sont dÉclarÉes d’un certain type, ce qui per-met de leur attribuer les caractÉristiques pour stocker des donnÉes de ce type.
Une constante conserve une mŒme valeur pendant toute l’exÉcution d’un programme, alors qu’une variable dÉsigne un emplacement de sto-ckage contenant des donnÉes pouvant Œtre modi Ées au cours de l’exÉ-cution du programme. L’instruction permettant de modi er la valeur d’une variable est l’affectation.

Notion de constante

Nature
Une constante est un nom pour une valeur calculÉe lors de l’analyse du programme en VBA. Noter qu’on ne peut pas modi er la valeur d’une constante : la valeur qui lui est affectÉe lors de sa dÉclaration reste la mŒme pendant toute l’exÉcution du programme.
DÉclaration des constantes en VBA
L’instruction Const permet de dÉclarer les constantes
pour une constante locale à un sous-programme
Const nomCons As type = <expr>
la dÉclaration explicite le nom nomCons à utiliser pour la valeur expr. En VBA dÉcrire le type est facultatif (lorsque le type n’est pas dÉclarÉ explicitement, la constante se voit attribuer le type de donnÉes qui convient le mieux à la valeur expr), mais dans ce cours nous rendrons obligatoires toutes les dÉclarations de type.
au niveau d’un module
Public Const nomCons As type = <expr>
[Private] Const nomCons As type = <expr>
Par dÉfaut, les constantes sont privÉes.
Au niveau d’un sous-programme ou d’un module, on peut combiner plusieurs dÉclarations de constantes sur une mŒme ligne, en sÉparant chaque dÉclaration par une virgule.
Une variable associe une valeur à un nom. Dans un langage impÉra-tif, la valeur associÉe au nom peut Évoluer au cours de l’exÉcution. Ceci est à opposer à ce qui se passe dans un langage purement fonctionnel oé la valeur associÉe au nom est immuable.

1 Présentation du cours 
2 Introduction à Visual Basic 
2.1 Introduction
2.2 Visual Basic – Préliminaires
2.3 Fonctions en VBA
2.4 Constantes et variables
2.5 Structures de contrôle : séquence
2.6 Structures de contrôle : alternative
3 Récursion et boucles 
3.1 Récursion
3.2 Itération : boucle For
3.3 Itération : boucle Do
3.4 Choix entre différents types de boucle
4 Procédures et entrées/sorties 43
4.1 Procédures
4.2 Macros
4.3 Entrées/sorties
5 Objets en VBA Excel R
5.1 Notion d’objet
5.2 Notion de classe
5.3 Notation pointée
5.4 Spécication et utilisation de propriété et de méthode
5.5 Instruction With
5.6 Notion de collection
5.7 Propriétés, fonctions et procédures globales
5.8 Propriétés et méthodes de la classe Worksheet
5.9 Propriétés et méthodes de la classe Range
5.10Déclaration et affectation d’objets
5.11Formatage d’une plage de cellules
6 Un exemple : opérations matricielles 
6.1 Opérations matricielles sans macros
6.2 Opérations matricielles avec macros
6.3 Conclusion
7 Algorithmes de Recherche 
7.1 Présentation du problème
7.2 Recherche séquentielle
7.3 Recherche dichotomique
8 Algorithmes de tri 
8.1 Présentation du problème
8.2 Tri par insertion
8.3 Tri par sélection
8.4 Tri rapide (Quicksort)
9 Recalcul dans le tableur 
9.1 Recalcul des valeurs
9.2 Recalcul des cellules