Programmation LDA

Le but de ce cours est d'étudier comment on peut résoudre un problème en utilisant le Langage de Description des Algorithmes suivant l'approche Bertini et Tallineau. Il va donc falloir étudier les principes fondamentaux de la programmation, base valable quel que soit le langage utilisé.

Pour pouvoir résoudre un problème et transposer la solution sur ordinateur, il est nécessaire de passer par différentes étapes. Dans un premier temps, il va falloir effectuer une analyse du problème. Lorsque cette analyse est terminée, il faut l'adapter à l'ordinateur en traduisant l'analyse en une suite d'actions plus ou moins élémentaires.

L'algorithme

Un algorithme est un ensemble de règles opératoires propres à un calcul ou l'enchaînement des actions nécessaires à l'accomplissement d'une tâche. Un algorithme est un procédé reprenant un ensemble de suites élémentaires d'actions à exécuter afin de résoudre un problème à partir des données de départ et d'arriver à un résultat final déterminé. L'algorithme est indépendant des langages de programmation : si vous prenez une méthode de tri d'un tableau, par exemple le tri bulle, vous pouvez l'écrire dans la plupart des langages de programmation usuels. L'algorithmique va donc s'attacher à l'étude de différentes méthodes permettant de résoudre un problème donné sans tenir compte des particularités de tel ou tel langage de programmation. À ce titre l'algorithmique se veut universelle.
Le schéma usuel de résolution d'un problème sera donc :
Problème à résoudre (Données à traiter) --> Algorithme --> Implémentation dans un langage de programmation ->Résultat final
Il est possible de décrire un algorithme de différente manière :

• Représentation grâce aux arbres programmatiques.
• LDA : Langage descriptif des algorithmes.

Il n'existe pas hélas de langages de description des algorithmes universellement reconnus. Nous proposerons ici une syntaxe particulière, qui ressemble aux langages algorithmiques usuellement utilisés.

Analyse du problème

Avant de résoudre un problème, il faut l'analyser avec précision. Cette réflexion passe par certaines étapes incontournables :

• Définition du problème :
  

On ne peut pas résoudre un problème si on ne l'a pas défini précisément ! Il faut donc fixer le plus clairement possible les différentes fonctionnalités du programme.

• Spécification des résultats :

Il faut définir les différentes étapes de notre programme depuis la saisie des données jusqu'à l'affichage du résultat. On peut définir un prototype qui décrira point par point comment doit fonctionner notre programme.

• Définition des données de base :
  

Avant de résoudre le problème, il faut définir la nature des différentes données que manipulera notre programme.

• Analyses des données :
  

Il faut définir ici quelles sont les données au point de départ et quelles données doivent être sauvegardées.

• Recherche d'une solution :
  

C'est la phase technique où il faut proposer une méthode pratique permettant de résoudre notre problème.

Les arbres programmatiques (AP)

