Référence : https://fr.calameo.com/read/00673140546fcda873cf0

Exercice 3¶

Question 1) a)¶

In [87]:

def total_hors_reduction(tab):
    """Renvoie la somme des valeurs numériques contenues 
    dans un tableau tab
    """
    somme = 0
    for element in tab:
        somme = somme + element
    return somme

#tests unitaires
def test_total_hors_reduction():
    assert total_hors_reduction([]) == 0
    assert total_hors_reduction([2,2]) == 4
    assert total_hors_reduction([1,2]) == 3
    assert total_hors_reduction([-1,2]) == 1
    print("Tests unitaires réussis pour total_hors_reduction")
    
test_total_hors_reduction()

def total_hors_reduction(tab): """Renvoie la somme des valeurs numériques contenues dans un tableau tab """ somme = 0 for element in tab: somme = somme + element return somme #tests unitaires def test_total_hors_reduction(): assert total_hors_reduction([]) == 0 assert total_hors_reduction([2,2]) == 4 assert total_hors_reduction([1,2]) == 3 assert total_hors_reduction([-1,2]) == 1 print("Tests unitaires réussis pour total_hors_reduction") test_total_hors_reduction()

Tests unitaires réussis pour total_hors_reduction

Question 1) b)¶

In [88]:

def offre_bienvenue(tab):
    """
    Le site de vente propose la promotion suivante 
    comme offre de bienvenue : 20% de réduction
    sur le premier article de la liste, 
    30% de réduction sur le deuxième article de la liste 
    (s’il y a au moins deux articles) 
    et aucune réduction sur le reste des articles 
    (s’il y en a).
    Fonction qui en prend paramètre le tableau tab 
    des prix des articles du panier d’un client 
    et qui renvoie  le total à payer lorsqu'on 
    leur applique l’offre de bienvenue.
    """
    somme = 0
    longueur = len(tab)
    if longueur > 0:
        somme = tab[0] * 0.8
    if longueur > 1:
        somme = somme + tab[1] * 0.7
    if longueur > 2:
        for i in range(2, longueur):
            somme = somme + tab[i]
    return somme

#tests unitaires
def test_offre_bienvenue():
    assert offre_bienvenue([]) == 0
    assert offre_bienvenue([100]) == 80.0
    assert offre_bienvenue([100, 200]) == 220.0
    assert offre_bienvenue([100, 200, 300]) == 520
    print("Tests unitaires réussis pour offre_bienvenue")

test_offre_bienvenue()

def offre_bienvenue(tab): """ Le site de vente propose la promotion suivante comme offre de bienvenue : 20% de réduction sur le premier article de la liste, 30% de réduction sur le deuxième article de la liste (s’il y a au moins deux articles) et aucune réduction sur le reste des articles (s’il y en a). Fonction qui en prend paramètre le tableau tab des prix des articles du panier d’un client et qui renvoie le total à payer lorsqu'on leur applique l’offre de bienvenue. """ somme = 0 longueur = len(tab) if longueur > 0: somme = tab[0] * 0.8 if longueur > 1: somme = somme + tab[1] * 0.7 if longueur > 2: for i in range(2, longueur): somme = somme + tab[i] return somme #tests unitaires def test_offre_bienvenue(): assert offre_bienvenue([]) == 0 assert offre_bienvenue([100]) == 80.0 assert offre_bienvenue([100, 200]) == 220.0 assert offre_bienvenue([100, 200, 300]) == 520 print("Tests unitaires réussis pour offre_bienvenue") test_offre_bienvenue()

Tests unitaires réussis pour offre_bienvenue

Question 2¶

In [89]:

def prix_solde(tab):
    """
    Lors de la période des soldes, le site de vente propose les réductions suivantes :
    — si le panier contient 5 articles ou plus, une réduction globale de 50%,
    — si le panier contient 4 articles, une réduction globale de 40%,
    — si le panier contient 3 articles, une réduction globale de 30%,
    — si le panier contient 2 articles, une réduction globale de 20%,
    — si le panier contient 1 article, une réduction globale de 10%.
    Prend pour argument le tableau tab des prix des articles
    du panier d’un client et renvoyant le total des  prix 
    de ces articles lorsqu’on leur applique la réduction des soldes    
    """
    total = total_hors_reduction(tab)
    longueur = len(tab)
    if longueur >= 5:
        return total * 0.5
    elif longueur >= 4:
        return total * 0.6
    elif longueur >= 3:
        return total * 0.7
    elif longueur >= 2:
        return total * 0.8
    return total * 0.9    

