algorithms

---------------------------------------------------------------------------------------------------
Partie "Nombres et calculs"
---------------------------------------------------------------------------------------------------

def BalayageRacine2(pas):
  """ encadrement de sqrt{2} d'amplitude inférieure ou égale à un pas fixe
  la fonction carré etant croisante, on part de 1 et on calcule les carrés des nombres
  tant qu'ils sont plus petits que 2, en avançant à chaque fois du pas """

  x = 1
  while x*x <=2:
      x = x + pas
  return (x-pas,x)

---------------------------------------------------------------------------------------------------
def AestmultipledeB(a,b):
  """ Déterminer si un entier naturel a est multiple d'un entier naturel b
  utilise le reste de la division euclidienne fourni par Python """

  if a%b == 0:
    return True
  else:
    return False

def AestmultipledeB_2(a,b):
  """ Déterminer si un entier naturel a est multiple d'un entier naturel b
  n utilise pas le reste de la division euclidienne fourni par Python """

  n = 0  
  while n*b < a:
    n = n+1
  if n*b==a:
    return True
  else:
    return False

---------------------------------------------------------------------------------------------
def PlusGrandMultiple(a,b):
  """ a et b donnés, déterminer le plus grand multiple de b inférieur ou égal à a """
  n = 1
  while n*b<=a:
    n = n+1
  return (n-1)*b

----------------------------------------------------------------------------------------------------
def EstilPremier(n):
  """ détermine si un entier naturel est premier """

  for i in range(2,n):
    if n%i==0:
      return False
  return True

def EstilPremier2(n):
  """ une variante basée sur l'obtention de la liste des diviseurs
  on peut créer une fonction qui détermine la liste des diviseurs de n 
  puis on teste si la longueur de cette liste est égale à 2 """

  ListeDiviseurs=[]
  for i in range(1,n+1):
    if n%i==0:
      ListeDiviseurs=ListeDiviseurs+[i]  # On peut aussi utiliser la méthode .append
  if len(ListeDiviseurs)==2:
    return True,ListeDiviseurs
  else:
    return False,ListeDiviseurs

def EstilPremier3(n):
  """ une variante utilisant la fonction précédemment définie pour savoir si a est un multiple de b """

  for i in range(2,n):
    if AestmultipledeB_2(n,i):
      return False
  return True

--------------------------------------------------------------------------------------------
def PremierePuissanceInferieure(a,b):
  """ détermine la première puissance d'un nombre positif donné supérieure ou inférieure à une valeur donnée
  on cherche la première puissance de b inférieure (strictement) ou supérieure (strictement) à a dans le cas
  où a n'est pas une puissance de b """ 

  puissance = 1
  while puissance < a:
    puissance = puissance * b
  return puissance/b

def PremierePuissanceSuperieure(a,b):
  puissance = 1
  while puissance < a:
    puissance = puissance * b
  return puissance

def PremieresPuissances(a,b):
  """ On peut améliorer l'algorithme en testant d'abord sir le nombre $a$ est une puissance de b puis,
  si ce n'est pas le cas, renvoyer les deux puissances de b qui encadrent a """ 
  n=0
  while b**n<a:
    n = n+1
  if b**n==a:
    return 'a est une puissance de b'
  else:
    return PremierePuissanceInferieure(a,b),PremierePuissanceSuperieure(a,b)

---------------------------------------------------------------------------------------------------
Partie "Géométrie"
---------------------------------------------------------------------------------------------------

# Etudier l'alignement de trois points dans le plan, version 1

def CoefficientDirecteur(x1,y1,x2,y2): # On se place dans le cas où x1 est différent de x2
    return (y2-y1)/(x2-x1)

def OrdonneeALorigine(x1,y1,x2,y2): # On se place dans la cas où x1 est différence de x3
    return y1-CoefficientDirecteur(x1,y1,x2,y2)*x1

def PointsAlignes(x1,y1,x2,y2,x3,y3):
    if abs(x1-x2) < 10**(-12):
        if abs(x1-x3) < 10**(-12):
            return True
        else:
            return False
    else:
        a = CoefficientDirecteur(x1,y1,x2,y2)
        b = OrdonneeALorigine(x1,y1,x2,y2)
        if abs(y3-a*x3-b) < 10**(-12):
            return True
        else:
            return False

# Version 2, utilisant la colinéarité de vecteurs
def determinant(xu,yu,xv,yv):
    return xu*yv-yu*xv

def PointsAlignes2(x1,y1,x2,y2,x3,y3):
    if abs(determinant(x2-x1,y2-y1,x3-x1,y3-y1))<10**(-12):
        return True
    else:
        return False