Cette méthode permet de représenter en arbre structuré les différents algorithmes du programme. Le programme (racine de l'arbre) peut se décomposer en sous-programmes (sous niveaux) toujours organisés en deux parties:

• Les Déclarations (variables et constantes - DONNEES)
• Les Instructions (traitements sur les données - OPERATIONS)

Les AP structurent le programme qui comprend :

• Variables
• Tests
• Répétitives

Le test fait l'objet d'un nœud en fonction d'une condition booléenne (True/False).

• La structure permet de distribuer le travail.

Struct=#Noeud+#Racine

• Le traitement comprends les instructions.

Traitements=#Feuilles

D- : Début // F- : Fin // T : Traitement // I : Instruction intermédiaire

Au niveau 0, le programme (prg) est ici initialisé de droite à gauche entre les blocs de début (D-Prog) et de fin (F-Prog) et se hiérarchise en sous prg et itérations en descendant dans les niveaux (couches). AP définit la structure logique du programme et l'ordre d’exécution des traitements. On instruit les feuilles de haut en bas (Niveau 0 -> ...) et de droite à gauche.

On a donc :

• STRUCTURE

Prog

T1

T4

T5

T7

• TRAITEMENT:

D-T1

D-T5

D-T7

T9

F-T7

T8

F-T5

F-T1

T2

I1

T3

D-T4

T6

F-T4

F-Prog

LES DECLARATIONS

Tout algorithme comprend deux parties :

• une partie déclaration
• une partie instruction

Bloc
 - declaration
 - instruction
FBloc

Un algorithme va utiliser des variables. Une variable peut être vue comme une zone mémoire réservée permettant de stocker une valeur. Toute variable utilisé dans la partie « instruction » de l'algorithme doit faire l'objet d'une déclaration préalable. La phase de déclaration doit s'accompagner d'une réflexion sur les données manipulées par notre algorithme. Quelle sera leur nature précise ? Leur valeur sera-t-elle variable ? Loin d'être une contrainte, la phase de déclaration est une aide pour guider le programmeur dans sa réflexion.

Les constantes

Une constante permet d'attribuer un nom à une valeur ou une expression fixe relativement complexe à retranscrire ou relativement longue. Elle permet également une meilleure lisibilité du code.

La déclaration d'une constante permet une modification simplifiée d'une valeur reprise à maintes reprises au sein du code. L'utilisation des constantes permettra d'améliorer la lisibilité de notre algorithme et sa généralisation.

Déclaration des constantes

Pour déclarer une constante on utilise le mot réservé CONST. La syntaxe générale de cette déclaration se présente sous la forme :

CONST identificateur = valeur

CONST pi = 3.14
CONST ttl = "Message à afficher régulièrement"
CONST oui=Vrai
CONST résu=pi*2+5*(15+4)

Pour des raisons de facilté il est préférable d'utiliser des noms de constantes plus ou moins courts et représentatifs de leur contenu.

Il est possible d'utiliser des déclarations multiples.

CONST pi=3.14
      ttl="Message à afficher"
      oui=Vrai
      résu=pi*2+5*(5+4)

Les variables

Une variable est une zone réservée de la mémoire permettant de stocker une valeur. Pour atteindre cette zone mémoire on lui attribue un nom. La valeur ainsi stockée par la variable pourra être modifiée au cours de l’exécution du code. Pour pouvoir réserver la place nécessaire à la valeur, il va falloir déclarer le type du contenu et éventuellement sa taille.

Déclaration

Pour déclarer une variable on utilise le mot réservé de VAR. La syntaxe générale de cette déclaration se présente sous la forme.

VAR identificateur : type

Identificateur représente le nom que l'on attribue à la variable.

Type permet de spécifier l'ensemble des valeurs dans lequel la valeur de la variable pourra varier. Il permet également de déterminer la dimension de la zone mémoire à réserver et le type d'opérations que pourra supporter la valeur.

On peut classer les différents types en catégories. Ainsi on parle de type primitif, il s'agit d'un type qui existe de fait avec le langage de programmation, il est défini en même temps que le langage. On parle également de type scalaire, il s'agit d'un type qui possède un précédent (hormis la première valeur qui est la plus petite et un suivant hormis la dernière valeur qui est la plus grande) et est représentée ou codée par un entier dans la machine.

Ascii (à chaque char correspond une valeur numérique)
 A=65
 B=66
 ...
 a=97
 b=98
 13->Numérique (1 bit) 
 13->Alphanumérique (2 bits) |1|3| = 49 & 51
 2^16=65536 -> 2 bytes = word
 4 byte=2^32+-4.10^9 -> double word
 8 bytes=2^64
 variable=zone mémoire allouée

Les types de variables

On dispose de quatre types primitifs, tous ordonnés mais dont 3 sont scalaires et 1 non.

• Scalaire : on trouve suivant ou précédant (ex. : 5, 6, 7...)
• Primitif : on trouve le plus petit ou le plus grand (ex. : 5,78 < 19,72)

• ENTIER (scalaire - primitif) // Var Max : Entier
• REEL (non scalaire - primitif) // Var Point : Reel
• CARACTERE (scalaire - primitif) // Var Initiale : Caractère
• BOOLEEN (scalaire - primitif) // Var Reussi : Booléen
• ALPHANUMERIQUE (chaine de ¢) // Var Message : Alphanumérique

Premières notions

• La lecture

La lecture d'une variable permet à l'utilisateur de saisir une valeur et de la stocker dans une variable.

Var Age : Entier
Entrer Age

Dans cet exemple, l'utilisateur tapera sur le clavier la valeur d'un entier et cette valeur sera stockée dans la variable Age.

• L'écriture

L'écriture permet d'afficher un message à l'écran à destination de l'utilisateur de l'algorithme.

Ecrire "Texte à afficher"
Ecrire Nom," ",Prenom," ",Age

• L'affectation

L'affectation permet d'effectuer un calcul et de stocker le résultat de ce calcul dans une variable.

Syntaxe :

identificateur <- expression 

Sémantique :
On commence par évaluer l'expression et on stocke le résultat dans la variable.

Exemple :

Var Valeur : Entier
Valeur<-15
Valeur<-19
Valeur<-Valeur*3
Valeur=19*3
Ecrire Valeur

Exécution de l'algorithme :
Notre programme affiche :
57

• La concaténation

Voyelle<-'a'
Phrase<-"Voici une voyelle:"
Phrase<-Phrase+Voyelle
Ecrire Phrase
>Voici une voyelle:a

• Les commentaires

Les commentaires sont des explications destinées à un programmeur qui lit l'algorithme et lui permettent de mieux le comprendre. Un commentaire n’est pas exécuté au cours de l'exécution d’un algorithme.

!Texte du commentaire!

OPERATEURS

• Mathématiques

^ puissance

* multiplication

/ division entière

mod modulo

• Relationnels (booléens)

= < > <= >= <>

• Logiques

non et ou

exercices

? Calculez le prix à payer en fonction de la quantité et du prix unitaire sachant que le taux de TVA est de 19 %

:: solution ::

Anal:

Introduire les QT

Introduire le Prix unitaire

Calculer le prix

Afficher le résultat

Algo:

BLOC
 ! DECLARATION !
 const tva=0.19
 var qt, pu : reel
 ! INSTRUCTION !
 ecrire "quantité désirée ?"
 entrer qt
 ecrire "prix unitaire ?"
 entrer pu
 ecrire "total à payer : ", pu*qt*(1+tva)
FBLOC

? Calculer surface et volume d'une sphère dont le rayon est introduit par l'utilisateur

:: solution ::

Anal:

introduire rayon

calc surf et vol

afficher

Algo:

BLOC
 const pi=3.1415
 var rayon : reel
 ecrire "entrer rayon ?"
 entrer rayon
 ecrire "surface :",4*pi*rayon^2
 ecrire "volume :",4/3.0*pi*rayon^3 !4/3.0 <- .0 pour sortie du reel!
FBLOC

? Calculer le laps de temps en seconde écoulé entre deux horaires exprimés en heure, en minute et en seconde

:: solution ::

Anal:

intro de deux horaire

conversion en secondes

calc de dif

sortie res

Algo:

BLOC
 const t1=3600
       t2=60
 var h1,m1,s1,h2,m2,s2 : entier
 ecrire "entrer h1"
 entrer h1,m1,s1
 ecrire "entrer h2"
 entrer h2,m2,s2
 s1<-s1+m1*t2+h1*t1
 s2<-s2+m2*t2+h2*t1
 ecrire "laps : ",s2-s1
FBLOC

? Introduire deux nombres et les permuter

:: solution ::

Anal:

intro nbr

permute

sortie res

Algo:

BLOC
 var n1,n2,n3 : reel
 ecrire "les nombres ?"
 entrer n1,n2
 n3<-n2
 n2<-n1
 n1<-n3
 ecrire "apres permute :",n1," ",n2
FBLOC

? Introduire 3 nombres et afficher la somme, la différence et le produit

:: solution ::

Anal:

input

calc

Algo:

BLOC
 var n1,n2,n3 : entier
 ecrire "n1 n2 n3 ?"
 entrer n1,n2,n3
 ecrire "somme de ",n1," et ",n2," et ",n3," = ", n1+n2+n3
 ecrire "diffe de ",n1," et ",n2," et ",n3," = ", n1-n2-n3
 ecrire "multi de ",n1," et ",n2," et ",n3," = ", n1*n2*n3
FBLOC

? Introduire une somme en franc belge et la convertir en euro

:: solution ::

Anal:

intro montant

calc

sortie

Algo:

BLOC
 const eur=40.3399
 var montant : reel
 ecrire "montant fb ?"
 entrer montant
 ecrire "conversion", montant/eur
FBLOC

? Calculer le déterminant d'une équation du second degré

:: solution ::

Anal:

intro des coefficients a,b,c

calc

sortie

Algo:

BLOC
 var a,b,c : entier
 ecrire "intro a,b,c ?"
 entrer a,b,c
 ecrire "discriminant (?)",b^2-4*a*c
FBLOC

? Introduire une valeur représentant des secondes et les convertir en heure, minutes, secondes

:: solution ::

Anal:

intro

conversion

sortie

Algo:

BLOC
 var d1 : entier
 ecrire "nbr sec ?"
 entrer d1
 ecrire d1," sec ",d1/3600,"h",(d1/3600)/60,"m",d1 mod 60,"s"
FBLOC

? On désire établir un prg permettant de calculer le nombre de rouleaux de papier peint nécessaire pour tapisser une pièce. Les dimensions d'un rouleau sont de 10m sur 95cm, sachant qu'une porte mesure 2m5 sur 80cm et qu'une fenêtre mesure 1m40 sur 1m. Sachant qu'on estime à 5% les chutes non réutilisables. Etablissez le programme permettant à l'utilisateur d'introduire les dimensions ainsi que le nombre de portes et fenêtres

:: solution ::

Anal:

intro nbr de portes et fen

intro hauteur, longueur, largeur

calc de surface tapissable

calc nbr rouleaux

sortie res

Algo:

BLOC
 const fen=140*100
 const por=250*80
 const rou=(1000*95)*0.95
 var ha,lo,la : reel
 var np,nf : entier
 ecrire "nbr de portes et fen"
 entrer np,nf
 ecrire "dimensions ha,lo,la ?"
 entrer ha,lo,la
 ecrire "nbr de rouleaux",(2*ha*(la+lo)-np*por-nf*fen)/rou
FBLOC

LES STRUCTURES DE CONTROLE

Séquence = suite ordonnée d'instructions (nœud ou feuille)

Alternative

Si condition Alors
 -sequence
Sinon
 -sequence
Fsi

• Plusieurs branches

Selon que
 condition 1 Faire
  -sequence
 condition 2 Faire
  -sequence
 consition 3 Faire
  -sequence
 autrement Faire
  -sequence
FSelon

On test le contenu d'une variable et en fonction de ses valeurs, dès qu'une condition est réalisée on quitte l'alternative.

exercices

? Introduire 2 nombres et les afficher dans l'ordre croissant

:: solution ::

Anal:

intro a,b

si a<b afficher a et b sinon afficher b et a

Algo:

 BLOC
  var n1,n2 : entier
  ecrire "n1,n2 ?"
  entrer n1,n2
  ecrire "par ordre croissant"
  si n1<n2 alors
   ecrire n1," ",n2
  sinon
   ecrire n2," ",n1
  fsi
 FBLOC

? Introduire deux horaires en H/M/S et afficher dans l'ordre croissant

:: solution ::

 BLOC
  var h1,h2,m1,m2,s1,s2 : entier
  ecrire "intro horaire 1 et 2 (h,m,s)"
  entrer h1,m1,s1
  entrer h2,m2,s2
  si h1>h2 ou ((h1=h2)et(m1>m2)ou((h1>h2)et(m1=m2)et(s1>s2)) Alors
   ecrire h2,m2,s2," ",h1,m1,s1
  sinon
   ecrire h1,m1,s1," ",h2,m2,s2
  fsi
 FBLOC

? Introduire la date de naissance d'une personne et date actuelle et sortir son age

:: solution ::

 BLOC
  var jn,mn,an,ja,ma,aa : entier
      age
  ecrire "date naissance (jn/mn/an) ?"
  entrer jn,mn,an
  ecrire "date actu (ja/ma/aa) ?"
  entrer ja,ma,aa
  age<-aa-an
  si (mn>ma) ou ((mn = ma) et (jn>ja)) Alors
   age<-age-1
  fsi
  ecrire "vous avez ",age
  si age >1 Alors
   ecrire "ans"
  sinon
   ecrire "an"
  fsi
 FBLOC

? En fonction d'un resultat introduit afficher la mention obtenue</>

:: solution ::

 BLOC
  var resu : entier
  ecrire "quel est le resultat ?"
  entrer resu
  selon que
   resu < 50 faire
    ecrire "mention Echec"
   resu < 60 faire
    ecrire "mention Fruit"
   resu < 70 faire
    ecrire "mention Satisfaction"
   resu < 80 faire
    ecrire "mention Distinction"
   resu < 90 faire
    ecrire "mention Grande distinction"
   resu <= 100 faire
    ecrire "resultat erroné"
  Fselon
 FBLOC

? On demande d'introduire 2 nombres entiers ainsi qu'un opérateur (+,-,*,/,^,m). Afficher le résultat

:: solution ::

 BLOC
  var a,b : entier
      op : caractere
  ecrire "intro deux entiers"
  entrer &,b
  ecrire "quel est l'operateur (+ - * / m)
  entrer op
  selon que
   op = '+' faire
    ecrire a,"+",b,"=",a+b
   op='-' faire
    ecrire a-b
   op='*' faire
    ecrire a*b
   op='m' ou op='/' faire
    si b=0 alors
     ecrire "impossible de diviser par 0"
    sinon
     si op='m' alors
      ecrire "le reste de la div de ",a," par ",b," = ",a mod b
     sinon
      ecrire a/b
     Fsi
    Fsi
   op='^' faire
    ecrire a^b
   autrement faire
    ecrire "operateur non valable"
  Fselon
 FBloc

Répétitive

• Tant que : tant que condition est vrai on entre dans la boucle

≡}Séquence D-TantQue
TantQue [Cond vraie] Faire
 ≡}traitement