def test_prix_solde():
    assert prix_solde([]) == 0
    assert prix_solde([100]) == 90.0
    assert prix_solde([100, 200]) == 240.0
    assert prix_solde([100, 200, 300]) == 420.0
    assert prix_solde([100, 200, 300, 400]) == 600.0
    assert prix_solde([100, 200, 300, 400, 500]) == 750.0
    print("Tests unitaires réussis pour prix_solde")

test_prix_solde()

def prix_solde(tab): """ Lors de la période des soldes, le site de vente propose les réductions suivantes : — si le panier contient 5 articles ou plus, une réduction globale de 50%, — si le panier contient 4 articles, une réduction globale de 40%, — si le panier contient 3 articles, une réduction globale de 30%, — si le panier contient 2 articles, une réduction globale de 20%, — si le panier contient 1 article, une réduction globale de 10%. Prend pour argument le tableau tab des prix des articles du panier d’un client et renvoyant le total des prix de ces articles lorsqu’on leur applique la réduction des soldes """ total = total_hors_reduction(tab) longueur = len(tab) if longueur >= 5: return total * 0.5 elif longueur >= 4: return total * 0.6 elif longueur >= 3: return total * 0.7 elif longueur >= 2: return total * 0.8 return total * 0.9 def test_prix_solde(): assert prix_solde([]) == 0 assert prix_solde([100]) == 90.0 assert prix_solde([100, 200]) == 240.0 assert prix_solde([100, 200, 300]) == 420.0 assert prix_solde([100, 200, 300, 400]) == 600.0 assert prix_solde([100, 200, 300, 400, 500]) == 750.0 print("Tests unitaires réussis pour prix_solde") test_prix_solde()

Tests unitaires réussis pour prix_solde

Question 3) a)¶

In [90]:

def minimum(tab):
    """
    Prend en paramètre un tableau de nombres tab
    Renvoie la valeur minimum de ce tableau    
    """
    if len(tab) > 0:
        mini = tab[0]
        for k in range(1, len(tab)):
            if tab[k] < mini:
                mini = tab[k]
        return mini
    
def test_minimum():
    assert minimum([]) == None
    assert minimum([-1]) == -1
    assert minimum([-1, 1]) == -1
    assert minimum([-1,-2,1]) == -2
    assert minimum([-2,-1,1]) == -2
    assert minimum([1, -1, -2]) == -2
    print("Tests unitaires réussis pour minimum")

test_minimum()

def minimum(tab): """ Prend en paramètre un tableau de nombres tab Renvoie la valeur minimum de ce tableau """ if len(tab) > 0: mini = tab[0] for k in range(1, len(tab)): if tab[k] < mini: mini = tab[k] return mini def test_minimum(): assert minimum([]) == None assert minimum([-1]) == -1 assert minimum([-1, 1]) == -1 assert minimum([-1,-2,1]) == -2 assert minimum([-2,-1,1]) == -2 assert minimum([1, -1, -2]) == -2 print("Tests unitaires réussis pour minimum") test_minimum()

Tests unitaires réussis pour minimum

Question 3) b)¶

In [91]:

def offre_bon_client(tab):
    """
    Pour ses bons clients, le site de vente propose
    une offre promotionnelle, à partir de 2
    articles achetés, l’article le moins cher
    des articles commandés est offert
    Prend pour paramètre le tableau des prix
    des articles du panier d’un client
    et renvoie le total à payer lorsquon leur applique 
    l'offre bon client.    
    """
    longueur = len(tab)
    if longueur >= 2:
        return total_hors_reduction(tab) - minimum(tab)
    return total_hors_reduction(tab)    

def test_offre_bon_client():
    assert offre_bon_client([]) == 0
    assert offre_bon_client([100]) == 100
    assert offre_bon_client([50, 200]) == 200
    assert offre_bon_client([100, 200, 300]) == 500
    assert offre_bon_client([200, 100, 300]) == 500
    assert offre_bon_client([200, 300, 100]) == 500
    print("Tests unitaires réussis pour offre_bon_client")

test_offre_bon_client()

