Algorithmique et Programmation - jfalycee.free.frjfalycee.free.fr/IMG/pdf_algo_jfa.pdf · Fin En organigramme ... Une fois le problème résolu et découpé, il faut le traduire en

Algorithmique et programmation 1 JFA11

Algorithmique et Programmation

A). Introduction :

Quand on utilise une carte à microprocesseur ou un microcontrôleur, il faut fournir au processeur, les

instructions à exécuter pour réaliser la fonction désirée. Pour cela, on doit lui fournir un programme

exécutable.

Pour créer ce programme exécutable, il faut analyser de manière rigoureuse les tâches à faire exécuter au

microprocesseur et en déduire les actions à effectuer, pour les traduire en programme.

B). Etude et traduction :

Après l’étude des tâches à réaliser, il faut traduire et décomposer le travail à effectuer en sous tâches à

l’aide

I ). I) Présentation :

Il est impossible d'écrire un programme correct du premier coup, depuis la première ligne jusqu'à la

dernière. Un programme est l'aboutissement d'un travail méthodique résumé par le schéma suivant :

Programme

executable


PROBLEME

DEFINITION

1

TESTS

5

CORRECTIONS

4

TRADUCTION

3

ANALYSE

2

1°). Première étape : Définition du problème :

Il faut être capable de définir très précisément tout ce que l'on attend du programme. Pour cela il

faut connaître quelles sont les informations nécessaires à la résolution du problème :

qui va les fournir et sous quelle forme,

est-on sûr de la validité de ces données ou faut-il les contrôler pour s'assurer quelles sont

conformes à ce que l'on avait prévu ?

Il faut également réfléchir à la présentation des résultat.

Exemple :

Ecrire un programme qui permet d’entrer 10 nombres.

2°). Seconde étape : Analyse structurée et pseudo code ou algorigramme :

Une fois les données déterminées et les résultats explicités, il ne reste plus qu'à trouver la méthode

qui permet d'obtenir les résultats à partir des données. Si la solution n'est pas évidente du premier coup

d'oeil, il est nécessaire :

- de le découper en sous-problèmes,

- et de le structurer.

Lorsqu'un problème est trop complexe, il faut le découper en plusieurs tâches distinctes, auxquelles

on attribue un nom significatif, de manière que le problème paraisse résolu avec la résolution des

sous-problèmes.

Puis on traite chaque tâche suivant le même processus, en la subdivisant en sous-tâches jusqu'à ce

que celles-ci deviennent évidentes à résoudre.

La structuration consiste à organiser les sous-tâches obtenues par la méthode de découpage,

de manière que leur agencement réponde effectivement au problème posé.

Une fois cet agencement trouvé, il reste à le traduire en pseudo code.

Exemple : Comptage de 10 nombres saisis au clavier :


En Pseudo Code :

Variables :

COMPTEUR : entier

NOMBRE : réel

Début

COMPTEUR = 0

Tantque (COMPTEUR < 10) faire

Saisir NOMBRE (on saisit le nombre)

COMPTEUR = COMPTEUR + 1 (on incrémente la variable)

Fintantque

Fin

En organigramme :

3°). Troisième étape : traduction :

Une fois la décision prise du langage utilisé, si l'analyse et la structuration et la traduction en

pseudo code (ou en algorigramme) ont été faite correctement, la traduction ou le codage est simple à

réaliser.

Exemple : en langage C :

Main ()

Int COMPTEUR ;

Float NOMBRE ;

{

COMPTEUR = 0 ;

While (COMPTEUR < 10) do {

Getch (NOMBRE) ;

COMPTEUR = COMPTEUR + 1 ;

}


}

4°). Quatrième étape : Tests :

Il reste maintenant à passer la dernière étape, qui est en faite l'aboutissement de tout notre travail, à

savoir si notre programme remplit bien les tâches prévues.

5°). Cinquième étape : Corrections :