--------------------------------------------------------------------------------------------------------------------------
def EquationDeDroite(x1,y1,x2,y2):
  """  Détermine une équation de droite (du type x=c ou y=ax+b) passant par deux points donnés """
    if abs(x1-x2)<10**(-12):
        return 'x='+str(x1)  # on revoie l'équation sous forme d'un texte
    else:
        a = CoefficientDirecteur(x1,y1,x2,y2)
        b = OrdonneeALorigine(x1,y1,x2,y2)
        return 'y='+str(a)+'*x+'+str(b)

----------------------------------------------------------------------------------------------------------------------------
Partie "Fonctions"

def f(x):
  return x**3+3*x**2-2*x+1

def BalayageExtremum(pas):
  """ version 1
  pour une fonction f(x), definie sur [-4 , 4], dont le tableau de variations est donné, algorithme d'approximation numérique
  d'un extremum (balayage, dichotomie)
  croissante sur [-4;c] puis décroissante sur [c;0]
  on cherche donc une valeur approchée de f(c) """

  x = -4
  maximum_provisoire = f(x)
  while x<=0:
    if f(x)>maximum_provisoire:
      maximum_provisoire = f(x)
    x = x + pas
  return maximum_provisoire

def f(x):
  return x**3+3*x**2-2*x+1

def BalayageExtremum2(pas):
  """ version 2
  pour une fonction f(x), definie sur [-4 , 4], dont le tableau de variations est donné, algorithme d'approximation numérique
  d'un extremum (balayage, dichotomie)
  croissante sur [-4;c] puis décroissante sur [c;0]
  on cherche une valeur approchée de c et de f(c) """
  x = -4
  maximum_provisoire = f(x)
  while x<=0:
    if f(x)>maximum_provisoire:
      maximum_provisoire = f(x)
      x_cherche = x
    x = x + pas
  return x_cherche,maximum_provisoire

------------------------------------------------------------------------------------------------
from math import *

def Distance(x1,y1,x2,y2):
  return sqrt((x2-x1)**2+(y2-y1)**2)

def f(x):
  return x**3   # Fonction a choisir par l'utilisateur

def LongueurCourbe(f,a,b,pas):
  """ calcul approché de longueur d'une portion de courbe f
  on ajoute des petits morceaux de courbe de pas choisi
  cette methode est generale et ce retrouve sur les integrales curvilignes ou en analyse complexe """

  longueur = 0
  x = a
  while x<b:
    longueur = longueur + Distance(x,f(x),x+pas,f(x+pas))
    x = x + pas
  return longueur

-----------------------------------------------------------------------------------------------------------------------------
Partie "Statistiques et Probabilités"

# Partie "Statistiques et Probabilités"

# Pour des données réelles ou issues d'une simulation, lire et comprendre une fonction écrite en Python
# renvoyant la moyenne m, l'écart type s, et la proportion d'éléments appartenant à [m-2s,m+2s]

# On peut proceder en deux temps:
# - créer une fonction permettant de simuler une expérience aléatoire
# - créer une autre fonction répondant renvoyant la moyenne m, l'écart type s, et la proportion d'éléments
# appartenant à [m-2s,m+2s]. Cette fonction peut également être utilisée pour toutes les listes de données numériques réelles

# On choisit n personnes dont on mesure le taux de glycémie dans le sang
# (qui suit la loi normale d'espérance 1 g/l et d'écart-type 0.1 g/l ce qui
# permet de simuler une liste et de la donner brute aux élèves)
# rappel: si X suit N(0,1^2) alors Z = 0.1*X + 1 suit N(1,0.1^2)

from math import *
from random import *
import numpy.random as alea

def TauxGlycemie(n):
  Liste = []
  for compteur in range(n):
    glycemie = alea.randn()*0.1+1  # randn() permet de simuler la loi normale centree reduite
    Liste = Liste + [glycemie]
  return Liste

def Moyenne(Liste):
  n = len(Liste)  # Longueur de la liste
  somme = 0
  for t in Liste:
    somme = somme + t
  moyenne = somme / n
  return moyenne

def Ecarttype(Liste):
  n = len(Liste)
  somme_ecart_moyenne = 0
  m = Moyenne(Liste)
  for t in Liste:
    somme_ecart_moyenne = somme_ecart_moyenne + (t-m)**2
  variance = somme_ecart_moyenne / n
  ecart_type = sqrt(variance)
  return ecart_type

def Parametres(Liste):
  m = Moyenne(Liste)
  s = Ecarttype(Liste)
    
  nombre_dans_intervalle = 0
  for t in Liste:
    if m-2*s < t and t < m+2*s:
      nombre_dans_intervalle = nombre_dans_intervalle + 1
  frequence = nombre_dans_intervalle / len(Liste)
    
  return m, s, frequence

# **Remarque:** Il est intéressant également d'ajouter une représentation graphique à la fonction précédente pour
# renforcer le côté "exceptionnel" des valeurs à l'extérieur de l'intervalle $[m-2s;m+2s]$

