Documentation Algorithme pour débutant

Participez au vote ☆☆☆☆☆★★★★★

Cours d’algorithmique pour la classe de 2nde

F.Gaudon

10 aouˆt 2009

Table des matières

Définition :

Un algorithme est une succession d’instructions (aussi appelées commandes) et permettant la résolution d’un problème donné.

Remarque :

Le terme d’algorithme vient du nom du mathématicien arabe du IX^e siècle Al Khuwarizmi qui écrivit la première méthode systématique de résolution de certaines équations.

Exemple :

pour A allant de 1 à 10 par pas de 1

Stocker A^2 dans B

Afficher B

L’algorithme précédent calcule et affiche le carré des nombres de 1 à 10. Dans cet algorithme,Stocker A² dans B est une instruction.

Définition :

Un langage de programmation est un ensemble d’instructions et de règles syntaxiques compréhensible par l’ordinateur et permettant de créer des algorithmes. Un programme est la traduction d’un algorithme dans le langage de programmation utilisé.

Exemples :

BASIC, PASCAL, C++, assembleur sont des langages de programmation pour ordinateurs. Dans ce cours nous utiliserons les langages de programmation associés aux calculatrices programmables Casio et Texas Instrument ainsi que le langage de programmation du logiciel libre et gratuit XCas téléchargeable

à l’adresse et le langage de programmation du logiciel libre et gratuit MAXIMA téléchargeable à l’adresse suivante fr (on installera l’interface graphique WxMaxima qui simplifie beaucoup l’utilisation de ce logiciel) .Ces deux logiciels sont par ailleurs des puissants logiciels de calcul dit formel utilisés dans le monde universitaire, mais la description de leurs possibilités n’est pas l’objet de ce cours.

1.3 Avant de programmer

Casio :

Touche MENU puis choisir PRGM et :

• EDIT pour modifier un programme existant;

• NEW pour créer un nouveau programme;

• EXEC pour exécuter un programme.

TI :

Touche PRGM puis :

• EDIT pour modifier un programme existant;

• NEW pour créer un nouveau programme;

• EXEC pour exécuter un programme existant.

Remarque :

Après création d’un nouveau programme sur TI ou CASIO, entrer le nom du programme; n’utiliser que les lettres (touches ALPHA + Lettre)

XCas :

L’édition d’un programme se fait dans la ligne de commande. Avant de commencer, aller dans le menu

Cfg configuration du CAS et vérifier que l’onglet PROG STYLE est en mode XCAS. On pourra aussi aller dans Cfg Polices (Toutes) et choisir une police de taille 14 plus lisible que la police de taille 18 par défaut.

Maxima :

L’édition d’un programme (on devrait plutôt parler d’une fonction ici mais cette distinction n’a pas d’importance pour la suite de ce cours) se fait dans le menu Entrée longue du menu Editer´ de l’interface graphique WxMaxima. La syntaxe du programme (fonction) doit être de la forme :

nom-du-programme()=(

instruction, ,instruction)$

Casio :

Les instructions des algorithmes peuvent être séparées par un retour à la ligne EXE . Une ligne peut éventuellement comporter plusieurs instructions séparées par.

TI :

Les instructions des algorithmes peuvent être séparées par un retour à la ligne EXE . Une ligne peut éventuellement comporter plusieurs instructions séparées par.

XCas :

Les instructions peuvent être séparées par un retour à la ligne SHIFT ENTER . Une ligne peut contenir plusieurs instructions séparées par ; . Attention, les lignes doivent absolument se terminer avec ; .

Maxima :

1.3 Avant de programmer

Les instructions (dans une fonction, ce qui sera le toujours le cas dans le cadre de ce cours) doivent être séparées par une virgule , .

2 LES VARIABLES

Définition :

On appelle variable tout emplacement de la mémoire de l’ordinateur ou de la calculatrice dans lequel on stocke une information qui peut être changée. Une variable est donc constituée :

