Sujet n°4

Sujet original

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

Exercice n°1

Écrire une fonction a_doublon qui prend en paramètre une liste triée de nombres et renvoie True si la liste contient au moins deux nombres identiques, False sinon.

Commentaires

Ici, 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.

Exemples

>>> a_doublon([])
False

>>> a_doublon([1])
False

>>> a_doublon([1, 2, 4, 6, 6])
True

>>> a_doublon([2, 5, 7, 7, 7, 9])
True

>>> a_doublon([0, 2, 3])
False

Une solution

def a_doublon(tab):
    """
    tab - list, tableau trié de nombres (int et/ou float)
    Sortie: bool - True si tab contient au moins deux nombres identiques,
            False sinon
    """
    for i in range(1, len(tab)):
        if tab[i-1] == tab[i]:
            return True
    return False


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(a_doublon([]) == False)
    print(a_doublon([1]) == False)
    print(a_doublon([1, 2, 4, 6, 6]) == True)
    print(a_doublon([2, 5, 7, 7, 7, 9]) == True)
    print(a_doublon([0, 2, 3]) == False)


    # Exemples supplémentaires
    print(a_doublon([1, 1]) == True)
    print(a_doublon([0, 1, 1]) == True)
    print(a_doublon([5, 4, 3, 2, 1, 1]) == True)
    print(a_doublon([5, 4, 3, 2, 1]) == False)

Exercice n°2

On souhaite générer des grilles du jeu de démineur à partir de la position des bombes à placer.

On se limite à la génération de grilles carrées de taille $n × n$ où $n$ est le nombre de bombes du jeu.

Dans le jeu du démineur, chaque case de la grille contient soit une bombe, soit une valeur qui correspond aux nombres de bombes situées dans le voisinage direct de la case (au-dessus, en dessous, à droite, à gauche ou en diagonal : chaque case a donc 8 voisins si elle n'est pas située au bord de la grille).

Exemple

Ci-contre, voici un exemple de grille 5x5 de démineur dans laquelle chaque bombe est représentée par une étoile.

On utilise une liste de listes pour représenter la grille et on choisit de coder une bombe par la valeur -1.
L'exemple ci-contre sera donc codé par la liste :

[[1, 1, 1, 0, 0],
 [1, -1, 1, 1, 1],
 [2, 2, 3, 2, -1],
 [1, -1, 2, -1, 3],
 [1, 1, 2, 2, -1]]

Commentaires

Ici, 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.

Compléter le code suivant afin de générer des grilles de démineur, on pourra vérifier que l’instruction

>>> génère_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)])

produit bien la liste donnée en exemple.

bombes = [(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)]
grille_test = [[1, 1, 1, 0, 0], [1, -1, 1, 1, 1], [2, 2, 3, 2, -1], [1, -1, 2, -1, 3], [1, 1, 2, 2, -1]]

def voisinage(n, ligne, colonne):
    """ Renvoie la liste des coordonnées des voisins de la case
        (ligne, colonne) en gèrant les cases sur les bords. """
    voisins = []
    for l in range(max(0,ligne-1), min(n, ligne+2)):
        for c in range(max(0, colonne-1), min(n, colonne+2)):
            if (l, c) != (ligne, colonne):
                voisins.append((l,c))
    return voisins

def incrémente_voisins(grille, ligne, colonne):
    """ Incrémente de 1 toutes les cases voisines d'une bombe. """
    voisins = ...
    for l, c in voisins:
        if grille[l][c] != ...: # si ce n'est pas une bombe
            ...         # on ajoute 1 à sa valeur

def génère_grille(bombes):
    """ Renvoie une grille de démineur de taille nxn où n est
        le nombre de bombes, en plaçant les bombes à l'aide de
        la liste bombes de coordonnées (tuples) passée en
        paramètre. """
    n = len(bombes)
    # Initialisation d'une grille nxn remplie de 0
    grille = [[0 for colonne in range(n)] for ligne in range(n)]

    # Place les bombes et calcule les valeurs des autres cases
    for ligne, colonne in bombes:
        grille[ligne][colonne] = ...  # place la bombe
        ...  # incrémente ses voisins

    return grille

Commentaire sur le code original

Pour télécharger l'original du fichier à compléter, cliquer ici.

Une solution

def voisinage(n, ligne, colonne):
    """ Renvoie la liste des coordonnées des voisins de la case
        (ligne, colonne) en gèrant les cases sur les bords. """
    voisins = []
    for l in range(max(0,ligne-1), min(n, ligne+2)):
        for c in range(max(0, colonne-1), min(n, colonne+2)):
            if (l, c) != (ligne, colonne):
                voisins.append((l,c))
    return voisins

def incrémente_voisins(grille, ligne, colonne):
    """ Incrémente de 1 toutes les cases voisines d'une bombe. """
    voisins = voisinage(len(grille), ligne, colonne)
    for l, c in voisins:
        if grille[l][c] != -1:      # si ce n'est pas une bombe
            grille[l][c] +=1        # on ajoute 1 à sa valeur

def génère_grille(bombes):
    """ Renvoie une grille de démineur de taille nxn où n est
        le nombre de bombes, en plaçant les bombes à l'aide de
        la liste bombes de coordonnées (tuples) passée en
        paramètre. """
    n = len(bombes)
    # Initialisation d'une grille nxn remplie de 0
    grille = [[0 for colonne in range(n)] for ligne in range(n)]

    # Place les bombes et calcule les valeurs des autres cases
    for ligne, colonne in bombes:
        grille[ligne][colonne] = -1                 # place la bombe
        incrémente_voisins(grille, ligne, colonne)  # incrémente ses voisins

    return grille


if __name__ == '__main__':
    # Exemple de l'énoncé
    bombes = [(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)]
    grille_test = [ [1, 1, 1, 0, 0],
                    [1, -1, 1, 1, 1],
                    [2, 2, 3, 2, -1],
                    [1, -1, 2, -1, 3],
                    [1, 1, 2, 2, -1]]
    print(génère_grille(bombes) == grille_test)

    # Exemple supplémentaire
    bombes = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
    grille = [  [-1, 2, 1, 0, 0],
                [2, -1, 2, 1, 0],
                [1, 2, -1, 2, 1],
                [0, 1, 2, -1, 2],
                [0, 0, 1, 2, -1]]
    print(génère_grille(bombes) == grille)