Cette étape est normalement inutile si l'analyse et la structuration ont été faites correctement. Mais

l'erreur est humaine !

6°). Sixième étape : Documentation :

Cette étape est souvent négligée à tort car elle permet une meilleure utilisation du programme, et

surtout une maintenance aisée. Il faut penser à l'utilisateur qui ne connaît pas forcément bien

l'informatique. Vous vous êtes sûrement déjà retrouvé devant un programme avec sa documentation et

ne pas savoir par où commencer.

II ). DEFINITION DU PROBLEME :

1°). Définition des variables d'entrées et de sorties :

On devra établir la liste des variables d'entrée et de sortie dont le programme a besoin. On pourra se

poser les questions suivantes :

- Sous quelle forme se présentent ces entrées ou ces sorties

(bit, octet, caractère, texte, ...)

- Quelle est la nature de ces entrées ou de ces sorties.

(temporaires, constantes, variables)

Il faudra leur choisir un nom évocateur de ce qu'elles représentent et ne pas hésiter à mettre un

commentaire en face de leur déclaration.

Exemple :

compteur boucle, nom, voyelle, ...

et non toto, tata, titi ...

2°). Contraintes supplémentaires :

Avant de s'attaquer à la résolution du problème, il faut encore répondre à quelques questions :

- Quelle est la procédure de base qui transforme les entrées en sorties ?

- Y a-t-il des contraintes de temps ?

- Y a-t-il des contraintes mémoires ?

- Y a-t-il des cas particuliers à traiter ?

- Quelle est la précision des résultats à fournir ?

- Comment le programme doit-il traiter les erreurs d'exécution, de débordement, d'entrées, de

sorties ?

Toutes ces questions sont à se poser avant d'écrire la moindre ligne de programme.


III ). CONCEPTION DU PROGRAMME :

1°). Principes de bases de la conception d'un programme :

Une fois le problème résolu et découpé, il faut le traduire en algorithme. Et c’est la version traduite

de l’algorithme qui sera notre programme. Ce programme dit source sera aussi traduit ensuite en un

programme exécutable par l'ordinateur.

Un algorithme doit être clair et lisible, pour cela un peu de soin dans sa présentation est nécessaire.

Aucun flou artistique n'est tolérable.

L'analyse/programmation peut donc être résumée dans le schéma suivant :

REALISATION ?

COMPILATION

PROGRAMMATION

ANALYSE

PROGRAMME ECRIT EN

LANGAGE EVOLUE

PROGRAMME

EXECUTABLE

ALGORITHMEPROCESSUS A

AUTOMATISER

L'analyse et la programmation sont à notre charge,la compilation est à la charge d'un programme

traducteur, appelé compilateur.

L’algorithme peut*être présenté sous deux formes :

En organigramme ou,

en pseudo code.

2°). Qu'est ce qu'un algorithme ?

Un algorithme est une série d’actes ou d’opérations élémentaires qu’il faut exécuter en séquence

pour accomplir une tâche quelconque, en suivant un enchaînement strict.

Remarque :

Lorsqu’il sera demandé d’élaborer un algorithme, la méthode pour atteindre cet objectif sera

de rédiger en français la succession des opérations élémentaires (phases courtes et précises) puis

de passer à une écriture conventionnelle appelée pseudo-code.

3°). Algorithme : Structure.

1. Un algorithme en pseudo-code ou sous forme d'organigramme, un programme en langage évolué

sont toujours structurés de façon suivante:

Déclarations,

Constantes


Variables

Programme,

début

Initialisation des variables

traitements

fin

2. Il faut systématiquement déclarer toutes les variables, et préciser leur type (caractère, chaîne de n

caractères, entier, réel, booléen ou logique, etc.) et les constantes.

Toute constante dans le corps d'un algorithme doit être déclarée. Par exemple, si nous voulons