def offre_bon_client(tab): """ Pour ses bons clients, le site de vente propose une offre promotionnelle, à partir de 2 articles achetés, l’article le moins cher des articles commandés est offert Prend pour paramètre le tableau des prix des articles du panier d’un client et renvoie le total à payer lorsquon leur applique l'offre bon client. """ longueur = len(tab) if longueur >= 2: return total_hors_reduction(tab) - minimum(tab) return total_hors_reduction(tab) def test_offre_bon_client(): assert offre_bon_client([]) == 0 assert offre_bon_client([100]) == 100 assert offre_bon_client([50, 200]) == 200 assert offre_bon_client([100, 200, 300]) == 500 assert offre_bon_client([200, 100, 300]) == 500 assert offre_bon_client([200, 300, 100]) == 500 print("Tests unitaires réussis pour offre_bon_client") test_offre_bon_client()

Tests unitaires réussis pour offre_bon_client

Question 4)¶

Afin de diminuer le stock de ses articles dans ses entrepôts, l’entreprise imagine faire l’offre suivante à ses clients : en suivant l’ordre des articles dans le panier du client, elle considère les 3 premiers articles et offre le moins cher, puis les 3 suivants et offre le moins cher et ainsi de suite jusqu’à ce qu’il reste au plus 2 articles qui n’ont alors droit à aucune réduction. Exemple : Si le panier du client contient un pantalon à 30,50 euros, un tee-shirt à 15 euros, une paire de chaussettes à 6 euros, une jupe à 20 euros, une paire de collants à 5 euros, une robe à 35 euros et un short à 10,50 euros, ce panier est représenté par le tableau suivant :

tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]

Pour le premier groupe (le pantalon à 30,50 euros, le tee-shirt à 15 euros, la paire de chaussettes à 6 euros), l’article le moins cher, la paire de chaussettes à 6 euros, est offert. Pour le second groupe (la jupe à 20 euros, la paire de collants à 5 euros, la robe à 35 euros), la paire de collants à 5 euros est offerte. Donc le total après promotion de déstockage est 111 euros. On constate que le prix après promotion de déstockage dépend de l’ordre dans lequel se pré- sentent les articles dans le panier.

In [132]:

def offre_bloc(tab, debut_bloc):
    """
    Renvoie le total pour un bloc de 3 articles consécutifs
    dans le panier, l'article avec le prix minimal étant déduit
    """
    mini_bloc = tab[debut_bloc]
    somme_bloc = tab[debut_bloc]
    for k in range(debut_bloc + 1, debut_bloc + 3):
        if tab[k] < mini_bloc:
            mini_bloc = tab[k]
        somme_bloc = somme_bloc + tab[k]
    return somme_bloc - mini_bloc


def test_offre_bloc():
    assert offre_bloc([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5], 0) == 45.5
    assert offre_bloc([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5], 3) == 55
    print("Tests unitaires réussis pour offre_bloc")


test_offre_bloc()



def promotion_bloc_trois(tab):
    """
    Prend en paramètre un tableau de prix d'articles dans un panier
    Renvoie le prix du panier après déduction du minimum des 3 premiers
    , du minimum des 3 suivants etc ...
    """
    total = 0
    longueur = len(tab)
    debut_bloc = 0
    while longueur - debut_bloc > 2:
        total = total + offre_bloc(tab, debut_bloc)
        debut_bloc = debut_bloc + 3
    while longueur - debut_bloc > 0:
        total = total + tab[debut_bloc]
        debut_bloc = debut_bloc + 1
    return total

def test_promotion_bloc_trois():
    assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 111
    assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0]) == 100.5
    assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5, 8, 6]) == 119
    print("Tests unitaires réussis pour promotion_bloc_trois")
    
test_promotion_bloc_trois()

def offre_bloc(tab, debut_bloc): """ Renvoie le total pour un bloc de 3 articles consécutifs dans le panier, l'article avec le prix minimal étant déduit """ mini_bloc = tab[debut_bloc] somme_bloc = tab[debut_bloc] for k in range(debut_bloc + 1, debut_bloc + 3): if tab[k] < mini_bloc: mini_bloc = tab[k] somme_bloc = somme_bloc + tab[k] return somme_bloc - mini_bloc def test_offre_bloc(): assert offre_bloc([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5], 0) == 45.5 assert offre_bloc([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5], 3) == 55 print("Tests unitaires réussis pour offre_bloc") test_offre_bloc() def promotion_bloc_trois(tab): """ Prend en paramètre un tableau de prix d'articles dans un panier Renvoie le prix du panier après déduction du minimum des 3 premiers , du minimum des 3 suivants etc ... """ total = 0 longueur = len(tab) debut_bloc = 0 while longueur - debut_bloc > 2: total = total + offre_bloc(tab, debut_bloc) debut_bloc = debut_bloc + 3 while longueur - debut_bloc > 0: total = total + tab[debut_bloc] debut_bloc = debut_bloc + 1 return total def test_promotion_bloc_trois(): assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 111 assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0]) == 100.5 assert promotion_bloc_trois([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5, 8, 6]) == 119 print("Tests unitaires réussis pour promotion_bloc_trois") test_promotion_bloc_trois()

