Cours d analyse et conduite de projet algorithmique .pdf

---

À propos / Télécharger Aperçu

---

Ce document au format PDF 1.5 a été généré par Acrobat PDFMaker 9.0 pour Word / Adobe PDF Library 9.0, et a été envoyé sur fichier-pdf.fr le 24/10/2013 à 19:21, depuis l'adresse IP 109.88.x.x. La présente page de téléchargement du fichier a été vue 1499 fois.
Taille du document: 1.3 Mo (105 pages).
Confidentialité: fichier public

Aperçu du document

---

HEPCUT – CAT. ECONOMIQUE

Analyse et conduite de
projet algorithmique
Jean-François CHALLE, maitre assistant

1ère Informatique classe 1 A & B

2009

ISEC-HEPCUT

Informations pédagogiques à
destination des étudiants

Catégorie :
Type :
Section :
Enseignant :
Année :
Fonction :
Activité d’enseignement :
Nombre d’heures :
Nombre de crédits :

économique
court
informatique
Jean-François Challe
1ère
maître-assistant
analyse et conduite de projets algorithmique
120
10

Etalement en quadrimestre
1er quadrimestre :
2ème quadrimestre :
1ème et 2ème quadrimestre :

60
60
120

PREREQUIS (Article 11 de l’AGCF du 02/07/1996) dans le cadre des crédits résiduels :

Non

1. Objectifs de l’activité d’enseignement
L’activité d’enseignement vise à permettre à l’étudiant de :
• développer des comportements professionnels ;
• prendre conscience des compétences à développer pour répondre à l’évolution de la
technique ;
• mettre en œuvre des méthodes spécifiques pour :
• appréhender, globalement, la diversité des techniques requises par la fonction de
programmation dans le secteur informatique ;
• développer des compétences de base applicables dans tous les langages
procéduraux ;
• adopter une démarche algorithmique cohérente ;

2 Définition des pré-requis (compétences et contenus)
Les compétences requises sont de deux ordres. D’une part des compétences en
langue française et d’autre part des compétences en mathématiques.
Face à un document de plusieurs pages rédigé en français, l’étudiant doit être
capable :
• de répondre à des questions de compréhension portant sur les liens logiques entre les
• idées développées ;
• de rédiger un commentaire critique portant sur les idées essentielles du texte ;
• d’établir un plan de la structure du texte et de le justifier.
• L’algorithmique et l’informatique puisant leurs racines dans le domaine des
mathématiques,
• l’étudiant doit maîtriser l’application des notions suivantes :
• les fonctions polynomiales ;
• l’algèbre linéaire (les vecteurs, les matrices, les déterminants, les systèmes d’équations
• linéaires) ;
• les fonctions de R dans R, graphe de la fonction, domaine de définition, variation,

2

•
•

croissance, parité, continuité ;
les suites, les séries et les logarithmes.

3 Place de l’activité d’enseignement dans l’ensemble de la formation
L’algorithmique est la clé de voûte de l’informatique aussi bien dans le domaine de la
programmation que dans l’étude des systèmes d’exploitation, des réseaux et des bases de
données. De bonnes compétences en algorithmique permettent d’appréhender les autres
disciplines propres à la formation, non pas comme des ensembles disjoints de matières à
mémoriser, mais comme un ensemble cohérent et logique. L’étude de l’informatique laisse
ainsi peu de place à la mémorisation en incitant à la réflexion logique.

4 Compétences minimales qui devront être maîtrisées à la fin de
l’activité d’enseignement
Pour atteindre le seuil de réussite, l’étudiant devra prouver qu’il est capable, face à un
problème de :
• mettre en œuvre une stratégie cohérente et efficace de résolution du problème posé ;
• concevoir, de construire et de représenter les algorithmes dans un langage de
description
• proche des langages de programmation usuels ;
• justifier la démarche algorithmique et les choix mis en œuvre ;

5 Méthodes et moyens didactiques
Dans un premier temps, l’enseignement de l’algorithmique passe par un exposé
magistral des concepts de bases. Dès que les étudiants ont assimilé les principes
élémentaires, le cours passe dans une phase de pédagogie active. La didactique employée
est une approche par problème enjoignant aux étudiants l’établissement de leur solution.
Pour chaque problème posé, une ou plusieurs solutions sont proposées en guise de
correction. La diversité des solutions présentées engendre une réflexion sur la qualité des
algorithmes. Cette qualité est dans un premier temps mesurée de manière qualitative mais
très rapidement une approche quantitative est préférée.
Toutes les séances de cours sont mises à profit pour aborder un nouveau sujet, un
nouveau problème. Cela permet à l’étudiant de comprendre qu’une étude basée sur la
mémorisation n’est pas la clé du succès.
Cette approche méthodologique se justifie par le fait que l’algorithmique n’est pas un
savoir à acquérir mais bien un savoir-faire. De cette manière, les étudiants sont placés en
situation d’examen lors de chaque séance.
Des exercices d’auto-évaluation sont organisés durant l’année. Cela permet à
l’étudiant de se familiariser avec la méthode d’interrogation ainsi qu’avec celle d’évaluation
avec pour conséquence la prise de conscience bilatérale de la situation de l’étudiant.

6 Contenu de l’activité d’enseignement
Voici les points abordés dans le cadre de ce cours :
• les variables ;
• les structures de programmation (la séquence, les alternatives, les répétitives) ;
• la décomposition d’un problème en sous-problèmes ;
• le contrôle de la saisie d’informations ;
• la récursivité ;
• les structures de données statiques (les vecteurs et les matrices) et les algorithmes
• spécifiques associés ;

3

•
•

les structures de données dynamiques (les listes et les arbres) et les algorithmes
spécifiques
associés ;

Références
[1] KYLE LOUDON, MASTERING ALGORITHM WITH C, O’REILLY, PARIS 1999.
[2] ROBERT SEDGEWICK, ALGORITHMS IN C, ADDISON-WESLEY, LONDON 1990.
[3] THOMAS CORMEN, CHARLES LEISERSON, RONALD RIVEST, AN INTRODUCTION TO ALGORITHMS, MIT
PRESS, LONDON, 1990.
[4] DONALD E. KNUTH, THE ART OF COMPUTER PROGRAMMING VOLUME 1 FUNDAMENTAL ALGORITHMS,
ADDISON-WESLEY, LONDON 1973.
[5] DONALD E. KNUTH, THE ART OF COMPUTER PROGRAMMING VOLUME 2 SEMINUMERICAL ALGORITHMS,
ADDISON-WESLEY, LONDON 1981.
[6] DONALD E. KNUTH, THE ART OF COMPUTER PROGRAMMING VOLUME 3 SORTING AND SEARCHING,
ADDISON-WESLEY, LONDON 1973.
[7] IAN PARBERRY, WILLIAM GASARCH, PROBLEMS ON ALGORITHMS, PRENTICE HALL, DENTON, 2002.
[8] STEVEN S. SKIENA, THE ALGORITHM DESIGN MANUAL, SPRINGER-VERLAG, NEW YORK, 1997.
[9] ROBERT SEDGEWICK, ALGORITHMS IN C++, ADDISON-WESLEY, LONDON, 1999.
[10] ROY A. PLASTOCK, GORDON KALLEY, THEORY AND PROBLEMS OF COMPUTER GRAPHICS,
MACGRAW-HILL, NEW YORK, 1986.
[11] SEYMOUR LIPSCHUTZ, THEORY AND PROBLEMS OF DATA STRUCTURES, MACGRAW-HILL, NEW YORK,
1986.
[12] ROBERT SEDGEWICK, ALGORITHMS, ADDISON-WESLEY, LONDON, 1983.
[13] ROBERT SEDGEWICK, ALGORITHMS IN JAVA, ADDISON-WESLEY, BOSTON, 2002.
[14] DOUGLAS BALDWIN, GREG W. SCRAGG, ALGORITHMS AND DATA STRUCTURES : THE SCIENCE OF
COMPUTING, CHARLES RIVER MEDIA, HINGHAM, 2004.
[15] P. S. DESHPANDE, O. G. KAKDE, C & DATA STRUCTURES, CHARLES RIVER MEDIA, HINGHAM, 2004.
[16] ALAN PARKER, ALGORITHMS AND DATA STRUCTURES IN C++, CRC PRESS, HUNTSVILLE, 1993.
[17] MI LU, ARITHMETIC AND LOGIC IN COMPUTER SYSTEMS, JOHN WILEY & SONS, HOBOKEN, 2004.
[18] WALLACE WANG, BEGINNING PROGRAMMING FOR DUMMIES, WILEY PUBLISHING, HOBOKEN, 2004.
[19] ADRIAN AND KATHIE KINGSLEY-HUGHES, BEGINNING PROGRAMMING, WILEY PUBLISHING,
INDIANAPOLIS, 2004.
[20] BRUNO R. PREISS, DATA STRUCTURES AND ALGORITHMS WITH OBJECT-ORIENTED DESIGN PATTERNS IN
C++, WILEY PUBLISHING, WATERLOO, 2002.
[21] BRUNO R. PREISS, DATA STRUCTURES AND ALGORITHMS WITH OBJECT-ORIENTED DESIGN PATTERNS IN
JAVA, WILEY PUBLISHING, WATERLOO, 2002.
[22] FRANCIS GLASSBOROW, ROBERTA ALLEN, A BEGINNER’S INTRODUCTION TO COMPUTER PROGRAMMING,
JOHN WILEY AND SONS, CHICHESTER, 2004.
[23] NELL DALE, C++ PLUS DATA STRUCTURES, JONES AND BARTLETT PUBLISHERS, LONDON, 2003.
[24] JIM KEOGH, KEN DAVIDSON, DATA STRUCTURES DEMYSTIFIED, MCGRAW-HILL, NEW YORK, 2004.
[25] JOHN NOLT, DENNIS ROHATYN, ACHILE VARZI, THEORY AND PROBLEMS OF LOGIC, MACGRAW-HILL,
NEW YORK, 1992.
[26] JOHN R. HUBBARD, THEORY AND PROBLEMS OF PROGRAMMING WITH C++, MACGRAW-HILL, NEW
YORK, 1996.
[27] DANIEL P. FRIEDMANMITCHELL, WANDCHRISTOPHER T. HAYNES, ESSENTIALS OF PROGRAMMING
LANGUAGES, THE MIT PRESS, LONDON, 2001.
[28] MATTHIAS FELLEISEN, ROBERT BRUCE FINDLER, MATTHEW FLATT, SHRIRAM KRISHNAMURTHI, HOW
TO DESIGN P ROGRAMS AN I NTRODUCTION TO C OMPUTING AND PROGRAMMING , THE MIT P RESS ,
LONDON, 2001.
[29] HAROLD ABELSON, GERALD JAY SUSSMAN, JULIE SUSSMAN, STRUCTURE AND INTERPRETATION OF
COMPUTER PROGRAMS, THE MIT PRESS, LONDON, 1996.
[30] JON ORWANT, JARKKO HIETANIEMI, JOHN MACDONALD, MASTERING ALGORITHMS WITH PERL,

