Upload
lamque
View
216
Download
1
Embed Size (px)
Citation preview
Lycée Français de DOHA 2nde A Année 2014 – 2015 M. Evanno
Algorithmique Séance N°3 : Boucles Pour et Tant que
A) Boucle Pour.
On souhaite calculer la somme des n premiers entiers. Un algorithme répondant au problème est le suivant :
Entrée : ENTRER N entier naturel
Initialisation : DANS A METTRE 0
Traitement : POUR I variant de 1 à N
DANS A METTRE IA + FIN DU POUR
Sortie : AFFICHER A .
On faire fonctionner cet algorithme avec 8=N :
N A I Entrée 8
Initialisation 0 Traitement 110 =+ 1
321 =+ 2 633 =+ 3 1046 =+ 4 15510 =+ 5 21615 =+ 6 28721 =+ 7 36828 =+ 8
Sortie : 36
On peut programmer cet algorithme sur calculatrice de la façon suivante :
Texas Instrument : Input "" N , N 0→ S
( )100,1,IFOR IS + → S
END DISP "" =S , S
Casio : "" N ?→N
0→ S NToIFOR →1
IS + → S NEXT
"" =S : S
Exercice n°1 : Taper ce programme sur votre calculatrice et vérifier le résultat obtenu.
Lycée Français de DOHA 2nde A Année 2014 – 2015 M. Evanno
B) Boucle Tant que. On souhaite obtenir un encadrement d’amplitude 0,1 de la solution de l’équation : 53 =x . La fonction 3x étant strictement croissante et 82511 33 =<<= , on peut affirmer qu’il existe une unique solution ] [1;0∈α . Un algorithme répondant au problème est le suivant :
Initialisation : DANS A METTRE 1
Traitement : TANT QUE 53 <A
DANS A METTRE 1,0+A FIN DU POUR
Sortie : AFFICHER ENTRE 1,0−A et A .
On faire fonctionner cet algorithme :
Condition Boucle ? A Entrée
Initialisation 1 Traitement 5113 <= Oui 1,11,01 =+
5331,11,1 3 <= Oui 2,11,01,1 =+
5728,12,1 3 <= Oui 3,11,02,1 =+
5197,23,1 3 <= Oui 4,11,03,1 =+
5744,24,1 3 <= Oui 5,11,04,1 =+
5375,35,1 3 <= Oui 6,11,05,1 =+
5096,46,1 3 <= Oui 7,11,06,1 =+
5913,47,1 3 <= Oui 8,11,07,1 =+
5832,58,1 3 >= Non
Sortie : Entre 1,7 et 1,8
On peut programmer cet algorithme sur calculatrice de la façon suivante :
Texas Instrument : 1→ A
53^ <AWHILE 1,0+A → A
END 1,0,"" −AENTREDISP
AETDISP ,""
Casio : 1→ A
53^ <AWHILE 1,0+A → A
NDWHILEE
"" ENTRE : 1,0−A
"" ET : A
Exercice n°2 : Taper ce programme sur votre calculatrice et vérifier le résultat obtenu.
Lycée Français de DOHA 2nde A Année 2014 – 2015 M. Evanno
C) Pré-requis.
1) Division euclidienne.
L’ensemble IN des entiers naturels est formé des nombres 0 ; 1 ; 2 ; 3 ; 4, etc. Si on adjoint à l’ensemble IN tous les opposés des entiers naturels 0 ; −1 ; –2 ; –3 ; –4 etc. on forme l’ensemble _ des entiers relatifs qui comprend entre autres, ...; −17 ; ...; − 3 ; − 2 ; −1 ; 0 ; 1 ; 2 ; 3 ... La division de 30 par 7 se pose de la manière suivante :
La division euclidienne de 30 par 7 s’écrit : 24730 +×= . Le reste (ici 2) doit être strictement inférieur au diviseur (ici 7).
Définition :
De manière générale, étant donnés deux entiers naturels a et b , il n’y a qu’une seule façon d’écrire rqba +×= avec br <≤0 (q et r doivent être des entiers naturels). Cette écriture s’appelle la division euclidienne de a par b . a s’appelle le dividende, b le diviseur, q le quotient, r le reste.
2) Divisibilité.
Définition :
Lorsque le reste de la division euclidienne de a par b est égal à zéro on dit que b est un diviseur de a ou que b divise a ou encore que a est divisible par b .
Exemple :
• 7 est un diviseur de 35 puisque 05735 +×= . • 1 et 5 sont d’autres diviseurs de 35 puisque 035135 +×= et que 07535 +×= . • Les nombres 1 ; 2 ; 3 ; 4 ; 6 ; 12 sont des diviseurs de 12.
3) Partie entière.
Pour la réalisation de certains algorithmes dans la suite du cours, lorsque nous disposerons d’un nombre réel, il sera utile d’utiliser la notation ( )aent pour parler de l’entier relatif immédiatement inférieur ou égal au nombre a .
Exemples : ( ) 39,3 =ent ; ( ) 81,7 −=−ent et ( ) 1212 =ent
Remarque :
Pour calculer la partie entière de 8,01 : • avec les Texas Instrument, on entre ( )01,8ent (ent est dans le menu MATH).
• avec les Casio, on entre ( )01,8Int ( Int est dans MENU OPTN NUM).
• avec CALC d’OPEN OFFICE, on entre dans une cellule la formule ( )01,8ENT= .
Lycée Français de DOHA 2nde A Année 2014 – 2015 M. Evanno
Exercice n°3 : On considère l’algorithme suivant :
Entrée : ENTRER A et B entiers naturels
Initialisation : DANS I METTRE 0
Traitement : TANT QUE BA ≥ FAIRE
DANS A METTRE BA − DANS I METTRE 1+I
FIN DU TANT QUE
Sortie : AFFICHER A et I
1) Faire fonctionner cet algorithme pour : 26=A et 4=B .
Condition Boucle ? I A B Entrée 26 4
Initialisation 0 Traitement 426 =≥= BA Oui
Sortie :
2) Faire fonctionner cet algorithme pour : 19=A et 7=B .
Condition Boucle ? I A B Entrée
Initialisation Traitement
Sortie :
3) Que fait cet algorithme?
Remarque : La variable I prend comme valeur, le nombre de tours effectués.
Lycée Français de DOHA 2nde A Année 2014 – 2015 M. Evanno
Exercice n°4 : On considère l’algorithme suivant :
Entrée : A et B sont des entiers naturels tels que AB ≤≤1
Initialisation : DANS R METTRE 1
Traitement : TANT QUE 0≠R
DANS R METTRE )/( BAENTBA ∗− DANS A METTRE B DANS B METTRE R
FIN DU TANT QUE Sortie :
AFFICHER A
4) Faire fonctionner cet algorithme pour : 26=A et 16=B .
Condition Boucle ? R A B Entrée 28 16
Initialisation 1 Traitement 01≠=R Oui
Sortie :
5) Faire fonctionner cet algorithme pour : 98=A et 56=B .
Condition Boucle ? I A B Entrée
Initialisation Traitement
Sortie :
6) Que fait cet algorithme?
Lycée Français de DOHA 2nde A Année 2014 – 2015 M. Evanno
Exercice n°5 : Les Babyloniens ont utilisé un algorithme très performant pour trouver une valeur approchée de
la racine carrée d’un nombre. Voici leur méthode pour trouver une valeur approchée de 7 :
Etape 1 : On part de 1=a et on divise 7 par a et on lui ajoute a, on obtient donc 81
71 =+ ; on
divise le résultat précédent par 2 ; on obtient 4.
Etape 2 : On recommence l’étape 1 en prenant pour a le résultat obtenu (c'est-à-dire 4=a ) ; on
obtient donc 4
23
4
74 =+ ; on divise le résultat précédent par 2 ; on obtient
8
23.
Etape 3 : On procède de même en repartant du résultat de l'étape 2 ; on obtient donc
184
977
8
237
8
23 =+ ; on divise le résultat précédent par 2 ; on obtient 368
977.
On obtient 65,2368
977 ≈ or ...646,27 ≈
On peut poursuivre cet algorithme pour obtenir une précision plus grande. Voici l’algorithme en langage naturel correspondant à ce programme :
Entrée : X un réel positif et N un entier naturel
Initialisation : DANS A METTRE 1
Traitement : POUR I variant de 1 à N
DANS A METTRE 2÷
+A
XA
FIN DU POUR
Sortie : AFFICHER A
AFFICHER XA −
1) Faire fonctionner cet algorithme pour : 12=X et 6=N .
X N I A Entrée 12 5
Initialisation 1 Traitement 1
Sortie :
2) Ecrire sur votre calculatrice le programme correspondant à cet algorithme.
Lycée Français de DOHA 2nde A Année 2014 – 2015 M. Evanno
Exercice n°6 : Valeur entre 1 et 100 ? On considère l’algorithme suivant rédigé en langage naturel :
Entrée : A un entier entre 1 et 100
Initialisation : DANS I METTRE un entier aléatoirement choisi entre 1 et 100
Traitement : TANT QUE IA ≠
SI IA > AFFICHER « UN PEU MOINS » DANS A METTRE un entier entre 1 et 100 choisi par l’utilisateur
FIN DU SI. SI IA <
AFFICHER « UN PEU PLUS » DANS A METTRE un entier entre 1 et 100 choisi par l’utilisateur
FIN DU SI FIN DU TANT QUE
Sortie : AFFICHER « BRAVO »
1) Quelle est le but de cet algorithme ? 2) Taper un programme nommé « JEU » correspondant à cet algorithme sur votre calculatrice.
On pourra utiliser les fonctions suivantes : • Avec les Texas Instrument : « NbrAléat » qui donne un nombre entre 0 et 1 au hasard. • Avec les Casio : « Ran# » qui donne un nombre entre 0 et 1 au hasard.