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.