FTant
≡}Séquence F-TantQue

ex:

Entrer b
Tantque b=0 Faire
 Ecrire "erreur"
 Entrer b
Ftant

• Jusque : jusque condition est vrai on entre dans la boucle

≡}Séquence D-Jusque
Jusque [Cond vraie] Faire
 ≡}traitement
FTant
≡}Séquence F-Jusque

ex:

Entrer b
Jusque b=0 Faire
 Ecrire "erreur"
 Entrer b
FJusque

• Pour : De valeur initiale à valeur finale on entre dans la boucle

Pour [Var] De [val. init] A [val. fin] Pas [val] Faire
 ≡}traitement
FPour

Pas : 1 par défaut, est la valeur d’incrémentation - ex.: de 1 en 1 / de 5 en 5 - ex:

Pour x De 8 A 20 Pas 1 Faire
 Ecrire x
FPour

exercices

? Afficher table de multiplication de 8

:: solution ::

• Tantque:

 Bloc
  Const N=8
  Var a:entier
  a<-0
  Tantque a<=20 Faire
   Ecrire a*N
   a<-a+1
  FTant
 FBloc

• Jusque:

 Bloc
  Const N=8
  Var a:entier
  a<-0
  Jusque a>20 Faire
   Ecrire a*N
   a<-a+1
  FJusque
 FBloc