4

O’REILLY, SEBASTOPOL, 1999.
[31] PETER DRAKE, DATA STRUCTURES AND ALGORITHMS IN JAVA, PRENTICE HALL, UPPER SADDLE RIVER,
2006.
[32] IAN PARBERRY, WILLIAM GASARCH, PROBLEMS ON ALGORITHMS, PRENTICE HALL, DENTON, 1994.

7 Evaluation
Interrogation(s)
dispensatoire (s) à
12/20

Travail année %
par rapport à la
note totale

Matière faisant
X
l’objet
de l’évaluation
X
Ecrit
X
Oral
X
Durée
X
Questionnaire
Aucune dérogation aux règles ci-dessus ne sera admise.

5

Examen % par
rapport
à la note totale

X

Tout à 100%

X
X
X
X

V
X
4h
X

Chapitre 1 : Entrée – Traitement Sortie :
Notion de base

Définition :

Algorithme : méthode composé d’un nombre fini d’étape en 1 temps fini.

Algorithme n° 01 : Afficher la somme de deux nombres.
Début
a, b :
Ecrire
Lire a
Ecrire
Lire b
Ecrire

entier
"1ère valeur :"
"2ème valeur :"
"Résultat " a+b

Fin

Remarque : A la définition des variables, beaucoup de langage de programmation remplissent les
nouvelles variables avec un "Je ne sais quoi" c'est-à-dire un chiffre qui n'a pas encore était entré, elle
n'est donc pas vide.

Algorithme n° 02 : Afficher effectuer une sommes de deux nombres mais
affecter cette valeur dans une variable.
Début
a, b, c : entier
Ecrire "1ère valeur :"
Lire a
Ecrire "2ème valeur :"
Lire b
c  a + b
Ecrire "Résultat " c
Fin

Symbole


Affecter,
assigner,
donner à

Règle n°01

Entrée

6

Traitement

Sortie

Algorithme n° 03 : Comparer le résultat entre une résolution de type PC (C)
et une résolution de type algorithmique.
Début
x, y, z : réel
x  1000/3
Y  x*333
Z  3*y-1
Ecrire z

•3 * ( x - 333 ) - 1
•3*(1000/3-333 ) - 1
•1000 - 999 - 1
•0

•0,000 031

Fin

Algorithme 4 : Inverser le contenu de 2 variables (avec une variable
temporaire).
Début

Début
a, b, tmp: entier
Ecrire "2 Valeurs"
Lire a, b
tmp  a
a  b
b  tmp
Ecrire a, b

a, b, tmp: entier
Ecrire "2 Valeurs"
Lire a, b
tmp  b
b  a
a  tmp
Ecrire a, b

OU

Fin

Fin

Algorithme 5 : Inverser le contenu de 2 variables (sans variable
temporaire).
Début

Faire la preuve

a, b: entier
Ecrire "2 Valeurs"
Lire a, b
b  a + b
a  b – a
a + b - a
b  b – a
a + b - a
Ecrire a, b

Pour vérifier, il faut être formelle et
cela grâce avec la méthode de remplacement
avec des lettres.

Algorithme 6 : l'incrémentation

Fin

Début

Fin

7

a : entier
Ecrire "Entrez A"
Lire a
a  a + 1
Début
Ecrire a
a, b :
Ecrire
Lire a
b  a
Ecrire
Fin

entier
"Entrez A"
+ 1
b

Algorithme 7 : Calculer la somme des n premier nombre impaire
Un nombre impaire est par formule = 2𝑖𝑖 − 1 ∀ 𝑖𝑖 ∈ ℕ0
Dès lors ∑𝑛𝑛𝑖𝑖=1(2i − 1) = ∑𝑛𝑛𝑖𝑖=1 2i − ∑𝑛𝑛𝑖𝑖=1 1

Début

n, s : entier
Ecrire "La valeur de n"
Lire n
s  n²
Ecrire s

= 2 ∑𝑛𝑛𝑖𝑖=1 i − n =

2 n ( n+1 )
2

− n = n²

Fin

Algorithme 8 : Ecrire un algorithme définissant les variables entières a et b
cette algorithme effectuera les opérations suivante : a + b; a –b; a * b; a / b; a
mod b.
Début

!!! Attention !!!
En ce qui concerne la division et le
modulo (le calcule du reste), il est
impossible d'effectuer une division
ou modulo par 0, et donc on va
ajouter une méthode pour rendre
l'algorithme intelligent, et va donc
vérifier si l'utilisateur n'a pas mis
un 0. Ce sujet sera abordé dans la
2ème partie

a, b, d, p, q, r, s : entier
Ecrire "A et B"
Lire a, b
s  a + b
d  a – b
p  a * b
q  a / b
r  a mod b
Ecrire d, p, q, r, s
Fin

Algorithme 9 : Ecrire un algorithme calculant la somme de n premier
nombre.
Début
a, b,: entier
Ecrire "A"
Lire a
b  (a (a + 1)) / 2
Ecrire b
Fin

8

Algorithme 10 : Ecrire un algorithme la somme des carrés de n premier
nombre entier.
Début
n, b : entier
Ecrire "N"
Lire n
b  (n(n+1)*(2*n+1))/6
Ecrire b
Fin

Algorithme 11 : Ecrire un algorithme de conversion de °F en °C
Début
c, f : réel
Ecrire "en F°"
Lire f
c  (5*(f-32))/9
Ecrire c

En algorithme tous comme les langages
de programmations, la règle des
priorités en vigueur.

Fin

Algorithme 12 : Ecrire un algorithme
qui affiche la résistance équivalente à 3
résistances r1, r2, r3 si elles sont
branchées en série et en parallèle.

Exposant – Racine
Parenthèse
Produit – Division
Somme – Différence
Il faut donc utiliser des parenthèses pour
les fractions.

Début
r1, r2, r3, p, s: entier
Ecrire " r1, r2, r3 "
Lire r1, r2, r3
s  r 1 + r2 + r 3
p  (r1 + r2 + r3)/( r1* r2+ r1* r3+ r2* r3)
Ecrire p, s
Fin

Algorithme 13 : Ecrire un algorithme qui calcule et affiche la distance entre
2 point a et b du plan dont les coordonnées sont�𝒙𝒙𝒙𝒙𝒂𝒂� �𝒚𝒚𝒚𝒚𝒂𝒂�.
𝒃𝒃

𝒃𝒃

Début
x1, x2, y1, y2, d: entier
Ecrire " 2 points "
Lire x1, x2, y1, y2

Fin
9

d  �(x1 − x2)² + ( y1 − y2)²
Ecrire d

Chapitre 2 : La prise de décision

Algorithme 14 : Recherche la valeur de x dans une équation du 1er degré.
Début

a, b, c, x : réel
Ecrire "3 Valeurs"
Lire a, b, c
x  (c-b)/a
Ecrire x

!!! ATTENTION !!!
Si a est nul, le programme plantera et ne
continuera pas. Car la division par 0 est
impossible.

Fin

Structure alternative : Organigramme 1ère forme
A

?

Oui

B

Non

