Aller au contenu

Ep 43

le document

l'algorithme

Issue de : 23-NSI-04⚓

EXERCICE 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.

Par exemple :

🐍 Script Python
>>> 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
RĂ©ponse

Complétez le code ci-dessous

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



Solution

###
def apy-unddoublon(lst):bksl-nl for i in range(len(lst)-1):bksl-nl if lst[i] == lst[i+1]:bksl-nl return Truebksl-nl return Falsebksl-nlbksl-nltry:bksl-nl assert apy-unddoublon([]) == Falsebksl-nl assert apy-unddoublon([1]) == Falsebksl-nl assert apy-unddoublon([1, 2, 4, 6, 6]) == Truebksl-nl assert apy-unddoublon([2, 5, 7, 7, 7, 9]) == Truebksl-nl assert apy-unddoublon([0, 2, 3]) == Falsebksl-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 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 \times 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 diagonale : chaque case a donc 8 voisins si elle n'est pas située au bord de la grille).

Voici un exemple de grille \(5 \times 5\) de démineur dans laquelle la bombe est représentée par une étoile :

image

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 :

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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 incremente_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 genere_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
Exemple :
🐍 Script Python
>>> genere_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)])
[[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]]

ComplĂ©ter le code suivant afin de gĂ©nĂ©rer des grilles de dĂ©mineur, on pourra vĂ©rifier que l’instruction genere_grille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)]) produit bien la liste donnĂ©e en exemple.

RĂ©ponse

Complétez le code ci-dessous

###
def voisinage(n, ligne, colonne):bksl-nl """ Renvoie la liste des coordonnĂ©es des voisins de la casebksl-nl (ligne, colonne) en gĂ©rant les cases sur les bords. """bksl-nl voisins = []bksl-nl for l in range(max(0,ligne-1), min(n, ligne+2)):bksl-nl for c in range(max(0, colonne-1), min(n, colonne+2)):bksl-nl if (l, c) != (ligne, colonne):bksl-nl voisins.append((l,c))bksl-nl return voisinsbksl-nlbksl-nlbksl-nldef incrementepy-undvoisins(grille, ligne, colonne):bksl-nl """ IncrĂ©mente de 1 toutes les cases voisines d'une bombe."""bksl-nl voisins = ...bksl-nl for l, c in voisins:bksl-nl if grille[l][c] != ...: # si ce n'est pas une bombebksl-nl ... # on ajoute 1 Ă  sa valeurbksl-nlbksl-nlbksl-nlbksl-nldef generepy-undgrille(bombes):bksl-nl """ Renvoie une grille de dĂ©mineur de taille nxn oĂč n estbksl-nl le nombre de bombes, en plaçant les bombes Ă  l'aide debksl-nl la liste bombes de coordonnĂ©es (tuples) passĂ©e enbksl-nl paramĂštre. """bksl-nl n = len(bombes)bksl-nl # Initialisation d'une grille nxn remplie de 0bksl-nl grille = [[0 for colonne in range(n)] for ligne in range(n)]bksl-nl # Place les bombes et calcule les valeurs des autres casesbksl-nl for ligne, colonne in bombes:bksl-nl grille[ligne][colonne] = ... # place la bombebksl-nl ... # incrĂ©mente ses voisinsbksl-nlbksl-nl return grillebksl-nlbksl-nl



Solution

###
def voisinage(n, ligne, colonne):bksl-nl """ Renvoie la liste des coordonnĂ©es des voisins de la casebksl-nl (ligne, colonne) en gĂ©rant les cases sur les bords. """bksl-nl voisins = []bksl-nl for l in range(max(0,ligne-1), min(n, ligne+2)):bksl-nl for c in range(max(0, colonne-1), min(n, colonne+2)):bksl-nl if (l, c) != (ligne, colonne):bksl-nl voisins.append((l,c))bksl-nl return voisinsbksl-nlbksl-nldef incrementepy-undvoisins(grille, ligne, colonne):bksl-nl """ IncrĂ©mente de 1 toutes les cases voisines d'une bombe."""bksl-nl voisins = voisinage(len(grille), ligne, colonne)bksl-nl for l, c in voisins:bksl-nl if grille[l][c] != -1: # si ce n'est pas une bombebksl-nl grille[l][c] += 1 # on ajoute 1 Ă  sa valeurbksl-nlbksl-nlbksl-nldef generepy-undgrille(bombes):bksl-nl """ Renvoie une grille de dĂ©mineur de taille nxn oĂč n estbksl-nl le nombre de bombes, en plaçant les bombes Ă  l'aide debksl-nl la liste bombes de coordonnĂ©es (tuples) passĂ©e enbksl-nl paramĂštre. """bksl-nl n = len(bombes)bksl-nl # Initialisation d'une grille nxn remplie de 0bksl-nl grille = [[0 for colonne in range(n)] for ligne in range(n)]bksl-nl # Place les bombes et calcule les valeurs des autres casesbksl-nl for ligne, colonne in bombes:bksl-nl grille[ligne][colonne] = -1 # place la bombebksl-nl incrementepy-undvoisins(grille, ligne, colonne) # incrĂ©mente ses voisinsbksl-nlbksl-nl return grillebksl-nlbksl-nltry:bksl-nl assert generepy-undgrille([(1, 1), (2, 4), (3, 1), (3, 3), (4, 4)]) == [[1, 1, 1, 0, 0],bksl-nl [1, -1, 1, 1, 1],bksl-nl [2, 2, 3, 2, -1],bksl-nl [1, -1, 2, -1, 3],bksl-nl [1, 1, 2, 2, -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