Aller au contenu

Sujet n°29

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

On s’intéresse à la suite d’entiers définie par

U_1 = 1 ; U_2 = 1 et, pour tout entier naturel n, par U_{n+2} = U_{n+1} + U_n.

Elle s’appelle la suite de Fibonnaci.

Écrire la fonction fibonacci qui prend un entier n > 0 et qui renvoie l’élément d’indice n de cette suite.

La rprogrammation récursive n'est pas autorisée pour résoudre cet exercice.

Commentaires

La dernière phrase de cet énoncé est en fait :
« On utilisera une programmation dynamique (pas de récursivité). »

La programmation dynamique est une programmation qui privilégie la mémoïsation, c'est-à-dire la mise en mémoire des calculs intermédiaires.
Dans cet exercice, ce n'est donc pas tant la programmation dynamique qui est privilégiée mais plutôt la programmation récursive qui est interdite.

Exemples

>>> fibonacci(1) 
1 
>>> fibonacci(2) 
1 
>>> fibonacci(25) 
75025 
>>> fibonacci(45) 
1134903170
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def fibonacci(n):
    """
    n - int, entier strictement positif
    Sortie: int, n-ième entier dans la suite de Fibonacci
    """
    if n == 1 or n==2:
        return 1
    else:
        U1 = 1
        U2 = 1
        for i in range(n-2):
            temp = U1+U2
            U1 = U2
            U2 = temp
        return temp


if __name__ == '__main__':
    print(fibonacci(1) == 1)
    print(fibonacci(2) == 1)
    print(fibonacci(25) == 75025 )
    print(fibonacci(45) == 1134903170)

Exercice n°2

Les variables liste_eleves et liste_notes ayant été préalablement définies et étant de même longueur, la fonction meilleures_notes renvoie la note maximale qui a été attribuée, le nombre d’élèves ayant obtenu cette note et la liste des noms de ces élèves.

Compléter le code Python de la fonction meilleures_notes ci-dessous.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
liste_eleves = ['a','b','c','d','e','f','g','h','i','j']
liste_notes = [1, 40, 80, 60, 58, 80, 75, 80, 60, 24]

def meilleures_notes():
    note_maxi = 0
    nb_eleves_note_maxi = ...
    liste_maxi =  ...

    for compteur in range(...):
        if liste_notes[compteur] == ...:
            nb_eleves_note_maxi = nb_eleves_note_maxi + 1
            liste_maxi.append(liste_eleves[...])
        if liste_notes[compteur] > note_maxi:
            note_maxi = liste_notes[compteur]
            nb_eleves_note_maxi = ...
            liste_maxi = [...]

    return (note_maxi,nb_eleves_note_maxi,liste_maxi)
Commentaires sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. La fonction travaille sans paramètre et sur deux variables globales, dans un cas particulier. Ce n'est clairement pas recommandé et contredit les règles usuelles de programmation...

  3. À nouveau, le mot « liste » est à comprendre dans le sens « liste Python » (c'est-à-dire tableau) plutôt que dans le sens du type abstrait de données liste étudié en Terminale.

Une fois complété, le code ci-dessus donne :

>>> meilleures_notes() 
(80, 3, ['c', 'f', 'h']) 

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
liste_eleves = ['a','b','c','d','e','f','g','h','i','j']
liste_notes = [1, 40, 80, 60, 58, 80, 75, 80, 60, 24]

def meilleures_notes():
    note_maxi = 0
    nb_eleves_note_maxi = 0
    liste_maxi =  []

    for compteur in range(len(liste_eleves)):
        if liste_notes[compteur] == note_maxi:
            nb_eleves_note_maxi = nb_eleves_note_maxi + 1
            liste_maxi.append(liste_eleves[compteur])

        if liste_notes[compteur] > note_maxi:
            note_maxi = liste_notes[compteur]
            nb_eleves_note_maxi = 1
            liste_maxi = [liste_eleves[compteur]]

    return (note_maxi,nb_eleves_note_maxi,liste_maxi)


if __name__ == '__main__':
    print(meilleures_notes() == (80, 3, ['c', 'f', 'h']) )