#### TP n°9: Diviser pour régner ####
#################



### EXPONENTIATION RAPIDE ###
## Question 1 
def puissance1(x:float,n:int) -> float:
    p=1
    for i in range(n):
        p=p*x
    return p
print(puissance1(2.5,18))
## Question 2 
def puissance2(x:float,n:int) -> float:
    if n==0:
        return 1
    if n%2==0:
        xp=puissance2(x,n//2)
        return xp*xp
    else:
        xp=puissance2(x,n//2)
        return x*xp*xp
print(puissance2(2.5,18))
## Question 3 
import time
debut=time.time()
puissance1(1.000001,1000000)
fin=time.time()
print(fin-debut,"s")
debut=time.time()
puissance2(1.000001,1000000)
fin=time.time()
print(fin-debut,"s")


### RECHERCHE D'UN ÉLÉMENT DANS UN TABLEAU TRIÉ ###



## Question 4 
def cherche_element_1(liste:[str|float],element:str|float) -> int:
    """ recherche la présence de element dans une liste """
    for i in range(len(liste)):
        if liste[i]==element:
            return i
    return -1
print(cherche_element_1(liste_mots,"zigoto"))
## Test de la fonction `cherche_element_1`; **à exécuter sans éditer**
ok=True
if cherche_element_1([1,3,4,2],3)!=1: ok=False
if cherche_element_1([1,3,4,2],2)!=3: ok=False
if cherche_element_1([1,3,4,2],5)!=-1: ok=False
if ok:
    print("Fonction cherche_element_1: test réussi!")
else:
    print("Fonction cherche_element_1: test échoué!")
## Question 5 
def cherche_element_2(liste:[str|float],element:str|float,debut:int,fin:int) -> int:
    """ recherche la présence de element dans une liste triée """
    if debut>fin:
        return -1
    if element<liste[debut] or element>liste[fin]:
        return -1
    m=(debut+fin)//2
    if liste[m]==element:
        return m
    if liste[m]>element:
        return cherche_element_2(liste,element,debut,m-1)
    if liste[m]<element:
        return cherche_element_2(liste,element,m+1,fin)
print(cherche_element_1(liste_mots,"lycee"))
print(cherche_element_2(liste_mots,"lycee",0,len(liste_mots)-1))
## Question 6 
import time
debut=time.time()
print(cherche_element_1(liste_mots,"zigoto"))
fin=time.time()
print(fin-debut,"s")
debut=time.time()
print(cherche_element_2(liste_mots,"zigoto",0,len(liste_mots)-1))
fin=time.time()
print(fin-debut,"s")
## Question 7 
import numpy.random
import time
liste_n=[]
liste_temps_1=[]
liste_temps_2=[]
for n in range(100,200000,2500):
    liste_n.append(n)
    liste=numpy.cumsum(numpy.random.randint(1,5,n))
    debut=time.time()
    cherche_element_1(liste,2*n)
    fin=time.time()
    liste_temps_1.append(fin-debut)
    debut=time.time()
    cherche_element_2(liste,2*n,0,n-1)
    fin=time.time()
    liste_temps_2.append(fin-debut)
import matplotlib.pyplot as plt
plt.figure()
plt.plot(liste_n,liste_temps_1,label="cherche_element_1")
plt.plot(liste_n,liste_temps_2,label="cherche_element_2")
plt.legend()
plt.show()
### MAXIMUM D'UNE FONCTION DÉRIVABLE ###
## Question 8 
import math
def f(x):
    return 3*x-math.exp(x)
def fp(x):
    return 3-math.exp(x)
def maximum(f,fp,a,b,eps):
    m=(b+a)/2
    if b-a<eps:
        return m,f(m)
    else:
        if fp(m)<0:
            return maximum(f,fp,a,m,eps)
        else:
            return maximum(f,fp,m,b,eps)
print(maximum(f,fp,0,10,1e-5))
## Question 9 
def maximum2(f,a,b,eps):
    m=(b+a)/2
    if b-a<eps:
        return m,f(m)
    else:
        d=1e-8
        fp=(f(m+d)-f(m))/d
        if fp<0:
            return maximum2(f,a,m,eps)
        else:
            return maximum2(f,m,b,eps)
print(maximum2(f,0,10,1e-5))
### ENVELOPPE CONVEXE ###




### TRI PAR FUSION ###

## Question 10 
def fusionne_listes(liste1:[float],liste2:[float]) -> [float]:
    i1,i2=0,0
    liste_fusionnee=[]
    while i1<len(liste1) or i2<len(liste2):
        if i1>=len(liste1):
            liste_fusionnee.append(liste2[i2])
            i2=i2+1
        elif i2>=len(liste2):
            liste_fusionnee.append(liste1[i1])
            i1=i1+1
        else:
            if liste1[i1]<liste2[i2]:
                liste_fusionnee.append(liste1[i1])
                i1=i1+1
            else:
                liste_fusionnee.append(liste2[i2])
                i2=i2+1
    return liste_fusionnee
print(fusionne_listes([1,3,4,7,8,10],[1,4,5,5,8]))
## Question 11 
def tri_fusion(L:[float]) -> [float]:
    if len(L)<=1:
        return L
    m=len(L)//2
    l1,l2=tri_fusion(L[:m]),tri_fusion(L[m:])
    return fusionne_listes(l1,l2)
print(tri_fusion([1,4,5,3,-1,2,3,4,3,2,3,7,13,2,1,4,5,-3,-5,0,-4,3,-2,7,6,-1,10]))
## Test de la fonction `tri_fusion`; **à exécuter sans éditer**
ok=True
if tri_fusion([1,4,3,6,2,4,7,-1])!=[-1,1,2,3,4,4,6,7]: ok=False
if tri_fusion(["il","etait","une","fois","un","petit","chaperon","rouge"])!=["chaperon","etait","fois","il","petit","rouge","un","une"]: ok=False
if ok:
    print("Fonction tri_fusion: test réussi!")
else:
    print("Fonction tri_fusion: test échoué!")
## Question 12 
import numpy.random
liste_n=[]
liste_temps=[]
for i in range(5,17):
    n=2**i
    liste_n.append(n)
    liste=numpy.random.random(n)
    debut=time.time()
    tri_fusion(liste)
    fin=time.time()
    liste_temps.append(fin-debut)
import matplotlib.pyplot as plt
plt.figure()
plt.plot(liste_n,liste_temps)
plt.show()