##Question 1.1

def jour_mois(a,m):
    """ Fonction auxiliaire qui renvoie le nombre jour du mois m dans l'année a"""
    if m in [1,3,5,7,8,10,12]: #On traite les mois de 31 jours
        return 31
    if m == 2: #Le mois de février est particulier
        if a%400==0:
            return 29
        elif a%100 ==0:
            return 28
        elif a%4 ==0:
            return 29
        else :
            return 28
    else: #Les autres mois ont 30 jours
        return 30


def jour_an(a):
    """ Fonction auxiliaire qui renvoie le nombre de jour dans l'année a (pour traiter les années bisextiles) """
    if a%400==0:
        return 366
    elif a%100 ==0:
        return 365
    elif a%4 ==0:
        return 366
    else :
        return 365

def jour_vecu (a,m,j ):
    res = 0 #On initialise à 0
    if j!=1: #On se ramène au premier jour du mois
        res += 1 -j
    res +=30 #On ajoute 30 pour se ramener au 31
    for k in range(m,12): #Pour chaque mois autre que le mois de décembre (déjà traité par l'ajout de 30) on ajout son nombre de jour
        res += jour_mois(a,k)
    for k in range(a+1,2022): #Idem pour les années
        res += jour_an(k)
    return res

##Question 1.2

def jour_de_naissance(a,m,j):
    nb = jour_vecu(a,m,j)%7 #On récupère le nombre de jour vécu. Le modulo 7 sert à retirer les semaines complètes
    if nb == 0 : #Si on a vécu un nombre rond de semaine, on est né le même jour donc vendredi
        return "vendredi"
    #Sinon il faut compter à reculons car on part du 31 décembre puis on retire des jours
    if nb==6 :
        return "samedi"
    if nb==5 :
        return "dimanche"
    if nb==4 :
        return "lundi"
    if nb == 3 :
        return "mardi"
    if nb==2 :
        return "mercredi"
    if nb==1 :
        return "jeudi"



##Question 1.3

def fibo(n):
    if n==0:
        return 0
    if n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)


##Question 1.4

def parmi(k,n):
    if n<k:
        return 0
    if k==0:
        return 1
    return parmi(k-1,n-1) + parmi(k,n-1)

##Question 2.1

def fibo(n):
    li = [0 for i in range(n+1)] #Liste qui contiendra les aleurs de la liste
    li[1] = 1 #li[0] vaut déjà 0, donc on initialise que li[1]
    for k in range(2,n+1): #on calcul les autres termes 1 à 1
        li[k] = li[k-1] + li[k-2]
    return li[-1] #Le dernier terme calculé est celui qu'on cherche

def parmi(k,n):
    tab = [[0 for j in range(n+1)] for i in range(n+1)] #On initialise un tableau de taille n*n de sorte que tab[k][n] contienne la valeur de k parmis n
    for i in range(n+1):
        tab[0][i] = 1 #0 parmis n vaut toujours 1

    for i in range(1,n+1): #On fait varier n d'abord
        for j in range(1,n+1): #Puis k
            tab[j][i] = tab[j-1][i-1] + tab[j][i-1] #On applique la formule de récurrence pour toutes les cases
    return tab[k][n]

## Question 2.2


def tri(li):
    """ Tri une liste avec l'algorithme du tri à bulle"""
    n = len(li)
    for j in range(n):
        for i in range(n-1):
            if li[i]> li[i+1]:
                li[i+1],li[i] = li[i], li[i+1]
    return li


## Question 2.3

def fusion(l1,l2):
    """ fonction auxiliaire qui fusionne 2 listes"""
    res = []
    i = j = 0 #variable indiquant la position dans la liste
    while i<len(l1) and j<len(l2): #Tant qu'on a pas atteint la taille d'une des 2 listes
        if l1[i]>l2[j]: #On compare les éléments considérés et on ajoute le plus grand
            res.append(l1[i])
            i+=1
        else:
            res.append(l2[j])
            j+=1
    #Une fois qu'on a finis une des 2 listes, on a joute les élements restants de la 2e
    if i == len(l1):
        res += l2[j:]
    else:
        res += l1[i:]
    return res


def tri_fusion(li):
    if len(li)==1: #Une liste de taille 1 est triée
        return li
    #Sinon on coupe la liste en 2
    l1 = li[0:len(li)//2]
    l2 = li[len(li)//2:]
    #Et on renvoie la fusion des 2 moitiées triées
    return fusion(tri_fusion(l1), tri_fusion(l2))


## Question 2.4


def liste_valeur(x):
    U = [x] #U contiendra la liste de nos valeurs. On a bien U[0]=x
    while U[-1] != 1: #Tant qu'on a pas atteint la valeur 1, on applique la formule
        if U[-1]%2 :
            U.append(3*U[-1] +1)
        else:
            U.append(U[-1]//2)
    return U

##Question 3.1

import numpy as np
import matplotlib.pyplot as plt



def cercle(x0,y0,r):
    inter = np.linspace(-np.pi,np.pi,200) #On coupe l'intervalle [-pi, pi] en 200 (arbitraire)
    lx = x0+r*np.cos(inter) #Equation de l'absisse
    ly = y0+r*np.sin(inter) #Equation de l'ordonnée
    plt.axis("equal") #Pour avoir un affichage plus joli. C'est pas obligatoire
    plt.plot(lx,ly, color = "black") #On ajoute le cercle
    #plt.show() #Décommenter cette ligne pour afficher le cercle. Elle est commentée pour la fonction suivante

##Question 3.2

def fractale(N):
    """ trace une fractale qui se répète N fois """
    plt.figure()
    Liste_cercle=[(0,0,1)] #Contient la liste des cercles à tracer
    for i in range(N):
        aux=[] #Variable auxiliaire qui contient la liste des cercles à tracer à l'étape d'après
        for x,y,r in Liste_cercle:  #On parcours notre liste de cercles de l'étape précédente
            cercle(x,y,r) #On trace le cercle
            #On stock dans aux les prochains cercles à tracer
            aux.append((x+3*r/2, y, r/2)) #Soit on se déplace de 3r/2 selon les absices
            aux.append((x, y-3*r/2, r/2)) #Soit selon les ordonnés
        Liste_cercle = aux
    plt.axis("equal")
    plt.show()