### Exercice 1

def Coeff_Binomial(n,k) :
    if k<0 or k>n :
        return 0
    elif k==0 :
        return 1
    else :
        return int(n/k*Coeff_Binomial(n-1,k-1))

# n=5
# print([Coeff_Binomial(n,k) for k in range(n+1)])

from numpy import *

def Tableau(n) :
    M=zeros((n+1,n+1))
    for i in range(n+1) :
        for j in range(n+1) :
            M[i,j]=Coeff_Binomial(i,j)
    return M

# print(Tableau(4))

### Exercice 2

def Algo_Iteratif(a,b) :
    p,q=a,b
    while q!=0 :
        p,q=q,p%q
    return p

# print(Algo_Iteratif(2*3*7*11,3*11*11*17))

def Algo_Recursif(a,b) :
    if b==0 :
        return a
    else :
        return Algo_Recursif(b,a%b)


# print(Algo_Recursif(2*3*7*11,3*11*11*17))

import time
from pylab import *


def Trace_Temps() :
    LX=[]
    k=4
    while k<=1000 :
        LX.append(k)
        k+=7
    a=1000
    LT_Ite=[]
    LT_Rec=[]
    
    for b in LX :
        t_0=time.clock()
        Algo_Iteratif(a,b)
        t_1=time.clock()
        Algo_Recursif(a,b)
        t_2=time.clock()
        LT_Ite.append(t_1-t_0)
        LT_Rec.append(t_2-t_1)
    figure()
    grid()
    semilogy()
    plot(LX,LT_Ite,color='blue')
    plot(LX,LT_Rec,color='red')
    legend(('algo itératif','algo récursif'),loc='upper left', shadow=True)
    show()
        
# Trace_Temps()
    
### Exercice 3

def Enleve_Redondances(L) :
    L_Temp=[]
    for x in L :
        if not(x in L_Temp) :
            L_Temp.append(x)
    return L_Temp
def Anagrammes(chaine) :
    if len(chaine)==0 :
        return []
    elif len(chaine)==1 :
        return [chaine]
    else :
        x=chaine[-1]
        S=Anagrammes(chaine[:-1])
        return Enleve_Redondances([y[:i]+x+y[i:] for y in S for i in range(len(chaine))])
        
# chaine="obob"
# print(Anagrammes(chaine))

### Exercice 4

def Recherche_Dicho(L,x) :
    """ L triée et L[0] <= x <= L[-1] """
    if len(L)==1:
        return 0
    elif len(L)==2 :
        if x>=L[-1] :
            return 1
        else :
            return 0
    else :
        m=len(L)//2
        if x<L[m] :
            return Recherche_Dicho(L[:m],x)
        else :
            return Recherche_Dicho(L[m:],x)+m

# x=2
# L=[1,1,1,1,1,2,3,4]
# print(Recherche_Dicho(L,x))  

def Recherche_naive(L,x) :
    c=0
    while c<len(L) and L[c]<=x:
        c+=1
    return c-1
 

def Essais(N) :
    
    for k in range(N) :
        L=sorted([uniform(0,1000) for k in range(1000)])
        x=uniform(L[0],L[-1])
        Test=Recherche_Dicho(L,x)==Recherche_naive(L,x)
    return Test
    
# N=200
# print(Essais(N))

def Traces() :
    Lk=list(range(2,15))
    LT_Dicho=[]
    LT_Naif=[]
    for k in Lk :
        L=sorted([uniform(0,1000) for i in range(3**k)])
        x=uniform(L[0],L[-1])
        t_0=time.clock()
        Recherche_Dicho(L,x)
        t_1=time.clock()
        Recherche_naive(L,x)
        t_2=time.clock()
        LT_Dicho.append(t_1-t_0)
        LT_Naif.append(t_2-t_1)
    figure()
    grid()
    semilogy()
    plot(Lk,LT_Dicho,color='green')
    plot(Lk,LT_Naif,color='magenta')
    legend(('algo dicho','algo naïf'),loc='upper left',shadow=True)
    show()
    
Traces()