• d’un nom qui permet de reconnaˆ?tre ou` elle se situe dans la mémoire de l’ordinateur ou de la calculatrice;

• d’une valeur : le nombre ou plus généralement l’information stockée.

Remarque :

Les variables sous Casio ou TI peuvent contenir uniquement des nombres. Sous XCas, Maxima et autres langages de programmation pour ordinateur, les variables peuvent contenir des caractères, des lettres, des chaˆ?nes de caractères.

Syntaxe :

Sur Casio ou TI, on écrira 3 ? A pour stocker le nombre 3 dans la variable A. Sur TI, la touche correspondante est STOI et sur casio ? . Sur XCas, on écrira a : 3 et avec Maxima, on écrira a : 3 pour stocker la valeur 3 dans la variable a.

3 EXERCICES SUR LES VARIABLES

Exercice 1 :

a) A l’issue de l’algorithme suivant, quel nombre est stocké dans la variable A? Dans la variable` B?

3?A

4?B

A?C

B?A

C?B

b) A quoi sert l’algorithme précédent?`

4 ENTR

Définition :

Les commandes d’affichage servent à afficher à l’écran du texte ou la valeur d’une variable.

Syntaxe en algorithmique :

Afficher a ou

print ( ” texte	”			)	affiche le texte suivi de la valeur de la variable a.
		,	a

Afficher "texte" Casio :

”

texte

du programme.

”

affiche le texte entre guillemets.

affiche la valeur de A et attend que l’utilisateur tape sur EXE pour poursuivre l’exécution

Les guillemets ” sont accessibles à partir de l’éditeur de programmes ( MENU ) en faisant défiler avec la touche $ puis en utilisant la touche Fn qui correspond ( F2 pour la Graph25). Le caractère est accessible à partir de l’éditeur de programme ( MENU PRGM ) puis SHIFT PRGM puis $ puis en utilisant la touche Fn qui correspond ( F2 sur Graph25).

TI :

	Disp		”	texte	”	, A affiche le texte entre guillemets puis le contenu de la variable A.

La commande Disp (”display” en anglais c’est à dire ”afficher”) est accessible dans le menu PRGM I/O (”Input/Output” en anglais c’est à dire ”entrée/sortie”).

XCas :

print ( ” texte	”			)	; affiche le texte suivi de la valeur de la variable a.
		,	a

Maxima :

4.2 Commandes d’entrée de valeurs 4 ENTR

Définition :

Les commandes d’entrée de valeurs permettent à l’algorithme de demander à l’utilisateur un nombre, un caractère ou un texte.

Syntaxe en algorithmique :

Saisir a Casio :

	?	?A demande à l’utilisateur d’entrer la valeur à stocker dans la variable A.

? est accessible à partir de l’éditeur de programmes en faisant défiler avec la touche $ puis en utilisant la touche Fn qui correspond ( F1 sur Graph25).

TI :

Prompt

demande à l’utilisateur d’entre une valeur pour la variable A.

Input A

Prompt et Input sont accessibles dans le menu PRGM I/O .

”
	,

A noter, sur TI, la commande^` Input ” texteA affiche le texte entre guillemets et demande d’entrer la valeur de A.

XCas :

input	(	”	Entrer A :	”			)	;	demande à l’utilisateur d’entrer une valeur pour la variable A et attend que la valeur soit
					,	A
entrée.

Maxima :

a	:	read	(	”	Entrer a :	”			)	demande à l’utilisateur d’entrer une valeur pour la variable a et attend que la valeur soit
							,	a
	entrée.

5 EXERCICES SUR LES ENTR

5 Exercices sur les entrées et sorties

Exercice 1 :

Que fait l’algorithme suivant?

Saisir A

Saisir B

A*B -> C

2*(A+B) -> D

Afficher C

Afficher D

Exercice 2 :

Que fait l’algorithme suivant?

Saisir D

D/2 -> R

3,14*R^2 -> A

Afficher A

Exercice 3 :

Ecrire un algorithme qui demande d’entrer deux nombres entiers A et B et calcule le reste de la´ division euclidienne de A et B. On utilisera pour cela la fonction partie entière int A qui donne la partie entière d’un nombre a (menu MATH NUM iPart sur TI, menu OPTN NUM Int sur Casio et iPart sur XCAS).

Exercice 4 :

Ecrire un algorithme qui demande d’entrer un nombre puis affiche son image par la fonction´ f définie par f(x) = 3x² + 5x? 9.

Exercice 5 :

1. Ecrire un algorithme qui convertit des secondes en heures, minutes et secondes.´

2. Ecrire un algorithme qui convertit des heures en jours et heures.´

Exercice 6 :