• Pour:

 Bloc
  Var a:entier
  Pour a DE 0 A 20 Faire
   Ecrire a*8
  FPour
 FBloc

? Calcul de somme, moyenne, min, max d'une série de nombres introduits au clavier. Valeur 0 indiquant la fin de la serie.

:: solution ::

 Bloc
  Var nb,cpt,somme,max,min:entier
  cpt<-0
  ecrire "veuillez entrer un nombre (0 pour stop)"
  entrer nb
  somme<-nb
  max<-nb
  min<-nb
  tantque nb<>0 faire
   cpt<-cpt+1
   ecrire "introduire le nbr suivant"
   entrer nb
   somme<-somme+nb
   si max<nb et nb<>0 Alors
    max<-nb
   fsi
   si min>nb et nb<>0 alors
    min<-nb
   fsi
  ftant
  si cpt<>0 alors
   ecrire "somme ", somme
   ecrire "moyenne ",somme*1.0/cpt
   ecrire "max ",max
   ecrire "min ",min
  sinon
   ecrire "pas de resultat à afficher"
  fsi
 FBloc

? Etablir un tableau reprenant la liste des nombres entre 1 et 20, leur exposant 2 et 3.

:: solution ::

 Bloc
  Var a:entier
  Pour a de 1 a 20 Faire
   ecrire a," ",a^2," ",a^3
  FPour
 FBloc

