Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : Algorithmes et structures de données - introduction et Pascal Libre
(Article écrit par Chorizo Kid et extrait d'A-News (Amiga News) - mai 1989)
|
|
De retour d'un congrès sur la pensée freudienne dans le 68030, je trouvais dans ma boîte aux lettres une lettre d'un
certain Yves Remord, habitant de Jarnac (Charentes) pays du Cognac et des MouetPièts ; celui-ci demandait "... je cherche
un algorithme pour calculer simplement les racines carrées. A ce propos, pourquoi vous, A-News, qui avez un visionnaire
dans l'équipe, n'avez pas encore fait une rubrique sur les bases et théories de la programmation...".
Bonne question notais-je, mais le visionnaire s'en était allé ! Alors c'est ce bon vieux Chorizo, grand mamamouchi shooté au
bifidus actif, dernier détenteur du flambeau des initiations que même les Bogdanoff ne voudraient pas (Bruce Lepper : bon, on va commencer
l'article un jour ?), qui s'y colle.
Je vais donc essayer de vous parler d'ASD, c'est-à-dire "d'algorithmes et structures de données".
ASD, introduction
Frédéric Autechaud qui est à côté de moi en train de colorier l'annuaire du Finistère me demande à quoi ça sert l'ASD ? Et bien, grosso merdo,
on va avoir des causeries sur les piles, les files, les arbres, les tris, les listes chaînées et tout ce genre de choses,
indispensables dès que vous voulez faire un programme digne de ce nom.
Je commence l'introduction. Tout d'abord, qu'est-ce qu'un algorithme ? Formellement, c'est une suite ordonnée d'opérations pour
passer de données à un résultat !
Un petit exemple pour détendre l'atmosphère : un algo simple pour calculer les racines carrées (pour les carrés non parfaits
il faudra faire un encadrement de la valeur cherchée). Or, donc on a comme données "carré" dont on cherche la racine carrée, "racine"
qui va contenir la racine cherchée, "impair" qui est une variable qui va contenir les nombres impairs successifs (1 puis 3, 5, 7...)
et enfin "test" qui va contenir la somme des nombres impairs (1 au premier tour de boucle, puis 1+3, puis 1+3+5, 1+3+5+7...).
L'algo :
Exemple, je cherche la racine de 16 :
Bon, c'est un exemple avec un petit nombre, et en plus c'est un algo simple donc pas vraiment efficace, on en verra des
hachement plus mieux.
Vous avez vu que l'algo est écrit dans un langage bizarre. C'est du Pascal Libre qui est par convention le langage d'écriture
d'algorithmes. Don't worry, ça ne va pas vous faire un langage de plus à ingurgiter ; certes le Pascal Libre
provient directement du Pascal, mais d'une part il est en français donc facilement lisible et compréhensible, d'autre part
on utilisera presque toujours des axiomes simples pour décrire l'algorithme, on sera donc très près d'un langage tel que le
C. Et puis A-News c'est comme les recettes légères de Marie, ce n'est pas parce que le journal il est tout prêt (quoique des fois !)
que vous n'avez rien à faire.
Ce que vous devez savoir du Pascal Libre
Nous avons des constantes : ce sont des nombres ou des caractères (yagut:=69;assis:="bonanga";).
Il y a aussi des variables définies par leur nom, leur type et leur valeur.
Un type est un ensemble de valeurs possibles pour la variable (entier, réel, caractère).
Une variable peut être indicée, ce sera alors un tableau : à une dimension on aura un vecteur (V[i]),
à deux dimensions on aura une matrice (M[i][j]). Une matrice, c'est comme à la bataille navale, c'est un tableau repéré
par des lignes et des colonnes, A2 coulé (ligne A, colonne 2).
Une expression arithmétique est tout simplement un calcul du style (A+3)*B.
Une expression booléenne c'est rien qu'avec des Vrais et des Faux du genre (A ou B) (A est vrai ou B est vrai),
(A et R) (A est vrai et B est vrai), (A ou (B=C)) (A est vrai ou B est égal à C).
L'affectation est notée := (Blurb:=666; par exemple ou positif := (A>=0) qui signifie que la variable booléenne
positif sera à vrai si A est supérieur à 0, à faux sinon).
Une instruction est une instruction (LIRE(X); ECRIRE(X); fonctions de lecture et d'écriture de la variable X).
Les structures de contrôle : il y en a de trois types :
- si alors sinon : c'est la boucle classique de tous les langages avec la syntaxe si P alors S1 sinon S2, où P est
un prédicat, et S1 et S2 des suites d'instructions.
- Boucle tant que P faire S : le test de sortie de la boucle est ici en tête. Exemple : division entière de "x" par "y"
par soustractions successives;
debut
q:=0
r:=x
tant que r>=y faire
debut
r:=r-y
q:=q+1
fin
fin
Voilà. Le résultat sera à la fin dans "q", le reste de la division dans "r". Essayez en faisant tourner à la main. Les
debut-fin délimitent des blocs (équivalents aux {...} en C).
Un cas particulier de la boucle tant que est la boucle pour.
I:=1
tant que I<=N faire
debut
S
I:=I+1
fin
...s'écrira plus simplement :
pour I=1 a N faire S
- Boucle repeter S jusqu'a P : dans cette boucle le test de sortie est à la fin, donc la suite d'instructions S
sera exécutée au moins une fois. Exemple : la multiplication de "x" par "y" (le résultat est dans "z");
z:=0
u:=y
repeter
z:=z+x
u:=u-1
jusqu'a u=0
Là aussi c'est mulet, mais c'est des exemples de base.
Voilà donc ce que l'on pouvait dire sur le Pascal Libre. On va d'ailleurs s'arrêter là pour la première. La prochaine fois
on fera risette essentiellement avec les tableaux, donc il y aura plus d'exemples, plus d'action, plus de cascades, plus de sexe.
|