saisir une suite de 10 éléments, il vaut mieux déclarer en constante N=10 puis utiliser N dans

l'algorithme ou le programme. Car si nous devons changer le programme pour traiter 8 ou 14

éléments, il suffit d'écrire N=8 ou N=14.

3. L'usage des commentaires doit être systématisé. En tête de programme, il doit se trouver un

commentaire disant ce que fait le programme.

De même toute partie délicate du traitement doit être commentée.

Il en est de même pour les variables, leur identificateur doit être explicite et un commentaire doit

en préciser l'utilité dans l'algorithme ou le programme.

Un commentaire peut se placer n'importe où (entre {}) dans l'algorithme.

4°). Les organigrammes :

Les organigrammes ne sont en rien une méthode de conception de programme, mais plutôt un outil

et un moyen d'y arriver !

a) Avantages des organigrammes :

- L'intérêt fondamental réside dans sa représentation imagée.

* les symboles standards sont normalisés

* Ils peuvent être compris par des personnes n'ayant aucune connaissance de la

programmation.

* Ils peuvent servir à diviser le projet entier en sous-tâches. Ils serviront alors à évaluer

les progrès accomplis.

* Ils décomposent les séquences d'opérations et aident ainsi à trouver les erreurs.

b) Inconvénients des organigrammes :

- Ils sont difficiles à concevoir, dessiner, ou modifier dans tous les cas.

- Il n'existe pas de méthode simple pour mettre au point, optimiser, ou tester un

organigramme.

- Ils tendent à devenir encombrants : il est difficile de décider entre l'introduction de détails

utiles et le nombres de ces détails qui les rendrait à peine plus lisibles.

- Ils ne montrent que l'organisation du programme, mais pas celle des données ou la structure

des entrées-sorties.


- Ils ne sont d'aucun secours pour les problèmes d'ordre matériel ou temporel. Ils ne suggèrent

même pas où de tels problèmes pourraient bien surgir.

- Ils n'autorisent pas une programmation structurée si l'on y prête pas attention. Les renvois,

les flèches, les boucles peuvent réaliser un joli méli-mélo.

c) Conclusion :

Les organigrammes constituent une technique utile pour la documentation des programmes. En

tant qu'outil de conception, ils ne peuvent cependant offrir qu'un moyen de commencer et

d'éclaircir les idées.

d) Symboles normalisés des organigrammes :

Voir annexes.

IV ). PROGRAMMATION :

1°). Notation algorithmique :

Nous disposons de deux notations strictement équivalentes :

Organigrammes,

Pseudo-code.

Ce sont deux représentations d'un même processus, elles sont donc identiques. Un organigramme

est une description plus visuelle à l'aide de schémas; le pseudo-code est plus proche de notre langage.

a) Le début et la fin d’un programme ou d’un sous programme.

Cette notation permet de situer le début et la fin du programme. Dans un sous-programme on

écrira le nom du sous-programme plutôt que « début ».

Exemple:

Pseudo Code Organigramme

Début

instructions

instructions

instructions

Fin

Elles sont représentées dans un rectangle

avec les cotés arrondis. Il y ne doit y

avoir qu’un seul début et une seule fin

Traduction en langage C :

Structure en C :

Main()

{

Instructions ;

DEBUT

FIN


}

b) La plus simple : la structure séquentielle.

Une séquence d'instructions est une suite d'instructions. Elles seront exécutées les unes derrière

les autres. Cela peut être des affectations ou des opérations.

Exemple:


A = 10 ;

B = A+5 ;


Chaque structure est une boîte. Il y a une

entrée, une sortie.


Structure en C :

Attention, chaque ligne se termine par un point virgule :

A=10 ;

B=A+5 ;

c) Le bloc :

Pour assembler une suite d'instructions qui représente une partie complète on peut la mettre dans

un bloc. Elles seront aussi exécutées les unes derrière les autres.

Exemple:


A = 10 ;