Tests unitaires réussis pour offre_bloc
Tests unitaires réussis pour promotion_bloc_trois

Question 4) a)¶

Proposer un panier contenant les mêmes articles que ceux de l’exemple mais ayant un prix après promotion de déstockage différent de 111 euros.

In [93]:

from random import shuffle
tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]
tab2 = tab[:]
print(tab2)
shuffle(tab2)
promotion_bloc_trois(tab2)

from random import shuffle tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5] tab2 = tab[:] print(tab2) shuffle(tab2) promotion_bloc_trois(tab2)

[30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]

Out[93]:

97.0

Question 4) b)¶

(b) Proposer un panier contenant les mêmes articles mais ayant le prix après promotion de déstockage le plus bas possible.

In [94]:

tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]
tab3 = sorted(tab, reverse = True)
promotion_bloc_trois(tab3)

tab = [30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5] tab3 = sorted(tab, reverse = True) promotion_bloc_trois(tab3)

Out[94]:

96.0

Question 4) c)¶

(c) Une fois ses articles choisis, quel algorithme le client peut-il utiliser pour modifier son panier afin de s’assurer qu’il obtiendra le prix après promotion de déstockage le plus bas possible ? On ne demande pas d’écrire cet algorithme.

On peut appliquer l'algorithme glouton ci-dessous :

• pour le premier bloc on prend les trois articles avec les prix les plus élevés, le minimum de ces trois est un choix optimal si on n'applique la réduction qu'au premier bloc : en effet il faut forcément en prendre trois et le plus petit de trois donc on ne peut faire mieux que le troisième prix par ordre décroissant
• pour le second bloc, on prend les trois articles avec les prix les plus élevés parmi ceux restants, le minimum de ces trois est un choix optimal si on n'applique la réduction qu'aux deux premiers blocs : en effet pour tout autre choix de deux blocs, en réordonnant événtuellement les blocs par ordre décroissant de leur minimum, on a forcément le minimum du premier bloc <= au minimum de notre premier choix glouton de bloc qui contient les trois plus grand prix, minimum du second bloc <= au minimum notre second choix glouton de bloc qui contient les plus grands de rangs 4, 5 et 6 .
• etc tant qu'il reste au moins trois articles. On peut démontrer en itérant le raisonnment qu'à l'étape k le choix optimal local en prenant les trois plus grand prix restants pour constituer un nouveau bloc donne un choix optimal global si on se restreint au choix de k blocs ...

Une façon de réaliser ces choix gloutons est de trier d'abord les valeurs ordre décroissant par exemple avec l'algorithme de tri par sélection et de sommer tous les prix dont l'index n'est pas de la forme 3 * k + 2 (troisième position dans le bloc donc minimum du bloc)

In [144]:

def index_maxi(tab, debut):
    maxi = tab[debut]
    imaxi = debut
    for k in range(debut + 1, len(tab)):
        if tab[k] > maxi:
            maxi = tab[k]
            imaxi = k
    return imaxi

def tri_selection_decroissant(tab):
    """Tri par sélection par ordre décroissant
    en place"""
    for i in range(len(tab) - 1):
        imax = index_maxi(tab, i)
        tab[i], tab[imax] = tab[imax], tab[i]

def promotion_bloc_trois_glouton(tab):
    copie_tab = tab[:]
    tri_selection_decroissant(copie_tab)
    return promotion_bloc_trois(copie_tab) 

def promotion_bloc_trois_glouton2(tab):
    total = 0
    longueur = len(tab)
    debut_bloc = 0
    while longueur - debut_bloc > 2:
        for i in range(debut_bloc, debut_bloc + 3):
            imax = index_maxi(tab, i)
            tab[i], tab[imax] = tab[imax], tab[i]
        total = total + tab[debut_bloc] + tab[debut_bloc + 1]
        debut_bloc = debut_bloc + 3
    while longueur - debut_bloc > 0:
        total = total + tab[debut_bloc]
        debut_bloc = debut_bloc + 1
    return total  

