Aller au contenu

Devoir commun Python: HTML/CSS et Algorithmes avancés Sujet B

L'usage de la calculatrice n'est pas autorisé

On n'autorise pas non plus l'usage des méthodes max, min, sort, reverse, count

Durée: 120 min

Exercice 1 - qcm

Question 1

Laquelle de ces syntaxes est correcte pour Ă©crire un commentaire en HTML ?

A <!--Commentaire-->

B <!--Commentaire--!>

C /Commentaire/

D <--Commentaire-->

Question 2

En CSS, comment sélectionnez-vous toutes les balises <p> d'une page ?

A <p> { }

B .p { }

C p { }

D #p { }

Question 3

En CSS, comment sélectionnez-vous une image par son identifiant ? <img id="imgprincipale" src="chat.png">

A img { }

B imgprincipale { }

C .imgprincipale { }

D #imgprincipale { }

Question 4

L’écriture <a href="#help">Aide</a> définit :

A un lien vers le site internet www.help.com

B cette écriture n’est pas valide

C un lien hypertexte vers un lien interne

D un lien interne (signet) qui s’appelle help

Question 5

Laquelle de ces syntaxes est correcte pour embarquer une image dans la page html ?

A <img href="mon-image.jpg" alt="Une image">

B <img>src="mon-image.jpg" alt="Une image"</img>

C <img>src="mon-image.jpg" alt="Une image"</img>

D <img src="mon-image.jpg" alt="Une image">

Question 6

Quelle balise sert à changer de ligne et à insérer une ligne blanche ?

A <P>

B <PRE>

C <HR>

D <BR>

Question 7

Quelle balise permet de souligner du texte?

A <I>

B <U>

C <B>

D <S>

Question 8

Où sont normalement placées les balises <HTML> et </HTML> dans un document HTML?

A Dans le corps <BODY>

B Au début et à la fin du document

C N'importe oĂą

D Dans l'entĂŞte <HEAD>

Question 9

CSS : Comment modifier la police d'Ă©criture ?

A Police-family : Comic ;

B Font-style : Comic ;

C Font-police : Comic ;

D Font-family : Comic ;

Question 10

CSS : Comment ajouter une image d'arrière-plan ?

A Background : url('darkness.png') ;

B Background-image : url('darkness.png') ;

C Image-back : url('darkness.png') ;

D Background-image : src='darkness.png' ;

\newpage

Exercice 2

É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:

>>> 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
Corrigé 
    def a_doublon(L):
        for i in range(len(L)-1):
            if L[i]==L[i+1]:
                return True
        return False

Exercice 3

On considère l'algorithme de tri de tableau suivant : à chaque étape, on parcourt le sous- tableau des éléments non rangés et on place le plus petit élément en première position de ce sous-tableau.

Exemple avec le tableau t = [41, 55, 21, 18, 12, 6, 25]

Étape 1 : on parcourt tous les éléments du tableau, on permute le plus petit élément avec le premier. Le tableau devient t = [6, 55, 21, 18, 12, 41, 25]

Étape 2 : on parcourt tous les éléments sauf le premier, on permute le plus petit élément trouvé avec le second. Le tableau devient t = [6, 12, 21, 18, 55, 41, 25]

Et ainsi de suite.

La code de la fonction tri_selection qui implémente cet algorithme est donné ci- dessous.

def tri_selection(tab):
    N = len(tab)
    for k in range(...):
    imin = ...
    for i in range(... , N):
    if tab[i] < ... :
    imin = i
    ... , tab[imin] = tab[imin] , ...

Recopier, compléter et indenter le code de cette fonction de façon à obtenir :

>>> liste = [41, 55, 21, 18, 12, 6, 25]
>>> tri_selection(liste)
>>> liste
[6, 12, 18, 21, 25, 41, 55]

On rappelle que l’instruction a, b = b, a échange les contenus de a et de b.

Corrigé 
def tri_selection(tab):
    N = len(tab)
    for k in range(N-1):
        imin = k
        for i in range(k+1 , N):
            if tab[i] < tab[imin] :
                imin = i
        tab[k] , tab[imin] = tab[imin] , tab[k]

Exercice 4 (source : lyceemed)

On considère un rectangle de dimensions 13 sur 11 (figure 0).

Carrés

Écrire un programme glouton minicarre(n,m) qui permettra de remplir un rectangle de longueur \(n\) et de largeur \(m\) avec le minimum de carrés. Que peut-on déduire en voyant la figure 2 ci-dessus ?

Corrigé 
def minicarre(n,m):
    carre=0
    if n<m:
        n,m=m,n
    while m!=0:
        carre=carre+n//m
        n,m=m,n%m
    return carre

Exercice 5

Recopier et compléter la fonction suivante en respectant la spécification. On ne recopiera pas les commentaires.

def partage(tab, x):
    """
        tab : tableau d'entiers trié dans l'ordre décroissant
        x : nombre entier
        La fonction renvoie True si tab contient x et False sinon
    """
    debut = len(tab)-1
    fin = 0
    while debut >= fin:
        m = ...
        if x == tab[m]:
            return ...
        if x > tab[m]:
            debut = ...
        else:
            fin = ...
    return ...

Exemples :

>>> partage([33, 31, 29, 28, 24, 23, 19, 18, 16, 15], 28)
True
>>> partage([33, 31, 29, 28, 24, 23, 19, 18, 16, 15], 27)
False
Corrigé 
def partage(tab, x):
    """
        tab : tableau d'entiers trié dans l'ordre décroissant
        x : nombre entier
        La fonction renvoie True si tab contient x et False sinon
    """
    debut = len(tab) - 1
    fin = 0
    while debut >= fin:
        m = (debut+fin)//2
        if x == tab[m]:
            return True
        if x > tab[m]:
            debut = m-1
        else:
            fin = m+1
    return False

Exercice 6

On souhaite générer des grilles du jeu de démineur. 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 sur laquelle les bombes sont représentées par des étoiles :

DĂ©mineur

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-dessus 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]]

Votre mission: écrire une fonction demineur(n) qui génère aléatoirement une grille de démineur de taille \(n \times n\) du type de celle ci-dessus.

Corrigé 
from random import *

def comptebombes(L):
    compte=0
    N=len(L)
    for i in range(N):
        for j in range(N):
            if L[i][j]==-1:
                compte=compte+1
    return compte

def voisins(x,y,n):
    vois=[]
    for i in range(n):
        for j in range(n):
                if abs(x-i)<=1 and abs(y-j)<=1:
                    vois.append((i,j))
    vois.remove((x,y))            
    return vois


def demineur(n):
    ligne=[0 for i in range(n)]
    grille=[ligne.copy() for i in range(n)]
    #On place les bombes sur la grille
    while comptebombes(grille)!=n:
        grille[randint(0,n-1)][randint(0,n-1)]=-1
    #On parcourt la grille en comptant pour chaque case
    #les bombes des cases voisines.
    for i in range(0,n):
        for j in range(0,n):
            if grille[i][j]!=-1:
                bombes=0
                listevoisins=voisins(i,j,n)
                for elt in listevoisins:
                    if grille[elt[0]][elt[1]]==-1:
                        bombes=bombes+1
                grille[i][j]=bombes
    return grille
print(demineur(10))