B = A+5 ;


Chaque structure est une boîte. Il y a une

entrée, une sortie.


A=10

B=A+5

A=10

B=A+5


Structure en C :

Un bloc commence par une accolade et se termine par une accolade ; et chaque ligne se

termine par un point virgule :

{

A=10 ;

B=A+5 ;

}

d) Les entrées sorties :

Les entrées sorties sont considérées comme des opérations à part car elles sont représentées de

manière différentes, mais c’est toujours une structure séquentielle. Par exemple pour exécuter

l'opération correspondant à l'allumage d'une diode électroluminescente, ou pour aller lire un mot

binaire sur le clavier de la serrure à code.

Exemple:


LIRE A ;

ECRIRE B ;

Elles sont représentées dans un losange.


Structure en C :

getch(A) ;

printf(B) ;

e) La structure alternative.

Elle sert à représenter des actions "optionnelles" ; dans certains cas, il faut exécuter une action,

dans l'autre une action différente. Suivant le résultat du test on exécute une action ou une autre.

Dans le cas de l'exemple ci-dessus suivant la valeur de A, B vaut 1 ou 0.

Un algorithme se lisant de haut en bas, nous ne pouvons donc utiliser qu'une seule des deux

branches : pas d'erreur possible. Les réponse à la condition peuvent être écrite de manière lisible

(oui, non) ou le non peut-être représenté par une barre oblique ou par un petit rond sur une des

sorties.

LIRE A

ECRIRE B


Exemple:


Si A<10

Alors

B=1 ;

Sinon

B=0 ;

FinSi

Elles sont représentées dans un losange.


Structure en C :

if (A<10)

{

B=1 ;

}

else

{

B=0 ;

}

Remarque : pourquoi ce finsi?

Derrière le finsi, il peut très bien y avoir d'autres actions. Il faut donc marquer la limite entre

les actions optionnelles et celles qui ne le sont pas. Le finsi correspond au point de rencontre des

flèches qui sortent des boites de l'organigramme.

Si il n'y a qu'un seul cas, la partie sinon peut est inexistante. On peut très bien écrire :

A<10 ?

B = 1 B = 0

non oui


Exemple:


Si A<10

Alors

B=0 ;

FinSi


Structure en C :

if (A<10)

{

B=0 ;

}

f) La structure répétitive.

Cette structure nous permet de représenter des processus à caractère répétitif. La condition est évaluée

puis la suite d'actions est exécutée. La suite d'actions est alors répétée tant que la condition reste vraie.

Dans ce cas, il se peut que la suite d'actions ne soit pas réalisée si la condition est fausse dès le début.

Exemple:


Tantque A<10

Faire

B=B+1 ;

A=A+1 ;

FinTantque


Structure en C :

While (A<10)

{

A<10 ?

B = 0

non oui

A<10 ?

B = B+ 1

A = A + 1

non

oui


B=B+1 ;

A=A+1 ;

}

Remarque : pourquoi ce fintantque?

De même derrière le fintantque, il peut très bien y avoir d'autres actions. Il faut donc marquer

la limite entre les actions optionnelles et celles qui ne le sont pas. Le fintantque correspond à la

fin des instructions à répéter.

g) La deuxième structure répétitive.

Cette structure permet de réaliser une action ou une suite d'actions tant que la condition de branchement

est réalisée. Elle est réalisée au moins une fois !

Exemple:


Faire

B=B+1 ;

A=A+1 ;

Tant que (A<10)


Structure en C :

do

{

B=B+1 ;

A=A+1 ;

} while (A<10)

h) La structure Répétitive avec compteur.

Nous avons vu que certains algorithmes nécessitaient un comptage d'éléments ou de situations

(exemple: comptage des lettres au clavier ou comptage du nombre de fois qu'il y a deux mêmes

lettres successivement), pour ce faire, on utilisera une variable entière que l'on incrémentera à

