Écrire un programme, c'est expliquer
la suite d'actions à entreprendre pour obtenir un résultat. Différents langages de
programmation existent. S'exprimer avec certains sera plus aisé pour résoudre un
problème donné. Ce qui importe avant tout est de savoir expliquer ce qu'il y a à faire.
Écrire un programme, c'est décrire ce que le programme doit faire à l'aide d'un langage de programmation.
Un bon programme :
accomplit la tâche prévue
peut être lu et compris
peut être modifié, si nécessaire, sans aucune difficulté
respecte les délais et le budget fixés
La technique de programmation est
importante. Il faut maîtriser le vocabulaire et la grammaire: les structures de contrôle
et l'art d'écrire des sous-programmes. Il faut définir et décrire les entrées et les
sorties de chaque composante du programme (type, structure, etc), et aussi les variables
temporaires utilisées. Dans le cas où des contraintes spéciales (temps de réponse,
performance, volume de données important, etc) existent, une analyse plus élaborée est
nécessaire pour décider la manière d'obtenir le résultat demandé.
Différentes techniques de
programmation existent : méthode ascendante, méthode descendante, ordinogramme,
etc. La méthode descendante (affinage graduel ou « diviser pour régner » )
décompose le problème en plusieurs grandes tâches elles mêmes divisées en tâches
plus petites, lesquelles seront à leur tour décomposées en sous-tâches, etc.
Cependant avant d'écrire un
programme, il faut réfléchir à la manière de résoudre le problème posé. Mille et
une manière existent ! On appelle algorithme une méthode pour parvenir à un résultat ou
un objectif donné en un temps fini.
Pour un problème donné, beaucoup
d'algorithmes existent. On peut en inventer autant qu'on veut. Un algorithme est une
manière particulière de résoudre un problème. Les algorithmes performants sont les
plus séduisants. Cependant les algorithmes les plus simples sont souvent les plus beaux
même s'ils ne sont pas les plus performants.
Pour un algorithme donné, de
nombreuses structures de données peuvent être utilisées : les tableaux, les
listes, les arbres, etc. Mais lorsque l'on réfléchit à l'algorithme à utiliser, on
doit faire abstraction des structures de données.
Un problème bien posé est à
moitié résolu. Rédiger l'idée de la résolution est déjà une manière de mettre ses
idées en place. Et il faut rédiger de telle manière qu'une autre personne ignorante du
problème sache à son tour comprendre le problème et comment elle peut le résoudre.
2. Recherche d'un élément dans un TABLEAU trié
La nécessité de trier des données
résulte du besoin de les retrouver rapidement. Par exemple, pour chercher l'adresse et le
numéro de téléphone d'une personne, on parcours un fichier jusqu'à trouver
l'enregistrement qui la concerne.
Pour rechercher séquentiellement un
élément dans un tableau, on passe en revue tous les éléments de ce tableau, un à un,
jusqu'à trouver la position de l'élément recherché (appelée encore indice). Un
recherche séquentielle est plus ou moins rapide selon que l'élément recherché est
situé au début ou en fin du tableau. En moyenne, on passe en revue la moitié des
éléments. Si N est le nombre d'élément du tableau, le nombre moyen de comparaisons
sera N/2.
Lorsque le tableau est trié
numériquement ou alphabétiquement, la méthode de recherche dichotomique permet de
diviser le temps de recherche par 2 à chaque étape. L'algorithme est le suivant :
Initialiser la section de recherche à l'ensemble du tableau
Comparer le nom cherché au nom de l'élément situé au milieu de la section de recherche
Si le nom cherché est plus petit que le nom de l'élément situé au milieu,
on recommence la recherche dans la première moitié
Si le nom cherché est plus grand que le nom de l'élément situé au milieu,
la recherche se poursuit dans la seconde moitié.
Sinon on a trouvé l'élément recherché
Recommencer au point (2) tant que l'élément cherché n'est pas trouvé
et si la section de recherche est constituée d'au moins un élément.
Lorsqu'il y a par exemples 1024 éléments, on retrouve l'élément recherché après au plus 10 comparaisons
(210 = 1024) alors qu'il en faut en moyenne 512 dans le cas d'une recherche séquentielle.
Comme on le voit, l'algorithmique a une très grande importance dans la programmation.
3. Recherche dans un tableau non trié à l'aide d'une sentinelle
A paraître...
4. Tirage aléatoire de NA nombres parmi NT nombres
Soit le tableau TAB de NT éléments.
Chaque élément du tableau a pour valeur un des nombres sur lesquels le tirage a lieu.
L'ordre de rangement de ces NT nombres dans le tableau importe peu.
Le tirage aléatoire s'effectuera sur la position c'est à dire l'indice de rangement dans le tableau.
Prenons par exemple le tableau suivants à NT = 9 éléments :
11 33 22 55 44 66 88 99 77
Rappelons que pour un tableau de 9 éléments, les indices varient de 0 à 8.
Effectuons un tirage aléatoire d'un valeur KA comprise entre 0 et 8 (NT-1).
Soit par exemple, KA = 3 le résultat obtenu. Comme KA est l'indice, c'est en fait le nombre 55 qui a été tiré.
Rangeons ce nombre au début de tableau en le permutant avec l'élement d'indice 0 dont la valeur est 11.
On obtient :
55 * 33 22 11 44 66 88 99 77
Le début du tableau (1 élément) contient le premier nombre tiré,
le reste du tableau contient les 8 nombres restants sur lesquels on continuera le tirage.
Le caractère * a été ici utilisé pour délimiter le début du tableau avec le reste du tableau.
Effectuons alors un tirage aléatoire d'un valeur KA comprise entre 1 et 8 (NT-1).
Soit par exemple, KA = 5 le résultat obtenu. Comme KA est l'indice, c'est en fait le nombre 66 qui a été tiré.
Rangeons ce nombre en 2e position du tableau en le permutant avec l'élément d'indice 1 dont la valeur est 33.
On obtient :
55 66 * 22 11 44 33 88 99 77
Le début du tableau (2 éléments) contient les 2 premiers nombres tirés,
le reste du tableau contient les 7 nombres restants sur lesquels on continuera le tirage.
...
Pour effectuer NA tirages parmi NT (cela peut être 7, 8 et même 9 sur 9!), nous allons utiliser une boucle.
Les variables utilisées sont :
le tableau TAB[ NT ] est supposé déjà initialisé
la variable NT est le nombre de valeurs du tableau
la variable K est le nombre de valeurs du tableau déjà tirées
la variable NA est le nombre de tirage à effectuer
la variable KA est l'indice de la valeur de l'élément tiré
la variable TMP est une variable utilisée pour effectuer la permutaion des valeurs
Nous aurons la boucle suivante pour le tirage de NA nombres parmi NT :
Nous aurons la boucle suivante pour l'affichage de valeurs tirées :
Cette méthode s'inspire du tri par sélection directe utilisant un seul tableau
dont les premiers éléments sont les éléments déjà triés (tous plus petits que les éléments restants).
Cette méthode est à comparer avec d'autres méthodes testant si l'élément tiré n'a pas été déjà tiré
précédemment. Comme ces méthodes recommencent le tirage tant que l'on n'a pas obtenu un élément non déjà tiré,
cela peut prendre un certain temps, voire un temps infini !
Par exemple si NA=999 et NT=1000, la probabilité de tirer du premier coup le 999e éléments
parmi, en fait, les 2 éléments restants est de 2/1000.
Ce qui donne 998/1000 chances de refaire un tirage, et cela un certain nombre de fois...
A noter : Le tableau modifié résultant d'un tirage de NA nombres peut être utilisé tel quel
pour un autre tirage de NA nombres parmi NT, l'ordre des valeurs n'ayant aucune importance.
Cliquez sur un élément en VERT,
il sera permuté en début de tableau après les nombres déjà choisis
qui en sont ROUGE.
Au départ, aucun élément n'est encore choisi :
tous les éléments sont en VERT.
5. Les carrés magiques d'ordre impair
Rappelons qu'un carré magique d'ordre N est un tableau de N*N cases comportant dans chacune
d'entre elles un nombre différent et tel que la somme des nombres de chaque ligne, de chaque colonne
ou de chaque grande diagonale soit la même.
Si N est égal à 5, le carré comportera 25 cases. Prenons les nombres de 1 à 25 pour remplir le carré.
Une méthode simple pour obtenir un
carré magique est d'essayer toutes les combinaisons possibles de mettre ces 25 nombres
dans les 25 cases du carré et de vérifier si les sommes des lignes, des colonnes et des
2 grandes diagonales sont identiques. Malheureusement il y a environ
Même avec un ordinateur très
puissant, on ne peut garantir de trouver la première solution en un temps fini.
On a démontré que la méthode
suivante permettait quant à elle d'obtenir un carré magique quel que soit l'ordre à
condition que celui-ci soit impair (nombre de cases impair). Les nombres de 1 à N2
doivent être déposés dans les cases du carré comme indiqué ci-dessous:
Mettre le chiffre 1 au milieu de la dernière colonne
Mettre le chiffre suivant dans la case en dessous à droite :
Si on est sur un bord du tableau, alors on juxtapose le même tableau à côté de telle
manière qu'il y ait toujours une case située en dessous à droite
Si la case pour le chiffre suivant est déjà occupée, alors on choisit la case située à
gauche
On recommence au point 2 tant qu'il y a des cases libres.
Cliquer sur une case vide de la grille pour trouver la suivante...
Les questions que l'on peut se poser
sont : Y a-t-il toujours une case de libre à gauche quand la case située en dessous à
droite est occupée ? L'algorithme marche-t-il quel que soit l'ordre impair du carré ?
Compte tenu des symétries et des rotations possibles, obtient-on tous les carrés
magiques possibles ? Cet algorithme permet-il d'obtenir des carrés magiques d'ordre pair ?
6. Création de labyrinthes
Citons deux méthodes pour la construction de labyrinthes :
On part d'une situation avec des
murs partout. Les murs sont supprimés et des galeries construites de telle manière qu'il
y ait un chemin unique entre 2 cases quelconques du labyrinthe (pas de boucle). Au cours
d'un parcours aléatoire du labyrinthe partiel, on abat des murs vers des cases non déjà
visitées. Régulièrement afin d'éviter des errances dans le labyrinthe en cours de
construction, on part de la première case non visitée. Celle-ci est forcément à côté
d'une case déjà visitée. Le mur de séparation est abattu et un nouveau parcours
aléatoire commence.
On part d'un situation avec aucun
mur à l'intérieur (seuls les murs externes existent). A partir des murs existants
d'autres murs sont engendrés de telle manière qu'il existe toujours un chemin entre 2
cases quelconques du labyrinthe. La jonction de 2 pans de murs est interdite car elle
sépare le labyrinthe en 2 régions distinctes.
Exercice 1:
Appliquer un des deux algorithmes, au choix, pour construire un labyrinthe sur une feuille
de papier (à l'aide d'un dé, d'un crayon et d'une gomme).
Exercice 2:
Réfléchir comment représenter un labyrinthe à l'aide d'un tableau ou de plusieurs
tableaux à deux dimensions. Il y a les murs et les cases à représenter.
7. Le jeu de Nim
Principe: Il y a 3 rangées de
jetons. On prend à tour de rôle autant de jetons qu'on veut mais tous de la même
rangée. Celui qui prend le dernier jeton est le vainqueur.
Stratégie gagnante: Si la situation
avant de jouer n'est pas perdante, il n'y a une façon de la rendre perdante. Il suffit de
prendre des jetons dans une rangée de telle manière que la position du jeu laissée soit
perdante. Pour cela on étudie la parité de la décomposition en système binaire du
nombre de jetons de chaque rangée. Exemple avec 3 piles de 2, 13 et 4 jetons:
Nombre de jetons
Colonnes des 8
Colonnes des 4
Colonnes des 2
Colonnes des 1
Pile 1
2
0
0
1
0
Pile 2
13
1
1
0
1
Pile 3
4
0
1
0
0
Parités
TRUE
FALSE
TRUE
TRUE
Une position est perdante lorsque les parités sont toutes paires (FALSE).
Résolution possible :
Essayer d'enlever 1 jeton, puis 2, puis 3, etc tour à tour dans chaque rangée afin de trouver
une solution perdante à laisser à l'adversaire. Il y a au plus autant d'essais à faire
que de jetons au total. (Cette démarche est facile pour une machine et moins pour une
personne).
Autre démarche :
Rechercher la première colonne impaire en commençant par celle des 8, puis des 4,
puis des 2, puis des 1;
Rechercher pour cette colonne la première pile avec un 1;
À partir de cette colonne et jusqu'à la colonne des 1, ajouter ou retrancher des 1
de façon à rendre toutes les parités paires (FALSE).
Dans l'exemple : la première
colonne est celle des 8 et la première pile avec un 1 est la pile 2. Le 1 de la colonne
des 8 est enlevé (-8 jetons), un 1 est ajouté dans la colonne des 2 (+2 jetons) et le 1
de la colonne des 1 est enlevé (-1 jeton).
Au total on enlèvera 7 jetons (+8-2+1) de la pile 2 :
Nombre de jetons
Colonnes des 8
Colonnes des 4
Colonnes des 2
Colonnes des 1
Pile 1
2
0
0
1
0
Pile 2
13 - 7 = 6
0
1
1
0
Pile 3
4
0
1
0
0
Parités
FALSE
FALSE
FALSE
FALSE
Une fois que le problème est dégrossi, il primordial de décomposer la suite d'actions à entreprendre.
Exemple pour le jeu de NIM :
Afficher la règle du jeu
REPETER
Tirage aléatoire des jetons
REPETER
Affichage des jetons
Prise en compte du coup de l'utilisateur
SI ( Fin de partie ) Alors
Félicitations
SINON
Affichage des jetons
Calcul du coup de l'ordinateur
Si NON( Fin de partie) Affichage des jetons
Fin SI
Fin REPETER si fin de partie
Fin REPETER si pas de partie suivante
Cette décomposition donne la forme
du programme et fait apparaître les actions de bases (exemples: affichage des jetons,
calcul du coup de l'ordinateur, test fin de partie, etc). Isoler ces actions en procédure
ou fonction permet de gagner du temps à l'écriture et surtout à la mise au point. En
effet chaque procédure sera testée sans attendre la fin complète du programme. Exemple
de démarche:
Tirage aléatoire des jetons
Affichage des jetons
Afficher résultat du Test Fin de partie
De même que le programme s'appuie
sur des actions fiables pré programmées et enregistrées sous formes de procédures ou
fonctions dans une bibliothèque, le programme se constitue sa propre boite à outils.
Constituer sa propre bibliothèque
de procédures et les collectionner pour les réutiliser sans avoir à les réinventer
c'est programmer avec un langage encore plus évolué que le langage de départ.
Nommer ses procédures
judicieusement permet d'être plus précis et plus efficace dans la décomposition du
problème. Décrire le mode d'emploi de ses procédures est nécessaire et permet de
s'assurer de la validité du choix des paramètres passés en arguments. En effet une
procédure se doit avant tout d'être réutilisable, les arguments en entrée et en sortie
doivent être décrits, ainsi les variables globales utilisées.
Une fois les actions de base
définies, écrites, documentées et testées, il y a toujours 1 ou 2 procédures plus
compliquées à écrire pour résoudre les sous problèmes particuliers du problème de
départ. En général, il s'agit de passer en revue des données numérotées (tableaux)
ou non (listes).
Exemple d'itération pour le jeu de NIM:
REPETER pour la rangée 1 à la rangée 3
REPETER pour 1 jeton au maximum de jetons
Retirer les jetons à la rangée
Si position perdante: enregistrer numéro de rangée et nombre de jetons
Remettre les jetons à la rangée
Fin REPETER jeton
Fin REPETER rangée
On remarque ici que toutes les
combinaisons sont passées en revue et seule la dernière position perdante trouvée
(supposée existante) est mémorisée. Suivant les langages utilisés, il est possible de
sortir d'une boucle prématurément (break en langage C; exit en Turbo-pascal si la boucle
a été mise dans une procédure).
L'itération se prête bien au
passage en revue d'éléments rangés en tableaux. La répétition conditionnelle peut
aussi être utilisée et peut permettre de prendre un compte un double test d'arrêt
(position perdante trouvée ou fin de recherche).
Exemple de boucle conditionnelle pour le jeu de NIM:
Numéro de rangée = 1
Nombre de jetons = 0
REPETER
Si Nombre de jetons < Nombre Max
Alors
Prendre un jeton de plus
Sinon
Passer à la rangée suivante
Mettre nombre de jeton à 1
Fin Si
Tester Numéro de rangée et
Tester si position perdante
Fin REPETER Si Numéro de rangée
> Nombre de rangées ou Si Position perdante trouvée
ANNEXE: EXEMPLE DE
DESCRIPTION DU PROGRAMME NIM
Description : Jeu
de logique contre l'ordinateur. Il y a 3 rangées de jetons. On prend à tour de rôle
autant de jetons qu'on veut mais tous de la même rangée. Celui qui prend le dernier
jeton est le vainqueur.
Déroulement : Les
3 rangées de jetons sont affichées à l'écran. L'utilisateur commence le premier. Il
indique le numéro de rangée puis le nombre de jetons à retirer. Les rangées sont
ensuite de nouveau affichées avec les jetons restant. C'est au tour de l'ordinateur de
jouer. Celui-ci annonce le numéro de rangée et le nombre de jetons qu'il supprime. Le
joueur appuie sur la touche ENTREE pour signaler qu'il a lu le coup de l'ordinateur. Les
rangées sont remises à jour. C'est ensuite au tour de l'utilisateur.
Algorithme :
Comment doit jouer l'ordinateur pour gagner ? Le principe est simple à mettre en oeuvre.
Si la situation avant de jouer n'est pas perdante, il n'y a qu'une façon de la rendre
perdante. Il suffit de prendre des jetons dans une rangée de telle manière que la
position du jeu laissée soit perdante. Pour cela on étudie la parité de la
décomposition en système binaire du nombre de jetons de chaque rangée. Exemple avec 3
piles de 2, 13 et 4 jetons:
Nombre de jetons
Colonnes des 8
Colonnes des 4
Colonnes des 2
Colonnes des 1
Pile 1
2
0
0
1
0
Pile 2
13
1
1
0
1
Pile 3
4
0
1
0
0
Parités
TRUE
FALSE
TRUE
TRUE
Si la parité est partout paire (FALSE), la situation est perdante
et l'ordinateur joue au hasard. Sinon :
il recherche la 1ère colonne
impaire en commençant par celle des 8, puis des 4, puis des 2, puis des 1.
puis il recherche pour celle-ci la première pile avec un 1.
à partir de cette colonne et
jusqu'à la colonne des 1, il ajoute ou retranche des 1 de façon à rendre toutes les
parités paires (FALSE).
Dans l'exemple : la première
colonne impaire est celle des 8. La première pile avec un 1 est la 2. Le 1 de la colonne
des 8 est enlevé, un 1 est ajouté dans la colonne des 2 et le 1 de la colonne des 1 est
enlevé.
On enlèvera 7 jetons de la pile 2:
Nombre de jetons
Colonnes des 8
Colonnes des 4
Colonnes des 2
Colonnes des 1
Pile 1
2
0
0
1
0
Pile 2
13 - 7 = 6
0
1
1
0
Pile 3
4
0
1
0
0
Parités
FALSE
FALSE
FALSE
FALSE
Décomposition du programme : Les variables principales sont les nombres de jetons par pile.
Il n'y a pas de structure de données particulière. Le programme principal se décompose
en plusieurs appels de procédures :
Répéter
GrOPEN : initialisation de l'affichage graphique
INITNIM: tirage aléatoire du nombre de jetons par pile entre 6 et 15
(nombre strictement inférieur à 16)
Répéter
DISPLAY : (ré-)affichage des rangées de jetons
USERMOVE : prise en compte du coup de l'utilisateur
Si partie finie (GAMEOVER) alors
félicitation!
Sinon :
DISPLAY : ré-affichage des jetons
ORDIMOVE : l'ordinateur joue, si partie
finie: il a gagné!