Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmique 1` ereSTI2D I - G´ en´ eralit´ es D´ eﬁnition : Un algorithme est

Algorithmique 1` ereSTI2D I - G´ en´ eralit´ es D´ eﬁnition : Un algorithme est une suite ﬁnie d’instructions permettant la r´ esolution syst´ ematique d’un probl` eme donn´ e. Un algorithme peut-ˆ etre utilis´ e pour • d´ ecrire par une suite d’instructions ou de proc´ edures la marche compl` ete ` a suivre pour r´ esoudre un probl` eme ; • automatiser une tˆ ache complexe ; on sait d´ ej` a dans ce cas r´ esoudre le probl` eme pos´ e et on cherche ` a tirer parti de moyens informatiques pour eﬀectuer automatiquement toutes les ´ etapes et tous les calculs interm´ ediaires qui permettent d’aboutir au r´ esultat ; • chercher la solution d’un probl` eme ; on ne sait pas a priori r´ esoudre le probl` eme pos´ e mais on peut tirer parti d’un syst` eme informatis´ e pour explorer l’ensemble des possibilit´ es, et ainsi tenter de trouver la solution, ou du moins une bonne approximation de celle-ci. Un exemple courant : notice d’utilisation ou mode d’em- ploi Voici la notice d’utilisation d’une huile teck, imprim´ ee au dos du ﬂacon d’huile : Mode d’application 1. V´ eriﬁer que la surface est bien du teck ou un bois exotique 2. Bien agiter avant emploi 3. Impr´ egner le bois g´ en´ ereusement 4. 20 minutes apr` es, essuyer l’exc´ edent ` a l’aide d’un chiﬀon 5. Laisser s´ echer 6 heures 6. Recommencer ` a partir de l’´ etape 2 7 Laisser couler quelques gouttes d’eau sur la surface trait´ ee Si les gouttes perlent ` a la surface, Alors le bois est correctement huil´ e et imperm´ eabilis´ e Sinon, recommencer ` a l’´ etape 2. D´ eﬁnition : Un langage de programmation est un ensemble d’instructions et de r` egles syntaxiques compr´ ehensibles par un syst` eme automatis´ e (calculatrice, ordinateur, puce ´ electronique,. . .). Un programme est la traduction d’un algorithme dans un langage de programmation particu- lier. Il existe de tr` es nombreux langages de programmation tels que, parmi bien d’autres, Basic, Fortran, Python, C, C++, Matlab, assembleur. . ., ainsi que ceux implant´ es dans les calculatrices (alors dites ”programmables”. . .). Dans la suite les langages des calculatrices TI et Casio, et le langage Python qui est un language gratuit, moderne, tr` es eﬃcace, et dont le code source est libre (”open source”). Il peut ˆ etre t´ el´ echarg´ e ` a l’adresse http ://www.python.org/. II - Premiers exemples : calcul du pgcd de deux nombres 1) Algorithme d’Euclide : Automatisation du calcul du pgcd de deux entiers. Par exemple, pour les entiers a = 462 et b = 60 : 462 = 60 × 7 + 42 60 = 42 × 1 + 18 42 = 18 × 2 + 6 18 = 6 × 3 + 0 Y. Morel - xymaths.free.fr/Lycee/1STI/ Algorithmique - 1` ereSTI2D - 1/6 Entrer les nombres entiers a et b Calculer le reste r de la division euclidienne de a par b r = 0 ? OUI pgcd = b NON a prend la valeur b b prend la valeur r Algorithme Lire a et b (reste division de a par b) →r Tant que r̸=0 faire b→a r→b (reste division de a par b) →r Fin tant que Exercice 1 a) D´ eterminer le pgcd de a = 140 et b = 42. b) D´ eterminer le pgcd de a = 1500 et b = 2310. 2) Algorithme des diﬀ´ erences Cet autre algorithme permettant de calculer le pgcd de deux nombres a et b s’ex´ ecute de la mani` ere suivante : on soustrait le plus petit des deux nombres a et b au plus grand, on obtient le nombre positif d ; puis on recommence de mˆ eme avec les deux plus petits nombres parmi les trois pr´ ec´ edents, et ainsi de suite... Par exemple, avec a = 14 et b = 6 : 14 −6 = 8 8 −6 = 2 6 −2 = 4 4 −2 = 2 2 −2 = 0 Algorithme Lire a Lire b a-b→d Afficher d Tant que d̸=0 Si d<b b→a d→b Sinon d→a Fin Si a-b→d Afficher d Fin Tant que Programme TI Prompt A Prompt B A-B→D Disp D Wile D̸=0 If D<B Then B→A D→B Else D→A End A-B→D Disp D End Programme Casio "A="?→A "B="?→B A-B→D Wile D̸=0 If D<B Then B→A D→B Else D→A IfEnd A-B→D D WhileEnd Programme Python a=input("a ?") b=input("b ?") d=a-b print d while d !=0: if d<b: a=b b=d else: a=d d=a-b print d Y. Morel - xymaths.free.fr/Lycee/1STI/ Algorithmique - 1` ereSTI2D - 2/6 III - Lire, ex´ ecuter et comprendre un algorithme Exercice 2 Ci-contre est donn´ e un algorithme : 1. Qu’aﬃche cet algorithme lorsque l’utilisateur entre le nombre 3 ? le nombre −12, 7 ? 2. A quoi sert cet algorithme ? Algorithme Entrer x Si x < 0 Affecter ` a x la valeur −x Fin Si Afficher la valeur x Exercice 3 Ci-contre est donn´ e un algorithme : 1. Qu’aﬃche cet algorithme lorsque l’utilisateur entre successivement les nombres 12 ; 3 ; 18 ; 11 ; 0 2. A quoi sert cet algorithme ? Algorithme x=1 S=0 i=0 Tant que x ̸= 0 Demander ` a l’utilisateur d’entrer un nombre Lire x Affecter ` a S la valeur S + x Affecter ` a i la valeur i + 1 Fin Tant que Afficher la valeur S/i IV - Variables D´ eﬁnition On appelle variable tout emplacement de la m´ emoire dans lequel une information peut- ˆ etre stock´ ee. Une variable est constitu´ ee de : – un nom qui permet ` a l’ordinateur de la localiser dans sa m´ emoire (en g´ en´ eral une lettre : A, B, . . ., X, . . .) – une valeur : l’information (souvent un nombre) qu’elle contient. La valeur d’une variable peut changer au cours de l’ex´ ecution de l’algorithme. Une aﬀectation consiste ` a attribuer une valeur ` a une variable, ou ` a en modiﬁer la valeur. La valeur val est attrivu´ ee ` a la variable nomm´ ee var. val→var V - Structures dans les algorithmes 1) Boucles it´ eratives Une boucle permet de r´ ep´ eter un ensemble d’instructions un nombre ﬁx´ e de fois. Pour variable de d´ ebut ` a Fin instructions 1 instructions 2 . . . Fin Pour Exercice 4 a) Ecrire un algorithme qui calcule et aﬃche la suite des carr´ es des nombres entiers de 1 ` a 10. b) Modiﬁer cet algorithme pour qu’il calcule et aﬃche la somme des carr´ es des entiers de 1 ` a 10. Y. Morel - xymaths.free.fr/Lycee/1STI/ Algorithmique - 1` ereSTI2D - 3/6 2) Tests et instructions conditionnelles Un test est une comparaison entre la valeur d’une variable et une valeur donn´ ee, ou entre les valeurs de deux variables. Un test a deux r´ esultats possibles : 0 (faux), ou 1 (vrai). Dans une structure conditionnelle, les instructions ne sont eﬀectu´ ees que si le test indiqu´ e est vrai. Si test instructions 1 instructions 2 . . . Fin Si Exercice 5 Ecrire un algorithme qui demande un nombre ` a l’utilisateur et aﬃche en r´ esultat si le nombre est positif ou n´ egatif. 3) Boucles conditionnelles Une boucle conditionnelle permet de r´ ep´ eter une s´ erie d’instructions sans connaˆ ıtre a priori le nombre d’it´ erations. La boucle est r´ ep´ et´ e tant que le test indiqu´ e est vrai. Tant que test instructions 1 instructions 2 . . . Fin Tant que Exercice 6 Ecrire un algorithme qui demande un nombre entier ` a l’utilisateur et compte ` a rebours jusqu’` a 0. VI - Jeu du nombre myst´ erieux Ce jeu se joue ` a deux personnes de la mani` ere suivante. Un des deux joueurs choisit un nombre entier au hasard compris entre 1 et 100. Le but du deuxi` eme joueur est de trouver ce nombre. Pour cela il propose un nombre au premier joueur qui lui fournit une des trois r´ eponses : – Gagn´ e, si le nombre propos´ e est le bon ; – Trop grand, si le nombre propos´ e est plus grand que le nombre myst´ erieux ; – Trop petit, si le nombre propos´ e est plus petit que le nombre myst´ erieux ; Si le nombre propos´ e n’est pas le bon, le deuxi` eme joueur propose un autre nombre, et le jeu se poursuit jusqu’` a ce qu’il trouve le nombre exact. Le but du jeu est de trouver le nombre myst´ erieux avec le moins de tentatives possible. 1) L’ordinateur fait deviner Le programme dans lequel l’ordinateur est le joueur choisissant un nombre au hasard compris entre 1 et 100, et l’utilisateur est le joueur qui doit trouver ce nombre. Le programme doit aussi aﬃcher le nombre de tentatives utilis´ ees. Lire attentivement l’algorithme uploads/Sports/ cours-algorithmique-1sti2d.pdf