chaque fois que la situation à compter se produit.

Il existe une autre structure de contrôle permettant de représenter un tel algorithme, la boucle

pour:

pour COMPTEUR 1, <10, +1 faire

|

| saisir NOMBRE

A<10 ?

B = B+ 1

A = A + 1

non

oui


|

finpour

Une telle boucle sous-entend l'initialisation du compteur (ici COMPTEUR), l'incrémentation au

fur à mesure (ici +1) et le test (COMPTEUR<10).

Syntaxe : effectuer un traitement pour un compteur, aussi appelé indice de boucle, I variant

d'une valeur initiale VI, jusqu'à une valeur finale VF, avec un pas PAS.

pour I VI,VF,PAS faire

| traitement

finpour

Si le pas est omis, on considère qu'il est égal à 1.

I vaudra VI, puis VI + PAS, puis VI + 2xPAS, etc. Si le pas est positif, le processus s'exécute

tant que I est inférieur à VF.Si il est négatif, le processus s'exécute tant que I est supérieur à VF.

Cette structure nous permet de représenter des processus à caractère répétitif. La condition est

évaluée puis la suite d'actions est exécutée. La suite d'actions est alors répétée tant que la condition

reste vraie. Dans ce cas, il se peut que la suite d'actions ne soit pas réalisée si la condition est fausse

dès le début.

Exemple:


Pour Y 50000,0, -1

Faire

B=B+1 ;

FinPour


Structure en C :

For (Y=5000 ; Y>=0 ; Y=Y-1)

{

B=B+1 ;

}


i) Renvoi vers un autre point du programme

Quand le programme est assez complexe on peut remplacer une longue ligne de connexion par

des repères numérotés pour clarifier la représentation.

j) Appel d’un sous programme.

Ce bloc comporte le nom du sous-programme à exécuter. Le sous-programme est un élément indépendant

du programme principal. Lorsqu'un appel de sous-programme est rencontré, l'exécution s'interrompt dans

le programme en cours, elle se poursuit dans le sous-programme. Dès que dans le sous-programme on

rencontre l'instruction de fin de sous-programme, l'exécution revient au programme l'ayant appelé là où il

s'était interrompu.

Le sous-programme est une entité où on y regroupe un ensemble de lignes qui réalisent une fonction. On

devrait trouver pour chaque sous-programme :

A). la définition précise de la fonction réalisée ;

B). les définitions des entrées et sorties de la fonction, exactement de la même manière que pour une fonction de l'électronique câblée.


EXERCICES

Exercice 1

Quel résultat produit le programme suivant ?

Variables val, double numériques

Début

Val ← 231

Double ← Val * 2

Ecrire Val

Ecrire Double

Fin

Exercice 2

Ecrire un programme qui demande un nombre à l’utilisateur, puis qui calcule et affiche le

carré de ce nombre.

Exercice 3

Ecrire un programme qui lit le prix HT d’un article, le nombre d’articles et le taux de TVA,

et qui fournit le prix total TTC correspondant. Faire en sorte que des libellés apparaissent

clairement.

Exercice 4

Ecrire un algorithme qui permet d'imprimer le résultat d'un étudiant à un module sachant que

ce module est sanctionné par une note d'oral de coefficient 1 et une note d'écrit de coefficient 2.

La moyenne obtenue doit être supérieure ou égale à 10 pour valider le module.

Exercice 5

On veut écrire une fonction permettant de calculer le salaire d'un employé payé à l'heure à

partir de son salaire horaire et du nombre d'heures de travail.

Les règles de calcul sont les suivantes : le taux horaire est majoré pour les heures

supplémentaires : 25% au-delà de 160 heures et 50% au-delà de 200 heures.

Exercice 6

Ecrire l'algorithme permettant d'afficher la table de multiplication par 9.

Exercice 7

Compte à rebours : écrire l'algorithme de la fonction qui, à partir d'un nombre entier positif n,

