Algorithmes et mathématiques - Exo7

1 Algorithmes et math matiquesVid o partie 1. Premiers pas avec PythonVid o partie 2. Ecriture des entiersVid o partie 3. Calculs de sinus, cosinus, tangenteVid o partie 4. Les r elsVid o partie 5. Arithm tique Algorithmes r cursifsVid o partie 6. Polyn mes Complexit d un algorithme1. Premiers pas avecPythonDans cette partie on v rifie d abord quePythonfonctionne, puis on introduira les boucles (foretwhile), le testif .. else ..et les Hello world !Pour commencer testons si tout fonctionne !Travaux pratiques D finir deux variables prenant les valeurs 3 et Calculer leur somme et leur quoi cela ressemble :Code 1( ).

2 >>> a=3>>> b=6>>> somme = a+b>>> print(somme)9>>> # Les r sultats>>> print("La somme est", somme)La somme est 9>>> produit = a*b>>> print("Le produit est", produit)Le produit est 18On retient les choses suivantes : On affecte une valeur une variable par le signe gal=. On affiche un message avec la fonctionprint(). Lorsque qu une ligne contient un di se#, tout ce qui suit est ignor . Cela permet d ins rer des commentaires, cequi est essentiel pour relire le la suite on omettra les symboles>>>. Voir plus de d tails sur le fonctionnement en fin de ET MATH MATIQUES1. PREMIERS PAS Somme des cubesTravaux pratiques Pour un entiernfix , programmer le calcul de la sommeSn=13+23+33+ + D finir une fonction qui pour une valeurnrenvoie la somme n=1+2+3+ + D finir une fonction qui pour une V rifier, pour les premiers entiers, queSn=( n) 2( (1)).

3 N = 10somme = 0for i in range(1,n+1): somme = somme + i*i*iprint(somme)Voici ce que l on fait pour calculerSnavecn=10. On affecte d abord la valeur 0 la variablesomme, cela correspond l initialisationS0=0. Nous avons d fini uneboucleavec l instructionforqui fait varierientre 1 etn. Nous calculons successivementS1,S2,.. en utilisant la formule de r currenceSi=Si 1+i3. Comme nousn avons pas besoin de conserver toutes les valeurs desSialors on garde le m me nom pour toutes les sommes, chaque tape on affecte sommel ancienne valeur de la somme plusi3:somme = somme + i*i*i. range(1,n+1)est l ensemble des entiers{1,2.}

4 ,n}. C est bien les entiersstrictement inf rieurs n+ raison est querange(n)d signe{0, 1, 2, .. ,n 1}qui contientn l Nous savons que n=1+2+3+ +n=n(n+1)2donc nous n avons pas besoin de faire une boucle :Code 3( (2)).def somme_entiers(n): return n*(n+1)/2 Unefonctionen informatique est similaire une fonction math matique, c est un objet qui prend en entr e desvariables (dites variables formelles ou variables muettes, icin) et retourne une valeur (un entier, une liste, unecha ne de caract res,.. icin(n+1)2).3. Voici la fonction qui retourne la somme des cubes :Code 4( (3)).def somme_cubes(n): somme = 0 for i in range(1,n+1): somme = somme + i**3 return somme4.

5 Et enfin on v rifie que pour les premiers entiersSn= n(n+1)2 2, par exemple pourn=12 :Code 5( (4)).n = 12if somme_cubes(n) == (somme_entiers(n)**2): print("Pour n=", n, "l'assertion est vraie.")else: print("L'assertion est fausse !") Algorithmes ET MATH MATIQUES1. PREMIERS PAS AVECP ython3On retient : Les puissances se calculent aussi avec**: 52s crit5*5ou5**2, 53s crit5*5*5ou5**3,.. Une fonction se d finit pardef ma_fonction(variable):et se termine parreturn resultat. if condition: .. else: ..ex cute le premier bloc d instructions si la condition est vraie ; si la conditionest fausse cela ex cute l autre bloc.

6 Exemple de conditions a < b:a<b, a <= b:a6b, a == b:a=b, a != b:a6=b. Attention ! Il est important de comprendre quea==bvaut soit vraie ou faux (on compareaetb) alors qu aveca=bon affecte dansala valeur deb. Enfin enPython(contrairement aux autres langages) c est l indentation (les espaces en d but de chaque ligne)qui d termine les blocs d Calcul de au hasardNous allons voir qu il est possible de calculer les premi res d cimales de par la m thode de Monte-Carlo, c est direavec l aide du hasard. On consid re le carr de cot 1, le cercle de rayon1 centr l origine, d quationx2+y2=1,et la portion de disque dans le carr (voir la figure).

7 (0, 0)(1, 0)(0, 1)Travaux pratiques Calculer l aire du carr et de la portion de un point(x,y)tir au hasard dans le carr , quelle est la probabilit que le point soit en fait dans la portionde disque ?3. Tirer un grand nombre de points au hasard, compter ceux qui sont dans la portion de En d duire les premi res d cimales de .Voici le code :Code 6( ).import random # Module qui g n re des nombres al atoiresTir = 0 # Num ro du tirNbTirDansLeDisque = 0 # Nombre de tirs dans le disquewhile (Tir < 1000): Tir = Tir + 1 # On tire au hasard un point (x,y) dans [0,1] x [0,1] x = () y = () if (x*x+y*y <= 1): # On est dans le disque NbTirDansLeDisque = NbTirDansLeDisque + 1 Algorithmes ET MATH MATIQUES1.

8 PREMIERS PAS AVECP ython4 MonPi = 4*NbTirDansLeDisque / Tirprint("Valeur exp rimentale de Pi : % " %MonPi)Commentaires : Un petit calcul prouve que l aire de la portion de disque est 4, l aire du carr est1. Donc la probabilit de tomberdans le disque est 4. Pour tirer un nombre au hasard on utilise une fonctionrandom()qui renvoie un nombre r el de l intervalle[0,1[.Bien s r chaque appel de la fonctionrandom()le nombre obtenu est diff rent ! Cette fonction n est pas connue par d faut dePython, il faut lui indiquer le nom dumoduleo elle se trouve. End but de fichier on ajouteimport randompour le module qui g re les tirages au hasard.]]

9 Et pour indiquer qu unefonction vient d un module il faut l appeler ()donc ()(module etfonction portent ici le m me nom !). La boucle estwhile condition: ..Tant que la condition est v rifi e les instructions de la boucle sontex cut es. IciTirest le compteur que l on a initialis 0. Ensuite on commence ex cuter la boucle. Bien s r lapremi re chose que l on fait dans la boucle est d incr menter le compteurTir. On continue jusqu ce que l onatteigne999. PourTir=1000la condition n est plus vraie et le bloc d instructions duwhilen est pas ex cut .On passe aux instructions suivantes pour afficher le r sultat. chaque tir on teste si on est dans la portion de disque ou pas l aide de l in galit x2+y261.

10 Cette m thode n est pas tr s efficace, il faut beaucoup de tirs pour obtenir le deux premi res d cimales de . Un peu plus surPython Le plus surprenant avecPythonc est que c estl indentationqui d termine le d but et la fin d un bloc d oblige pr senter tr s soigneusement le code. Contrairement d autres langages on n a pas besoin de d clarer le type de variable. Par exemple lorsque l oninitialise une variable parx=0, on n a pas besoin de pr ciser sixest un entier ou un r el. Nous travaillerons avec la version 3 (ou plus) dePython, que l on appelle parpythonoupython3. Pour savoirsi vous avez la bonne version tester la commande4/3.