GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Correction exercice 4 du TP1 ======

<WRAP box>On considère une séquence -- ''list'', ''tuple'', ''str'' -- L de longueur ''n = len(L)'' non nulle.

On voudrait préciser ses éléments et le nombre de représentants par élément. Par exemple pour ''L = [1, 0, 4, 2, 1, 0, 4, 1, 0]'', on a trois fois le ''0'', trois fois le ''1'', une fois le ''2'' et deux fois le ''4''.

Le mieux est d’utiliser un dictionnaire. Ici nous aurions le dictionnaire ''{0:3, 1:3, 2:1, 4:2}''

===== Question 1 =====

Implémenter une fonction ''compte'' qui prend en argument une séquence et, avec un parcours séquentiel, renvoie le dictionnaire décrit ci-dessus. On testera la fonction bien sûr !

<code lang-none>
FONCTION compte
ENTRÉE: séquence (liste, chaîne...)
SORTIE: dictionnaire dont les clés sont les valeurs de la séquence
        et les valeurs sont les effectifs
DÉBUT
    initialiser un dictionnaire vide
    POUR CHAQUE item de la séquence FAIRE
        SI l'item est présent dans le dictionnaire ALORS
            ajouter 1 à l'effectif de cet item
        SINON
            ajouter cet item comme clé du dictionnaire avec la valeur 1
        FIN
    FIN
    renvoyer le dictionnaire
FIN
</code>
</WRAP>

On traduit le pseudo-code en Python :

<code python linenums>
def compte(s):
    """
    s: une séquence (list, tuple, ...)
    renvoie un dictionnaire dont les clés sont
    les items de s et les valeurs sont les effectifs
    exemple:
        s = [1, 0, 4, 2, 1, 0, 4, 1, 0] -> {0:3, 1:3, 2:1, 4:2}
    """
    dico = {}
    for item in s:
        if item in dico:
            dico[item] += 1
        else:
            dico[item] = 1
    return dico
    
# exemple d'utilsiation
s = [1, 0, 4, 2, 1, 0, 4, 1, 0]
d = comtpe(s)
print(d)
# affiche : {0:3, 1:3, 2:1, 4:2}, pas forcément dans cet ordre
</code>

<WRAP box>
===== Question 2 =====

Lorsque la séquence L est une séquence d’entiers **naturels**, au lieu d'un dictionnaire, on peut renvoyer un tableau T : Par exemple si l'entrée L contient 4 fois la valeur 12, alors on aura T[12] = 4.

  * Soit p = max(L). Justifier que T doit avoir la longueur p + 1.
  * Implémenter une fonction ''compte2'' selon le schéma suivant.
  * Testez...

<code lang-none>
FONCTION compte2
ENTRÉE: séquence L (liste ou tupple) d'entiers naturels
SORTIE: tableau T contenant les effectifs des valeurs
    soit p la valeur maximale de L (donc p entier naturel)
    initialiser T comme tableau de longueur p + 1
      et ne contenant que des 0
    POUR CHAQUE item de L FAIRE
        augmenter de 1 la valeur de T[item]
    FIN
    renvoyer T
FIN
</code>
</WRAP>

En version Python :
<code python linenums>
def compte2(s):
    """
    s: séquence
    renvoie un tableau T tel que avec 0 <= indice <= max(s)
      et T[valeur] = effectif de valeur dans la séquence
    exemple : [4, 6, 3, 2, 4, 2, 1, 3, 4, 2] -> [0, 1, 3, 2, 3, 0, 1]
    """
    p = max(s)
    T = [0]*(p+1) # crée un tableau de p+1 cases ne contenant que des 0
    for item in s:
        # il faut absolument que item soit un entier positif !
        T[item] += 1
    return T

# exemple d'utilisation
s = [4, 6, 3, 2, 4, 2, 1, 3, 4, 2]
t = compte2(s)
print(t) # affiche [0, 1, 3, 2, 3, 0, 1]
</code>