Seconde-Algorithmique-Activite Decembre 2010

Debuter en algorithmique

1 Qu’est-ce qu’un algorithme ?

Definition Un alogorithme est une suite d’operations elementaires, a appliquer dans un ordre determine a des donnees.Un algorithme est donc une liste d’instructions elementaires a suivre. Ces instructions fournissent en un nombre fini d’etapesdes resultats.Ecrire un algorithme consiste a donner une methode detaillee decrivant toutes les etapes d’une tache a ccomplir.

Exemples : une notice de montage, une recette de cuisine, un chemin indique par un GPS, une division a la main, trier descartes a jouer · · · sont des algorithmes.

On peut considerer un algorithme comme une machine fonctionnant en trois etapes :

1. les elements dont on part : les entrees ;

2. les instructions a effectuer sur ces elements : le traitement ;

3. les resultats obtenus : les sorties.

Exercice On considere le programme de calcul suivant :

1. Choisir un nombre.

2. Lui ajouter 1.

3. Multiplier le resultat par 2.

4. Soustraire 3 au resultat.

5. Afficher le resultat.

1. Appliquer cet algorithme a 3 ; −4, 0 et1

3.

2. Identifier les trois etapes de cet algorithme.

2 Variables et affectation

Pour commencer un algorithme, il faut des elements sur lesquels on souhaite travailler (dans l’exemple precedent, il nousfaut un nombre). Ces elements sontles donnees d’entree qui seront utilisees lors des etapes du traitement.

Les donnees d’entree sont stockees dans la memoire de la calculatrice ou de l’ordinateur, a un emplacement appele variableet repere par un nom. On peut donc considerer une variable comme une boıte.Le nom de la variable est son etiquette.La variable peut contenir une valeur (un nombre, un mot, une liste de nombres · · · )

Lorsque les variables sont declarees, nous n’avons fait que reserver un espace dans la memoire de l’ordinateur ou de lacalculatrice. Cela revient a reserver poser une affiche ”RESERVE” sur une place de parking. Pour autant, la place n’est pasoccupee. Occuper cette place, c’est donner une valeur a l’espace memoire reserve : c’est l’affectation.

Une affectation est l’attribution d’une valeur a la variable.

Si la variable s’appelle A, l’affectation peut s’ecrire de differentes manieres :– Affecter a A la valeur 3 ;– A prend la valeur 3 ;– A← 3Exemples

1. Considerons l’algorithme suivant :

Debut de l’algorithmeDeclaration de la variable V

Affectation V ← 4Nouvelle affectation V ← V + 7Instruction de sortie Afficher VFin de l’algorithme

Que lit-on a la fin de l’algorithme?

2. Considerons a present l’algorithme suivant :

Isabelle Morel 1

Seconde-Algorithmique-Activite Decembre 2010

Debut de l’algorithmeDeclaration des variables a ; b ; c

Affectation a← 3

Affectation a← a2 − 2a+ 1Affectation b← 7

Affectation b← b2 − 4b+ 4Affectation c← a+ b− 9Instruction de sortie Afficher cFin de l’algorithme

Que lit-on a la fin de l’algorithme?

3. Considerons a present un algorithme plus general :

Debut de l’algorithmeDeclaration de la variable a

Affectation a← x

Affectation a← 2a+ 1

Affectation a← a2

Affectation a← a− 4Instruction de sortie Afficher aFin de l’algorithme

Developper et reduire l’expression obtenue (on obtient une fonction !).

4. Ecrire l’algorithme donnant la fonction f(x) = (2x+ 3)2 − 1.

5. Considerons un algorithme programme avec le logiciel Algobox :

Variablesa est du type nombreb est du type nombrec est du type nombren est du type nombre

Debut de l’algorithmeLire a

Lire b

n prend la valeur 10× a+ b

Afficher nc prend la valeur aa prend la valeur bb prend la valeur de c

n prend la valeur 10× a+ b

Afficher nFin de l’algorithme

(a) Tester cet algorithme ave a = 2 et b = 3.

(b) Expliquer l’importance de la variable c.

3 Les instructions conditionnelles

On souhaite ecrire un algorithme testant si un triangle est rectangle ou non en A.Pour cela, il faut calculer BC2 d’une part et AB2 +AC2 d’autre part, puis comparer les deux valeurs. Cela fait intervenirun test, aussi appele instruction conditionnelle.

La resolution de certains problemes necessite la mise en place d’un test pour effectuer une tache :– si le test est positif, on effectue la tache ;– sinon, c’est-a-dire si le test est negatif, on effectue une autre tache.On parle d’instruction conditionnelle (ou test ou structure alternative).En algorithmique, cette instruction conditionnelle se redige ainsi :

Si condition

alors traitement 1

sinon traitement 2

FinSi

Exemples :