LES STRUCTURES COMPOSEES

Structures consecutives

• En LDA:

 !Double alternative!
 ≡} D-Trait
 Si c1 Alors
  ≡} T1
 Sinon
  ≡} T2
 FSi
 ≡}I-Trait !(Fin de 1er Si) et (Debut de 2e Si)!
 Si c2 Alors
  ≡} T3
 Sinon
  ≡} T4
 FSi
 ≡} F-Trait

 !Double repetitive!
 ≡} D-Trait
 Tantque c1 Faire
  ≡} T1
 FTant
 ≡} I-Trait
 Jusque c2 Faire
  ≡} T2
 FJusque
 ≡} F-Trait

 !Alternative suivant repetitive!
 ≡} D-Trait
 Jusque c1 Faire
  ≡} T1
 FJusque
 ≡}I-Trait
 Si c2 Alors
  ≡} T2
 Sinon
  ≡} T1
 FSi
 ≡} F-Trait

Structures imbriquées

• En LDA:

 ! Repetitive de repetitive !
 ≡} D-Trait
 Tantque c1 Faire
  ≡} D-T1
  Tantque c2 Faire
   ≡} T2
  FTant
  ≡} F-T1
 FTant
 ≡} F-Trait

 ! Repetitive d'alternative !
 ≡} D-Trait
 Si c1 Alors
  ≡} T1
 Sinon
  ≡} D-T2
  Tantque c2 Faire
   ≡} T3
  FTant
  ≡} F-T2
 FSi
 ≡} F-T

 ! Alternative de repetitive !
 ≡} D-Trait
 Tantque c1 Faire
  ≡} D-T1
  Si c2 Alors
   ≡} T2
  Sinon
   ≡} T3
  FSi
  ≡} F-T1
 FTant
 ≡} F-Trait

