Apprendre et enseigner l’algorithmique
Institut National d’Informatique
Introduction
Ce livre est le fruit d'une vingtaine d’années d’expérience dans le domaine de l'algorithmique et de la programmation. C'est le cours tel qu'il est assuré à l'Institut National d'Informatique d'Alger (Ex C.E.R.I) pour les étudiants de première année du cycle "ingénieur d'état en informatique".
Il constitue un support de cours pour des étudiants n'ayant aucune connaissance en programmation. Il est aussi destiné à des étudiants ayant déjà une première expérience en programmation et qui veulent connaître davantage sur l'art de la programmation.
Objectif du cours
Le cours couvre quatre grands aspects très liés : algorithmique, donnée, méthodologie et programmation. Dans une première étape, on s’intéresse essentiellement au formalisme algorithmique, ensemble de conventions permettant d'exprimer des solutions. On opère alors sur des objets simples et on développe des algorithmes sur la machine de Turing. Quant à la seconde étape, elle est totalement consacrée à l'étude des structures de données élémentaires à savoir les vecteurs, les listes linéaires et les fichiers . Un langage de programmation pédagogique est utilisé afin de s'initier à la programmation (PASCAL). Une méthode de recherche d'algorithmes, l'analyse descendante, est abordée avec tous les concepts qui s'y rattachent.
Contenu
La première partie renferme le cours d'algorithmique. Les concepts de base sont donnés en montrant la construction de programmes simples depuis leur expression en langage naturel avec ses inconvénients à leur expression entièrement dans un langage algorithmique. Une multitude d'algorithmes sont développés sur la machine de Turing afin de se familiariser avec le langage algorithmique. Une introduction aux fichiers et particulièrement aux structures de fichiers est donnée avec de nombreux programmes. On y trouvera essentiellement, les programmes de création, de maintenance et de tri de fichiers. Une méthode de conception d'algorithmes qu'est l'analyse descendante est exposée et illustrée en PASCAL en présentant tous les concepts qui s'y rattachent tels que la notion de portée, de communication entre modules, paramètres formels et réels, objet locaux et globaux, etc
La seconde partie fournit un recueil de sujets d'examens. Pour chaque sujet, il est spécifié l'ensemble des cours à connaître.
La partie 3 fournit des corrigés types des sujets présentés dans la partie 2.
La partie 4 présente un ensemble d'exercices de programmation corrigés. Pour chaque programme, nous avons présenté les données et les résultats parfois détaillés dans le but de montrer leur conformité.
La partie 5 présente une série d'annexes très utiles pour un environnement de programmation. L'annexe 1 résume le langage algorithmique utilisé. Les annexes 2 et 3 donnent des compléments d'informations sur quelques notions élémentaires et sur les disques. L'annexe 4 résume les principales fonctions DOS utiles pour toute utilisation de micro-ordinateur. Les annexes 5 et 6 fournissent des moyens, d'une part, pour représenter schématiquement des algorithmes (organigrammes) et, d'autre part, pour les traduire dans des langages de bas niveau ( langage d'assemblage par exemple). Dans l'annexe 7, on trouvera une façon de rédiger un dossier de programmation. Enfin, nous avons terminé par l'annexe 8 par un ensemble de conseils pratiques sous forme de proverbes utiles pour tout programmeur.
Remerciements
Nous exprimons nos remerciements les plus chaleureux à notre collègue W.K Hidouci pour ses conseils et surtout son efficacité dans la lecture approfondie de certaines parties de ce manuscrit.
Professeur Djamel Eddine
ZEGOUR
Organisation du livre
Tome1
Partie 1
. Cours d'algorithmique
Partie 2 : Annexes
1. Langage algorithmique
2. Notions élémentaires
3. Les Disques
4. Système d'exploitation MS-DOS : aide mémoire
5. Organigrammes
6. Traduction des algorithmes vers les langages de bas niveau
7. Rapport de programmation
8. Proverbes de programmation
Tome2
Partie 1 (Page 7)
. Enoncés de sujets d'examens
Partie 2 (Page 35)
. Corrigés de sujets d'examens
Partie 3(Page 111)
. Exercices programmés en PASCAL
Partie 4 : Annexes(Page 143)
1. Langage algorithmique
2. Rappel PASCAL
3. Proverbes de programmation
S O M M A I R E
I. Enoncés de sujets d'examens
C1. Concepts de base
C2. Concepts de base - Programmation PASCAL - Machine de Turing
C3. Concepts de base - Machine de Turing
C4. Concepts de base - Machine de Turing
C5. Machine de Turing - Programmation PASCAL
C6. Machine de Turing - Vecteurs - Programmation PASCAL
C7. Concepts de base
C8. Machine de Turing - Programmation modulaire - Programmation PASCAL
C9. Vecteurs - Fichiers - Programmation PASCAL
C10. Programmation modulaire - Vecteurs - Programmation PASCAL
C11. Machine de Turing - Vecteurs - Programmation PASCAL
C12. Machine de Turing - Vecteurs - Programmation PASCAL
C13. Listes linéaires chaînées - Programmation PASCAL
C14. Machine de Turing - Programmation PASCAL
C15. Vecteurs - Programmation PASCAL
C16. Listes linéaires chaînées - Vecteurs - Fichiers
C17. Machine de Turing - Programmation PASCAL
C18. Vecteurs - Machine de Turing
C19. Concepts de base - Machine de Turing
C20. Machine de Turing - Vecteurs
C21. Vecteurs
C22. Concepts de base
C23. Machine de Turing - Programmation modulaire - Programmation PASCAL
C24. Programmation modulaire - Vecteurs - Programmation PASCAL
C25. Vecteurs
C26. Machine de Turing - Vecteurs - Programmation PASCAL
C27. Machine de Turing - Programmation PASCAL
C28. Concepts de base - Vecteurs - Programmation PASCAL
C29. Machine de Turing
II. Corrigés de sujets d'examens
Corrigé 1 .
Corrigé 2 .
Corrigé 3 .
Corrigé 4 .
Corrigé 5 .
Corrigé 6 .
Corrigé 7 .
Corrigé 8 .
Corrigé 9 . Corrigé 10 ..
Corrigé 11 ..
Corrigé 12 ..
Corrigé 13 ..
Corrigé 14 ..
Corrigé 15 ..
Corrigé 16 ..
Corrigé 17 ..
Corrigé 18 ..
Corrigé 19 ..
Corrigé 20 ..
Corrigé 21 ..
Corrigé 22 ..
Corrigé 23 ..
Corrigé 24 ..
Corrigé 25 ..
Corrigé 26 ..
Corrigé 27 ..
Corrigé 28 .. Corrigé 29 ..
III. Exercices programmés en PASCAL
PROGRAMME 1. Réalisation d'un dessin
PROGRAMME 2. Etablissement d'une facture
PROGRAMME 3. Course de Ski ( I )
PROGRAMME 4. Les mots de la forme .XY
PROGRAMME 5. Les mots de la forme .X .Y .
PROGRAMME 6. Analyse des constantes "virgule flottante"
PROGRAMME 7. Recherche dichotomique dans un vecteur
PROGRAMME 8. Course de ski ( II )
PROGRAMME 9. Parties d'un ensemble PROGRAMME 10. Inventaire
IV. Annexes
Annexe 1. Langage algorithmique
Annexe 2. Rappel PASCAL Annexe 3. Proverbes de programmation
Partie 1
_________________________________________________________
Enoncés de sujets d’examens
_________________________________________________________
Exercice 1 : 2N
Ecrire deux algorithmes différents permettant de calculer 2N pour tout N >=0 donné a) d'abord en remarquant que 2N = 2 * 2 * . . * 2 ( N fois)
b) puis en remarquant que 2N = 2N-1 + 2N-1
Exercice 2 : Extremum
Soit une liste de K nombres ( K donné ). Ecrire l'algorithme qui permet de rechercher le maximum et le minimum. On suppose que chaque nombre est obtenu par un ordre de lecture.
Exercice 3 : F ?
Que fait l'algorithme suivant ? Justifier votre réponse.
ALGORITHME F
VAR
Res, N, I : ENTIER
DEBUT
Lire(N)
I := N
Res := 1
TANTQUE I > 1 :
Res := Res * I
I := I - 1
FINTANTQUE
Ecrire( N, res)
FIN
Exercice 4 : PGCD
On suppose que MOD( N, A) est une fonction qui détermine le reste de la division de l'entier N par A. ex : Mod( 12, 7) = 5
Si Reste est le nom d'un objet de type variable entière l'action " Reste := Mod(N,A)" permet d'affecter à la variable Reste le reste de la division de N par A.
Ceci étant, écrire l’algorithme permettant de déterminer le PGCD de deux nombres A et B donnés.
Exercice 5 : Calcul
Soit l'algorithme suivant :
ALGORITHME Calcul
VAR
E1, E2, E3 : ENTIER
R : REEL
DEBUT
E1 := 5 ; E2 := 8
E3 := E1 * E2
E3 :=(E1 * E2) / 3
R := (E1 * E2) / 3
E3 := ( E1 + E2) / 2
R := ( E1 + E2 ) / 2
FIN
Quelles sont les différentes valeurs que prennent E3 et R? Faire une trace.
* * * * *
Turing
1. Aspect algorithmique
A - Soit une liste de N entiers. Ecrire les algorithmes suivants :
a) - Calcul de la somme des nombres positifs et celle des nombres négatifs.
b) - Nombre des sous-suites décroissantes.
Exemple : si la liste est 7, 8, -1, 3, 5, -17, 15, -28 a) - somme des nombres positifs = 38 somme des nombres négatifs = -46
b) Les sous-suites décroissantes sont : {7}, {8, -1}, {3}, {5, -17}, {15, -28}
B- On dit que deux nombres x et y sont amis si et seulement si x2 + y2 est un carré parfait.
Ecrire l'algorithme qui recherche tous les nombres entiers amis compris entre 1 et 1000.
On n'utilisera pas l'opération "racine carrée".
Exemple : 3 et 4 sont amis car 32 + 42 = 52.
2. Aspect programmation
a) Traduire B en PASCAL.
b) Ecrire le programme qui réalise le dessin suivant :
*
* *
* 1 *
* 2 2 *
* 3 3 3 *
. .
* N N N . . *
* * * * . . * * *
pour un entier N donné. ( 1 <= N <= 20 )
* * * * *
Exercice 1 : Calcul de la somme 1 + 5 + 9 + . .
Ecrire l'algorithme qui réalise la somme
Sn = 1 + 5 + 9 + . . + (4N + 1) pour un entier N donné.
Exercice 2 : Calcul de 2N avec l'addition
On dispose d'une machine qui ne sait qu'additionner. Ecrire l'algorithme qui réalise 2N (N >=0).
Exercice 3 : Comptage du nombre de mots
Soit une suite de caractères terminée par un point('.'). On définit un mot comme étant une suite de caractères ne contenant pas de blanc. La longueur d'un mot est par conséquent le nombre de caractères qu'il contient. Ecrire un algorithme permettant de compter le nombre de mots de longueur L donnée.
NB. On suppose que chaque ordre de lecture délivre le prochain caractère.
* * * * *
Exercice 1 : Calcul de la somme 13 + 33 + 53 ..
Ecrire l'algorithme qui réalise la somme : Sn = 1 3 + 33 + 53 + . . + (2N+1)3 pour un entier N donné.
Exercice 2 : Division de deux entiers A et B avec l'opérateur '-'
On dispose d'une machine qui ne sait que soustraire. Ecrire l'algorithme qui fait la division de deux entiers A et B ( A >= B >= 0). On imprimera le reste et le quotient.
Exercice 3 : Longueur du mot le plus long
Soit une suite de caractères terminée par un point('.'). On définit un mot comme étant une suite de caractères ne contenant pas de blanc. La longueur d'un mot est par conséquent le nombre de caractères qu'il contient. Ecrire un algorithme qui détermine la longueur du mot le plus long. NB. On suppose que chaque ordre de lecture délivre le prochain caractère.
* * * * *
C5. Machine de Turing - Programmation PASCAL
1. Aspect algorithmique
Soit une liste de N entiers naturels ( N > 2).
Ecrire les algorithmes suivants :
a) Recherche du minimum et du maximum.
b) Recherche du premier nombre dont le carré est égal à la somme des deux précédents.
c) Recherche du nombre de sous-suites croissantes.
Exemple : si la liste est la suivante : { 7, 8, 1, 3, 5, 17, 15, 28, 3} a) maximum = 28 minimum = 2
b) c'est le nombre 3 car 32 = 1 + 8
c) les sous-suites sont {7, 8}, {1, 3, 5, 17}, {15, 28}, {3}. Le nombre de sous-suites est alors 4.
2. Aspect programmation
a) Traduire le dernier algorithme en PASCAL.
b) Ecrire le programme PASCAL qui réalise le dessin suivant :
* * * * . . * * *
* 1 1 1 . . 1 * *
* 1 1 * 0 *
* 1 1 * 0 0 * . . . . .
. . . . .
* * 0 0 0 *
* * * * * . . * *
N X N caractères.
* * * * *
Exercice 1 : Moyenne
Soit un vecteur contenant N mesures. Calculer leur moyenne et le nombre de mesures qui diffèrent de la moyenne de plus d'une quantité donnée.
1) Donner l'algorithme
2) Ecrire le programme PASCAL correspondant.
Exercice 2 : Reconnaissance de données arithmétiques
Dans le langage PL1, une donnée arithmétique DECIMAL FIXED (W, D) peut avoir l'une des deux formes suivantes :
chchch .ch
ou
chchch .ch
W est le nombre total de caractères, D est le nombre de chiffres après le point décimal.
Ecrire l'algorithme puis le programme PASCAL permettant de reconnaître N données arithmétiques DECIMAL FIXED (W, D) lues. Les données utilisées sont séparées par des blancs, des virgules ou une combinaison des deux.
Ce programme doit reconnaître ces données, les contrôler et les ranger ( sans conversion) dans un tableau en spécifiant leur précision.
Exemple :
Si on a : 123,,,143.5 ,12A3 1538.38 , , 342.56 AABCD 1,2,34 # on aura :
* * Constante erronée : 12A3
* * Constante erronée : AABCD
Premier élément :123 W=3 D=0
Deuxième élément :143.5 W=5 D=1
Troisième élément :1538.38 W=7 D=2
Remarques :
- Le programme doit signaler les erreurs éventuelles.
- l <= 15 et N <= 10
Exercice 3 : Tri par interclassement
On considère le vecteur initial à N éléments comme N sous-vecteurs triés à un élément. Un premier interclassement des sous-vecteurs deux à deux conduit à des sous-vecteurs triés de deux éléments. On recommence alors jusqu'à obtenir un seul vecteur trié. Si à une étape, on a un nombre impair de sous vecteurs, le dernier est reporté sans changement à l'étape suivante.
Exemple :
12 4 8 11 14 10 11 5 1 13
(4 12) (8 11) (10 14) (5 11) (1 13)
(4 8 11 12) (5 10 11 14) (1 13)
(4 5 8 10 11 11 12 14) (1 13)
(1 4 5 8 10 11 11 12 13 14)
Donner l'algorithme réalisant cette méthode de tri. On utilisera le module d'interclassement sans le développer.
* * * * *
Exercice 1 : Carré parfait
Ecrire un algorithme qui donne comme résultat la valeur :
- VRAI si N est un carré parfait
- FAUX sinon N étant une donnée.
nombre A est dit carré parfait s'il existe un entier B tel que B2=A. On n'utilisera pas l'opérateur de puissance.
Exercice 2 : Couples (A, B) tels que A = 3B
Imprimer tous les couples (A, B) d'entiers naturels compris entre 1 et 100 tels que A= 3 B.
Exercice 3 : Calcul de somme
Calculer la somme
S = 1 + 5 + 9 + + 4N+1 pour N >=0
Exercice 4 : Fibo ?
Soit l’algorithme suivant :
ALGORITHME FIBO
VAR Fb, Fb0, Fb1, K, N : ENTIER
Trouv : BOOLEEN
DEBUT
Lire(N)
Fb0 := 0
Fb1 := 1
Trouv := FAUX
K := 2
TANTQUE NON Trouv : Fb := Fb0 + Fb1 SI Fb > N :
K := K + 1
Trouv := VRAI
SINON
K := K + 1
Fb0 := Fb1
Fb1 := Fb
FSI
FINTANTQUE
Ecrire(K, Fb)
FIN
Questions :
1 Faire une trace complète pour N = 10.
2 Que fait-il ?
3 Peut on l'écrire de façon plus simplifié ?
* * * * *
Programmation PASCAL
Partie 1 : Machine-caractères
Considérons la machine-caractères abstraite définie en cours.
a) Ecrire l'algorithme qui recherche un mot donné dans le ruban de cette machine.
b) Ecrire l'algorithme qui imprime tous les mots commençant par 'T' et se terminant par
'S'.
Partie 2 : Les actions composées
a1) Ecrire l'algorithme qui calcule sans l’utilisation de l'opérateur '**' l'expression suivante :
((AB + CD ) / AD ) A
pour A,B, C et D donnés et non nuls.
a2) Le traduire en PASCAL.
b1) Ecrire ( ou définir en langage algorithmique ) les fonctions suivantes :
F(X) = X5 + X2 + 18
G(X) = X7 + X3 + X + 1
et le prédicat A = B
b2) Utiliser ces actions composées pour écrire l'algorithme qui donne les solutions de l’équation F(X) = G(X) pour X dans Z ( ensemble des entiers relatifs) et X dans [-1000, +1000].
b3) Traduire cet algorithme en PASCAL.
* * * * *
Exercice 1 : Inventaire
On dispose d'un fichier TEXT PASCAL décrivant la liste des produits en stock dans les différents magasins d'une chaîne de supermarché.
Chaque ligne de ce fichier a le format suivant :
N°produit Prix unitaire Nombre d'unités en stock
BB BB
La dernière ne contient que des zéros. B désigne un blanc.
1) Créer à partir de ce fichier un autre fichier STOCK (de type FILE) où chaque enregistrement est une structure à 3 champs : numéro du produit, prix unitaire et nombre d'unités en stock.
2) Pour l'inventaire de fin d'année et à partir du fichier STOCK défini en 1), éditer un état ayant la forme suivante :
MAGASIN 1
RAYON 1 : MONTANT DU STOCK ???
RAYON 2 : MONTANT DU STOCK ???
MONTANT TOTAL DU STOCK ???
MAGASIN 2
RAYON 1 : MONTANT DU STOCK ???
MONTANT DU STOCK POUR L'ENSEMBLE DES MAGASINS ???
où les '?' sont remplacés par les valeurs calculées par le programme.
- Les numéros de magasins et de rayons dans chaque magasin sont supposés tous présents à partir de 1. Le fichier est trié par numéro de magasin croissant et pour un magasin donné par numéro de rayon croissant.
- Pour un produit donné, le numéro de magasin est constitué par les deux premiers chiffres du numéro de produit, et le numéro du rayon par les deux chiffres suivants. Exemple : O4174043 produit vendu au magasin n° 4, rayon n° 17.
Pour les questions 1) et 2) fournir les algorithmes avant de donner les programmes PASCAL correspondants.
Exercice 2 : Histogramme
Une assemblée vote en choisissant une possibilité parmi 10. Donner l'algorithme qui imprime l'histogramme du vote.
Exemple d'histogramme :
*
* * *
* * * *
* * * * * * * *
* * * * * * * * * *
---1---2---3---4---5---6---7---8---9---10----->
Exercice 3 : Tri par insertion
Soit un vecteur T(1..N) dans lequel on a défini une relation d'ordre. On désire trier ce vecteur selon la méthode suivante :
1) On suppose T(1..K) trié avec K<N, puis on insère l'élément T(K+1) dans le sous-vecteur T(1..K+1) à sa bonne position.
2) Faire varier K de 1 à N-1 dans 1)
Ecrire l'algorithme correspondant.
* * * * *
PASCAL
Exercice 1 : Variétés
Considérons une liste de N nombres entiers ( N>1). On veut écrire un algorithme qui répond aux questions suivantes :
- déterminer le troisième nombre premier s'il existe,
- déterminer le deuxième carré parfait s'il existe,
- déterminer le nombre des diviseurs du premier nombre pair et du dernier nombre impair.
Pour le faire on définit les modules suivants :
a) PREM(Nbr, Bool) :
En entrée : un nombre quelconque Nbr. En sortie : Bool
Rôle : reconnaît si un nombre est premier ou non.
b) CARRE(Nbr, Bool) :
En entrée : un nombre quelconque Nbr.
En sortie : Bool
Rôle : reconnaît si un nombre est carré parfait ou non.
c) PAIR ( Nbr) :
En entrée : un nombre quelconque Nbr.
en sortie : VRAI si Nbr est un carré parfait, FAUXsinon.
Rôle : reconnaît si un nombre est pair ou non.
NBDIV( Nbr, Ndiviseurs) :
En entrée : un nombre quelconque Nbr.
En sortie : le nombre des diviseurs de Nbr est rangé dans la variable Ndiviseurs. Rôle : détermine le nombre de diviseurs d'un nombre donné.
QUESTIONS :
a) Ecrire séparément les 4 actions ainsi définies.
b) Utiliser ces actions pour écrire UN SEUL algorithme qui répond aux questions posées.
Remarques :
a) Ne pas utiliser 'opérateur "racine carrée".
b) Chaque nombre de la liste est délivré par un ordre de lecture.
c) Les questions a) et b) sont indépendantes.
Exercice 2 : Norme euclidienne
Etant donnés P vecteurs (X1, X2, . . , XN) de dimension N. ( P et N donnés).Quel est le rang du vecteur qui possède la plus grande norme euclidienne ?
Vous devez répondre à cette question :
a) en énonçant d'abord le principe que vous utilisez en langage naturel,
b) puis, en écrivant un algorithme.
Rappel : la norme euclidienne d'un vecteur est donnée par la formule :
Racine carré ( somme (X12+X22+ . XN2) )
Exercice 3 : Id ?
Soit le programme PASCAL suivant :
PROGRAM Id;
VAR
N, X, I, P, K, W : INTEGER;
S : REAL;
PROCEDURE Y ( VAR A, B : INTEGER);
VAR L : INTEGER;
BEGIN
B := 1;
FOR L:=2 TO A DO B := B * L
END;
BEGIN
READ(X); READ(N);
S := 1;
FOR I:=1 TO N DO
BEGIN
Y(I, P);
W:= 1;
FOR K:=1 TO I DO W := W * X;
S := S + ( W/ P) END END.
Questions :
a) Dérouler le programme pour X=3 et N = 4
b) Donner les contenus des variables P, S et W.
c) Que fait le programme ?
* * * * *
Exercice 1 : Le plus apparent
On considère un vecteur contenant N entiers. Ecrire l'algorithme qui recherche l'élément ayant le maximum d'occurrences dans le vecteur, c'est à dire qui apparaît le plus de fois.
Exercice 2 : Course de ski
On désire contrôler par ordinateur l'affichage d'une course de ski. Ecrire l'algorithme et le programme PASCAL qui après chaque arrivée d'un concurrent affiche le classement partiel sous la forme :
*****************************************************
*CLASSEMENT* NOM DU CONCURRENT *PAYS* TEMPS *
* * * * *
* * * * MN SEC CT *
*****************************************************
* * * * *
* 1 * xxxxx * yy * 5 10 86 *
* * * * *
*****************************************************
* * * * *
Remarques :
1) A chaque arrivée, il faudra insérer le concurrent à la place correspondante au classement fait sur le temps de parcours.
2) Description des données :
Pays, Nom prénom, Temps( en minutes, secondes et centièmes de seconde). Les données sont disposées à raison d'une ligne par concurrent comme suit :
PaysBB Nom et Prénom BBMnScCs
< 4> < 20 > < 6 >
3) L'affichage se fera sur imprimante suivant le format ci-dessus. Chaque tableau sera imprimé au milieu d'une page du listing.
4 Le jeu d'essai comportera 10 concurrents, on n'oubliera pas de traiter les ex-aequos.
Exercice 3 : Edition d'une ligne
Soit S une suite de caractères terminée par ".". Il s'agit de recopier sur listing une suite de caractères en fonction de la suite en entrée. S comprend des caractères représentant une succession de lignes de texte et des caractères-clés exprimant des actions à entreprendre par l'éditeur ( votre programme) ; ces derniers ne doivent pas être recopiés sur listing. Il y a 4 caractères-clés qui sont récapitulés dans le tableau ci-dessous :
Caractère Fonction
/ Annulation du dernier caractère de la
ligne en cours de formation (s'il existe)
< Annulation de toute la ligne
> Caractère de tabulation sur la ligne en cours; il indique que le prochain caractère doit apparaître dans une colonne multiple de 10.
# Fin de la ligne en cours qui peut alors être imprimée.
Les lignes à imprimer ne devront pas dépasser 120 caractères. En cas de tentative de création d'une ligne plus longue, on imprimera les 120 premiers caractères, puis un message d'erreur " ligne tronquée".
Exemple :
Soit la suite de caractères en entrée :
X<ABC//234567>ZZZ#1234#ABCDA//8#<1///AB#>9#1/FIN#.
On aura alors sur listing :
Travail à faire :
Faire une analyse du problème en le décomposant en modules, puis écrire l'algorithme répondant au problème posé.
NB. La lecture de S se fait caractère par caractère.
* * * * *
Exercice 1 : vérification syntaxique des déclarations FORTRAN
Soit un ensemble de N lignes où chacune renferme une déclaration FORTRAN. Ecrire un algorithme commenté qui imprime pour chaque déclaration la valeur VRAI si elle est correcte, un message d'erreur si elle est fausse.
Une déclaration FORTRAN a la forme suivante :
Colonne 1 à 6 : des blancs
Colone 7 à 72 : texte de la déclaration
Le texte de la déclaration a la forme suivante :
TYPE Idf1, Idf2, ,Idfn
avec type dans { INTEGER, REAL, LOGICAL}
Idf1, Idf2, ..et Idf3 sont des identificateurs.
a)Entre TYPE et l'identificateur il y a au moins un blanc. Les identificateurs sont séparés par des virgules. Des blancs peuvent exister entre les identificateurs et les virgules.
b) Idfi : suite de caractères alphanumériques dont le premier est alphabétique. La longueur est au maximum égale à 8.
On suppose qu'il existe une relation d'ordre dans l'ensemble des caractères. On a ainsi par définition :
autres caractères <'1'<'2'< <'9'<'A'<'B'.. < 'Z'
Chaque ligne renfermant une déclaration est lue caractère par caractère. On utilisera la fonction Sauter-ligne qui permet le positionnement en colonne 1 de la ligne suivante.
Exercice 2 : Course de ski
Pendant une course de ski, on a relevé après un essai les temps mis par N concurrents. On désire, après avoir mis les informations sur fichier, obtenir d'abord le tableau d'affichage des temps mis par les N concurrents, puis le tableau d'affichage concernant uniquement les trois
premiers.
Les données sur fichier ont la forme suivante :
Première ligne : nombre de concurrents sur 3 positions.
Dans les N lignes suivantes, on a recensé les informations concernant les concurrents. Chaque ligne est organisée comme suit : Colonne 1 à 4 : Numéro du concurrent
Colonne 12 à 19 : Nom du concurrent
Colonne 30 à 31 : Minutes
Colonne 32 à 33 : Secondes
Colonne 34 à 35 : Centièmes de seconde
Le tableau d'affichage aura la forme suivante :
*----------*---------------*--------------*
* * * *
* NUMERO * NOM * TEMPS *
* * *----*----*----*
* * * MM * SS * CC *
*----------*---------------*----*----*----*
* * * * * *
* numéro 1 * nom 1 * mm * ss * cc *
* * * * * *
*----------*---------------*----*----*----* * * * * * *
Etc.
Ecrire l'algorithme et le programme PASCAL correspondant.
* * * * *
Exercice 1 : Parties d'un ensemble donné.
Ecrire l'algorithme qui engendre toutes les parties d'un ensemble V donné. On assimilera V à un vecteur V(1..N)
Exemple :
Donnée : V = { 2, 4, 8 }
Résultat : {}, {2}, {4}, {8}, {2, 8}, {2, 4}, {4, 8}, {2, 4, 8}
Coder l'algorithme en PASCAL.
* * * * *
Exercice 1: Facture
En vue d'établir une facture, on a relevé sur chaque ligne d'un fichier TEXT PASCAL les informations que l'on organise comme suit : Ccolonne 1 à 5 : numéro du produit ou désignation
Colonne 10 à 14 : quantité ( entier)
Colonne 20 à 28 : prix unitaire
La dernière ligne ne contient que des zéros.
Ecrire l'algorithme puis le programme PASCAL qui édite la facture selon le format suivant :
*---------------*----------*----------*----------*
* DESIGNATION * QUANTITE * PU * TOTAL *
*---------------*----------*----------*----------*
* ??? * ??? * ??? * ??? *
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *
*---------------*----------*----------*----------*
* *
* NET A PAYER : ??? *
* *
*---------------*----------*----------*----------*
Exercice 2 : Analyse d'un texte
Soit un texte se terminant par le mot 'FINTEX'. Le texte contient des mots et des commentaires. Un commentaire est une suite de caractères comprise entre /* et */.
Un mot est une suite de caractères ne contenant pas de blancs et ne commençant pas /*. Un mot est dit numérique s'il ne contient que des caractères numériques. Un mot est dit alphabétique s'il ne contient que des caractères alphabétiques.
Ecrire un algorithme commenté qui rend la valeur 0 s'il s'agit d'un commentaire, la valeur 1 si le mot est alphabétique, la valeur 2 s'il est numérique et la valeur 3 dans les autres cas. De plus, dans le cas où le mot est numérique, l'algorithme doit fournir la valeur entière de ce mot et ce en utilisant la fonction PRENDRE(Mot, I) définie ci-dessous.
NB.
- La fonction PRENDRE(Mot, I) donne le caractère de rang I dans le mot Mot.
- On suppose que l’ensemble des caractères est muni d'une relation d'ordre "<" définie comme suit : autres caractères < '0'<'1'
Exemple
Texte : DEBUT---A-=-B5--/*AX--*/---V5+---;-A/*X---FIN--385---4B+----/*AB+-/*-X34--*/-25--FINTEX
Résultat
1, 1, 3, 3, 0, 3, 3, 3, 1, 2(385), 3, 0, 2(25)
Exercice 3 : Tri de 4 variables
Ecrire un algorithme qui liste en ordre croissant les contenus de 4 données A, B, C et D.
* * * * *
Exercice 1 : gestion des polynômes
Supposons que nous voulions manipuler des polynômes de la forme : P(x)= c1xe1 + c2xe2+ .. + cnxen (1)
avec a) e1 > e2 .. > en b) n<=20 c1, c2, .. cn sont des réels e1, e2, .. en sont des entiers compris entre 0 et 19.
Un tel polynôme peut être représenté par une structure dont le premier élément indique le nombre de termes non nuls et dont le second élément est un tableau à deux dimensions où chaque ligne représente le couple (ci, ei).
Ecrire les modules suivants :
Point(P, V) : fonction qui rend la valeur P(V)
Somme(P, Q, R) : somme des polynômes P et Q; résultat dans R.
Produit(P, Q, R) : produit des polynômes P et Q; résultat dans R. Dérivé(P, V) : dérivé du polynôme P; résultat dans R.
Ecrire une procédure PASCAL qui imprime le polynôme P sous la forme (1).
NB. On définira le type polynôme comme suit :
TYPE Polynome = STRUCTURE
Nbr : ENTIER { Nombre d'éléments non nuls }
Tab : TABLEAU[40, 2] DE REEL { Les monômes }
FIN
Exercice 2 : Accès par fonction
On a défini sur les vecteurs deux types d'accès :
- l'accès séquentiel
- l'accès dichotomique
Si l'on veut faire de l'accès séquentiel, on construit le vecteur de telle sorte que l'ordre des éléments est quelconque. Par contre, si on veut faire de l'accès dichotomique l'ordre des éléments est imposé.
On peut envisager un autre type d'accès que l'on définit comme suit :
Soit à construire un vecteur V à partir d'une liste de N valeurs V1,V2,.. Vn. On définit une fonction F qui à toute valeur Vi attribue un entier compris entre 1 et N. L'élément Vi est alors rangé à la place F(Vi). Comme on ne peut dans la pratique trouver une fonction F qui attribue une valeur différente à chaque élément de V, il se peut que l'on ait :
F(Vi) = F(Vj) = F(Vk)= . . = F(Vt)
Dans ce cas
- l'élément Vi sera rangé dans le vecteur à la position F(Vi)
- les autres Vj, Vk, .. , Vt seront rangés dans un vecteur V' de telle sorte qu'ils soient liés entre eux comme le montre la figure ci-dessous :
F(V) = (V + 5) Mod N + 1
N = 10
Valeurs : 6, 12, 10, 9, 8, 7, 16, 2, 3, 0, 5, 26, 32.
L'élément 10 est rangé à la place 6 car F(10) = 6
Dans l'exemple on a F(6) = F(16) = F(26) = 2; le premier élément 6 est rangé à la place 2 et est lié au second élément 16 par l'indice 1; 16 et 26 sont rangés dans V' et sont liés entre eux par l'indice 4.; l'élément 7 est rangé dans V à la position 3; il n'est lié à aucun élément.
Exercice 3 : Tri de couleurs
Soit un vecteur de N éléments contenant 3 types de couleurs : vert(V), rouge(R) et blanc(B) . Ecrire un algorithme qui ordonne les couleurs comme suit :
RRR BBBBB VVVVV
* * * * *
Exercice 1 : Gestion des polynômes
veut écrire un ensemble de procédures permettant d'effectuer du calcul algébrique sur des polynômes à une variable. On choisit d'exprimer un polynôme sous la forme d'une liste linéaire chaînée. A chaque élément est associé un monôme.
Exemple : le polynôme 12 + 32x2 + 2x3 + x20 (I) s'exprimera sous la forme :
a) Ecrire un algorithme dont la donnée est une chaîne de caractères constituant un polynôme (que l'on convient de terminer par le caractère '*' ) et dont le résultat est une liste linéaire chaînée représentant ce polynôme.
b) Ecrire une action composée qui calcule la valeur d'un polynôme en un point donné.
c) Ecrire une action composée qui construit le polynôme somme de deux polynômes P1 et P2 donnés.
d) Ecrire une action composée qui construit le polynôme produit de deux polynômes P1 et P2 donnés.
e) Ecrire une action composée qui construit le polynôme dérivé d'un polynôme donné.
f) Ecrire une action composée qui imprime sous la forme (I) un polynôme P se trouvant en mémoire.
g) Programmer le module a)
NB. Toutes les questions sont indépendantes. On utilisera le module Nombre(Chaine) qui convertit la chaîne de caractères Chaine en un entier.
Exercice 2 : Accès par fonction
On a défini sur les vecteurs deux types d'accès
- l'accès séquentiel
- l'accès dichotomique
On peut définir un autre type d'accès que l'on peut décrire comme suit : Soit à construire un vecteur V à partir d'une liste de N valeurs V1,V2,.. VN. On définit une fonction F qui à toute valeur Vi attribue un entier compris entre 1 et N. L'élément Vi est alors rangé à la place F(Vi). Comme on ne peut dans la pratique trouver une fonction F qui attribue une valeur différente à chaque élément de V, il se peut que l'on ait :
F(Vi) = F(Vj) = F(Vk)= . . = F(Vt)
Dans ce cas
- l'élément Vi sera rangé dans le vecteur à la position F(Vi),
- les autres Vj, Vk, .. , Vt seront rangés dans une liste linéaire chaînée de telle sorte qu'ils soient liés entre eux comme le montre la figure ci-dessous:
L'élément 10 est rangé à la place 6 car F(10) = 6
Dans l'exemple on a F(6) = F(16) = F(26) = 2; le premier élément est rangé à la place 2; 16 et 26 dans une liste linéaire chaînée; le deuxième champ de l'élément 2 du vecteur contient le pointeur de tête de cette liste. Etc..
Ecrire un algorithme permettant d'insérer un ensemble de valeurs.
* * * * *
Partie A
Soit une suite de caractères se terminant par le caractère ".". Chaque lecture délivre le prochain caractère de la suite.
Ecrire les algorithmes suivants :
1 - Compter le nombre de mots commençant par "M" et se terminant par "S". 2 - Imprimer pour chaque mot rencontré : le mot, sa longueur, le nombre de voyelles et le dernier caractère.
Partie B
Soit une suite de N nombres (N>3). Chaque lecture délivre le prochain nombre. Ecrire les algorithmes suivants :
1 - Rechercher le premier nombre dont le carré est égal à la somme des 3 précédents.
2 - calculer la somme (-1)i . Xi / i i = 1,2,. ,N pour N et x donnés.
* * * * *
Exercice 1 : Analyse des constantes "virgule flottante"
Soit sur le ruban de la machine-caractères une suite de constantes réelles représentées en Virgule flottante. La suite est terminée par le caractère '$'. Les constantes sont séparées par une combinaison de blancs et de virgules. Ecrire un algorithme qui donne pour chaque constante correcte ses attributs W et D. W étant le nombre total de caractères et D le nombre de caractères de la partie décimale. Une constante en virgule flottante a la forme suivante :
[+/-] [chchch ] [.][chchch .] E [+/-]chch
Les crochets désignent les parties facultatives, le symbole / désigne ou.
Exercice 2 : Classement
Dans une classe de 30 élèves en vue d'établir un classement à partir des notes obtenues en 9 compositions et des coefficients correspondants, calculer pour chaque élève la somme des produits de chaque note par son coefficient et la moyenne correspondante.
NB. Vous devez dire d'abord comment vous organisez les données avant d'écrire l'algorithme correspondant. On utilisera le module de tri sans le développer.
* * * * *
Exercice 1 : Couples parfaits
Imprimer tous les couples (A, B) de nombres entiers compris entiers 1 et 1000 tels que A + B est parfait. ( Un nombre est parfait s'il est égal à la somme de ses diviseurs 1 inclus, N exclu)
Exercice 2 : Mots de la forme X Y .Z
Sur la machine-caractères déterminer les mots de la forme X Y Z de longueur L donnée.
* * * * *
Exercice 1 : Tri par insertion
Soit un vecteur T[1..N] à valeurs numériques. Trier ce vecteur selon la méthode suivante:
1) Supposer T[1..K] trié (K<N), insérer l'élément T(K+1) dans le sous-vecteur T[1..K+1] à sa bonne position.
2) Faire varier K de 1 à N-1 dans 1)
Exercice 2 : Représentation des polynômes
Soit le polynôme suivant :
P(x) = a0xn + a1xn-1+ . an.
(i) - Donner 2 façons de représenter le polynôme. L'une en représentant les termes nuls et l'autre sans les représenter. (ii) - Ecrire les modules suivants:
Dérivé(P, P') : dérivé du polynôme P, résultat dans P', Valeur(P, X) : valeur de P pour X donné dans chacune des 2 représentations.
(iii) - Ecrire l'algorithme qui calcule la valeur P(X) pour X donné en utilisant la factorisation de Horner :
P(x) = ( ( a0x + a1)x + an-1)x + an, dans chacune des 2 représentations.
* * * * *
