import time
import matplotlib.pyplot as plt
import random as rd
import math


## Exo 1 : Factorielle


def fact_it(n):
    f=1
    for k in range(1,n+1):
        f*=k
    return f

def fact_rec(n):
    if n==0:
        return 1
    else:
        return n*fact_rec(n-1)

N=[]
Ti=[]
Tr=[]
p=4

for n in range(0,10**p,10**(p-2)):
    print(n)
    t1=time.process_time()
    fact_it(n)
    t2=time.process_time()
    N.append(n)
    Ti.append(t2-t1)
    t1=time.process_time()
    # fact_rec(n)
    t2=time.process_time()
    Tr.append(t2-t1)

plt.plot(N,Ti,c='g')
plt.plot(N,Tr,c='b')
plt.show()

## Exo 2 : Primalité

def est_premier(n):
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True

N=[]
T=[]
P=[]

for a in range(10,14):
    for b in range(1,9):
        for c in [7,11,13,17,19]:
            p=b*10**a+c
            if est_premier(p):
                P.append(p)

for p in P:
    print(p)
    t1=time.process_time()
    est_premier(p)
    t2=time.process_time()
    N.append(p)
    T.append(t2-t1)

plt.plot(N,T,c='b')
plt.show()

## Exo 3 : Exponentiation rapide

def exp(x,n):
    if n==0:
        return 1
    else:
        return x*exp(x,n-1)

def expr(x,n):
    if n==0:
        return 1
    elif n==1:
        return x
    else:
        return expr(x,n%2)*expr(x,n//2)**2


p=3
x=10**200-1
N=[]
T=[]
Tr=[]

for n in range(0,10**p,10**(p-1)):
    print(n)
    t1=time.process_time()
    exp(x,n)
    t2=time.process_time()
    N.append(n)
    T.append(t2-t1)
    t1=time.process_time()
    expr(x,n)
    t2=time.process_time()
    Tr.append(t2-t1)

plt.plot(N,T,c='g')
plt.plot(N,Tr,c='b')
plt.show()

## Exo 4 : Fibonacci

def fib(n):
    if n==0 or n==1:
        return n
    else:
        return fib(n-1)+fib(n-2)


N=[]
T=[]

for n in range(0,35):
    t1=time.process_time()
    print(fib(n))
    t2=time.process_time()
    N.append(n)
    T.append(t2-t1)

plt.plot(N,T)
plt.show()

## Exo 5 : Recherche du max

def max(L):
    m=L[0]
    for k in range(len(L)):
        if L[k]>m:
            m=L[k]
    return m


N,T=[],[]
p=7

for n in range(1,10**p,10**(p-1)):
    print(n)
    L=[rd.randint(1,1000) for k in range(n)]
    t1=time.process_time()
    max(L)
    t2=time.process_time()
    N.append(n)
    T.append(t2-t1)

plt.plot(N,T,c='g')
plt.show()

## Exo 6 : Recherche des communs

def communs(A,B):
    C=[]
    for a in A:
        for b in B:
            if a==b:
                C.append(a)
    return C


N,T=[],[]
p=4

for n in range(1,10**p,10**(p-1)):
    print(n)
    A=[rd.randint(1,1000) for k in range(n)]
    B=[rd.randint(1,1000) for k in range(n)]
    t1=time.process_time()
    communs(A,B)
    t2=time.process_time()
    N.append(n)
    T.append(t2-t1)

plt.plot(N,T,c='g')
plt.show()


## Exo 7 : Recherche d'un élément

def recherche_lin(c,L):
    for k in range(len(L)):
        if L[k]==c:
            return k
        elif L[k]>c:
            return False
    return False

def recherche_dicho(c,L):
    a,b=0,len(L)-1
    while a<=b:
        m=(a+b)//2
        if L[m]==c:
            return m
        elif L[m]<c:
            a=m+1
        else:
            b=m-1
    return False

N,Tl,Td=[],[],[]
p=7
c=666

for n in range(0,10**p,10**(p-1)):
    print(n)
    L=[rd.randint(1,1000) for k in range(n)]
    L.sort()
    t1=time.process_time()
    recherche_lin(c,L)
    t2=time.process_time()
    N.append(n)
    Tl.append(t2-t1)
    t3=time.process_time()
    recherche_dicho(c,L)
    t4=time.process_time()
    Td.append(t4-t3)

plt.plot(N,Tl,c='g')
plt.plot(N,Td,c='b')
plt.show()

##

def echange(L,i,j):
    L[i],L[j] = L[j],L[i]
    return

def select(L):
    l = len(L)
    for i in range(l):
        for j in range(i+1,l):
            if L[j] < L[i]:
                echange(L,i,j)
    return


def insere(L):
    for k in range(1,len(L)):
        i = k-1
        while i>=0 and L[i] > L[i+1]:
            L[i],L[i+1] = L[i+1],L[i]
            i = i-1
    return


N=[]
Ts,Ti=[],[]
p=4

for n in range(0,10**p,10**(p-1)):
    print(n)
    L=[rd.randint(1,1000) for k in range(n)]
    L2=L.copy()
    t1=time.process_time()
    select(L)
    t2=time.process_time()
    N.append(n)
    Ts.append(t2-t1)
    t3=time.process_time()
    insere(L2)
    t4=time.process_time()
    Ti.append(t4-t3)

plt.plot(N,Ts,c='g')
plt.plot(N,Ti,c='b')
plt.show()