Isabelle Morel 2

Seconde-Algorithmique-Activite Decembre 2010

1. On considere l’algorithme suivant :

Variablesx du type nombrey du type nombre

Entreedemander un nombre x

TraitementSi x < 0

Alors affecter a y le nombre1

xSinon affecter a y le nombre

√x

FinSiAfficher y

(a) Tester cet algorithme pour x = 1 ; −2 ; 4 ; −1 ; 0.

(b) Ecrire la fonction obtenue sur R.

2. Ecrire l’algorithme testant si un triangle est rectangle en A ou non.

4 La boucle iterative

On souhaite calculer le nombre 210. Pour cela, on considere le nombre 2 puis on le multiplie par 2. On multiplie ensuite leresultat obtenu par 2 et ainsi de suite. On repete donc 9 fois l’operation : multiplier par 2. Repeter plusieurs fois de duiteune meme tache s’appelle en algorithme executer une boucle (a compteur).

La boucle a compteur consiste a repeter une tache fixe n fois, n etant fixe a l’avance.On la redige de la maniere suivante :

Pour i allant de 1 a n

TraitementFin boucle pour

Exemples :

1. On considere l’algorithme suivant :

VariablesN du type nombreS du type nombrei du type nombre

EntreeSaisir N0→ S

TraitementPour i allant de 1 jusqu’a N faire

S + i→ S

FinPourAfficher S

(a) Completer le tableau ci-dessous en prenant comme valeur initiale de N : N = 5.

Numero de passage dans la boucle Valeur de S avant le passage dansla boucle

Valeur de S apres le passage dansla boucle

1

2

3

4

5

(b) A quoi sert cet algorithme?

Isabelle Morel 3

Seconde-Algorithmique-Activite Decembre 2010

2. Considerons a present l’algorithme suivant :

VariablesN du type nombreA du type nombreB du type nombre

EntreeSaisir N2→ A

1→ B

TraitementPour i allant de 0 jusqu’a N faire

B +A→ B

FinPourAfficher B

(a) Utilisez cet algorithme pour completer le tableau suivant :

N 0 1 2 3 4 5

B 3

(b) Placez les points de coordonnees (N ; B). Que constatez-vous ?

(c) Donnez une expression de la fonction f qui, au nombre N saisi, associe le nombre B en sortie.

3. Completez l’algorithme suivant pour qu’il affiche la table de multiplication (de 0 a 12) d’un nombre entier naturel Nsaisi par l’ordinateur :

VariablesN du type nombrei du type nombreR du type nombre

EntreeSaisir N

TraitementPour i allant de 0 jusqu’a . . . . . . faire

. . . . . . . . .→ R

Afficher . . . . . . ≪ × ≫. . . . . .≪ = ≫. . . . . .

FinPour

5 La boucle conditionnelle

Considerons l’algorithme suivant :

VariablesN du type nombreC du type nombre

EntreeN recoit un nombre au hasard entre 10 et 20C recoit 0

TraitementTant que N 6= C faire

Afficher ≪ Entrez un nombre entier entre 10 et 20 ≫

Saisir CSi N = C

Alors Afficher ≪ Vous avez gagne ≫

Sinon Afficher ≪ vous avez perdu ≫

FinSiFinTant

1. Testez cet algorithme.

2. A quoi sert cet algorithme?

Dans cet algorithme, on voit repete une operation tant qu’une condition est verifiee. On parle alors de boucle conditionnelle.

Isabelle Morel 4

Seconde-Algorithmique-Activite Decembre 2010

La boucle conditionnelle (ou boucle tant que) consiste a repeter plusieurs fois les memes instructions tant qu’une certainecondition est remplie : la boucle s’arrete quand la condition n’est plus remplie. On utilise pour cela les instructions suivantes :

Tant que ConditionFaire Tache

FinTant

Exemple : Considerons l’algorithme suivant :

Debut algorithmeVariables

x du type nombreN du type nombre

EntreeSaisir x0→ N

TraitementTant que N + 1 6 x faire

N + 1→ N

FinTantAfficher N

Fin algorithme

1. On choisit pour valeur initiale x = 5, 2. Completez le tableau ci-dessous :

Numero de passage de laboucle

Valeur de N avant le pas-sage dans la boucle

Valeur de N apres le pas-sage dans la boucle

Arret de la boucle condi-tionnelle (oui/non)

1

Combien de passages dans la boucle conditionnelle ont ete necessaires pour l’arret de l’algorithme?

2. Recommencer l’algorithme pour x = 2.

3. Que donne l’algorithme pour x = 3, 1 ?

4. Le nombre N obtenu est appele la partie entiere de x, note Ent(x). On a donc : Ent(5,2)=. . . . . . Ent(2)=. . . . . . etEnt(3,1)=. . . . . .

Isabelle Morel 5