<
Afpa
Page 2 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Sommaire
1. Les structures de base d'un langage de programmation-------------------------- 6
1.1.
La séquence d'instructions--------------------------------------------------------------------------- 6
1.2. L'affectation ------------------------------------------------------------------------------------------11
1.3. la
structure
alternative ------------------------------------------------------------------------------13
1.4. La
structure
répétitive -------------------------------------------------------------------------------15
1.5. La
compilation ---------------------------------------------------------------------------------------17
1.6. La
déclaration
des variables------------------------------------------------------------------------18
1.7.
Les fonctions et procédures ------------------------------------------------------------------------21
2. Règles de programmation------------------------------------------------------------------ 24
3. La syntaxe du pseudo-langage ----------------------------------------------------------- 26
4.
Comment analyser un problème ?-------------------------------------------------------- 29
5. Un peu d'entraînement --------------------------------------------------------------------- 41
5.1. L'alternative ------------------------------------------------------------------------------------------41
5.2. La
boucle ---------------------------------------------------------------------------------------------43
5.3. Contraction -------------------------------------------------------------------------------------------47
5.4. Doublons----------------------------------------------------------------------------------------------49
5.5. Equivalence ------------------------------------------------------------------------------------------51
5.6. Eparpillement ----------------------------------------------------------------------------------------55
5.7. Inversion ----------------------------------------------------------------------------------------------57
5.8. Palindrome -------------------------------------------------------------------------------------------59
5.9. Cryptage ----------------------------------------------------------------------------------------------61
5.10. Comptage ---------------------------------------------------------------------------------------------63
5.11. Les
tris ------------------------------------------------------------------------------------------------66
5.12. Le calcul des heures ---------------------------------------------------------------------------------77
5.13. Le
jeu
du pendu --------------------------------------------------------------------------------------79
5.14. Le crible d'Erathostène------------------------------------------------------------------------------82
AFPA
Page 3 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
66. Quelques corrigés en langage Java ----------------------------------------------------- 83
6.1. Alternative--------------------------------------------------------------------------------------------83
6.2. Alternative2 ------------------------------------------------------------------------------------------85
6.3. Boucle-------------------------------------------------------------------------------------------------87
6.4. Statistiques -------------------------------------------------------------------------------------------89
6.5. Contraction -------------------------------------------------------------------------------------------91
6.6. Doublons----------------------------------------------------------------------------------------------92
6.7. Equivalence ------------------------------------------------------------------------------------------93
6.8. Eparpillement ----------------------------------------------------------------------------------------95
6.9. Inversion ----------------------------------------------------------------------------------------------97
6.10. Palindrome -------------------------------------------------------------------------------------------99
6.11. Cryptage -------------------------------------------------------------------------------------------- 101
6.12. Comptage ------------------------------------------------------------------------------------------- 103
6.13. Dichotomie ----------------------------------------------------------------------------------------- 105
6.14. TriSelection ---------------------------------------------------------------------------------------- 108
6.15. Tri
Bulle -------------------------------------------------------------------------------------------- 110
6.16. TriPermutation ------------------------------------------------------------------------------------- 112
6.17. Tri
Comptage -------------------------------------------------------------------------------------- 114
6.18. Tri
Alphabétique----------------------------------------------------------------------------------- 116
Afpa
Page 4 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
AFPA
Page 5 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Pour illustrer notre propos, prenons l'exemple du déroulement de la journée de Buggy.
Une séquence d'instruction serait :
Vous voyez que l'ordre des instructions a de l'importance : "S'habiller" puis "prendre sa douche" conduit à un
résultat pas génial que nous appellerons un "bug". Cependant certaines instructions peuvent se dérouler dans
un ordre indifférent: "prendre sa douche" et "prendre son petit déjeuner" peuvent être inversés sans préjudice
pour le résultat.
Une alternative s'exprime par si ….. sinon……
Que la condition soit réalisée (condition vraie) ou qu'elle ne le soit pas (condition fausse) les premières actions
sont les mêmes et se passent dans le même ordre ce qui permet la simplification suivante :
Remarquez que les actions si vrai ou si faux sont décalées par rapport aux autres instructions afin de
permettre une meilleure lisibilité; on parle d'indentation.
Afpa
Page 7 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Pour illustrer l'itérative ou répétitive (les deux termes sont équivalents), continuons notre exemple en supposant
que Buggy dont nous vivons la journée palpitante, soit un employé de banque. La routine journalière de cet
employé est :
Les deux actions "Traiter client" et "Appeler client suivant" vont se répéter tant que la condition située
derrière l'instruction "Tant que" est vérifiée.
Afpa
Page 8 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Considérons maintenant le programme complet de la journée de Buggy
Afpa
Page 9 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Dans notre pseudo-langage, nous n'aurons que la liste minimum d'instructions, nécessaire et suffisante pour
les programmes que nous aurons à écrire.
1.2.L'affectation
Ce qui se lit "variable reçoit valeur" et qui signifie que nous mémorisons la valeur à un endroit nommé
variable. Nous pourrions aussi dire que nous rangeons une valeur dans des cases de la mémoire que nous
nommons variable.
Par exemple :
Il ne faut jamais confondre valeur et variable. Une variable est caractérisée par :
une adresse c'est à dire un emplacement dans la mémoire de la machine,
un type permettant d'indiquer la nature de l'information contenue,
éventuellement une longueur si le type ne le définit pas.
Quand nous aurons affaire à une variable numérique, nous écrirons
Dans le premier exemple, nous envoyons la constante 0 dans une variable nommée nCompteur.
Dans le deuxième exemple, nous envoyons le contenu de la variable nSalaireBase comme contenu de la
variable nSalaire.
Quand nous sommes en présence d'une variable alphanumérique, nous écrirons
Dans le premier cas, nous envoyons la constante Bonjour dans une variable nommée strMessage.
"AFFICHER strMessage" donnera comme résultat l'affichage du mot Bonjour.
Dans le deuxième exemple, nous envoyons le contenu de la variable nommée Bonjour qui peut contenir BYE
comme contenu de la variable strMessage.
"AFFICHER strMessage" donnera comme résultat l'affichage du mot BYE.
Afpa
Page 11 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
1.3.la structure alternative
Il est souvent nécessaire lorsque nous écrivons un programme de distinguer plusieurs cas conditionnant
l'exécution de telles ou telles instructions. Pour ce faire, on utilise une structure alternative : si on est
dans tel cas, alors on fait cela sinon on fait ceci.
La syntaxe de cette instruction est la suivante :
Les crochets signifient que la partie "sinon actions" est facultative.
Exemples :
Pour avoir la valeur absolue (appelée nAbsolu dans notre exemple) d'un nombre (n1 dans notre
exemple), s'il est négatif nous le multiplions par –1 sinon la valeur absolue égale le nombre :
Ne faire la division que si le diviseur n2 n'est pas égal à zéro :
Afpa
Page 13 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
1.3.1.Les conditions
Pour exprimer les conditions on utilise les opérateurs conditionnels suivants :
= égal
< inférieur
> supérieur
<= inférieur ou égal
>= supérieur
ou
égal
<> différent
On peut combiner des conditions à l'aide des opérateurs logiques suivants : ET OU NON XOR(ou
exclusif)
Lorsque l'on écrit de telles conditions, il est recommandé de mettre toutes les parenthèses afin d'éviter
les erreurs car les opérateurs ont une hiérarchie qui ne collera pas nécessairement avec votre logique.
1.3.2.Les actions
Les actions qui suivent sinon ou alors peuvent être :
- une simple instruction
- une suite d'instructions séparées par des ;
- une autre alternative
- une répétitive
Afpa
Page 14 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
1.4.2.Faire Jusqu'à
Ce qui signifie que l'on exécute les actions jusqu'à ce que la condition soit vraie.
exemple :
1.4.3.Pour
Très souvent, nous utilisons une structure répétitive avec un compteur et nous arrêtons lorsque le
compteur a atteint sa valeur finale.
C'est pourquoi la plupart des langages de programmation offrent une structure permettant d'écrire cette
répétitive plus simplement. Dans le pseudo-langage c'est la structure pour :
Lorsque le PAS est omis, il est supposé égal à +1.
Afpa
Page 16 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
1.6.La déclaration des variables
Un programme exécutable est composé de deux parties :
données
instructions
La partie instructions contient les instructions à exécuter.
La partie données contient toutes les variables utilisées par le programme.
Un programme exécutable est chargé dans la mémoire centrale de l'ordinateur, les valeurs que l'on a
affectées aux variables doivent être conservées tout le temps du déroulement du programme. Par
conséquent, il faut que le programme soit capable de réserver la place nécessaire aux variables.
Pour ce faire, les variables doivent être déclarées afin que le compilateur sache quelle place elles vont
occuper.
1.6.1.Les types de variables
Les variables que l'on utilise dans les programmes ne sont pas toutes de même nature, il y a des
nombres, des caractères, On dit que les variables sont typées.
Il est nécessaire de donner un type aux variables, car cela permet d'une part de contrôler leur
utilisation (ex: on ne peut pas diviser un caractère par un entier) et d'autre part car cela indique quelle
place il faut réserver pour la variable.
Généralement les langages de programmation offrent les types suivants :
entier : il s'agit des variables destinées à contenir un nombre entier positif ou négatif.
Dans notre pseudo-langage, nous écrirons la déclaration des variables de type entier :
Généralement un entier occupe 2 octets, ce qui limite les valeurs de -32768 à +32768.
Cependant cela dépend des machines, des compilateurs, et des langages.
Afpa
Page 18 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
exemple :
Le premier exemple montre la déclaration d'un tableau de 10 postes de type caractère dont les postes
seront nommées mot (i) i allant de 1 à 10.
Dans certains langages i ira de 0 à 9
Afpa
Page 20 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
1.7.Les fonctions et procédures
Lorsque l'algorithme devient trop compliqué, nous avons envie de le découper, de manière à ce que
chaque partie soit plus simple et donc plus lisible.
De même, lorsqu'une partie de code doit être exécutée plusieurs fois à des endroits différents ou
réutilisée ultérieurement on pourra ne l'écrire qu'une fois et lui donner un nom en en faisant une
fonction ou une procédure.
1.7.1.Procédure
Une procédure est une suite d'instructions servant à réaliser une tâche précise en fonction d'un certain
nombre de paramètres.
Ce lot d'instructions est écrit une fois dans la procédure mais peut être exécutée autant de fois que
voulu en appelant la procédure : on aura donc une ligne de code pour exécuter n instructions.
De plus une procédure peut fonctionner avec des paramètres qui sont indiqués au moment de l'appel et
pris en compte dans l'exécution de la procédure.
Les paramètres sont de deux types.
Les paramètres de type VAL : ils contiennent une valeur qui sera utilisée dans la procédure.
Les paramètres de type VAR : ils représentent une variable du programme appelant qui pourra être
lue et modifiée si nécessaire.
Dans notre pseudo-langage, une procédure se déclare de la manière suivante :
Les variables que nous déclarons à l'intérieur de procédure ne sont connues que dans cette procédure.
Elles sont d'ailleurs nommées variables locales.
Pour utiliser cette procédure dans un programme appelant, on écrit :
Afpa
Page 21 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
1.7.2.Fonction
Une fonction est une procédure dont le but est de déterminer une valeur et de la retourner au
programme appelant.
Dans notre pseudo-langage, elle se déclare de la manière suivante :
Les mêmes remarques que pour la procédure s'appliquent.
De plus, il faut noter que la fonction retourne une valeur (ou le contenu d'une variable) et que donc à
la déclaration on doit indiquer son type, c'est à dire le type de cette valeur.
L'appel d'une fonction s'écrit :
Une fonction ne peut donc pas retourner un tableau.
exemples :
Nous l'utiliserons ainsi :
Afpa
Page 23 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
2.Règles de programmation
Un programme doit être le plus lisible possible, de manière à ce que n'importe qui d'autre que l'auteur
soit capable de comprendre ce qu'il fait rien qu'en le lisant. Pour cela il faut suivre les quelques règles
suivantes :
• le nom des variables doit être significatif, c'est à dire indiquer clairement à quoi elles servent
• un algorithme ne doit pas être trop long (une page écran). S'il est trop long, il faut le découper en
fonctions et procédures (voir 1.7)
• les structures de contrôle doivent être indentées, c'est à dire, par exemple, que les instructions qui
suivent le alors doivent toutes être alignées et décalées d'une tabulation par rapport au si. Il en
est de même pour les répétitives.
• A chaque imbrication d'une structure de contrôle, on décale d'une tabulation.
exemples :
Afpa
Page 24 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
3.La syntaxe du pseudo-langage
Un programme comportera
Une partie déclaration
Une partie encadrée par début fin où sont décrites les actions
Dans la partie déclarations, nous trouvons :
déclaration de variables
déclaration de fonction
déclaration de procédure
3.1.1.Déclaration de variables :
Où type peut être: ENTIER ou REEL ou CAR ou BOOLEEN
3.1.2.Déclaration de fonction :
3.1.3. Déclaration de procédure:
Afpa
Page 26 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Dans la partie actions, nous trouvons :
suite d'instructions
alternative
répétitive
3.1.4.Suite d'instructions :
3.1.5.Alternative :
3.1.6.Répétitive :
Tantque
Faire
Pour
Afpa
Page 27 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
3.1.7.Pour exprimer une condition :
Opérateurs logiques ET, OU, NON, XOR
Opérateurs de comparaison =, <, >, <=, >=, <>
3.1.8.Les instructions
variable
valeur
LIRE variable
AFFICHER [texte valeur ]
Appel de fonction : variable
nomFonction ( param1, param2, ) ;
Appel de procédure nomProcédure ( param1, param2, ) ;
Pour exprimer une valeur, nous pouvons utiliser :
Un nom de variable
Une constante
Afpa
Page 28 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Quels sont les différents types de cas à traiter ?
Premier cas
Les éléments de départ sont :
2 3 3 5 6 8 12 25 26 42 53 55
Nous voulons insérer le nombre 7 au milieu
Le résultat devrait être :
2 3 3 5 6 7 8 12 25 26 42 53 55
Deuxième cas
Les éléments de départ sont :
Nous voulons insérer le nombre 7 dans une liste ne comportant aucun élément
Le résultat devrait être :
7
Troisième cas
Les éléments de départ sont :
2 3 3 5 6 8 12 25 26 42 53 55
Nous voulons insérer le nombre 1en première case
Le résultat devrait être :
1 2 3 3 5 6 8 12 25 26 42 53 55
Quatrième cas
Les éléments de départ sont :
2 3 3 5 6 8 12 25 26 42 53 55
Nous voulons insérer le nombre 60 qui sera en fin de liste
Le résultat devrait être :
2 3 3 5 6 8 12 25 26 42 53 55 60
Afpa
Page 30 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Résumons notre démarche :
Soit
un
nombre
à
insérer nAInserer
Soit
1
le
départ
de
notre
recherche
nDebut
Soit
le
nombre
d'élements
à
consuler
nFin
nbElement prend la valeur de nFin
Nous cherchons le nombre d'éléments à consulter
nbElement
Nous
divisons
ce
nombre
par
2
nPosition
Si le résultat n'est pas entier, nous arrondissons à l'entier supérieur
nPosition
Nous comparons le nPositioniéme numéro de la liste avec notre nombre à Insérer
Si ce nombre est inférieur au nombre à insérer,
nous prenons la partie droite du tableau depuis l'élément en nPosition jusqu'à la fin; cela revient
à dire que nous changeons la position de début du tableau nDebut prend la valeur de nPosition.
autrement nous prenons la partie gauche depuis le 1er élément jusqu'à l'élément en nPositio; cela
revient à dire que nous changeons la position de fin du tableau nFin prend la valeur de nPosition
Nous cherchons le nombre d'éléments restant à consulter
nbElement
nbElement prend la valeur de nFin – nDebut + 1
Nous
divisons
ce
nombre
par
2
nPosition
Si le résultat n'est pas entier, nous arrondissons à l'entier supérieur
nPosition
Voyez que nous sommes en train de recommencer la démarche telle qu'elle a été décrite un peu au
dessus. Nous sommes donc en train de répéter une même séquence de ligne ce qui veut dire que nous
sommes en présence d'une répétitive.
Afpa
Page 32 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Notre démarche devient donc
Soit
un
nombre
à
insérer nAInserer
Soit
1
le
départ
de
notre
recherche
nDebut
Soit
le
nombre
d'élements
à
consuler
nFin
Nous cherchons le nombre d'éléments à consulter
nbElement
la première fois nbElement prend la valeur de nFin
Nous répétons TANTQUE nombre d'éléments > 2
Nous
divisons
ce
nombre
par
2
nPosition
Si le résultat n'est pas entier, nous arrondissons à l'entier supérieur
nPosition
Nous comparons le nPositioniéme numéro de la liste avec notre nombre à Insérer
Si ce nombre est inférieur au nombre à insérer,
nous prenons la partie droite du tableau depuis l'élément en nPosition jusqu'à la fin; cela revient
à dire que nous changeons la position de début du tableau nDebut prend la valeur de nPosition.
autrement nous prenons la partie gauche depuis le 1er élément jusqu'à l'élément en nPosition; cela
revient à dire que nous changeons la position de fin du tableau nFin prend la valeur de nPosition
FINSI
Nous cherchons le nombre d'éléments restant à consulter
nbElement
les autres fois nbElement prend la valeur de nFin – nDebut + 1
Fin de la séquence répétée FINTQ
Nous sommes maintenant avec deux éléments à consulter.
Toujours en se basant sur le bon sens, nous savons que le deuxième élément est nécessairement plus
grand ou égal que le nombre à insérer car quand nous coupions notre tableau en deux c'était par un
"inférieur". Il suffit donc de comparer notre nombre à insérer au premier élément.
SI l'élément en position nDebut est inférieur à notre nombre à insérer
La position dans laquelle nous allons insérons notre nombre à insérer est nDebut + 1
Autrement c'est nDebut
FINSI
Afpa
Page 34 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
En résumé, notre démarche est devenue :
Soit
un
nombre
à
insérer nAInserer
Soit
1
le
départ
de
notre
recherche
nDebut
Soit
le
nombre
d'élements
à
consuler
nFin
Nous cherchons le nombre d'éléments à consulter
nbElement
la première fois nbElement prend la valeur de nFin
Nous répétons TANTQUE nombre d'éléments > 2
Nous
divisons
ce
nombre
par
2
nPosition
Si le résultat n'est pas entier, nous arrondissons à l'entier supérieur
nPosition
Nous comparons le nPositioniéme numéro de la liste avec notre nombre à Insérer
Si ce nombre est inférieur au nombre à insérer,
nous prenons la partie droite du tableau depuis l'élément en nPosition jusqu'à la fin; cela revient
à dire que nous changeons la position de début du tableau nDebut prend la valeur de nPosition.
autrement nous prenons la partie gauche depuis le 1er élément jusqu'à l'élément en nPosition; cela
revient à dire que nous changeons la position de fin du tableau nFin prend la valeur de nPosition
FINSI
Nous cherchons le nombre d'éléments restant à consulter
nbElement
les autres fois nbElement prend la valeur de nFin – nDebut + 1
Fin de la séquence répétée FINTQ
SI l'élément en position nDebut est inférieur à notre nombre à insérer
La position dans laquelle nous allons insérons notre nombre à insérer est nDebut + 1
Autrement c'est nDebut
FINSI
POUR n ALLANT de nFIN à nPosition en faisant –1 à chaque tour
Prendre la valeur en position n et la mettre dans la valeur en position n+1
FINPOUR
Mettre la nombre à insérer dans la valeur qui est en position nPosition
Afpa
Page 36 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Nous adaptons notre démarche du premier cas
Soit
un
nombre
à
insérer nAInserer
Soit
1
le
départ
de
notre
recherche
nDebut
Soit
le
nombre
d'élements
à
consuler
nFin
Nous cherchons le nombre d'éléments à consulter
nbElement
la première fois nbElement prend la valeur de nFin
La
position
d'insertion
est
1
nPosition
Si nFin n'est pas zéro
Nous répétons TANTQUE nombre d'éléments > 2
Nous divisons ce nombre par 2
nPosition
Si le résultat n'est pas entier, nous arrondissons à l'entier supérieur
nPosition
Nous comparons le nPositioniéme numéro de la liste avec notre nombre à Insérer
Si ce nombre est inférieur au nombre à insérer,
nous prenons la partie droite du tableau depuis l'élément en nPosition
jusqu'à la fin; cela revient à dire que nous changeons la position de début
du tableau nDebut prend la valeur de nPosition.
autrement nous prenons la partie gauche depuis le 1er élément jusqu'à
l'élément en nPosition; cela revient à dire que nous changeons la position
de fin du tableau nFin prend la valeur de nPosition
FINSI
Nous cherchons le nombre d'éléments restant à consulter
nbElement
les autres fois nbElement prend la valeur de nFin – nDebut + 1
Fin de la séquence répétée FINTQ
SI l'élément en position nDebut est inférieur à notre nombre à insérer
La position d'insertion est nDebut + 1
Autrement c'est nDebut
FINSI
Soit le nombre d'élements à consuler
nFin
POUR n ALLANT de nFIN à nPosition en faisant –1 à chaque tour
Prendre la valeur en position n et la mettre dans la valeur en position n+1
FINPOUR
FINSI
Mettre la nombre à insérer dans la valeur qui est en position nPosition
Afpa
Page 38 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
La démarche finale est :
Soit
un
nombre
à
insérer nAInserer
Soit
1
le
départ
de
notre
recherche
nDebut
Soit
le
nombre
d'élements
à
consuler
nFin
Nous cherchons le nombre d'éléments à consulter
nbElement
La
position
d'insertion
est
1
nPosition
Si nFin n'est pas zéro
Nous répétons TANTQUE nombre d'éléments > 2
Nous divisons ce nombre par 2
nPosition
Si le résultat n'est pas entier, nous arrondissons à l'entier supérieur
nPosition
Ajouter nDebut – 1 à nPosition
Nous comparons le nPositioniéme numéro de la liste avec notre nombre à Insérer
Si ce nombre est inférieur au nombre à insérer,
nous prenons la partie droite du tableau depuis l'élément en nPosition
jusqu'à la fin; cela revient à dire que nous changeons la position de début
du tableau nDebut prend la valeur de nPosition.
autrement nous prenons la partie gauche depuis le 1er élément jusqu'à
l'élément en nPosition; cela revient à dire que nous changeons la position
de fin du tableau nFin prend la valeur de nPosition
FINSI
Nous cherchons le nombre d'éléments restant à consulter
nbElement
les autres fois nbElement prend la valeur de nFin – nDebut + 1
Fin de la séquence répétée FINTQ
SI l'élément en position nDebut est inférieur à notre nombre à insérer
La position d'insertion est nDebut + 1
Autrement c'est nDebut
FINSI
Soit le nombre d'élements à consuler
nFin
POUR n ALLANT de nFIN à nPosition en faisant –1 à chaque tour
Prendre la valeur en position n et la mettre dans la valeur en position n+1
FINPOUR
FINSI
Mettre la nombre à insérer dans la valeur qui est en position nPosition
Afpa
Page 40 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Pour la deuxième partie de l'exercice, il faut rajouter une boucle :
Afpa
Page 42 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.2.La boucle
Autre sujet : Écrire un programme qui saisit des entiers et en affiche la somme et la moyenne (on
arrête la saisie avec la valeur 0)
Afpa
Page 43 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 44 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Les statistiques
On saisit des entiers (comme exercice précédent) et on les range dans un tableau (maximum 50)
Écrire un programme qui affiche le maximum, le minimum et la valeur moyenne de ces nombres.
Afpa
Page 45 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 46 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.3.Contraction
Recopier une phrase dans une autre en ôtant toutes les occurrences d’un caractère
Soit une phrase terminée par un point.
Il s'agit de la restituer en supprimant les occurrences d'un caractère donné.
Exemple :
phrase
:
abbcccdeeeffg
caractère
:
c
résultat
:
abbdeeeffg
Donnez le jeu d'essai qui permet de tester cette procédure.
Donnez l'algorithme de la procédure en pseudo code.
Afpa
Page 47 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 48 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Jeu d'essai:
bbbbiidooooonn. donne bidon
aaaaaaaaaaaaa. donne a
meilleur
donne meilleur
Les deux derniers cas sont des cas extrêmes mais dans un jeu d'essai sérieux, ce sont des cas à ne pas oublier
Si nous voulions être très rigoureux, nous devrions tester que la phrase saisie se termine bien par un point. Si
ce n'est pas le cas, le TANTQUE va provoquer une boucle dont nous ne sortirons jamais. Nous pourrions
appeler çà le mouvement perpétuel.
Afpa
Page 50 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.5.Equivalence
Déterminer si deux phrases sont équivalentes.
Soit deux phrases terminées par un même terminateur.
Elles sont dites équivalentes si elles ont les mêmes lettres dans le même ordre mais avec un nombre
d'occurrences de ces lettres qui peut différer entre les deux phrases.
On supposera qu'il existe une fonction longueur lg de chaîne qui renvoie un entier
Exemple :
abbcccdeeeffg
aabcdeffffg
sont
équivalentes
Donnez le jeu d'essai qui permet de tester cette procédure.
Donnez l'algorithme de la procédure toujours en pseudo code.
Afpa
Page 51 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 52 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Il est assez fastidieux de "dérouler" le programme de cette manière; Des outils appelés "déboggeur" vous
permettent de laisser le travail à la machine. Ils permettent de :
Faire avancer le programme "pas à pas" c'est à dire ligne par ligne
Lister le contenu des variables à un point d'arrêt c'est à dire à une ligne précise (nous vous
rappelons que les valeurs ne sont modifiées qu'une fois l'affectation finie; il faut donc se
positionner sur la ligne après l'affectation pour voir la valeur prise par la variable.
Faire avancer le programme de point d'arrêt en point d'arrêt
Eventuellement de modifier les valeurs des variables : attention si vous travaillez dans un contexte
aussi utilisé par les utilisateurs, vous risquez de faire des bêtises en modifiant la base de données
réelle.
Cas n° 1
Phrase n° 1 ccccccdddddaaaagggg
Phrase n° 2
cccdddggggaa
Résultat
phrases différentes
Cas n° 2
Phrase n° 1 aaazzzeeerrty
Phrase n° 2 azerty
Résultat phrases équivalentes
Cas n° 3
Phrase n° 1 Immobile
Phrase n° 2 imobile
Résultat phrases différentes ou équivalentes
En effet, une lettre majuscule est différente d'une lettre minuscule sur un système "casse sensitive". Elles sont
équivalence sur les autres systèmes.
Afpa
Page 54 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 56 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.7.Inversion
Effectuer la saisie d'une chaîne de caractères qui contiendra un nom et un prénom.
Les prénoms composés seront obligatoirement séparés par des tirets.
Afficher une chaîne de caractères sous forme prénom nom séparés par un espace, en ayant fait disparaître les
tirets saisis dans le prénom.
Ecrire la procédure en pseudo-code (éventuellement ensuite avec un langage).
Ne pas utiliser les instructions de type concaténation et recherche d'un caractère dans une chaîne.
Afpa
Page 57 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 58 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.8.Palindrome
Déterminer si une chaîne de caractères est un palindrome.
Un palindrome est une phrase qui peut se lire dans les deux sens.
Les espaces sont ignorés.
Exemple :
esope reste ici et se repose.
Le terminateur est ici un point.
Donnez l'algorithme du programme.
Afpa
Page 59 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 60 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 62 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.10.Comptage
Compter le nombre de mots d’une phrase ayant une terminaison donnée.
Soit une phrase terminée par un point.
Les espaces sont des séparateurs de mot.
Il s'agit de donner le nombre de mots de la phrase ayant pour terminaison la chaîne intitulée terminaison.
Exemple :
Caractère final : .
Phrase :
rien ne sert de courir il faut partir à point il ne faut pas rire.
Terminaison :
rir
Résultat :
1
Note : les terminaisons de longueur nulle indiquent à la procédure qu'il faut renvoyer le nombre de mots de la
phrase.
Ecrire la procédure en pseudo code
Afpa
Page 63 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 64 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 65 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 67 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.11.2.
Le tri bulle
Le tri bulle est un tri plus astucieux. Son principe est de faire remonter petit à petit un élément trop
grand vers le haut du tableau en comparant les éléments deux à deux.
Si l'élément de gauche est supérieur à son voisin de droite on les inverse et on continue avec le suivant.
Lorsque l'on est en haut du tableau on repart au début et on s'arrête lorsque tous les éléments sont
bien placés.
52 10 1 25 62 3 8 55 3 23
10 52 1 25 62 3 8 55 3 23
10 1 52 25 62 3 8 55 3 23
10 1 25 52 62 3 8 55 3 23
10 1 25 52 62 3 8 55 3 23
10 1 25 52 3 62 8 55 3 23
10 1 25 52 3 8 62 55 3 23
10 1 25 52 3 8 55 62 3 23
10 1 25 52 3 8 55 3 62 23
10 1 25 52 3 8 55 3 23 62
On a parcouru tout le tableau, on recommence, jusqu'à ce que tout soit bien placé.
Écrire l'algorithme qui réalise ce tri.
Afpa
Page 68 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 69 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 71 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.11.4.
le tri par comptage
Le tri par comptage consiste pour chaque élément du tableau à compter combien d'éléments
sont plus petits que lui, grâce à ce chiffre on connaît sa position dans le tableau résultat.
52 10 1 25 62 3 8 55 3 23
nbre
de
plus
petit 7 4 0 6 9 1 3 8 1 5
position
8 5 1 7 10 2 4 9 3 6
1 3 3 8 10 23 25 52 55 62
Afpa
Page 72 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 73 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.11.5.
Le tri alphabétique
Le programme consiste à saisir des mots (au maximum 10) de 20 caractères maximum et de les insérer
dans un tableau dans l'ordre alphabétique. Puis d'afficher ensuite ce tableau.
Le tableau résultat est du type TABLEAU CAR [10,20].
Afpa
Page 74 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 75 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 76 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.12.Le calcul des heures
Le programme réalise l'addition de deux données exprimées en HH :MM:SS et affiche le résultat sous
la même forme.
Afpa
Page 77 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 78 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Corrigé
Afpa
Page 80 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 81 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
5.14.Le crible d'Erathostène
Cet algorithme permet d'afficher progressivement la liste des nombres premiers inférieurs à une valeur
donnée : MAX.
Pour ce faire, on construit un tableau de MAX éléments, vide au départ, que l'on parcourt.
Chaque fois que la case est vide cela signifie que l'indice du tableau est un nombre premier, on
l'affiche puis on remplit avec une valeur quelconque toutes les cases du tableau indicées par un multiple
de l'indice courant.
exemple pour MAX = 10
tableau au départ = 0 0 0 0 0 0 0 0 0 0
indice :
1
1 est un nombre premier (je ne marque rien !)
2
2 est un nombre premier ==> je marque 1 pour tableau (2)
je marque 1 pour tableau (2 + 2)
je marque 1 pour tableau (2 +2 +2)
tableau = 0 1 0 1 0 1 0 1 0 1
3
3 est un nombre premier ==> je marque 1 pour tableau(3)
je marque 1 pour tableau (3 + 3)
je marque 1 pour tableau (3 +3 +3)
tableau = 0 1 1 1 0 1 0 1 1 1
4
4 n'est pas un nombre premier car il est déjà à 1
5
5 est un nombre premier ==> je marque etc .
Écrire un programme qui demande un nombre et affiche tous les nombres premiers inférieurs au nombre
donné.
Afpa
Page 82 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.Quelques cor igés en langage Java
Remarque : ces classes programmes sont perfectibles : il y manque l'aspect contrôle des informations
saisies volontairement ignoré ici.
D'autre part le \r est parfois à remplacé par \n si Jbuilder 4 et plus.
6.1.Alternative
Afpa
Page 83 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.2.Alternative2
Afpa
Page 85 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 86 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.3.Boucle
Afpa
Page 87 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 88 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.4.Statistiques
Afpa
Page 89 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 90 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.5.Contraction
Afpa
Page 91 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.6.Doublons
Afpa
Page 92 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.7.Equivalence
Afpa
Page 93 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 94 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.8.Eparpillement
Afpa
Page 95 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 96 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.9.Inversion
Afpa
Page 97 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 98 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.10.Palindrome
Afpa
Page 99 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 100 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.11.Cryptage
Afpa
Page 101 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.12.Comptage
Afpa
Page 103 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 104 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.13.Dichotomie
Afpa
Page 105 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 106 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 107 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.14.TriSelection
Afpa
Page 108 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 109 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.15.Tri Bulle
Afpa
Page 110 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 111 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.16.TriPermutation
Afpa
Page 112 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 113 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.17.Tri Comptage
Afpa
Page 114 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 115 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
6.18.Tri Alphabétique
Afpa
Page 116 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 117 de 118
28/09/2005
Algorithmes et structuration de programmes
Support de formation
Afpa
Page 118 de 118
28/09/2005