Ecrire un algorithme qui demande d’entrer trois nombres A, B et C et calcule et affiche leur´ moyenne non pondérée.

Exercice 7 :

Ecrire un algorithme qui, l’utilisateur ayant entré le taux annuel d’épargne en pourcentage et le´ capital initialement placé, calcule et affiche le capital disponible auquel sont ajoutés les intérêts de l’année.

Définitions :

Ces instructions permettent de tester si une condition est vraie ou fausse et de poursuivre le programme d’une manière différente selon que la condition est vraie ou fausse.

Syntaxe en algorithmique :

Si condition

Alors instructions si condition vraie

Sinon instructions si condition fausse

FinSi

TI :

If condition

Then instructions

Else instructions

End

If Then, Else et

Endsont accessibles dans le menu PRGM

CTL(contrôle).

Casio :

If condition

Then instructions

Else instructions

ifEnd

If then, Else et

IfEndsont accessibles dans le menu

SHIFT PRGM

puis COM ( F1 sur

Graph25).

XCas : if

( condition )

instruction ; instruction ; } else

{instruction ;

	}
;	}	;

instruction

Maxima : if

( condition )

( instruction ,

instruction ) else

( instruction ,

instruction )

6.1 Si..alors..sinon

Exemple :

TI :

input	”	A =?	”
				,

If A < 7

Then

A + 1 ? A

Else A? 1 ? A

End Disp A

Casio :

? ? A

If A < 7

Then

A + 1 ? A

Else

A? 1 ? A

ifEnd ” A ”

XCas :

input(" a = ? ",a); if (a<7)

{a:=a+1;} else

{a:=a-1;}; print("a = ",a);

Maxima :