def test_promotion_bloc_trois_glouton():
    assert promotion_bloc_trois_glouton([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 96
    print("Test unitaire réussi pour bloc_trois_glouton")
    
def test_promotion_bloc_trois_glouton2():
    assert promotion_bloc_trois_glouton2([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 96
    print("Test unitaire réussi pour bloc_trois_glouton2")
    
test_promotion_bloc_trois_glouton()
test_promotion_bloc_trois_glouton2()

def index_maxi(tab, debut): maxi = tab[debut] imaxi = debut for k in range(debut + 1, len(tab)): if tab[k] > maxi: maxi = tab[k] imaxi = k return imaxi def tri_selection_decroissant(tab): """Tri par sélection par ordre décroissant en place""" for i in range(len(tab) - 1): imax = index_maxi(tab, i) tab[i], tab[imax] = tab[imax], tab[i] def promotion_bloc_trois_glouton(tab): copie_tab = tab[:] tri_selection_decroissant(copie_tab) return promotion_bloc_trois(copie_tab) def promotion_bloc_trois_glouton2(tab): total = 0 longueur = len(tab) debut_bloc = 0 while longueur - debut_bloc > 2: for i in range(debut_bloc, debut_bloc + 3): imax = index_maxi(tab, i) tab[i], tab[imax] = tab[imax], tab[i] total = total + tab[debut_bloc] + tab[debut_bloc + 1] debut_bloc = debut_bloc + 3 while longueur - debut_bloc > 0: total = total + tab[debut_bloc] debut_bloc = debut_bloc + 1 return total def test_promotion_bloc_trois_glouton(): assert promotion_bloc_trois_glouton([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 96 print("Test unitaire réussi pour bloc_trois_glouton") def test_promotion_bloc_trois_glouton2(): assert promotion_bloc_trois_glouton2([30.5, 15.0, 6.0, 20.0, 5.0, 35.0, 10.5]) == 96 print("Test unitaire réussi pour bloc_trois_glouton2") test_promotion_bloc_trois_glouton() test_promotion_bloc_trois_glouton2()

Test unitaire réussi pour bloc_trois_glouton
Test unitaire réussi pour bloc_trois_glouton2

Exercice 4¶

In [97]:

ARBRE_VIDE = None

def arbre(arbre_gauche, valeur, arbre_droit):
    return (arbre_gauche, valeur, arbre_droit)

def racine(arbre):
    return arbre[1]

def gauche(arbre):
    return arbre[0]

def droit(arbre):
    return arbre[2]

def est_vide(arbre):
    return arbre is ARBRE_VIDE

ARBRE_VIDE = None def arbre(arbre_gauche, valeur, arbre_droit): return (arbre_gauche, valeur, arbre_droit) def racine(arbre): return arbre[1] def gauche(arbre): return arbre[0] def droit(arbre): return arbre[2] def est_vide(arbre): return arbre is ARBRE_VIDE

In [98]:

B = arbre(
     arbre(
         arbre(
             arbre(ARBRE_VIDE, "Marc", ARBRE_VIDE)
             , "Lea"
             , arbre(ARBRE_VIDE, "Lea", ARBRE_VIDE)
             )
         ,"Lea"
         ,arbre(
             arbre(ARBRE_VIDE, "Claire", ARBRE_VIDE)
             , "Theo"
             , arbre(ARBRE_VIDE, "Theo", ARBRE_VIDE)
             )
     )
    , "Lea"
    ,arbre(
         arbre(
             arbre(ARBRE_VIDE, "Marie", ARBRE_VIDE)
             , "Louis"
             , arbre(ARBRE_VIDE, "Louis", ARBRE_VIDE)
             )
         ,"Louis"
         ,arbre(
             arbre(ARBRE_VIDE, "Anne", ARBRE_VIDE)
             , "Anne"
             , arbre(ARBRE_VIDE, "Kevin", ARBRE_VIDE)
             )
    )
)

B = arbre( arbre( arbre( arbre(ARBRE_VIDE, "Marc", ARBRE_VIDE) , "Lea" , arbre(ARBRE_VIDE, "Lea", ARBRE_VIDE) ) ,"Lea" ,arbre( arbre(ARBRE_VIDE, "Claire", ARBRE_VIDE) , "Theo" , arbre(ARBRE_VIDE, "Theo", ARBRE_VIDE) ) ) , "Lea" ,arbre( arbre( arbre(ARBRE_VIDE, "Marie", ARBRE_VIDE) , "Louis" , arbre(ARBRE_VIDE, "Louis", ARBRE_VIDE) ) ,"Louis" ,arbre( arbre(ARBRE_VIDE, "Anne", ARBRE_VIDE) , "Anne" , arbre(ARBRE_VIDE, "Kevin", ARBRE_VIDE) ) ) )

In [99]:

B

B

Out[99]:

((((None, 'Marc', None), 'Lea', (None, 'Lea', None)),
  'Lea',
  ((None, 'Claire', None), 'Theo', (None, 'Theo', None))),
 'Lea',
 (((None, 'Marie', None), 'Louis', (None, 'Louis', None)),
  'Louis',
  ((None, 'Anne', None), 'Anne', (None, 'Kevin', None))))

In [100]:

def vainqueur(arbre):
    return racine(arbre)

def vainqueur(arbre): return racine(arbre)

In [101]:

vainqueur(B)

vainqueur(B)

Out[101]:

'Lea'

In [102]:

def finale(arbre):
    return [racine(gauche(arbre)), racine(droit(arbre))]

def finale(arbre): return [racine(gauche(arbre)), racine(droit(arbre))]

In [103]:

finale(B)

finale(B)

Out[103]:

['Lea', 'Louis']

In [104]:

def occurences(arb, nom):
    if est_vide(arb):
        return 0
    if racine(arb) == nom:
        return 1 + occurences(gauche(arb), nom) + occurences(droit(arb), nom)
    else:
        return occurences(gauche(arb), nom) + occurences(droit(arb), nom)

def occurences(arb, nom): if est_vide(arb): return 0 if racine(arb) == nom: return 1 + occurences(gauche(arb), nom) + occurences(droit(arb), nom) else: return occurences(gauche(arb), nom) + occurences(droit(arb), nom)

In [105]:

occurences(B, "Lea")

occurences(B, "Lea")

Out[105]:

4

In [106]:

occurences(B, "Louis")

occurences(B, "Louis")

Out[106]:

3

In [107]:

def a_gagne(arb, nom):
    if est_vide(arb):
        return None
    #cas d'une feuille
    if (droit(arb) is  ARBRE_VIDE 
        and gauche(arb) is  ARBRE_VIDE):
        return False
    #cas d'une victoire
    if racine(arb) == nom:
        return True
    #recherche récursive dans les sous-arbres
    return a_gagne(gauche(arb), nom) or a_gagne(droit(arb), nom)

def a_gagne(arb, nom): if est_vide(arb): return None #cas d'une feuille if (droit(arb) is ARBRE_VIDE and gauche(arb) is ARBRE_VIDE): return False #cas d'une victoire if racine(arb) == nom: return True #recherche récursive dans les sous-arbres return a_gagne(gauche(arb), nom) or a_gagne(droit(arb), nom)

In [108]:

a_gagne(B, "Marc")

a_gagne(B, "Marc")

Out[108]:

False

In [109]:

a_gagne(B, "Louis")

a_gagne(B, "Louis")

Out[109]:

True

In [110]:

def nombre_matchs_faux( arb , nom):
    """ arbre_competition , str -> int """
    return occurences( arb , nom )

def nombre_matchs_faux( arb , nom): """ arbre_competition , str -> int """ return occurences( arb , nom )

In [111]:

nombre_matchs_faux(B , "Lea")

nombre_matchs_faux(B , "Lea")

Out[111]:

4

Lea a gagné trois matchs et non quatre, de même Louis en a gagné deux et non trois

In [112]:

nombre_matchs_faux(B , "Louis")

nombre_matchs_faux(B , "Louis")

Out[112]:

3

In [113]:

def nombre_matchs_correct( arb , nom):
    """ arbre_competition , str -> int """
    if est_vide(arb):
        return 0
    return occurences( arb , nom ) - 1

def nombre_matchs_correct( arb , nom): """ arbre_competition , str -> int """ if est_vide(arb): return 0 return occurences( arb , nom ) - 1

In [114]:

nombre_matchs_correct(B , "Lea")

nombre_matchs_correct(B , "Lea")

Out[114]:

3

In [115]:

def liste_joueurs ( arb ):
    """ arbre_competition -> tableau """
    #cas d'une arbre vide
    if est_vide ( arb ):
        return []
    #feuille
    elif est_vide(gauche(arb)) and est_vide(droit(arb)):
        return [racine(arb)]
    else :
        return liste_joueurs(gauche(arb)) + liste_joueurs(droit(arb))

def liste_joueurs ( arb ): """ arbre_competition -> tableau """ #cas d'une arbre vide if est_vide ( arb ): return [] #feuille elif est_vide(gauche(arb)) and est_vide(droit(arb)): return [racine(arb)] else : return liste_joueurs(gauche(arb)) + liste_joueurs(droit(arb))

In [116]:

liste_joueurs(B)

liste_joueurs(B)

Out[116]:

['Marc', 'Lea', 'Claire', 'Theo', 'Marie', 'Louis', 'Anne', 'Kevin']

Exercice 5¶

In [117]:

def creer_pile_vide():
    return []

def est_vide_pile(pile):
    return len(pile) == 0

def empiler(pile, element):
    pile.append(element)
    
def depiler(pile):
    return pile.pop()

def creer_pile_vide(): return [] def est_vide_pile(pile): return len(pile) == 0 def empiler(pile, element): pile.append(element) def depiler(pile): return pile.pop()

In [118]:

FILE_VIDE = None

class Noeud:
    
    def __init__(self, valeur, suivant):
        self._valeur = valeur
        self._suivant = suivant
        
    def __str__(self):
        return f"({self._valeur}, {str(self._suivant)})"
        
class File:
    
    def __init__(self):
        self._premier = None
        self._dernier = None
        self._taille = 0
        
    def __len__(self):
        return self._taille
    
    def est_vide(self):
        return self._taille == 0
    
    def enfiler(self, element):
        nouveau = Noeud(element, None)
        if self.est_vide():
            self._premier = self._dernier = nouveau
        else:
            self._dernier._suivant = nouveau
            self._dernier = nouveau
        self._taille += 1
    
    def defiler(self):
        if not self.est_vide():
            valeur = self._premier._valeur
            self._premier = self._premier._suivant
            self._taille -= 1
            if self.est_vide():
                self._dernier = None
            return valeur
    
    def __str__(self):
        return str(self._premier)
    
    
        
        
        
def creer_file_vide():
    return File()

def est_vide_file(file):
    return file.est_vide()

def enfiler(file, element):
    file.enfiler(element)
    
def defiler(file):
    return file.defiler()

FILE_VIDE = None class Noeud: def __init__(self, valeur, suivant): self._valeur = valeur self._suivant = suivant def __str__(self): return f"({self._valeur}, {str(self._suivant)})" class File: def __init__(self): self._premier = None self._dernier = None self._taille = 0 def __len__(self): return self._taille def est_vide(self): return self._taille == 0 def enfiler(self, element): nouveau = Noeud(element, None) if self.est_vide(): self._premier = self._dernier = nouveau else: self._dernier._suivant = nouveau self._dernier = nouveau self._taille += 1 def defiler(self): if not self.est_vide(): valeur = self._premier._valeur self._premier = self._premier._suivant self._taille -= 1 if self.est_vide(): self._dernier = None return valeur def __str__(self): return str(self._premier) def creer_file_vide(): return File() def est_vide_file(file): return file.est_vide() def enfiler(file, element): file.enfiler(element) def defiler(file): return file.defiler()

In [119]:

F = creer_file_vide()
enfiler(F, "jaune")
enfiler(F, "rouge")
enfiler(F, "jaune")
enfiler(F, "vert")
enfiler(F, "rouge")
str(F)

F = creer_file_vide() enfiler(F, "jaune") enfiler(F, "rouge") enfiler(F, "jaune") enfiler(F, "vert") enfiler(F, "rouge") str(F)

Out[119]:

'(jaune, (rouge, (jaune, (vert, (rouge, None)))))'

On inverse une file en la transférant dans une pile

In [120]:

P = creer_pile_vide()
while not(est_vide_file(F)):
    e = defiler(F)
    print(e)
    empiler(P, e)
    print(P)
print(P)

P = creer_pile_vide() while not(est_vide_file(F)): e = defiler(F) print(e) empiler(P, e) print(P) print(P)

jaune
['jaune']
rouge
['jaune', 'rouge']
jaune
['jaune', 'rouge', 'jaune']
vert
['jaune', 'rouge', 'jaune', 'vert']
rouge
['jaune', 'rouge', 'jaune', 'vert', 'rouge']
['jaune', 'rouge', 'jaune', 'vert', 'rouge']

In [121]:

def taille_file(F):
    G = creer_file_vide()
    compteur = 0
    while not (est_vide_file(F)):
        enfiler(G , defiler(F)) 
        compteur += 1
    while not (est_vide_file(G)):
        enfiler(F, defiler(G)) 
    return compteur

def taille_file(F): G = creer_file_vide() compteur = 0 while not (est_vide_file(F)): enfiler(G , defiler(F)) compteur += 1 while not (est_vide_file(G)): enfiler(F, defiler(G)) return compteur

In [122]:

F = creer_file_vide()
enfiler(F, "jaune")
enfiler(F, "rouge")
enfiler(F, "jaune")
enfiler(F, "vert")
enfiler(F, "rouge")
print(F)
taille_file(F)

F = creer_file_vide() enfiler(F, "jaune") enfiler(F, "rouge") enfiler(F, "jaune") enfiler(F, "vert") enfiler(F, "rouge") print(F) taille_file(F)

(jaune, (rouge, (jaune, (vert, (rouge, None)))))

Out[122]:

5

In [123]:

def former_pile(F, debug = True):
    P1 = creer_pile_vide()
    while not(est_vide_file(F)):
        e = defiler(F)
        if debug:print(e)
        empiler(P1, e)
        if debug:print(P1)
    if debug:print(P1)
    P2 = creer_pile_vide()
    while not(est_vide_pile(P1)):
        empiler(P2, depiler(P1))
    return P2

def former_pile(F, debug = True): P1 = creer_pile_vide() while not(est_vide_file(F)): e = defiler(F) if debug:print(e) empiler(P1, e) if debug:print(P1) if debug:print(P1) P2 = creer_pile_vide() while not(est_vide_pile(P1)): empiler(P2, depiler(P1)) return P2

In [124]:

F = creer_file_vide()
enfiler(F, "jaune")
enfiler(F, "rouge")
enfiler(F, "jaune")
enfiler(F, "vert")
enfiler(F, "rouge")
print(F)
former_pile(F)

F = creer_file_vide() enfiler(F, "jaune") enfiler(F, "rouge") enfiler(F, "jaune") enfiler(F, "vert") enfiler(F, "rouge") print(F) former_pile(F)

(jaune, (rouge, (jaune, (vert, (rouge, None)))))
jaune
['jaune']
rouge
['jaune', 'rouge']
jaune
['jaune', 'rouge', 'jaune']
vert
['jaune', 'rouge', 'jaune', 'vert']
rouge
['jaune', 'rouge', 'jaune', 'vert', 'rouge']
['jaune', 'rouge', 'jaune', 'vert', 'rouge']

Out[124]:

['rouge', 'vert', 'jaune', 'rouge', 'jaune']

In [125]:

def nb_elements(F, elt):
    G = creer_file_vide()
    compteur = 0
    while not (est_vide_file(F)):
        e = defiler(F)
        enfiler(G , e) 
        if e == elt:
            compteur += 1
    while not (est_vide_file(G)):
        enfiler(F, defiler(G)) 
    return compteur

def nb_elements(F, elt): G = creer_file_vide() compteur = 0 while not (est_vide_file(F)): e = defiler(F) enfiler(G , e) if e == elt: compteur += 1 while not (est_vide_file(G)): enfiler(F, defiler(G)) return compteur

In [126]:

F = creer_file_vide()
enfiler(F, "jaune")
enfiler(F, "rouge")
enfiler(F, "jaune")
enfiler(F, "vert")
enfiler(F, "rouge")
print(F)
nb_elements(F, "jaune")

F = creer_file_vide() enfiler(F, "jaune") enfiler(F, "rouge") enfiler(F, "jaune") enfiler(F, "vert") enfiler(F, "rouge") print(F) nb_elements(F, "jaune")

(jaune, (rouge, (jaune, (vert, (rouge, None)))))

Out[126]:

2

In [127]:

def verifier_contenu(F, nb_rouge, nb_vert, nb_jaune):
    return (nb_elements(F, "rouge") <= nb_rouge
            and nb_elements(F, "vert") <= nb_vert
            and nb_elements(F, "vejaune") <= nb_jaune)

def verifier_contenu(F, nb_rouge, nb_vert, nb_jaune): return (nb_elements(F, "rouge") <= nb_rouge and nb_elements(F, "vert") <= nb_vert and nb_elements(F, "vejaune") <= nb_jaune)

In [128]:

verifier_contenu(F, 2, 2,1)

verifier_contenu(F, 2, 2,1)

Out[128]:

True