Structures multiples

• En LDA:

 ≡} D-Trait
 Tantque c1 Faire
  ≡} D-T1
  Si c3 Alors
   ≡} D-T4
   Tantque c5 Faire
    ≡} T7
   FTant
   ≡} F-T4
  Sinon
   ≡} T5
  FSi
  ≡} F-T1
 FTant
 ≡} I1
 Si c2 Alors
  ≡} T2
 Sinon
  ≡} D-T3
  Tantque c4 Faire
   ≡} D-T6
  FTant
  ≡} F-T3
 FSi
 ≡} F-Trait

exercices

? Additionner tous les nombres pairs entre 2 nombres introduits par l'utilisateur

:: solution ::

 BLOC
  Var nb1,nb2,somme,cpt:entier
  ecrire "input de 2 nombres"
  entrer nb1,nb2
  si nb1>nb2 alors
   somme<-nb1
   nb1<-nb2
   nb2<-somme
  fsi
  si nb1 mod 2 <> 0 alors
   nb1<-nb1+1
  fsi
  somme<-0
  pour cpt de nb1 a nb2 pas 2 faire
   somme<-somme+cpt
  fpour
  ecrire "somme ",somme
 FBLOC

LES TABLEAUX

Ensemble de valeurs

Unidimensionnel

Dans un VECTEUR de X : Type

Multidimensionnel

Dans une MATRICE de X * X : Type

Programme permettant de permuter les valeurs d'une matrice carrée de 10 selon sa diagonale principale

:: solution ::

Var cpt1, cpt2 : Entier
Perm : MATRICE de 10x10 Entier
Temp : Entier

Pour cpt1 de 2 à 10 Faire
  Pour Cpt2 de 1 à Cpt-1 Faire
    Tmp <- Perm (cpt1, cpt2)
    Perm(cpt1,cpt2) <- Perm(cpt2,cpt1)
    Perm(cpt2,cpt1) <- Temp
  FPour
FPour

LES SOUS-PROGRAMMES

Ensemble nommé d'instructions paramétrable et appelable.

Procédures

Sans sortie:

Proc nom1(param1 : Type, param2 : Type)
  ...
FProc

Fonctions

Avec sortie.

? faire une fonction qui retourne le carre d'un nombre

:: solution ::

Fonc carre(nombre : Entier) 
  carre <- nombre * nombre
FFonc

LA RECURSIVITE

La récursivité consiste en une procédure ou une fonction faisant appel à elle même.

exercices

? Ecrire une fonction récursive permettant de trouver la valeur d'un élément du triangle de pascal connaissant sa position

:: solution ::

Fonction Pascal(Col:Entier,lig:Entier) A valeur Entier

  Si Col = 1 ou Col = lig Alors
    Pasc<-1
  Sinon
    Pasc<-Pasc(Col,Lig-1)+Pasc(Col-1,Lig-1)
  FSi

FFonc

? Ecrire une procédure permettant de convertir une valeur décimale en une valeur binaire et une procédure convertissant une valeur décimale en une valeur hexadécimale

:: solution ::

Procedure Bin(V:Entier)

  Var Reste:Entier
  Si V<>0 Alors
    Reste <- V Mod 2
    Bin(V/2)
    Ecrire Reste
  FSi

FProc