Les Conditions
Affirmation
Négation
(contraire de
l'affirmation)
𝒂𝒂 = 𝒃𝒃
𝑎𝑎 ≠ 𝑏𝑏
𝒂𝒂 ≠ 𝒃𝒃
𝑎𝑎 = 𝑏𝑏
𝒂𝒂 < 𝑏𝑏
𝑎𝑎 ≥ 𝑏𝑏
𝒂𝒂 ≤ 𝒃𝒃
𝑎𝑎 > 𝑏𝑏
𝒂𝒂 > 𝑏𝑏
𝑎𝑎 ≤ 𝑏𝑏
𝒂𝒂 ≥ 𝒃𝒃
𝑎𝑎 < 𝑏𝑏

C

Algorithme 14 : Recherche la valeur de x dans une équation du 1er degré.

Ajout d'une notation : La structure
Alternative.
…
SI [condition] alors
Si la condition est remplie (Vrai)
…
Sinon
Si la condition n'est pas remplie
(Faux)
…
FSi
…

Début
a, b, c, x : réel
Ecrire "3 Valeurs"
Lire a, b, c
Si a ≠ b alors
x  (c-b)/a
Ecrire x
Fsi
Fin

10

Algorithme 15 : Recherche la valeur de x dans une équation du 1er degré.
A

Structure alternative : Organigramme 2ème forme
Non

C

?

Oui

B

D

Début

1ère
Possiblité

a, b, c, x : réel
Ecrire "3 Valeurs"
Lire a, b, c
Si a ≠ 0 alors
x  (c-b)/a
Ecrire x
Sinon
Ecrire "Impossible
de réalisé
l'opération."
Fsi

Début
a, b, c, x : réel
Ecrire "3 Valeurs"
Lire a, b, c
Si a = 0 alors
Ecrire "Impossible
de réalisé
l'opération."
Sinon
x <-- (b - c) / a
Ecrire x
Fsi

2ème
possibilité

Fin

Fin

Algorithme 16 : Connaître le signe d'un produit sans le calculer.
Début

Début
a, b: réel
Ecrire "2 Valeurs"
Lire a, b
Si a ≥ 0 alors
Si b ≥ 0 alors
Ecrire '+'
Sinon
Ecrire '-'
Fsi
Sinon
Si b ≥ 0 alors
Ecrire '-'
Sinon
Ecrire '+'
Fsi
Fsi
Fin

Début
a, b: réel
c : caractère
Ecrire "2 Valeurs"
Lire a, b
Si (a0 et b≥ 0) ou (a<0 et b<0)
alors
c  '+'
Sinon

a, b: réel
c : caractère
Ecrire "2 Valeurs"
Lire a, b
Si a ≥ 0 et b ≥ 0 alors
c  '+'
Sinon
Si a <0 et b < 0 alors
c  '+'
Sinon
Fin
c  '-'
Fsi
Fsi

c  '-'
Fsi

Fin

ET et du OU : Tableau de vérité
ET

OU
Condition 1

Condition 2

Réponse

Condition 1

Condition 2

Réponse

O
O
I
I

O
I
O
I

O
I
I
I

O
O
I
I

0
I
O
I

O
O
O
I

Pour le Ou, il ne suffit que d'avoir une seule condition vrai et la
réponse est vrai.
Pour le Et, il est impérative que toutes conditions soient vrai pour
envoyé une réponse vrai.

11

Algorithme 17 : Connaître le signe d'une somme.
Etude des différents cas possibles
I.

+

II.

+

III.

-

IV.

-

V.

+

VI.

-

VII.

+

VIII.

-

Analyse:
Début

|a|<|b| dans les cas 1, 3, 5, 8
b > 0  (+)
b < 0  (-)

a, b: réel
c : caractère
Ecrire "2 Valeurs"
Lire a, b
Si |𝑎𝑎| < |𝑏𝑏| alors
Si 𝑏𝑏 < 0 alors
c  '-'
Sinon
c  '+'
Fsi
Sinon
Si a < 0 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎
c  '+'
Sinon
c  '-'
Fsi
Fsi
Ecrire c

|a|>|b| dans les cas 2, 4, 6, 7
a > 0  (+)
a < 0  (-)

Fin

Algorithme 18 : Le booléen
Les variables :
Réel -> réel
Entier  Entier
1 caractère  caractère
Booléen  Booléen

Début

Fin

12

a, b : entier
c : booléen
Ecrire "2Valeurs"
Lire a,b
c  (( 𝑎𝑎 ≥ 0 𝑒𝑒𝑒𝑒 𝑏𝑏 ≥ 0)𝑜𝑜𝑜𝑜 (𝑎𝑎 < 0 𝑒𝑒𝑒𝑒 𝑏𝑏 < 0)
Ecrire c

Algorithme 19 : Connaitre le signe d'un nombre en du booléen
Début
a, b : entier
c : booléen
Ecrire "2Valeurs"
Lire a, b
c  (( 𝑎𝑎 ≥ 0 𝑒𝑒𝑒𝑒 𝑏𝑏 ≥ 0)𝑜𝑜𝑜𝑜 (𝑎𝑎 < 0 𝑒𝑒𝑒𝑒 𝑏𝑏 < 0)
Ecrire c
Si c alors 'Si c = vrai  alors cela donne directement le vrai
Ecrire '+'
Sinon 'Si c = faux
Ecrire '-'
Fsi
Fin

Algorithme 20 : Lisez 2 nombre, soustrayait le plus grand du plus petit et
imprimez le résultat.
Début

a, b, c : réel
Ecrire "2 Valeurs"
Lire a, b
Si a > b alors
c  b –a
Sinon
c  a -b
Fsi
Ecrire c
Fin

Algorithme 21 : Ecrivez un Algorithme permettant d'obtenir les solutions
réels d'une équation du seconde réel de la forme ax² + bx c = 0.
Analyse
Début
a, b, c, d, r1, r2 : réel
Ecrire "ax² + bx + c = 0"
Lire a, b, c
d = b² - 4*a*c
Si d > 0 alors

ax² + bx + c = 0
∆= 𝑏𝑏 2 − 4. 𝑎𝑎. 𝑐𝑐
−𝑏𝑏 ± √∆

∆>0:

−𝑏𝑏

∆=0:

2𝑎𝑎

r1  (-b + √△)/2𝑎𝑎

2𝑎𝑎

∆ > 0 :∄ 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 ℝ

Sinon

Si d = 0 alors
r1  -b /2𝑎𝑎
Ecrire r1
Sinon
Ecrire "Pas de réponse"
Fsi
Fsi
Fin

13

r2  (-b - √△)/2𝑎𝑎
Ecrire r1, r2

Algorithme 22 : Ecrivez un algorithme donnant les solutions réels d'une
équation bi carrée ax4 + bx² + c = 0.
Analyse

Début
a, b, c, d, r1, r2 : réel
Ecrire " ax4 + bx² + c = 0"
Lire a, b, c
d  b² - 4*a*c
Si d > 0 alors

ax4 + bx² + c = 0
posons y = x²
ay² + by + c = 0
∆= 𝑏𝑏 2 − 4. 𝑎𝑎. 𝑐𝑐

�−𝑏𝑏+ √𝑑𝑑�

r1  �

2𝑎𝑎

−𝑏𝑏 ± √∆

∆>0:

�−𝑏𝑏− √𝑑𝑑�

r2 �

−𝑏𝑏

∆=0:

2𝑎𝑎

Ecrire r1, -r1, r2, -r2

Sinon

2𝑎𝑎

∆ > 0 :∄ 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 ℝ
Et donc la réponse devra être la
racine carrée de la réponse r1 et
r2

Si d = 0 alors
−𝑏𝑏

r1  �

2𝑎𝑎

2𝑎𝑎

Ecrire r1
Sinon

Ecrire "Pas de réponse"
Fsi
Fsi
Fin

Algorithme 23 : Ecrivez un algorithme calculant l'inverse d'une valeur réel,
cet algorithme ne doit jamais produire d'erreur.
Début
a, b: réel
Ecrire " 1 Valeur"
Lire a
Si a = 0 alors
Ecrire "Erreur"
Sinon
b = 1/a
Fsi
Ecrire a
Fin

Algorithme 24 : Ecrivez un Algorithme permettant d'élevé un nombre à une
puissance quelconque cette algorithme ne doit jamais produire d'erreur.
Début
a, b, c : réel
Ecrire "2 valeurs"
Lire a, b
Si a = 0 alors
Ecrire "Erreur"
Sinon
c = 𝑒𝑒𝑒𝑒𝑒𝑒(log(𝑏𝑏, 𝑎𝑎))
Ecrire c
Fsi

𝑎𝑎𝑏𝑏 𝑎𝑎 > 0
log 𝑎𝑎𝑏𝑏

𝑎𝑎𝑏𝑏 = 𝑒𝑒 𝑏𝑏 𝑙𝑙𝑙𝑙𝑙𝑙

14

Fin

Chapitre 3 : Les itérations a bornes
définies

Algorithme 25 : Faire les sommes des N nombres.
i1
Début
i, n, s: entier
Ecrire "Valeur"
Lire n
Pour i de 1 à n faire
ss+1
FPour
Ecrire S

𝑖𝑖 ≤ 𝑛𝑛

Non

B

Oui
Traitement

Fin
ii+1

Algorithme 26 : Faire la moyenne arithmétique des tailles d'une
classe.
Début
i, n: entier
s, v : réel
Ecrire "Nombre"
Lire n
s0
Pour i de 1 à n faire
Ecrire "Taille"
Lire v
ss+v
FPour
ss/n
Ecrire s
Fin

15

Algorithme 27: Connaître le maximum d'une série de valeur.
Début
i, n, max, v: entier
Ecrire "Nombre"
Début
Lire n
i, n, max, v: entier
Si n ≠ 0 alors
Ecrire "Nombre"
Ecrire "Valeur"
Lire n
Lire max
max  0 (ou -∞)
Pour i de 1 à n faire
Pour i de 1 à n faire
Ecrire "Taille"
Ecrire "Taille"
Lire v
Lire v
Si v > max alors
Si v > max
max  v
max  v
FSi
FSi
Copie de l’entrée. Il ne
FPour
FPour
changera pas v (X2  v) si
Ecrire max
Ecrire max
x2 change
FSi
Fin
Fin

Algorithme 28: Connaître le minimum d'une série de valeur.
Début
i, n, min, v: entier
Ecrire "Nombre"
Début
Lire n
i, n, min, v: entier
Si n ≠ 0 alors
Ecrire "Nombre"
Ecrire "Valeur"
Lire n
Lire max
min  +∞
Pour i de 2 à n faire
Pour i de 1 à n faire
Ecrire "Taille"
Ecrire "Taille"
Lire v
Lire v
Si v > max alors
Si v < min
min  v
min  v
FSi
FSi
FPour
FPour
Ecrire min
Ecrire min
FSi
Fin
Fin

Algorithme 29 : Pouvoir donner l'infini.
Le float : la norme IEEE 754.

16

Algorithme 30 : Ecrire les x premiers nombre entier.
X = 20

X = 30

Début

Début
i : entier
pour i de 1 à 19 faire
Ecrire i
FPour

X = Constante
Début

Fin

Fin

Constante n=50
i : entier
pour i de 1 à n-1 faire
Ecrire i
Fsi

i : entier
pour i de 1 à 29 faire
Ecrire i
FPour
Fin

Algorithme 31 : Afficher les nombres impaires et les nombres paires et
compris entre 1 et n.

Début

Début
i, n : entier
Ecrire "Nombre"
Lire n
Pour i de 1 à n faire
Si i mod 2 = 0 alors
Ecrire i
Fsi
FPour
Pour i de 1 à n faire
Si i mod 2 ≠0 alors Fin
Ecrire i
Fpour

i, n : entier
Ecrire "Nombre"
Lire n
Pour i de 2 à n par pas 2 faire
Ecrire i
FPour
Pour i de 1 à n par pas 2 faire
Ecrire i
FPour

Fin

Algorithme 32 : Faire une table de multiplication.
Début
i, j, n : entier
Ecrire "Valeur"
Lire
Pour i de 1 à n faire
Pour j de 1 à n faire
Ecrire (i*j) 'Exécuté n²
FPour
Fpour
Fin

17

Algorithme 33 : Ecrivez un algorithme lisant un nombre entier et
déterminant tout ces diviseurs. Début
i, n : entier
Ecrire "Valeur"
Lire n
Pour i de 1 à n/2 faire
Si n mod i = 0 alors
Ecrire i
FSi
FPour
Ecrire n

Début
i, n : entier
Ecrire "Valeur"
Lire n
Pour i de 1 à n faire
Si n mod i = 0 alors
Ecrire i
FSi
FPour
Fin

Fin

Algorithme 34: Entrez n nombre formant un vecteur u, calculez la
norme de ce vecteur. (�∑𝒏𝒏𝒊𝒊=𝟏𝟏 𝒖𝒖²)

Début
i, n, u, s : entier
Ecrire "Valeur"
Lire n
Pour i de 1 à n faire
Ecrire "U"
Lire u
s  s + u²
FPour
Fin

Ecrire √𝑠𝑠

Algorithme 35 : Ecrivez un algorithme calculant la somme des n
𝟏𝟏

premiers terme de la série harmonique. (∑+∞
𝒊𝒊=𝟏𝟏 )
𝒊𝒊

Début

i, n, s : entier
Ecrire "Valeur"
Lire n
Pour i de 1 à n faire
s=s+
FPour
Ecrire s
Fin

18

1
𝑖𝑖

Algorithme 36 : Ecrivez un algorithme qui traite n nombre réel positif
ou négatif, les nombres sont lues, n est défini comme un constante en
tête de l'algorithme. L'algorithme calcule la somme des nombres
positif et la somme des nombres négatifs, il écrit ses sommes ainsi que
le nombre d'élément de chaque une d'elle.
Début
ip, in, sp, sn, v : réel
n : entier
Ecrire "Valeur"
Lire n
ip = 0
in = 0
Pour i de 1 à n faire
Ecrire "Valeur"
Lire v
Si v < 0 alors
sn = sn + v
in = in + 1
Sinon
sp =sp+v
ip=ip+1
Fsi
FPour
Ecrire sp"Somme positif pour "ip" nombre positif"
Ecrire si"Somme négative pour "is" nombre négatif"
Fin

Algorithme 37 : Ecrivez un algorithme qui vérifie cos 2x = 2 cos²x – 1.
sin

cos

19

Début
Constante n = 360
i: entier
x: réel
x
pour i de 1 à n faire
Ecrire cos(2*x), 2*cos(x)*cos(x)-1
x x + 2Pi/n
fpour
Fin

Algorithme 38 : Le mathématicien italien Leonardo Fibonatchi, qui
vivait a Pise s'est posé le problème crucial de savoir combien de
couple de lapin serait engendré au bout de n période de reproduction.
Il supposa pour cela que chaque couple peut engendre un nouveau
couple à partir de la 2ème génération. Autre hypothèse nulle animal
n'est supposée mourir pendant la période étudiée. Essayé de trouve
un algorithme de calcul de nombre représentant la population de la
unième génération.
Début
F0
F1
F2
F3
F4
F5
F6

=
=
=
=
=
=
=

0
1
1
2
3
5
8

F0 =0
F1 = 0
𝐹𝐹𝑖𝑖 = 𝐹𝐹𝑖𝑖−1 + 𝐹𝐹𝑖𝑖−2

I, n, f0, f1,fn : entier
Ecrire "n?"
Lire n
F0  0
F1  1
Fn  n
Pour i de 2 a n faire
Fn  f0 + f1
F0  f1
F1  Fn
FPour

∀𝑖𝑖 > 1

Fin

Algorithme 39: Ecrire un algorithme qui dessine un sapin de n rangée.
Début
i, j, n: entier
Ecrire "n?"
Lire n
Pour i de 1 à n faire
Pour j de 1 à n – i faire
Ecrire " "
FPour
Pour j de 1 à 2i – 1 faire
Ecrire "*"
Fpour
Ecrire CRLF 'Passage à la ligne
Fpour
Fin

20

n-i

*
***
*****
*******
*********
***********
*************

i
1|1
2|3
3|5
4| 7
5|9

n

2i - 1

Algorithme 39: Ecrire un algorithme qui dessine un sapin de n rangée.
n-i

1
232
34543
4567654
567898765
67890109876
7890123210987

21

i
1|1
2|3
3|5 n
4|7
5|9
6 | 13 2i - 1

Début
i, j, n: entier
Ecrire "n?"
Lire n
Pour i de 1 à n faire
Pour j de 1 à n – i faire
Ecrire " "
FPour
Pour j de 1 à 2i – 1 faire
Pour k de 1 à n faire
Ecrire 10 mod i
Pour k de n à n-i
Fpour
Ecrire CRLF 'Passage à la ligne
Fpour
Fin

Chapitre 5 : Boucle tant que
La boucle "tant que" à été crée pour itérée un ensemble
vide.

Si la condition est déjà remplie avant d'arriver dans la boucle,
la boucle ne sera pas exécutée.

Algorithme 40 : Disposez une suite de nombre
entré par l'ordinateur et additionné- les.
Début
v, s: entier
Ecrire "Valeur"
Lire v
s0
Tant que v ≠ 0 faire
s  s+v
Ecrire "Valeur"
Lire v
FTant
Ecrire s
Fin.

Algorithme 41: Faire la moyenne de plusieurs cotes
Début
v, cpt: entier
s: réel
cpt  0, s  0
Ecrire "Valeur"
Lire v
Tant que v ≥ 0 faire
ss+v
cpt  cpt + 1
Ecrire "Valeur"
Lire v
FTant
Si cpt ≠ 0 alors
S  s /cpt
Ecrire s
FSi
Fin.

22

Initiation

Pas le
dernier

Non
Traitement

Oui
Traitement

Suivant

Fait dans un livre d'algorithme
Début
v, s: entier
v0
s0
Tant que v ≠ −1 faire
Ecrire "Valeur"
Lire v
Si v≠ 1 alors
s  s+v
Fsi
FTant
Ecrire s
Fin.

Dans un tant que on ne met pas de OU mais plutôt des ET ainsi que d'utilisé surtout des négations.
Tant que je ne suis pas arrivé à l'école, je continue de marché.
Tant qu'il n'est pas 10h15 ou que je n'ai pas fini de terminé mon cours, je ne
m'arrête pas.
Tant que l'eau n'est pas arrêtée, je continue de me laver

Algorithme 41 : Interactivité avec l'utilisateur – Lui permettre un choix
Début
Choix : entier
Ecrire "Choisir"
Lire choix
Tant que choix ≠ 1 𝑒𝑒𝑒𝑒 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜 ≠ 2 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓
Ecrire "Choisir"
Lire Choix
Ftant
Fin.

Rappel :
Table de vérité
de ET
O O O
O I
O
I
O O
I
I
I

1
𝑐𝑐 > 1 𝑜𝑜𝑜𝑜 𝑐𝑐 > 10 Pas possible
𝑐𝑐 < 1 𝑜𝑜𝑜𝑜 𝑐𝑐 > 10

2
Début
c: entier
Ecrire "Choix"
Lire c
Tant que pas (𝑐𝑐 ≥ 1 𝑒𝑒𝑒𝑒 𝑐𝑐 ≤ 10) faire
Ecrire "Choix"
Lire c
FTant
Fin.

Algorithme 42 : Ecrivez un algorithme calculant le maximum et le minimum
d'une série de valeur terminée par 0 (marque la fin par 0)
Début
v, max, min
Ecrire "Valeur"
Lire v
Max  -∞
Min  ∞
Tant que v ≠ 0 faire
Si v > max alors
Max  v
23

Fsi
Si v < min alors
Min  v
Fsi
Ecrire "Valeur"
Lire v
Ftant
Ecrire Max, min
Fin

Algorithme 43: Concevez un algorithme comptant le nombre de couple LE
d'une phrase terminée par un POINT.
Début
Cpt : entier
c, p : caractère
Cpt  0
P  'x' 'Tous sauf un "l"
Ecrire "Phrase"
Lire c
Tant que 𝑐𝑐 ≠′ . ′ faire
Si c = 'e' et p = 'l' alors
Cpt  cpt + 1
Fsi
Pc
Lire c
Ftant
Ecrire Cpt
Fin.

Algorithme 44 : Ecrivez un algorithme comptant le nombre de mot d'une
phrase terminée par un point, les mots son séparez par au moins un espace.
Début
Cpt : entier
C, p : caractère
Cpt  0
P''
Ecrire "Phrase"
Lire c
Tant que 𝑐𝑐 ≠′ . ′ faire
Si 𝑝𝑝𝑝𝑝𝑝𝑝(c ≠ ' 'and c = ' ') alors
Cpt  cpt + 1
Fsi
Pc
Lire c
Ftant
Ecrire Cpt
Fin.

Algorithme 45 : Rédigé un algorithme qui réalise le jeu suivant :
•
•

24

A tour de rôle, l'ordinateur et le joueur choisissent un nombre qui ne peux prendre que 3
valeurs 0, 1, 2.
Si la différence entre les nombre choisi vaut :
- 2 : Le joueur qui a proposé le plus grand nombre gagne un point

•
•

- 1 : Le joueur qui a proposé le plus petit nombre gagne un point
- 0 : Aucun point n'est marqué
Le jeu se termine quand l'un des deux joueurs totalise 10 points.
Ou quand l'être Humain introduit un nombre négatif indiquant sa volonté d'arrêté.

Début
Ph, po, ch, co: entier
Ph  0
Po  0
Ecrire "Valeur"
Lire ch
Co  aléatoire(0,2)
Tant que ph < 10 et ch≥ 0 faire
Selon |ch - co|
C0s2: si ch > co alors
Ph  ph +1
Sinon
Po  po + 1
Fsi
FCas

Cos1 : Si ch < co alors
Ph  ph + 1
Sinon
Po  po + 1
Fsi
FCase
Fselon
Ecrire po, ph
Ecrire "Valeur"
Lire Ch
Co  aléatoire (0,2)
Ftant
Ecrire po, ph
Fin.

Algorithme 46 : Calculé par des soustractions successives le quotient entier
et le reste de la division entier de deux entier entré au clavier.
15 4

15
-4
7
-4
3

15 4
3 3

Début
Nbre1, nbre2, cpt : entier
Ecrire "2Valeurs"
Lire nbre1, nbre2
Cpt  0
Si nbre2 ≠ 0 alors
Tant que nbre1 > nbre2
Nbre1  nbre1 – nbre2

Cpt  cpt +1
FTant
Ecrire Nbre1, cpt
Sinon
Ecrire "Impossible"
Fsi
Fin

Algorithme 47 : Lisez un nombre entier et déterminé s'il est premier.

25

Début
N, i : entier
Ecrire "Valeur"
Lire n
I2
Tant que n mod i ≠ 0 alors
Ii+1
Ftant
Si i = n alors
Ecrire "Premier"
Sinon
Ecrire " pas premier"
Fsi
Fin

Début
N, i : entier
Ecrire "Valeur"
Lire n
I2
Tant que n mod i ≠ 0 et 𝑖𝑖 ≤ √𝑛𝑛 alors
I1+i
Ftant
Si 𝑖𝑖 ≥ √𝑛𝑛 alors
Ecrire "Premier"
Sinon
Ecrire "Pas premier"
Fsi
Fin

Chapitre 6 : Boucle répété jusqu'à ce que
Initiation

Suivant

Traitement

1 1 1 1
+ − + + ….
3 5 7 9
+∞
1
= �(−1)𝑖𝑖+1
2𝑖𝑖 − 1
𝑆𝑆 = 1 −
𝑖𝑖=1

1−

S0

1 1 1 1
+ − + + ….
3 5 7 9

S1

Fin?

Algorithme 48: Calculer pi / 4

…

Le choix du "répéter jusqu'à ce que" est
bonne car il faut l'acquisition d'une deuxième
valeur.

Début
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝜀𝜀 = 10−5
S0, S1 : réel
i : entier
S1  1
i0
Répéter
S0  S1
ii+1
S1  S0 + (−1)𝑖𝑖 /(2𝑖𝑖 + 1)
Jusqu'à ce que |S0 – S1| < 𝜀𝜀
Ecrire S0
Fin.

Algorithme 49 : Calculer pi / 4 avec un si
Début
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝜀𝜀 = 10−5
S0, S1 : réel
i : entier
S1  1
i0
Répéter
S0  S1
ii+1
Si i mod 2 = 0 alors
S1  S0 + 1 /(2𝑖𝑖 + 1)
Sinon

S1  S0 - 1 /(2𝑖𝑖 + 1)
Jusqu'à ce que |S0 – S1| < 𝜀𝜀
Ecrire S0
Fin.
26

Début
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝜀𝜀 = 10−5
S0, S1 : réel
I, signe : entier
S1  1
i0
signe  1
Répéter
S0  S1
ii+1
Signe  - signe
S1  S0 + Signe/(2i +1)
Jusqu'à ce que |S0 – S1| < 𝜀𝜀
Ecrire S0
Fin.

Algorithme 50 : Ecrivez l'algorithme de Newton

L'algorithme de newton
1 + 𝑎𝑎
2
𝑎𝑎
𝑥𝑥𝑛𝑛 +
𝑥𝑥𝑛𝑛
𝑛𝑛 > 0
𝑥𝑥0 =
2
a=2
5
𝑥𝑥0 = = 2,5
2
5 2∗4
+
5 = �5 + 8� ∗ 1
𝑥𝑥1 = 2
2
2 5 2
41
= = 2.05
𝑥𝑥0 =

20

41 4 ∗ 20
+
41 = �41 + 80� ∗ 1
𝑥𝑥2 = 20
2
20 41 2
= 2.0006

Début
Const E = 10−5
x0, x1, a : réel
Ecrire "Valeur"
Lire a
x1  (1+a)/2
Répéter
x0  x1
x1 (x0 +a/x0)/2
Jusqu'à ce que |x0 – x1| < E
𝑥𝑥0 – 𝑥𝑥1
Ecrire x0
|
|
𝑥𝑥0
Fin.

Utiliser par les processeurs
afin de réaliser les racines
carrés. Car cette méthode
améliore le résultat décimal

+∞
Algorithme 51 : Ecrivez un algorithme qui produit 𝒆𝒆𝒙𝒙 = ∑𝒏𝒏=𝟎𝟎

Début
Const ℇ = 10−5
x, x0, x1: réel
i: entier
Entrez "Valeur"
Lire x
Devient alors
x1  1
i0
Répéter
Temps : n²
X0  x1
ii+1
S1  s0 + 𝑥𝑥 𝑖𝑖 /𝑖𝑖!
Nn+1
Jusqu'à ce que |x0 – x1| < E
Fin.



27

i–1
I–1
1
----2i - 1

𝒙𝒙𝒏𝒏
𝒏𝒏!

Même énoncé mais e diminuant
les calculs
Début
Const ℇ = 10−5
x, x0, x1, y : réel
i, j : entier
Entrez "Valeur"
Lire x
x1  1,
i0,
y  1,
j1
Répéter
x0  x1
ii+1
Temps : 3n
yy*x
jj*i
x1  x0 + j/y
Jusqu'à ce que |x0 – x1| < E
Fin.

𝒏𝒏 𝒏𝒏
1
Algorithme 52 : Ecrivez l’algorithme de ∑+∞
𝒏𝒏=𝟎𝟎(−𝟏𝟏) 𝒙𝒙 = 1 – x + x² - x³ +
x4+… |x| < 1

Début
Const ℇ = 10−5
x, S0, S1: réel
n: entier
Entrez "Valeur"
Lire x
S1  1
Devient alors
n0
Répéter
S0  S1
nn+1
S1  S0 + (-1)n xn
Jusqu'à ce que |S0 – S1| < E
Ecrire S0
Fin.

Début
Début
−5
Const ℇ = 10
Const ℇ = 10−5
x, S0, y, z, S1: réel
x, S0, y, S1: réel
n: entier
Entrez "Valeur"
Entrez "Valeur"
Lire x
Lire x
S1  1
S1  1
y1
x  -x
n0
Répéter
y  -1
S0  S1
z1
yy*x
Répéter
S1 S0 + y
S0  S1
Jusqu'à ce que |S0 – S1| < E
nn+1
Ecrire S0
y=-y
Fin.
zz*x
S1 S0 + y * z
Jusqu'à ce que |S0 – S1|< E E
Ecrire S0
Fin.

O
U

𝒙𝒙𝒏𝒏

𝒏𝒏
Algorithme 52 : Ecrivez l’algorithme de ∑+∞
𝒏𝒏=𝟎𝟎(−𝟏𝟏) (𝟐𝟐𝟐𝟐+𝟏𝟏)!

Début
Const ℇ = 10−5
x, S0, S1: réel
n: entier
Entrez "Valeur"
Lire x
S1  x
Devient alors
n0
Répéter
S0  S1
nn+1
S1  S0 + x2n+1 /(2n+1)!
Jusqu'à ce que |S0 – S1| < E
Ecrire S0
Fin.

28

Début
Const ℇ = 10−5
X,s0, s1, y: réel
N : entier
Entrez "Valeur"
Lire x
S1  x
N0
Yx
J1
X-x*x
Répéter
S0  S1
Nn+1
Yy*x
J  j * 2n * 2n+1
S1  S0 + y / j
Jusqu'à ce que |S0 – S1|< E
Ecrire S0
Fin.

𝒙𝒙𝟐𝟐𝟐𝟐

𝒏𝒏
Algorithme 53 : Ecrivez l’algorithme de ∑+∞
𝒏𝒏=𝟎𝟎(−𝟏𝟏) (𝟐𝟐𝟐𝟐)!

Début
Const ℇ = 10−5
x, S0, S1: réel
n: entier
Entrez "Valeur"
Lire x
Devient alors
S1  x
n0
Répéter
S0  S1
nn+1
S1  S0 + x2n /(2n)!
Jusqu'à ce que |S0 – S1| < E
Ecrire S0
Fin.

Début
Const ℇ = 10−5
X,s0, s1, y: réel
N : entier
Entrez "Valeur"
Lire x
S1  1
N0
Y1
J1
X-x*x
Répéter
S0  S1
Nn+1
Yy*x
J  j * (2n – 1) * 2n
S1  S0 + y / j
Jusqu'à ce que |S0 – S1|< E
Ecrire S0
Fin.

Algorithme 54 : Ecrivez en algorithme qui détermine les n premiers
nombres de Hamming la suite doit être créée selon l’ordre croissant de ces
termes.

2, 3, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20,…

Début
Vv/3
Nbre, r, n, i : entier
Ftant
Ecrire ‘’N’’
Tant que v mod 5 = 0 faire
Lire n
Vv/5
I0
Ftant
Et je fais
nbre  2
Si v = 1 alors
l’hypothèse
Tant que n ≠ i faire
Ecrire « Hamming »
que
n
peut
être
nul
v nbre
Ii+1
Tant que v mod 2 = 0 faire
Fsi
Vv/2
Nbre  nbre +1
Ftant
Ftant
Tant que v mod 3= 0 faire
Fin.

29


La suite des nombres d
Hamming est définie comme
la séquence ordonnée des
entiers naturels n’admettant
d’autres diviseurs premiers
que 2, 3 et 5 de nombre
naturel.



Début
Nbre, r, n, i : entier
Ecrire ‘’N’’
Lire n
i0
Et je fais
nbre  1
l’hypothèse
Répéter
Nbre  nbre +1 que n ne peut être
v nbre
Tant que v mod 2 = 0 faire
Vv/2
Ftant
Fin.

Tant que v mod 3= 0 faire
Vv/3
Ftant
Tant que v mod 5 = 0 faire
Vv/5
Ftant
Si v = 1 alors
Ecrire « Hamming »
Ii+1
Fsi
Jusqu’à ce que n = cpt

Algorithme 55 : Ecrivez un algorithme demandant à l’utilisateur un entier n
et construisant un entier m composé des chiffres de n dans l’ordre inverse.
Début
N, m, i : entier
Entrez ‘n’
Lire n
M0
Tant que n ≠ 0 faire
M  m * 10 + n mod 10
N  n /10
Ecrire m
Ftant
Fin

30

Les Bibliothèques de Fonction

31

Algorithme 56 : Calcul de la distance entre deux points sur un plan.
𝑑𝑑 = �(𝑥𝑥1 − 𝑥𝑥2 )2 + (𝑦𝑦1 − 𝑦𝑦2 )²

Fonction Distance (↓x1, ↓y1, ↓x2, ↓y2 : réel) à résultat
réel
D : réel

x1 x2 y1 y2 d

X1  t
X2  u
Y1  v
Y2  w

t

Xd

D  �(𝑥𝑥1 − 𝑥𝑥2 )2 + (𝑦𝑦1 − 𝑦𝑦2 )²
Résultat d.
FFonc

u

Début
t, u, v, w, x : réel
Ecrire ‘’Valeurs 1er point’’
Lire t, u
Ecrire ‘’Valeurs 2eme point’’
Lire v, w
x  Distance(t, u, v, w)
Ecrire x
Fin

tmp

Début
X, y entier
Ecrire ‘’2 Valeurs ‘’
Lire x, y
Echange (x,y)
Ecrire x, y
Fin

32

w

X

Copie

Algorithme 57 : Procédure d’échange.

Procédure Echange (↕ 𝑎𝑎, ↕ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒)
Tmp : entier
Tmp  a
A  b
B  tmp
FProc

v

a

b

Ax
By

x

y

Xd

Tmp

a

b

x

Y

ax
by

Algorithme 58 : Permutation cyclique de 3 nombres.
Procédure Echange (↕ 𝑎𝑎, ↕ 𝑏𝑏, ↕ 𝑐𝑐, ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒, ↓ 𝑠𝑠: 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐è𝑟𝑟𝑟𝑟)
Tmp : entier
Si s = ‘g’ alors
Tmp  a
A  b
B  c
C  tmp
Sinon
Tmp  c
b  a
c  b
a  tmp
Fsi
FProc
Début
X, y, z entier
Sens : caractère
Ecrire ‘’3 Valeurs ‘’
Lire x, y, z
Ecrire ‘’Sens ? [g] = gauche - [d] = droite’’
Lire Sens
Echange (x,y,z, sens)
Ecrire x, y, z
Fin

Es

Eg
Ech
Ech

Eg
Es (g)

33

Ech

Procédure Echange (↕a,↕b∶entier)
Tmp : entier
Tmp  a
A  b
B  tmp
FProc
Procédure eg(↕ 𝑎𝑎, ↕ 𝑏𝑏, ↕ 𝑐𝑐, ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒)
Echange(a,c)
Echange(a,b)
Fproc
Procédure ed(↕ 𝑎𝑎, ↕ 𝑏𝑏, ↕ 𝑐𝑐, ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒)
Echange(a,c)
Echange(b,c)
Fproc
Procédure Es(↕ 𝑎𝑎, ↕ 𝑏𝑏, ↕ 𝑐𝑐, ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒, ↓ 𝑠𝑠: 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐è𝑟𝑟𝑟𝑟)
Si s=’g’ alors
Eg(a,b,c)
Sinon
Ed(a,b,c)
Fsi
Fproc
Fonction Es(↕ 𝑎𝑎, ↕ 𝑏𝑏, ↕ 𝑐𝑐, ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒)à résultat booléen
Res : booléen
Res  V
Si s=’g’ alors
Eg(a,b,c)
Sinon
Si s=’d’ alors
Ed(a,b,c)
Sinon
Res  F
Fsi
Fsi
Résultat Res
Fin

Algorithme 59 : Ecrivez un algorithme qui traite une fonction qui donne les
racines carrées d’une fonction du second degré.
Fonction Eq2d (↓ 𝑎𝑎, ↓ 𝑏𝑏, ↓ 𝑐𝑐 ∶ 𝑟𝑟é𝑒𝑒𝑒𝑒, ↕ 𝑥𝑥1, ↕ 𝑥𝑥2 ∶ 𝑟𝑟é𝑒𝑒𝑒𝑒) à résultat booléen
Res : boolén
Delta : réel
Res  V
Delta  b²-4ac
Si Delta ≥ 0 alors

Delta  √𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑
X1  (-b + delta) / (2*a)
X2  (-b - delta) / (2*a)
Sinon
Res  F
Fsi
Résultat Res
FFonc

Début
A, b, c, x1, x2 : réel
Ecrire ‘’3Valeur’’
Lire a, b, c
Si Eq2d(a,b,c,x1,x2) alors
Ecrire x1, x2
Sinon
Ecrire ‘’Impossible dans R’’
Fsi
Fin

Algorithme 60 : Ecrivez une fonction déterminant la racine carrée d’un
nombre par la méthode de Newton.
Fonction sqrt (↓ 𝑎𝑎: 𝑟𝑟é𝑒𝑒𝑒𝑒) à résultat réel

Const E=10−5
X0, x1 : réel
L’utilisateur doit testé si le
X1  (1+a)/2
nombre a élevée a la racine est
Répéter
positif ou nul
X0  x1
X1  (X0 + a/x0)/2
Jusqu’à ce que |(x0 – x1)/x0| < E
Résultat x1
FFonc

Algorithme 61 : Calcul de la distance entre deux point en utilisant la
fonction racine carrée
Fonction sqrt (↓ 𝑎𝑎: 𝑟𝑟é𝑒𝑒𝑒𝑒) à résultat réel

Const E=10−5
X0, x1 : réel
X1  (1+a)/2
Répéter
X0  x1
X1  (X0 + a/x0)/2
Jusqu’à ce que |(x0 – x1)/x0| < E
Résultat x1
FFonc
Fonction Distance (↓x1, ↓y1, ↓x2, ↓y2 : réel) à résultat réel
Résultat sqrt ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
Résultat d.
FFonc

34

Algorithme 62 : Appel de fonction dans un appel de fonction
Début
A, b, c : réel
Lire a, b
C  sqrt (sqrt (a) + sqrt (b))
Ecrire c
Fin

Algorithme 63 : L’incrémentation
Procédure Inc (↕ 𝑎𝑎 : entier)
A  a +1
FProc
Début
X : entier
X  4
Inc(x)
Ecrire x
Fin

Début
X, y : entier
X  2
Y  3
Inc (y+x)
…
Fin

Impossible car on ne
retourne
qu’une
seule valeur)

Algorithme 64 : Ecrivez une fonction recevant en paramètre une valeur
entière n et calculant la somme des n premier entier, la valeur de retour de
la fonction sera la somme recherchée.
Fonction SomN (↓n : entier) à résultat entier
X0,x1 : entier
X0  0
Pour i de 1 a n faire
X1  x0 + n
FTant
Résultat x1
FFonc

Fonction spe ( ↓n : entier) à résultat entier
Résultat n*(n+1)/2
FFonc

Algorithme 65 : Ecrivez une fonction déterminant de combien de chiffre est
composé un nombre entier positif non nul.
⌊ ⌋ Valeur planché
Retire les nombres décimaux

Fonction nbrech (↓n : entier) à résultat entier
Résultat ⌊𝑙𝑙𝑙𝑙(𝑛𝑛)⌋ + 1
FFonc

Pour obtenir le nombre de chiffre binaire sont nécessaire pour représenté un nombre

𝑙𝑙𝑙𝑙𝑙𝑙𝑏𝑏 𝑥𝑥
𝑙𝑙𝑙𝑙𝑙𝑙𝑎𝑎 𝑥𝑥 =
𝑙𝑙𝑙𝑙𝑙𝑙𝑏𝑏 𝑎𝑎

35

Fonction nbrech_bien (↓n : entier) à résultat entier
Résultat ⌊𝑙𝑙𝑙𝑙𝑙𝑙2 (𝑛𝑛)/𝑙𝑙𝑙𝑙𝑙𝑙10 2⌋ + 1
FFonc

Algorithme 66 : Ecrivez une fonction déterminant si une année est bissextile
ou non.
Fonction bissextile (↓a : entier) à résultat booléen
Résultat a mod 400 = 0 ou (a mod 100 ≠ 0 et a mod 4 = 0)
FFonc

Algorithme 67 : Ecrivez une fonction déterminant le plus grand de deux
nombres.
Fonction max (↓a, ↓b : entier) à résultat entier
R : entier
R : entier
Si a > b alors
R  b
R  a
Si a > b alors
Sinon
R  a
R  b
Fin
Fin
Résultat r
Résultat r
FFonc
FFonc

Algorithme 68 : Ecrivez une fonction déterminant le maximum de trois
nombre
Fonction bissextile (↓a, ↓b, ↓ 𝑐𝑐: entier) à résultat entier
R : entier
Si a > b alors
R  a
Sinon
Si b > c alors
R  b
Sinon
R  c
Fin
Résultat r
FFonc
Fonction max (↓a, ↓b : entier) à résultat entier
R : entier
Si a > b alors
R  a
Sinon
R  b
Fin
Résultat r
FFonc
Fonction max3 (↓a, ↓b, ↓c : entier) à résultat entier
Résultat max(max(a, b), c)
FFonc

36

Algorithme 69 : Le mathématicien Léonardo Fibonacci a défini une suite de
nombre qui porte son nom : écrivez une fonction écrivant le énième nombre
le Fibonacci.
F0= 0
F1=1
Fn = Fn-1 + Fn-2 ∀𝑛𝑛 ≥ 2
On inscrit ici n car si le n est
inférieur à 2 (0 ou 1), alors
fn n’aurait pas était calculé,
et le programme retournera
la valeur de n.

Fonction fibonacci (↓ 𝑛𝑛 : entier) à résultat entier
F0, f1, fn, i : entier
F0  0
F1  1
Fn  n
Pour i de 2 à n faire
Fn  f1 + f0
F0  f1
F1  fn
FPour
Résultat Fn
FFonc

Algorithme 70 : Un nombre parfait est un nombre représentant la
particularité d’être égale à la somme de tous ses diviseurs excepté luimême, le premier nombre parfait est six, il est bien égale à 1 + 2 + 3, 1 2 et
3sont bien les diviseurs de 6. Ecrivez une fonction qui détermine si un
nombre est parfait.
Fonction nparfait (↓ 𝑛𝑛 : entier) à résultat booléen
I, nbre, sdiv: entier
On aurait pu mettre
Pour i de 1 à n-1 faire
n/2 au lieu de n-1
Si (n mod I = 0) alors
SDiv  SDiv + i
Fonction nparfait (↓ 𝑛𝑛 : entier) à résultat booléen
Fsi
I, s: entier
FPour
S  1
Résultat sdiv = n
FFonc
I  2
Tant que s < n faire
Si n mod i alors
S  s + i
Fsi
I  i + 1
Ftant
Résultat s = n et i > n/2
FFonc

37

Algorithme 71 : Les nombres de Fibonacci peuvent être calculé au moyen du
nombre d’or qui à pour valeur
nombre de Fibonacci

𝟏𝟏+ √𝟓𝟓
𝟐𝟐

. Ecrivez une fonction calculant le énième

Fonction fibonacci (↓ 𝑡𝑡 : entier) à résultat entier
Const O = √5/2

Const N = 1 + √5

Const M = 1 - √5
G, n, m : réel
J : entier
G n
n  N
m  M
Si i > 1 alors
Pour j de 2 à i faire
n  n *N
m  m * M
FPour
g  O * (n/2 – m/2)
Fsi
Résultat ⌊𝑔𝑔⌋
FFonc

Algorithme 72 : Ecrivez une fonction calculant le PGCD de deux entier A et B
en utilisant les propriétés suivantes :
𝑏𝑏 𝑠𝑠𝑠𝑠 𝑎𝑎 = 0
⎧
𝑎𝑎 𝑠𝑠𝑠𝑠 𝑏𝑏 = 0
⎪
𝑎𝑎 𝑏𝑏 𝑠𝑠𝑠𝑠 𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 2 = 0
⎪ 𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 � , �
2 2 𝑠𝑠𝑠𝑠 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 2 = 0
⎪
⎪ 2𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 �𝑎𝑎 , 𝑏𝑏� 𝑠𝑠𝑠𝑠 𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 2 = 0
2
𝑠𝑠𝑠𝑠 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 2 ≠ 0
⎪
𝑏𝑏
𝑠𝑠𝑠𝑠
𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 2 ≠ 0
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃(𝑎𝑎, 𝑏𝑏)
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃
�𝑎𝑎,
�
⎨
2 𝑠𝑠𝑠𝑠 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 2 = 0
⎪
𝑠𝑠𝑠𝑠 𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 2 ≠ 0
⎪𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃(𝑎𝑎 − 𝑏𝑏, 𝑏𝑏) 𝑠𝑠𝑠𝑠 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 2 ≠ 0
⎪
𝑎𝑎 > 𝑏𝑏
⎪
𝑠𝑠𝑠𝑠 𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 2 ≠ 0
⎪𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃(𝑎𝑎, 𝑏𝑏 − 𝑎𝑎) 𝑠𝑠𝑠𝑠 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 2 ≠ 0
⎩
𝑏𝑏 > 𝑎𝑎

38

Fonction pgcd (↓ 𝑎𝑎, ↓ 𝑏𝑏 : entier) à résultat
entier
P, r : entier
P 1
Tant que que a ≠ 0 𝑒𝑒𝑒𝑒 𝑏𝑏 ≠ 0 faire
Si a mod 2 = 0 alors
Si b mod 2 = 0 alors
P  2 * p
A  a/2
B  b/2
Sinon
A  a/2
FSi
Sinon
Si b mod 2 = 0 alors
B  b/2
Sinon
Si a > b alors
A  a–b
Sinon
B  b-a
Fsi
Fsi
Fsi
FTant
Si a = 0 alors
R  p * b
Sinon
R  p * a
Fsi
Résultat r
FFonc

Algorithme 73 : Ecrivez une fonction : écrivez une méthode de « Plus Grand
Commun Multiple » par la méthode d’Euclide. Cette méthode fait intervenir
le reste de la division entier de a par b. Si le reste est nul alors b est le PGCB
sinon on remplace A par B et B par r et on itère.
Fonction PGCD (↓ 𝑎𝑎, ↓ 𝑏𝑏 : entier) à résultat entier
r: entier
r  a mod b
r: entier
Tant que r ≠ 0 faire
répéter
A  b
r  a mod b
B  r
a  b
R  a mod b
b  r
FTant
Jusqu’à ce que r = 0
Résultat B
Résultat a
FFonc
FFonc

a
48
13
9
4

b
13
9
4
1

R
9
4
1
0

Algorithme 74 : Ecrivez une fonction qui à partir d’un nombre réel appelé x
et d’une valeur entier positive appelée N retourne x à la puissance n.
Fonction PGCD (↓ 𝑥𝑥 ∶ 𝑟𝑟é𝑒𝑒𝑒𝑒, ↓ 𝑏𝑏 : entier) à résultat entier
I : entier
R : réel
Fonction PGCD (↓ 𝑥𝑥 ∶ 𝑟𝑟é𝑒𝑒𝑒𝑒, ↓ 𝑛𝑛 : entier) à résultat entier
R  1
P : réel
Pour i de 1 à n faire
P  1 ‘car si on entre exposé en 0 ca donne 1
R  r * x
Tant que n ≠ 0 faire
FPour
Si n mod 2 ≠ 0 faire
Résultat r
P  p * x
FFonc
N  n - 1
Sinon
N  n /2
X  x * x
Fsi
FFaire
Résultat r
FFonc

Algorithme 75 : Ecrivez une procédure qui réalise :
Procédure PGCD (↓ 𝑛𝑛 : entier) à résultat entier
I, j : entier
Pour i de 1 à n faire
Pour j de 1 à n-i
Ecrire ‘ ‘
FPour
Pour j de 1 à i
Ecrire ‘*’
FPour
Ecrire CRLF
FPour
Pour i de 1 à n-1 faire
Pour j de 1 à i faire
Ecrire ‘ ‘
FPour
Pour j de 1 à n-1 faire
Ecrire *
FPour
Ecrire CRLF
FFonc

39

*
** n
***
****
2n-1
***
**
*

Les automates d’Etat Fini

40

ch
1

ch
2

4

cr
3

1 : Etat Initiale
2 : Etat intermédiare
3 : Etat final
4 : Etat Erreur

Algorithme 76 : Ecrivez une fonction qui vérifie si un caractère entré est
entier jusqu'à ce que l’on a appuyé sur ENTER
Fonction Verif() à résultat booléen
Etat : entier
C : caractère
Etat  1
Répéter
Lire c
Selon que Etat faire
Cas 1 : Selon que c faire
Cas ‘0’ ;
Cas ‘1’ ;
Cas ‘2’ ;
Cas ‘3’ ;
Cas ‘4’ ;
Cas ‘5’ ;
Cas ‘6’ ;
On vérifie si le caractère entré est un
Si c n’est pas 0, 1, 2, 3, 4, 5, 7, 8 ou 9.
Cas ‘7’ ;
nombre. S’il est entré alors l’état devient 2.
Alors l’état devient 4.
Cas ‘8’ ;
Cas ‘9’ : Etat  2
Fcas
Autre : est le sinon du cas
Autre : Etat  4 ‘Default’
FCas
FSelon
FCas
Cas 2 : Selon que c faire
Cas ‘0’ ;
Cas ‘1’ ;
Cas ‘2’ ;
Cas ‘3’ ;
Cas ‘4’ ;
Cas ‘5’ ;
Cas ‘6’ ;
On vérifie si le caractère entré est un nombre.
Cas ‘7’ ;
S’il est entré alors l’état ne change pas.
Cas ‘8’ ;
Si c est CR (retour chariot)
Cas ‘9’ ;
alors l’état devient 3.
FCas
Cos ‘CR’ : Etat  3
FCas
Autre : Etat  4
FSeln
Si c n’est pas 0, 1, 2, 3, 4, 5,
FCas
FSelon
Si l’état est 3 alors, résultat sera Vrai
7, 8, 9 ou CR. Alors l’état
Fselon
devient 2.
Jusqu’à ce que etat = 3 ou etat = 4
Sinon l’état est 4 alors, résultat sera faux
Résultat etat = 3
FFonc

41

Mais la simple
retranscription du
schéma ne suffit
pas, il faut renvoyé
les nombres.

Fonction CarEnt(↓ 𝑛𝑛) à
Etat : entier
Selon que c faire
Cas ‘0’ : r  0
Cas ‘1’ : r  1
Cas ‘2’ : r  2
Cas ‘3’ : r  3
Cas ‘4’ : r  4
Cas ‘5’ : r  5
Cas ‘6’ : r  6
Cas ‘7’ : r  7
Cas ‘8’ : r  8
Cas ‘9’ : r  9
Fselon
Résultat R
FFonc

42

résultat entier

FCas
FCas
FCas
FCas
FCas
FCas
FCas
FCas
FCas
Fcas

Fonction LireEnt(↕ 𝑛𝑛: 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à résultat booléen
Etat : entier
C : Caractère
Répéter
Lire C
Selon que etat faire
Cas 1 : Selon que c faire
Cas ‘0’ ;
Cas ‘1’ ;
Cas ‘2’ ;
Cas ‘3’ ;
Cas ‘4’ ;
Cas ‘5’ ;
Cas ‘6’ ;
Cas ‘7’ ;
Cas ‘8’ ;
Cas ‘9’ :
n  carent(c)
Etat  2
FCas
Autre : etat  4
FSelon
FCas
Cas 2 : Selon que c faire
Cas ‘0’ ;
Cas ‘1’ ;
Cas ‘2’ ;
Cas ‘3’ ;
Cas ‘4’ ;
Cas ‘5’ ;
Cas ‘6’ ;
Cas ‘7’ ;
Cas ‘8’ ;
Cas ‘9’ : n  n * 10 + carent(c) Fcas
Cas ‘CR’ : Etat  3 Fcas
Autre : Etat  4
Fselon
FSelon
Jusqu’à ce que etat = 3 ou etat = 4
Résutlat Etat = 3
FFonc

Automate 2 : Ecrivez une fonction qui vérifie si un caractère entré est entier
et signé jusqu'à ce que l’on a appuyé sur ENTER

Fonction LireEntSign(↕ 𝑛𝑛: 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à résultat
booléen
Etat : entier
C : Caractère
Répéter
Lire C
Selon que etat faire
Cas 1 : Selon que c faire
Cas ‘0’ ;
Cas ‘1’ ;
Cas ‘2’ ;
Cas ‘3’ ;
Cas ‘4’ ;
Cas ‘5’ ;
Cas ‘6’ ;
Cas ‘7’ ;
Cas ‘8’ ;
Cas ‘9’ :
n  carent(c)
Etat  3
FCas
Cas ‘+’ s  1 etat  2 FCas
Cas ‘-‘ s  -1 etat  2 FCas
Autre : etat  5
FSelon
FCas
Cas 2 : Selon que c faire
Cas ‘0’ ;
Cas ‘1’ ;
Cas ‘2’ ;

43

Cas ‘3’
Cas ‘4’
Cas ‘5’
Cas ‘6’
Cas ‘7’
Cas ‘8’
Cas ‘9’
Autre :

;
;
;
;
;
;
: n  carent(c) etat  3 Fcas
Etat  5

Fselon
FCas
Cas 3 : Selon que c faire
Cas ‘0’ ;
Cas ‘1’ ;
Cas ‘2’ ;
Cas ‘3’ ;
Cas ‘4’ ;
Cas ‘5’ ;
Cas ‘6’ ;
Cas ‘7’ ;
Cas ‘8’ ;
Cas ‘9’ : n  n * 10 + carent(c) FCas
Cas ‘CR’ : n  s * n etat  4 FCas
Autre : etat  5
FSelon
FSelon
Jusqu’à ce que etat = 5 ou etat = 4
Résultat etat = 4
FFonc

Automate 3 : Concevez un automate ainsi que la fonction d’analyse associée
comptant le nombre de couple ‘le’ figurant dans une phrase terminé par un
point.
Fonction cptle() à résultat entier
Cpt, etat :entier
C : caractère
Etat  1
Cpt  0
Répéter
Lire c
Selon que etat faire
Cas 1 :
Selon que c faire
Cas ’L’, etat  2 FCas
Cas ‘.’ Etat  4 FCas
FSelon
FCas
Cas 2 :
Selon que c faire
Cas ‘e’: cpt  cpt + 1 etat  3, FCas
Cas ‘.’: etat  4, fcas
Cas ‘l’ : fcas
Autre : etat  1, fcas
FSelon
Cas 3 :
Selon que c faire
Cas ‘l’ : etat  2, fcas
Cas ‘.’ : etat  4, fcas
Autre : Etat  1, fcas
FSelon
FCas
FSelon
Jusqu’à ce que etat = 4
Résultat cpt
FFonc

Représentation
Matriciel
1 2 3 4
1 * L
.
2 * L E .
3 * L
.

Retranscription
en c

Int cptle(){
Int cpt = 0, etat = 0;
Char c;
Do{
Scanf("%c" ,&c) ;
Switch(etat){
Case 1: switch(c){
Case ‘l’:
etat = 2,
break;
Case ‘.’:
etat = 4;
}
Break;
Case ‘2’:switch(c){
Case ‘e’:
etat = 3;
cpt++;
Break;
Case ‘.’;

44

Etat = 4;
Break;
Case ‘l’:
Break;
Default: etat=1
}
Break;
Case 3: switch(c){
Case ‘l’:
Etat = 2;
Break;
Break;
Case ‘.’:
Etat = 4;
Break;
Default :
Etat = 1;
}}}
While (ett!=4);
Return cpt;}

Automate 3 : Concevez un automate qui permet de compter le nombre mot
dans une phrase terminée par un point.

Automate 4 : Concevez un automate ainsi que la fonction d’analyse associée
assurant la saisie correcte d’un nombre rationnel (4/3, 7/8, -8/2, -4, -6)

Automate 5 : Concevez un automate ainsi que la fonction d’analyse associée
assurant la saisie correcte d’un nombre complexe. (Forme d’un nombre
complexe : a + bi  a, b∈ ℝ)

45

La récursivité

46

La récursivité est utilisée depuis des siècles et des siècles. « La poule nait d’un œuf qui est produite
d’une poule qui nait d’un œuf qui est produite d’un œuf,… »,…
FACTORIEL

Fonction fact(↓n : entier) à résultat entier
Res ,i : entier
Res  1
Pour i de 1 à n faire
Res  res * i
FPour
Resultat Res
FFonc

𝑛𝑛
𝑛𝑛! = 𝛱𝛱𝑖𝑖=1
𝑖𝑖

La Base utilisée pour la transmission ne prenait pas compte de la récursivité était utilisée dans les
années 60.
Fonction fact(↓n : entier) à résultat entier
Res: entier
Si n = 0 alors
Res 1
Sinon
Res  n*fact(n-1)
𝛽𝛽
Fonction
Fsi
Résultat Res
FFonc

Début
R, i : entier
Algorithme
I  4
Appelant la
R  fact(i)
fonction
Ecrire r
Fin

La récursivité est comme une pile d’assiette que l’on doit « dépiler »
avant de pouvoir atteindre la dernière.
Dans le processeur, il y a différente partie qui compose celui-ci :
-

L’UAL
Les registres

Dans les processeurs INTEL il existe EAX (32 bits).

res
n
res
n
res
n

Et donc la valeur RES va être placée dans le registre du processeur EAX
afin de pouvoir faire l’échange

res
n

Dans le schéma, trois signe se nomme un frame de stagne.

res
n

Dans toutes récursivité, il faut une condition d’arrêt, car sinon cela
fera une boucle infinie.

Voici un algorithme qui pourra un être algorithme mais qui ne peux pas l’être

47

Fonction fact(↓n : entier) à résultat entier
I, res : entier
I  n
Tant que n ≠ 0 faire
N  n - 1
FTant
Res  1
Pour n de 1 à i faire
Res  res * n
FPour
Résultat Res
FFonc

1
0
Β
1
1
Β
2
4
Β
6
3
Β
24
4
α

𝛼𝛼

On peut s’intéressé dès lors à un autre type d’algorithme, on va prendre une phrase et le lire à
l’envers.
Procédure Lecture ()
C : caractère
Lire c
Si c ≠′ .′ 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎
Lecture ()
A
Ecrire c
FSi
FProc

BONJOUR.
.
R
U
O
J
N
O
B

Procédure Lecture ()
C : caractère
Lire c
Si c ≠′ .′ 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎
Lecture ()
B
FSi
Ecrire c
FProc

A:
RUOJNOB
B:
.RUOJNOB

𝒎𝒎!

𝒑𝒑

Fonction Récursive n° 01 : Ecrivez une récursivité qui résout 𝒄𝒄𝒏𝒏 = (𝒏𝒏−𝒑𝒑)!𝒑𝒑! en
𝒑𝒑

𝒑𝒑

𝒑𝒑−𝟏𝟏

sachant que 𝒄𝒄𝟎𝟎𝒏𝒏 = 𝟏𝟏 𝒔𝒔𝒔𝒔 𝒑𝒑 = 𝒐𝒐 et que 𝒄𝒄𝒏𝒏𝒏𝒏 = 𝟏𝟏 𝒔𝒔𝒔𝒔 𝒏𝒏 = 𝒑𝒑 et que 𝒄𝒄𝒏𝒏 = 𝒄𝒄𝒏𝒏+𝟏𝟏 + 𝒄𝒄𝒏𝒏−𝟏𝟏
Fonction Combinaison (↓ 𝑛𝑛, ↓ 𝑝𝑝 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
N, p, res : entier
Si n = p ou p = 0 alors
Res  1
Sinon
Res  combinaison (n-1, p) + combinaison (n-1, p-1)
Fsi
Résultat Res
FFonc

6

C²4

3-3
1 - 2 - 2 -1

C²3
C²2

C12
C11

48

C13
C12
C11

C11

C02
C01

Ecrivez une fonction récursive calculant xn avec x appartenant à R et n
appartenant à Z
Fonction p (↓ 𝑥𝑥: 𝑟𝑟é𝑒𝑒𝑒𝑒, ↓ 𝑛𝑛 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 réel
res : réel
Si n = 0 alors
Res  1
Sinon
Res  x * p(x, n-1)
Fsi
Resultat Res
FFonc

Fonction pu (↓ 𝑥𝑥: 𝑟𝑟é𝑒𝑒𝑒𝑒, ↓ 𝑛𝑛 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 réel
res : réel
Cette procédure
Si n ≥ O alors
Res  P(x,n)
permet de gérer les
Sinon
exposants négatifs
Res  1/P(x, -n)
FSi
Resultat Res
FFonc

Ecrivez une fonction récursive permettant de calculer le polynôme de
Legendre

(𝑛𝑛 + 1) 𝑃𝑃𝑛𝑛 +1 (𝑥𝑥) = (2𝑛𝑛 + 1)𝑥𝑥 𝑃𝑃𝑛𝑛 (𝑥𝑥) − 𝑛𝑛 𝑃𝑃𝑛𝑛 −1 (𝑥𝑥)

Fonction L (↓ 𝑥𝑥 ∶ 𝑟𝑟é𝑒𝑒𝑒𝑒, ↓ 𝑛𝑛 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑟𝑟é𝑒𝑒𝑒𝑒
𝑃𝑃0 (𝑥𝑥) = 1
res : réel
Si n = 0 alors
𝑃𝑃1 (𝑥𝑥) = 𝑥𝑥
Res  1
Sinon
(2𝑛𝑛 + 1)𝑥𝑥 𝑃𝑃𝑛𝑛 −1 (𝑥𝑥) −
Si n = 1 alors
𝑃𝑃𝑛𝑛 =
𝑛𝑛
Res  x
Sinon
Res ((2n+1)* L* P(x, n-1) - (n-1)* L(x, n-2))/n
FSi
FSi
Résultat Res
FFonc

(𝑛𝑛 − 1)𝑃𝑃𝑛𝑛 −𝑥𝑥 (𝑥𝑥)

Ecrivez deux fonctions récursives qui calculent respectivement la somme et
le produit de deux nombre entier a et b positif ou nul
Fonction S (↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
Si a = 0 alors
Res  b
Sinon
Si b = 0 alors
Res  a
Sinon
Res  2 + S(a-1,b-1)
Fsi
Sinon la condition
Fsi
Resulat Res
est a≠ 0 et b ≠ 0
FFonc

Si a = 0  b
Si b = 0  a
Si a ≠ 0  1 + S(a-1,b)

Si b ≠ 0 → 1 + S(a,b-1)
Si a ≠ 0 𝑒𝑒𝑒𝑒 𝑏𝑏 ≠ 0 → 2 + (a-21,b-1)

49

Fonction S(↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
Si a = 0 alors
Res  a
Sinon
Res  1 + (a-1,b)
Résultat Res
FFonc
Fonction S(↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
Si a = 0 alors
Res  a
Sinon
Res  1 + (a-1,b)
Résultat Res
FFonc

Fonction P(↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
Si a = 0 alors
Res  0
Sinon
Res  a + p(a-1,b)
Fsi
Résultat Res
FFonc

Fonction P(↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
Si b = 0 alors
Res  0
Sinon
Res  a + p(a,b-1)
Fsi
Résultat Res
FFonc

Fonction P(↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
Si a ≠ 𝑜𝑜 𝑒𝑒𝑒𝑒 𝑏𝑏 ≠ 0 alors
Res  a + b-1 + p(a-1,b-1)
Sinon
Res  0
Fsi
Résultat Res
FFonc

On a pu remarquer que de nombreuse fonctions mathématiques
élémentaires peuvent être définies et donc calculées de façon récursive il
est permit de se demandé si il n’existe pas une fonction générale et unique
qui permettent de calculer de façon récursive la somme, le produit et
l’élévation à une puissance de deux nombre A et B une telle fonction existe
c’est la fonction d’Ackermann, elle est définie de la manière suivante :
Ecrivez une fonction récursive permettant de calculer A(n,a,b) où n est un
entier et où a et b sont des réels.
Fonction P(↓ 𝑛𝑛 ↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
Si n = 0 alors
Res  a + 1
Sinon
Si b = 0
Selon que n faire
Cas 1 : res  a Fcas
Cas 2 : Res  0 fcas
Cas 3 : res  1 Fcas
Autre : Res  2
FSelon
Sinon
Res  A(n-1,A(n,a,b-1),a)
FSi
FSi
Résultat Res
FFonc

A (0,a,b) = a +1
A(1,a,0) = a
A(2,a,0)= 0
A(3,a,0)= 1
A (n,a,0)= 2 si n > 3
A (n,a,b) = A(n-1,A(n,a,b-1),a)

Calculer le nombre de combinaison de n élément parmi m au moyen de la
𝑪𝑪𝒏𝒏−𝟏𝟏
formule suivante : 𝑪𝑪𝟎𝟎𝒎𝒎 = 𝟏𝟏 𝒆𝒆𝒆𝒆 𝑪𝑪𝒏𝒏𝒎𝒎 = 𝒎𝒎−𝒏𝒏+𝟏𝟏
𝒎𝒎
𝒏𝒏
Fonction P(↓ 𝑎𝑎, ↓ 𝑏𝑏 ∶ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒) à 𝑟𝑟é𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
res : entier
si n = 0 alors
res  1
Sinon
Res  ((m-n+1)*c (n-1,m))/m
FSi
Résultat res
FFonc

50



Sur le même sujet..

---