essaitest()=(

a:read(" a = ? "), if (a<7) then

(a:a+1) else

(a:a-1), print("a = ",a)

Ce programme teste si la variable a entrée a une valeur inférieure à 7 et, si c’est le cas, ajoute 1. Sinon, il enlève 1 à la valeur de la variable. Puis, quelle que soit la valeur de a, il affiche le contenu de la variable a. On remarquera les espaces laissés au début de certaines lignes pour Xcas et Maxima : ils ne sont pas indispensables mais aident à clarifier la compréhension du programme, c’est donc une bonne habitude à prendre que de les utiliser.

6.2 Opérateurs relationnels et logiques

Définition :

Pour tester une condition on utilise les opérateurs relationnels suivants :

• a = b teste l’égalité de a et de b;

• a < b teste si a est strictement inférieur à b;

• a ? b teste si a est inférieur ou égal à b;

• a > b teste si a est strictement supérieur à b;

• a ? b teste si a est supérieur ou égal à b;

• a 6= b teste si a est différent de b.

On utiliser ausi pour les conditions plus complexes les opérateurs logiques ”et” (”AND”), ”ou”(”OR”) et ”non” (”not”).

Casio :

Les opérateurs relationnels se trouvent dans MENU PRGM $ REL .

TI :

Les opérateurs relationnels se trouvent dans 2nd TEST TEST et les opérateurs logiques dans LOGIC .

XCas :

• a == b teste l’égalité de a et de b;

• a < b teste si a est strictement inférieur à b;

• a <= b teste si a est inférieur ou égal à b;

• a > b teste si a est strictement supérieur à b;

• a >= b teste si a est supérieur ou égal à b;

• a! = b teste si a est différent de b;

• condition1 && condition2 teste si les deux conditions sont vraies simultanément; • condition1 || condition2 test si l’une au moins des deux conditions est vraie;

• !condition teste si la négation de la condition est vraie.

Maxima :

• a = b teste l’égalité de a et de b;

• a < b teste si a est strictement inférieur à b;

• a <= b teste si a est inférieur ou égal à b;

• a > b teste si a est strictement supérieur à b;

• a >= b teste si a est supérieur ou égal à b;

• not(a = b) teste si a est différent de b;

• condition1 and condition2 teste si les deux conditions sont vraies simultanément; • condition1 or condition2 test si l’une au moins des deux conditions est vraie;

• not(condition) teste si la négation de la condition est vraie.

7 EXERCICES SUR LES STRUCTURES CONDITIONNELLES

Exercice 1 :

Ecrire un programme qui demande l’âge de l’utilisateur et répond ”vous êtes mineur” ou ”vous´ êtes majeur” suivant le cas.

Exercice 2 :

Ecrire un programme qui demande la température extérieure en degrés celsius et affiche ”il gèle”´ si le nombre est négatif et ”alerte à la canicule” si le nombre est supérieur à 30.

Exercice 3 :

1. Qu’affiche l’algorithme suivant?

1000->tirelire

19->^age

Si (^age >=19 et tirelire >=1000) alors afficher "Vous pouvez ouvrir un compte" sinon afficher "pas de compte possible"

2. Ecrire le code correspondant à l’algorithme précédent pour la calculatrice ou pour XCas.´

Exercice 5 :

Ecrire un algorithme qui, à partir d’un nombre entré par l’utilisateur, affiche ce même nombre s’il´ est positif et son opposé s’il est négatif (le nombre obtenu est appelé la valeur absolue du nombre entré).

Exercice 6 :

Ecrire un algorithme qui, à partir de la donnée de la longueur de chacun des trois côtés d’un´ triangle, teste si le triangle est rectangle.

Définition :

Les boucles sont utilisées pour qu’une séquence d’instructions soit répétée un nombre donné de fois ou tant qu’une condition n’est pas remplie.

Définition :

Ces instructions sont utilisées pour contrôler les boucles en incrémentant (augmentant) une variable. La variable est augmentée d’une valeur de départ jusqu’à une valeur d’arrivée d’un pas donné (l’incrément).

Syntaxe :

Pour variable

allant de

valeur de départ

valeur d’arrivée faire

instructions fin

Casio :

	For	valeur de départ?variable To valeur d’arrivée Step incrémentinstructions
	Next

Les instructions For , To , Step , Next se trouvent dans SHIFT PRGM COM .

TI :

For

End

(

variable , valeur de départ , valeur d’arrivée , incrément

)

instructions

Les instructions For , End se trouvent dans le menu PRGM CTL .

8.1 Boucles ”pour”

Maxima :

for

variable

instruction

instruction , instruction

valeur de départ

thru

valeur finale step incrément

(

)

Exemple :

Pour a allant de 0 à 10 par pas de 2 faire a*a -> b

Afficher a et b

Fin Pour

Casio :

For 0 ? A To 10 Step 2

A?A ? B

TI :

For ( A , 0 , 10 , 2 )

A?A ? B

Disp A , B

End

XCas :

for (a:=0; a<=10;a:=a+2)

{b:=a^2; print(a,b);}

Maxima :

tableau()=(

for a:0 thru 10 step 2 do

(b:a^2, print(a,b))

Cet algorithme affiche le tableau de valeurs de la fonction carré de 0 à 10 par pas de 2.

8.2 Boucles ”Tant que”

Définition :

Exécute un groupe de commandes tant qu’une condition est vraie. La condition´ est testée en début de boucle.

Syntaxe :

Tant que condition instructions faire

instructions fin tant que

Casio :

While condition instructions WhileEnd

Whileet WhileEnd se trouvent dans le menu

SHIFT PRGM COM

( F1 sur Graph25)

TI :

While condition instructions

End

Whileet End se trouvent dans le menu PRGM CTL .

XCas :

While ( condition )

{ instruction ; instruction ;

	}
;

instruction

Maxima :

While ( condition

)

( instruction instruction ,

instruction

)

8.2 Boucles ”Tant que”

Exemple :

10 -> a

Tant que a>0 faire a-1 -> a

Afficher a fin tant que

TI :

10 ? A

While A > 0

A? 1 ? A

Disp A

End

Casio :

10 ? A

While A > 0

”

A? 1 ? A

” A=A

WhileEnd

XCas :

a:=10; while (a>0) {a:=a-1; print(a);};

Maxima :

decompte()=( a:10, while (a>0) do (a:a-1, print(a))

Cet algorithme affiche le décompte de 9 à 0.

Exemple :

Saisir A

Saisir B

1->R Tant que R<>0 faire

A-B*Int(A/B) -> R

Afficher R

B->A

R->B

FinTantque

Afficher "PGCD=",A

8.3 Boucles ”répéter”

TI :

”
	,

Input ” A =A

”
	,

Input ” B =B

1? R

While R 6= 0

A-B* iPart (A/B)? R

Disp R

B?AR?B

End

	”
	”	,

Disp ” PGCD = A

Casio :

” A=

” B=

1? R

While R6=0

A-B* Int (A/B)? R

B?AR?B

WhileEnd

”

” PGCD= A

XCas :

input("a= ",a); input("b= ",b); r:=1; while (r!=0) { r:=a-b*intDiv(a,b); print("r= ",r); a:=b;b:=r; }; print("PGCD =",a);

Maxima :

euclide()=( a:read("a= "), b:read("a= "), r:1, while not(r=0) do (r:mod(a,b), print("r= ",r), a:b, b:r),

print("PGCD =",a)

Cet algorithme utilise l’algorithme d’Euclide pour calculer le PGCD de deux entiers A et B entrés.

Définition :

Comme les boucles ”tant que”, une boucle ”répéter” éxécute un groupe d’instructions mais ceci jusqu’à ce que la condition soit vraie et la condition est testée en fin de boucle. Dans les deux cas, la boucle est toujours réalisée au moins une fois.

Syntaxe :

Répéter

instructions

jusqu’à condition

8.3 Boucles ”répéter”

Casio :

Do instructions

LpWhile condition

Doet LpWhile (”Loop” en anglais signifie ”boucle”) se trouvent dans le menu SHIFT

PRGM COM ( F1 sur

Graph25).

Attention sur Casio, la boucle Do LpWhile s’effectue tant que la condition est vraie et non pas jusqu’à ce que la condition soit vraie.

TI :

repeat condition

instructions End

repeatet End se trouvent dans le menu PRGM CTL .

Attention sur TI : La condition se met au début de la boucle mais elle est testée en fin de boucle uniquement.

XCAS :

Pas de telle boucle pour

XCAS, utiliser une boucle ”tant que”.

Maxima :

Pas de telle boucle pour

Maxima, utiliser une boucle ”tant que”.

Exemple :

Saisir A

Saisir B

1->R

Répéter

A-B*Int(A/B) -> R

Afficher R

B->A

R->B jusqu’à R=0

Afficher "PGCD=",A

TI :

”
	,

Input ” A =A

”
	,

Input ” B =B

1? R

Repeat R = 0

A-B* iPart (A/B)? R

Disp R

B?AR?B

End

	”
	”	,

” PGCD = A

Casio :

” A=

” B= Do

A-B* Int (A/B)? R

B?AR?B

LpWhile R 6= 0

”

” PGCD= A

Il s’agit du même algorithme d’Euclide. Observer les différences avec l’algorithme écrit à l’aide de boucles ”tant que” et les différences d’écriture sur les modèles TI et Casio.

9 EXERCICES SUR LES BOUCLES

Exercice 1 :

1. Combien de fois le message ”Salut” sera-t-il affiché à partir de l’algorithme suivant?

15 -> A

Répéter

afficher "Salut"

A+1->A jusqu’à A<15

2. Combien de fois ce même message sera-t-il affiché dans le cas suivant?

14->A

Tant que A<15 faire

afficher "Salut"

finTantque

Exercice 2 :

1. Ecrire un algorithme qui calcule la somme des nombres entiers de 0 à 50.´

2. Ecrire un algorithme qui calcule le produit des nombres entiers de 1 à 7´

3. Ecrire un algorithme qui calcule la somme des 20 premiers nombres impairs.´

4. Ecrire un algorithme qui calcule la somme des 20 premiers nombres paires.´

Exercice 3 :

Ecrire un algorithme qui calcule la variance et l’écart type d’une série de nombres entrés par´ l’utilisateur. L’algorithme demandera le nombre de nombres que comprend la série avant de demander d’entrer la série de nombres.

Exercice 4 :

Ecrire un algorithme qui, une somme initiale ayant été demandée à l’utilisateur ainsi qu’une durée´ de placement en année et un taux de placement en pourcentage à intérêts composés, affiche la somme disponible au bout de la durée de placement.

Exercice 5 :

Ecrire un algorithme permettant le calcul du PGCD de deux nombres entrés par l’utilisateur par´ la méthode des différences successives (on rappelle que les différences successives consistent à faire la différence du plus grand nombre par le plus petit et à garder la différence et le plus petit nombre à chaque étape pour recommencer jusqu’à obtention de 0).

Télécharger Plus de Téléchargements