DS INFO Diane Hamlat

###Exercice 1 question 4
def f(x,a):   # on définit f pour une meilleure lisibilité
  return x**2-a
def g(x):     # idem avec la dérivée de f
  return 2*x

def newton(a,eps):
  x0=a+1
  while abs(f(x))>eps:
    x=x-f(x)/g(x)
  return x

###Exercice 2.1 question 3
def derive(P):
  n=len(P)
  P1=[]
  for i in range (1,n):
    P1.append(i*P[i])   #on définit P1 comme la somme des i*P[i]*X**(i-1), i variant de 1 à (n-1). Ainsi en partant de i=1, on a supprimé le terme constant pour X=0
  return P1

###Exercice 2.1 question 4
def primitive(P):
  n=len(P)
  Q=[1]                     #il s'agit du coefficient constant tq Q(0)=1
  for i in range (n):
    Q.append(1/(i+1)*P[i]) #Q prend les coefficients de la primitive de P. On a degP=n car les coeffcients sont décalés d'un rang grâce à l'initialisation
  return Q

###Exercice 2.1 question 5
def addition(P,Q):
  n=len(P)
  R=[]
  assert len(P)==len(Q)
  for i in range(n):
    R.append(P[i]+Q[i])
  return R

###Exercice 2.1 question 6
def addition_v2(P,Q):
  n,m=len(P),len(Q)
  S,R=[],[]
  if m==n:
    R=addition(P,Q)
  elif m>n:
    for i in range (m):
      S.append(0)     #degS=degQ
    for i in range(n):
      S[i]=P[i]       #S correspond au polynôme P auquel on a rajouté des 0 tq degS=degQ
    R=addition(S,Q)   #on peut ainsi calculer la somme de P et de S
  else:
    for i in range (n):
      S.append(0)     #degS=degP
    for i in range (m):
      S[i]=Q[i]       #idem que précédemment avec le polynôme Q
    R=addition(S,P)
  for i in range(n-1,-1,-1):
    if R[i]==0:
      R.pop()       #on supprime tous les derniers éléments nuls
    else:
      break
  return R

###Exercice 2.2 question 3
def evalue_naive(P,x):
  n=len(P)
  A=P[0]
  X=1
  for i in range(1,n):
    X*=x        #avec la variable X on peut augmenter d'une puissance à chaque passage dans la boucle
    A+=P[i]*X
  return A

###Exercice 2.3 question 1
def evalue_rapide(P,x):
  n=len(P)
  A=0
  for i in range(n):
    A+=P[i]*x**i  #par principe de l'exponenciation rapide
  return A

###Exercice 2.5 question 3
def evalue_horner(P,x):
  n=len(P)
  A=P[n-1]        #on pose alpha0=an-1
  for k in range(n-1):
    A=A*x+P[n-(k+2)]   #par la relation de récurrence sur alpha définie question1
  return A