### Exercice 1 ###

def Ascenseur(d,L) :
    if L==[] :
        return []
    else :
        L_Temp=[]
        for x in L   :
            if  not(x in L_Temp) and abs(L[0]-x)+abs(x-d)==abs(L[0]-d) : #x entre d et L[0]
                L_Temp.append(x)
        L_Temp.sort(reverse=(d>L[0]))
        return L_Temp+Ascenseur(L[0],[x for x in L if not(x in L_Temp or x==d)])
        
d=4
L=[3,7,-2,5,4,6]
# print(Ascenseur(d,L))

### Exercice 2 ###


from pylab import *
from scipy.integrate import *


def rhs(V,t):
    return [V[0]*(2-V[1]),V[1]*(V[0]-1)]

def Resolution():
    t_plus=linspace(1,10,1000)
    sol_plus=odeint(rhs,[2,1],t_plus)
    t_moins=linspace(1,-10,1000)
    sol_moins=odeint(rhs,[2,1],t_moins)
    figure()
    title("trajectoires en fonction du temps")
    grid()
    plot(t_plus,sol_plus[:,0],color="red")
    plot(t_plus,sol_plus[:,1],color="blue")
    legend(('courbe x ','courbe y '),"upper right",shadow=True)
    plot(t_moins,sol_moins[:,0],color="red")
    plot(t_moins,sol_moins[:,1],color="blue")
    plot([-10,10],[0,0],color="black",lw=2)
    SOL_ORD=[x for x in sol_plus[:,0]]+[x for x in sol_moins[:,0]]+[x for x in sol_plus[:,1]]+[x for x in sol_moins[:,1]]
    plot([0,0],[min(SOL_ORD)-1,max(SOL_ORD)+2],color="black",lw=2)
    plot(1,2,marker="s",color="orange")
    plot(1,1,marker="o",color="magenta")
    
    figure()
    title("portrait de phase")
    grid()
    plot(sol_plus[:,0],sol_plus[:,1],color="green")
    plot(sol_moins[:,0],sol_moins[:,1],color="green")
    plot(2,1,color="red",marker="o")
    show()

# Resolution()


### Exercice 3 ###

def Test_Premier(p) :
    k=2
    while p%k!=0 :
        k+=1
    return k==p
    
# print([k for k in range(2,100) if Test_Premier(k)])

def Liste_Couples_Premiers_Jumeaux() :
    c=0
    p=3
    Res=[]
    while c!=100 :
        if Test_Premier(p) and Test_Premier(p+2) :
            Res.append([p,p+2])
            c+=1
        p+=2
    return Res
    
# print(Liste_Couples_Premiers_Jumeaux())

def Test_Parfait(p): 
    s=0
    for k in range(1,p+1):
        if p%k==0 :
            s+=k
    return s==2*p

# print([k for k in range(1,1001) if Test_Parfait(k)])


### Exercice 4 ###

def Piles(L) :
    Res=[]
    for k in range(len(L)) :
        c=0
        while c<len(Res) and Res[c][-1]>L[k] :
            c+=1
        if c==len(Res) :
            Res.append([L[k]])
        else :
            Res[c].append(L[k])
    return Res
    
# L=[1,4,2,3,7,6,5,9,10,8]
# print(Piles(L))

def U_s(L) :
    """ L de longueur s """
    Res=Piles(L)
    return max([len(x) for x in Res])

def V_s(L) :
    Res=Piles(L)
    return len(Res)

L=[1,4,2,3,7,6,5,9,10,8]
# print(Piles(L))
# print(U_s(L))
# print(V_s(L))

def X_s(L) :
    s=len(L)
    m,imax=0,0
    T,Pred=s*[0],s*[0]
    for j in range(s) :
        aux=0
        iaux=None
        for i in range(j) :
            if L[i]<=L[j] and T[i]>aux : #< pour stricte croissance
                aux=T[i]
                iaux=i
                
        T[j]=1+aux
        Pred[j]=iaux
        if T[j]>m :
            m=T[j]
            jmax=j
        print('j=',j,'T=',T,'Pred=',Pred)
    iaux=jmax
    Res=m*[0]
    i=m-1
    while iaux != None :
        Res[i]=iaux
        iaux=Pred[iaux]
        i-=1
    return m # [L[i] for i in Res] #est la sous-séquence recherchée
    

def Y_s(L) :
    s=len(L)
    m,imax=0,0
    T,Pred=s*[0],s*[0] # T[i]=  la  longueur de la plus longue sous-liste terminant par L[i] ; Pred[i]= prédécesseur de L[i] dans cette plus longue sous-liste terminant par L[i]
    for j in range(s) :
        aux=0
        iaux=None
        for i in range(j) :
            if L[i]>L[j] and T[i]>aux : #< pour stricte croissance
                aux=T[i]
                iaux=i
        T[j]=1+aux
        Pred[j]=iaux
        if T[j]>m :
            m=T[j]
            jmax=j
    
    iaux=jmax
    Res=m*[0]
    i=m-1
    while iaux != None :
        Res[i]=iaux
        iaux=Pred[iaux]
        i-=1
    return m # [L[i] for i in Res] est la sous-séquence recherchée
        
        
L=[1,2,1,3,6,2,4,5,1,8,7,2]
print('L=',L)
X_s(L)# print(X_s(L))
        
from pylab import *

 
def Esperances(s) :
    u,v,x,y=0,0,0,0
    for essai in range(1000) :
        L=[uniform(0,1) for k in range(s)]
        u+=U_s(L)
        v+=V_s(L)
        x+=X_s(L)
        y+=Y_s(L)
    return [u/1000,v/1000,x/1000,y/1000]
    
# print(Esperances(100))

def Traces() :
    s=10
    S=[]
    Points=[]
    while s<=100 :
        S.append(s)
        Points.append([t/s for t in Esperances(s)])
        s+=10
    figure()
    grid()
    plot(S,[u[0] for u in Points],color='blue',marker='o',label='$U_s/s$')
    plot(S,[v[1] for v in Points],color='red',marker='o',label='$V_s/s$')
    plot(S,[x[2] for x in Points],color='green',marker='o',label='$X_s/s$')
    plot(S,[y[3] for y in Points],color='yellow',marker='o',label='$Y_s/s$')
    legend(loc='upper center',shadow=True)
    show()
    
#Traces()

# variables $X_s$ et $Y_s$ assez proches car la probabilité d'avoir deux valeurs égales dans $L$ est presque nulle 

# on a toujours $V_s=Y_s$