from math import *
from random import *
import numpy.random as alea
import matplotlib.pyplot as plt

def TauxGlycemie(n):
  Liste = []
  for compteur in range(n):
    glycemie = alea.randn()*0.1+1  # randn() permet de simuler la loi normale centrée réduite
    Liste = Liste + [glycemie]
  return Liste

def Moyenne(Liste):
  n = len(Liste)  # Longueur de la liste
  somme = 0
  for t in Liste:
    somme = somme + t
  moyenne = somme / n
  return moyenne

def Ecarttype(Liste):
  n = len(Liste)
  somme_ecart_moyenne = 0
  m = Moyenne(Liste)
  for t in Liste:
    somme_ecart_moyenne = somme_ecart_moyenne + (t-m)**2
  variance = somme_ecart_moyenne / n
  ecart_type = sqrt(variance)
  return ecart_type

def Parametres2(Liste):
  m = Moyenne(Liste)
  s = Ecarttype(Liste)
    
  nombre_dans_intervalle = 0
  for t in Liste:
    if m-2*s < t and t < m+2*s:
      nombre_dans_intervalle = nombre_dans_intervalle + 1
  frequence = nombre_dans_intervalle / len(Liste)
    
  Liste_X = range(1,len(Liste)+1)
  Liste_Y = Liste
    
  plt.plot(Liste_X,Liste_Y,"b.")
  plt.plot((0,len(Liste)+1),(m,m),"g")
  plt.plot((0,len(Liste)+1),(m-2*s,m-2*s),"r")
  plt.plot((0,len(Liste)+1),(m+2*s,m+2*s),"r")
  plt.show()
    
  return m, s, frequence

-------------------------------------------------------------------------------------------------------
2. Lire et comprendre une fonction Python renvoyant le nombre ou la fréquence de succès
dans un échantillon de taille n pour une expérience aléatoire à deux issues

On considère une expérience aléatoire à deux issues dont le succès à pour probabilité p
On répète cette expérience aléatoire n fois
On peut écrire la fonction renvoyant la fréquence de succès en modifiant la fin de la fonction
renvoyant le nombre de succès ou alors appeler cette fonction
from random import *

def nombre_succes(n,p):
  nb_succes = 0
  for compteur in range(n):
    if random()<p:
      nb_succes = nb_succes + 1
  return nb_succes

def frequence_succes(n,p):
  """ on considère une expérience aléatoire à deux issues dont le succès à pour probabilité p
  on répète cette expérience aléatoire n fois
  on renvoie la frequence de succes """
  return nombre_succes(n,p)/n

-------------------------------------------------------------------------------------------------------
# Observer la loi des grands nombres à l'aide d'une simulation sur Python ou tableur

# On considère un dé à 6 faces dont la face 6 a été remplacée par 1
# On souhaite observer la fréquence de 1 au fur et à mesure de la répétition d'épreuves 
# Remarque: Plutôt que d'utiliser la fonction random(), on peut utiliser la fonction choice()

import matplotlib.pyplot as plt
from random import *

def de_truque():
  DE = [1,1,2,3,4,5]
  return choice(DE)
    
def representation_graphique(n):
  Liste_X=[0]
  Liste_Y=[0]
  nb_succes = 0
  for compteur in range(1,n+1):
    Liste_X = Liste_X + [compteur]
    if de_truque()==1:
      nb_succes = nb_succes + 1
    Liste_Y = Liste_Y + [nb_succes / compteur]
  plt.plot(Liste_X,Liste_Y,'b.')
  plt.grid()
  plt.show()

# Remarque: Il est intéressant de montrer la stabilisation de manière "dynamique" en utilisant l'animation
de matplotlib
# Penser à choisir la valeur de N nombre d'expériences aléatoires à réaliser

import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from random import *
from IPython.display import HTML

###########
N = 300   # Nombre d'expériences aléatoires à réaliser
###########

def de_truque():
  DE = [1,1,2,3,4,5]
  return choice(DE)
    
def frequences(n):
  Liste_Y=[0]
  nb_succes = 0
  for compteur in range(1,n+1):
    if de_truque()==1:
      nb_succes = nb_succes + 1
    Liste_Y = Liste_Y + [nb_succes / compteur]
  return Liste_Y

fig, ax = plt.subplots()
xdata, ydata = [], []
points, = plt.plot([], [], 'b.')

Liste_a_representer = frequences(N)

def init():
  ax.set_xlim(0, N)
  ax.set_ylim(0, 1)
  return points,

def update(i):
  xdata.append(i)
  ydata.append(Liste_a_representer[i])
  points.set_data(xdata, ydata)
  return points,

ani = FuncAnimation(fig, update, frames=N,init_func=init, blit=True)
HTML(ani.to_jshtml())
#HTML(ani.to_html5_video())