Aller au contenu

Ep 25

le document

l'algorithme

Issue de : 23-NSI-27⚓︎

EXERCICE 1⚓︎

Écrire une fonction recherche_min qui prend en paramètre un tableau de nombres non trié tab, et qui renvoie l'indice de la première occurrence du minimum de ce tableau. Les tableaux seront représentés sous forme de liste Python.

Exemples :

🐍 Script Python
>>> recherche_min([5])
0
>>> recherche_min([2, 4, 1])
2
>>> recherche_min([5, 3, 2, 2, 4])
2

Réponse

Complétez le code ci-dessous

###
# Mettez votre code icibksl-nlbksl-nl

Solution

###
def recherchepy-undmin(tab):bksl-nl indicepy-undmin = 0bksl-nl for i in range(len(tab)):bksl-nl if tab[i] < tab[indicepy-undmin]:bksl-nl indicepy-undmin = ibksl-nl return indicepy-undminbksl-nlbksl-nltry:bksl-nl assert recherchepy-undmin([5]) == 0bksl-nl assert recherchepy-undmin([2, 4, 1]) == 2bksl-nl assert recherchepy-undmin([5, 3, 2, 2, 4]) == 2bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl

EXERCICE 2⚓︎

On considère la fonction separe ci-dessous qui prend en argument un tableau tab dont les éléments sont des 0 et des 1 et qui sépare les 0 des 1 en plaçant les 0 en début de tableau et les 1 à la suite.

Compléter la fonction separe ci-dessus.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def separe(tab):
    '''Separe les 0 et les 1 dans le tableau tab'''
    gauche = 0
    droite = ... 
    while gauche < droite:
        if tab[gauche] == 0 :
            gauche = ... 
        else :
            tab[gauche] = ... 
            tab[droite] = ... 
            droite = ... 
    return tab

Exemples :

🐍 Script Python
>>> separe([1, 0, 1, 0, 1, 0, 1, 0])
[0, 0, 0, 0, 1, 1, 1, 1]
>>> separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0])
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Description d’étapes effectuées par la fonction separe sur le tableau ci-dessous, les caractères ^ indiquent les cases pointées par les indices gauche et droite

📋 Texte
tab = [1, 0, 1, 0, 1, 0, 1, 0]
       ^                    ^
* Etape 1 : on regarde la première case, qui contient un 1 : ce 1 va aller dans la seconde partie du tableau final et on l’échange avec la dernière case. Il est à présent bien positionné : on ne prend plus la dernière case en compte.
📋 Texte
tab = [0, 0, 1, 0, 1, 0, 1, 1]
       ^                 ^
* Etape 2 : on regarde à nouveau la première case, qui contient maintenant un 0 : ce 0 va aller dans la première partie du tableau final et est bien positionné : on ne prend plus la première case en compte.
📋 Texte
tab = [0, 0, 1, 0, 1, 0, 1, 1]
          ^              ^
* Etape 3 : on regarde la seconde case, qui contient un 0 : ce 0 va aller dans la première partie du tableau final et est bien positionné : on ne prend plus la seconde case en compte.
📋 Texte
tab = [0, 0, 1, 0, 1, 0, 1, 1]
             ^           ^
* Etape 4 : on regarde la troisième case, qui contient un 1 : ce 1 va aller dans la seconde partie du tableau final et on l’échange avec l’avant-dernière case. Il est à présent bien positionné : on ne prend plus l’avant-dernière case en compte.
📋 Texte
tab = [0, 0, 1, 0, 1, 0, 1, 1]
             ^        ^
* Et ainsi de suite...
📋 Texte
tab = [0, 0, 0, 0, 1, 1, 1, 1]

Réponse

Complétez le code ci-dessous

###
def separe(tab):bksl-nl gauche = 0bksl-nl droite = ...bksl-nl while gauche < droite :bksl-nl if tab[gauche] == 0 :bksl-nl gauche = ...bksl-nl else :bksl-nl tab[gauche], tab[droite] = ...bksl-nl droite = ...bksl-nl return tabbksl-nlbksl-nl

Solution

###
def separe(tab):bksl-nl gauche = 0bksl-nl droite = len(tab) - 1bksl-nl while gauche < droite :bksl-nl if tab[gauche] == 0 :bksl-nl gauche = gauche + 1bksl-nl else :bksl-nl tab[gauche], tab[droite] = tab[droite], tab[gauche]bksl-nl droite = droite - 1bksl-nl return tabbksl-nlbksl-nltry:bksl-nl assert separe([1, 0, 1, 0, 1, 0, 1, 0]) == [0, 0, 0, 0, 1, 1, 1, 1]bksl-nl assert separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0]) == [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le résultat de votre fonction n\'est pas conforme 🤔')bksl-nl