Procedure Hex(V:Entier)

  Var Reste : Entier
      Ve : Vecteur 16 Chars
  Ve(1) <- '0'
  Ve(2) <- '1'   
  ...
  Ve(11) <- 'A'
  Ve(16) <- 'F'      

  Si V <> 0 Alors
    Reste <- V Mod 16
    Hex(V/16)
    Ecrire Ve(Reste + 1)
  FSi

FProc

LES TRIS

Réorganisation de données

• Par insertion
• A bulle
• Hybrides
• Par selection
• Par comptage

LES ENREGISTREMENTS

Un enregistrement permet de regrouper sous un identificateur commun des variables de types différents

? Faire une fiche personnelle

:: solution ::

VAR Identite : ENREGISTEMENT

  Nom : Alphanum
  Prenom : Alphanum
  DateN
    JJ : Entier
    MM : Entier
    AA : Entier
  FENREGISTREMENT
  Adresse : Alphanum
  CodePostal : Entier
  Commune : Alphanum

FENREGISTREMENT

LES POINTEURS

Les pointeurs sont des directeurs de gestion d'allocations.

Les listes à simple chaînage

Structure de données linéaires unidirectionnelles

Les listes à double chaînage

Structure de données linéaires bidirectionnelles

Les arbres binaires

Structures de données non linéaires

? Compter le nombre de feuilles et sommets d'un AB

:: solution ::

Type P Est Pointer Vers Enreg
     Enreg Est Enreg
     ...
     Gauche : P
     Droite : P
FEnreg

Fonction Feuille (A : Pointeur) A valeur Entier

  Var Actuel : P
  Gau, Dro : Pointeur
  Total : Entier

  Si A = Vide Alors
    Total <- 0
  Sinon
    Actuel <- A
    Si Pointee(Actuel).Gauche = vide ET Pointee(Actuel).Droite = vide Alors
      Total <- 1
    Sinon
      Gau <- Pointee(Actuel).Gauche
      Dro <- Pointee(Actuel).Droite
      Total <- Feuille(Gau)+Feuille(Dro)
    FSi
  FSi
  Feuille <- Total

FFonc

Fonction Noeud (A: pointer) A Valeur Entier

  Var Actuel : P
      Gau, Dro : Pointer
      Total : Entier
 
  Si A = Vide Alors
    Total <- 0
  Sinon
    Actuel <- A
    Si Pointee(Actuel).Gauche <> vide ou
       Pointee(Actuel).Droite <> vide Alors
      Gau <- Pointee(Actuel).Gauche
      Dro <- Pointee(Actuel).Droite
      Total <- 1 + Noeud(Gau)+Noeud(Dro)
    Sinon
      Total <- 0
    FSi
  FSi
  Noeud <- Total

FFonc
  

LES FICHIERS

Piles stockées

Sequentiels

Stockage de données

Acces Directs

Stockage d'enregistrements

Exercices

? Soit un FAD et un FS contenant des infos similaires on demande de créer un nouveau FAD fusionnant alternativement les enregistrements des 2 fichiers

:: solution ::

Proc Fusion

  Type Info Est Enregistrement
       Nom : Alphanumerique * 30
       Pseudo : Alphanum * 10
       Pwd : Alphanum * 10

  FEnreg

  Var F1, F3 : Fichier de Info       ! fichier acces direct !
      F2 : Fichier                   ! fichier sequentiel !
      Donnee : Info
      N, Pseudo, Pwd : Alphanum

  Ouvrir F1,F2,F3

  Jusque EOF(F1) ou FEO(F2) Faire
    Lire Donnee F1
    Ecrire donnee F3
    Lire N,Pseudo,Pwd F2
    Donnee.Nom <- N
    Donnee.Pseudo <- Pseudo
    Donnee.Pwd <- Pwd
    Ecrire Donnee F3
  FJusque

  Si EOF(F1) Alors
    Jusque EOF(F2) Faire
      Lire N, Pseudo, Pwd F2
      Donnee.Nom <- N
      ...
      Ecrire Donnee sur F3
    FJusque
  Sinon
    Jusque EOF(F1) Faire
      Lire Donnee F1
      Ecrire Donnee F3
    FJusque
  FSi

  Fermer F1, F2, F3

FProc

Liens externes

http://www.ac-nancy-metz.fr/eco-gestion/eric_crepin/accueil.htm

http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud//Teaching/Algo-DEUG-02/Cours/node1.html