affiche tous les nombres par ordre décroissant jusqu'à 0.


CORRIGE DES EXERCICES

Exercice 1

Quel résultat produit le programme suivant ?

Variables val, double numériques

Début

Val ← 231

Double ← Val * 2

Ecrire Val

Ecrire Double

Fin

On verra apparaître à l’écran 231, puis 462 (qui vaut 231 * 2)

Exercice 2

Ecrire un programme qui demande un nombre à l’utilisateur, puis qui calcule et affiche le

carré de ce nombre.

Variables nb, carr en Entier

Début

Ecrire "Entrez un nombre :"

Lire nb

carr ← nb * nb

Ecrire "Son carré est : ", carr

Fin

En fait, on pourrait tout aussi bien économiser la variable carr en remplaçant les deux

avant-dernières lignes par :

Ecrire "Son carré est : ", nb*nb

C'est une question de style ; dans un cas, on privilégie la lisibilité de l'algorithme, dans

l'autre, on privilégie l'économie d'une variable.

Exercice 3

Ecrire un programme qui lit le prix HT d’un article, le nombre d’articles et le taux de TVA,

et qui fournit le prix total TTC correspondant. Faire en sorte que des libellés apparaissent

clairement.

Variables nb, pht, ttva, pttc en Numérique

Début

Ecrire "Entrez le prix hors taxes :"

Lire pht

Ecrire "Entrez le nombre d’articles :"


Lire nb

Ecrire "Entrez le taux de TVA :"

Lire ttva

pttc ← nb * pht * (1 + ttva)

Ecrire "Le prix toutes taxes est : ", pttc

Fin

Là aussi, on pourrait squeezer une variable et une ligne en écrivant directement. :

Ecrire "Le prix toutes taxes est : ", nb * pht * (1 + ttva)

C'est plus rapide, plus léger en mémoire, mais un peu plus difficile à relire (et à écrire !)

Exercice 4

Ecrire un algorithme qui permet d'imprimer le résultat d'un étudiant à un module sachant

que ce module est sanctionné par une note d'oral de coefficient 1 et une note d'écrit de

coefficient 2. La moyenne obtenue doit être supérieure ou égale à 10 pour valider le module.

Données : la note d'orale et la note d'écrit

Résultat : impression du résultat pour le module (reçu ou refusé)

Principe : on calcule la moyenne et on la compare à 10

Algorithme

début

ne <- lire()

no <- lire()

moy <- (2 * ne + no)/3

si moy >= 10

alors écrire ("reçu")

sinon écrire ("refusé")

fsi

fin

Lexique

- ne : réel, note d'écrit (coefficient 2)

- no : réel, note d'oral (coefficient 1)

- moy : réel, moyenne du module

Exercice 5

On veut écrire une fonction permettant de calculer le salaire d'un employé payé à l'heure à

partir de son salaire horaire et du nombre d'heures de travail.

Les règles de calcul sont les suivantes : le taux horaire est majoré pour les heures

supplémentaires : 25% au-delà de 160 heures et 50% au-delà de 200 heures.


fonction calculerSalaire (sh:réel, nbh:entier):réel

début

si nbh < 160

alors salaire <- sh * nbh

sinon si nbh < 200

alors salaire <- 160 * sh + (nbh - 160) * 1,25 *

sh

sinon salaire <- 160 * sh + 40 * sh * 1,25 +

(nbh - 200) * sh * 1,5

fsi

fsi

retourne salaire

fin

Lexique

- sh : réel, salaire horaire

- nbh : entier, nombre d'heures de l'employé

- salaire : réel, salaire de l'employé


Symbole d’organigramme

Documents

Algorithmique et Programmation - jfalycee.free.frjfalycee.free.fr/IMG/pdf_algo_jfa.pdf · Fin En organigramme ... Une fois le problème résolu et découpé, il faut le traduire en