Aller au contenu

Exercices Diviser pour RĂ©gner

Le tri fusion : autre version⚓

Comprendre les appels du tris fusion

1. Compléter le script ci-dessous :

###(DĂ©s-)Active le code aprĂšs la ligne # Tests (insensible Ă  la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activĂ©, le texte copiĂ© dans le terminal est joint sur une seule ligne avant d'ĂȘtre copiĂ© dans le presse-papier
Évaluations restantes : 5/5

.128013f06S:d=4yr/oxpg2mcb1w937vej[ l,8*+OP5)tài]kné;ua(_shq050g0A0N0W0P0E0Z0D0s0E0W0Z0Z0h010N0P0o010406050Z0V0r0r0W0k0j040e0m0E0V0_0m0S050l101214160~0o04051m1f1p0l1m0~0g0P0z0.0:0=0@0!0P0p0!0E1D0!0N0|050)0t0E0A1y0;0?011C1E1G1E0N1M1O1K0N0k1n0N0!0.190Z0o0W0S0@0q011Q1A010b0+0A0S0W0r0A1K1-1/1@1S1`1O1}1 0|0a0D0K0k0m0o0m0Z0P1c0S0D0%1+0k0k0A0s2k1f220S1n0l1)2x1$1(1%1L0g240@1G0S1|2h1K1v1x0/1R2H0P2J0S0m2N1K0o2q1n2v2x2#0 1.2l2P1^2U0k130E0|0D0u2u2)0}2(232+1S2-2/2;0q2@1/2_2v2G012~0W2:040D0x322w0~352|0@383a0D0i3e342)363k2;0L3o3g3q3i370m2.392;0d3v2`2*1z2}3A2 3b0y3F3h3I3j3K3C3b0G3O3x3Q3z3B3l0w3W2{3Y3s040u0c3%3H2Q3Z3L0u2?1g2^3w3(3:3*0u313^333`3/2,3S3a0u3d403f3G3r450|0u3n493p3{443!4e3u4h424c4l3+3E4o4b3y3}3N4u3P3|4d3+3V4z3X4B4r0u3$4F4j3J4r0q3-4L434N3L0q3@2#4p4w4C0q3 4X4v3)4!484%4A4k4U4g4,4G4.3T0q4n4;4M3R4O4t4`4S4|4U4y4 4q4U4E544Z4O4K584)4r0x4Q5c4H3L0x4W3_4(5i3T0x4$5m4-4T5p4+5s4=5u3a0x4:5x4{3;5p4_5D505F5A4~2^1q2Z1f2N2A0g1(2F3y0s2V201n5R1o5P2%4h055X0%2!5y0@0R0|0%0b3o5n1^0v2;5@5t3j0b0|0b0V2i1d5|5.010{040X655E0S0|1M5l335^1S680F3o0D6i3j6e0W0t5r6h5}670|0M0f3v0D6B6n6v0S0t0|2Y2S0N6b5J686a5)6v0Z1=04020#0V0m0N0U1d0D61630S2J6U6W6Y6L366k6m6o376q0t6g2w6;6/4h6D666R0|6*6X0U0(716,6P666{2#6}6c6?6t6_6v680M6A6C6;6d040S6^3b6;0m0|0h6:6E6G04276-3y6N7A3)6?7p6`6x7j6B7l0|0S7e7q6v7s047u6|7l7x7z775E7C7Y5J7m1M7O7H047i4o6C7b7$6?7v667R7T7a7*0C7D3:0r0P0|5g5N7g0|0Q7=5E7R0H866M0|6O2%6E7M7G7Q0|0I7|2,7M7)837+7J7/3r0|0P7p8s3y7@8a367~808r7L040P7O8x3Y8z7U6v8C0481417.6;0s0u0|030D0J2*1d0_0S0V1P0B626V02030x0w0U0O0D0W0z0m0P0k6#2S0P0D0V2l0%0-1Z0A0W0V0n8E6v5:040v1C1O8A4w8u8w7r700E767_8f7n9j7Q5`041/0g9g7E8G8I9k6T9m0U9x3|8n8l6j0|6z7-7.7k9a8u5?8M667%6r8h780|7{7#8t8G9W7Z849F1^7R029D9*2}7d9I0@689Z8e9T8u8o9X040Q9L4X9Na28J9G041M9=6w049^829`9$a87R8k9!9h9za868859S877t9/6pa69Val9Ya87m8vav9~8ra3a48maeao5Jag7^2^aE1S8O7p06aD6;9b0A0,0AaAa03_aD8S9pa7ai3Y9@ax9iaf8ja+aka(3:amar018L9oad7(aAab6uad8HaAana1a!7K9pb1aH36aJa@aO99668U8W8Y8!0o0P1P1O0D2q0Z0N1P2n6f0D2i0D0S0T0s0A0=0*2qbe5E9b9d1{a@ay9r7?9l9naL8F7oaXaC9Oa{6ra}a/aza;9+a.b#9:a:9_9(aBb98yaqb.9y6fbYb(asb!b+8bb-b4a28Fb`bQ8i040IaK33aM0@bd9Mb6bf8V048X8Z1+bkbm1Pbpbr2m1P7(bv8~bybAbC8`aWcbc801bH9ecxa`7cb*c2bN9CbPc7bR9|b,aY8Ra38Fa%b{6.awb^6=aGcUb/c4bZcNb|b3cHap7SbK9;cXa*cXayc(cVb}aZcRb79Ac3c5bc7 3+bF5J9b2q0N0V0k1eb;a5cT3_4Y3Y9b5=a89t6nc=5 a60k0P0Y6$0P64c:8ca/dda b,6yd33r7x6I0S6Kdv69a86 6T6V726!1$bl759EdI6ldbaFdy7f9}7,b~cz7mdacEaIb:d*dD0|7Xc!a)dwc=7;dId#c`ccbG9Qc.7na@9,0pcK2wczcad;a=9KbUd|5Jbgcfbicibl0D1O936r1O9698cya#bW6@e1d,c+b|a~dZcFdY5-b,eyeC7:8Gb2a@9b0b3Ad 0Pe19t2SbK7x0k1/0pcDacb,8deY5J8O8Qezb|dVd-ajd)e#ba0|0l0la88Oc@7B6xc*cQb a$6rc}cIc6e57`dxbXdIeEc0eIdW1SeKeMfcb_eP8ue.cL7w0|eU0SeWaAe!dzeGfke)e:04e=e@d1e_d=04e+ew9#fveFc^0Me|3faR6veecg2lds1d2JejbBco970D94eof!dp0T0Zebczd50(d8fId%6062dtfI7*fsfwajdQdrf?due81^7!g1b)b?d_fFfla{dpf~6%frf66saA0Md`e}f,0|aU0ZeXftc^cPfNc{66f-d7d9d eB0~0l5+0A2x2YgE5Q1w5S2A2D2yemgH0l5RgB0%0)0+0Z04.

2. Bien comprendre les affichages en console.

Labyrinthe en POO⚓

D'aprĂšs bac 2022, MĂ©tropole, J2, Ex. 5

Un labyrinthe est composé de cellules possédant chacune quatre murs (voir ci-dessous). La cellule en haut à gauche du labyrinthe est de coordonnées (0, 0).

Le labyrinthe

On définit la classe Cellule ci-dessous. Le constructeur possÚde un attribut murs de type dict dont les clés sont 'N', 'E', 'S' et 'O' et dont les valeurs sont des booléens (True si le mur est présent et False sinon).

class Cellule:
    def __init__(self, murNord, murEst, murSud, murOuest):
        self.murs = {
            "N": murNord,
            "E": murEst,
            "S": murSud,
            "O": murOuest
            }

1. Recopier et compléter sur la copie l'instruction Python suivante permettant de créer une instance cellule de la classe Cellule possédant tous ses murs sauf le mur Est.

cellule = Cellule(...)
RĂ©ponse 
cellule = Cellule(True, False, True, True)

2. Le constructeur de la classe Labyrinthe ci-dessous possĂšde un seul attribut grille.

Cette grille est un tableau à deux dimensions hauteur et largeur contenant des cellules possédant chacune ses quatre murs.

Recopier et compléter sur la copie les lignes 4 à 8 de la classe Labyrinthe.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Labyrinthe:
    def __init__(self, hauteur, longueur):
        self.grille=self.construire_grille(hauteur, longueur)

    def construire_grille(self, hauteur, longueur):
        grille = []
        for i in range(...):
            ligne = []
            for j in range(...):
                cellule = ...
                ligne.append(...)
            grille.append(ligne)
        return grille
RĂ©ponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Labyrinthe:
    def __init__(self, hauteur, longueur):
        self.grille=self.construire_grille(hauteur, longueur)

    def construire_grille(self, hauteur, longueur):
        grille = []
        for i in range(hauteur):
            ligne = []
            for j in range(longueur):
                cellule = Cellule(True, True, True, True)
                ligne.append(cellule)
            grille.append(ligne)
        return grille

Pour générer un labyrinthe, on munit la classe Labyrinthe d'une méthode creer_passage permettant de supprimer des murs entre deux cellules ayant un cÎté commun afin de créer un passage.

Cette mĂ©thode prend en paramĂštres les coordonnĂ©es (c1_lig, c1_col) d’une cellule notĂ©e cellule1 et les coordonnĂ©es (c2_lig, c2_col) d’une cellule notĂ©e cellule2 et crĂ©e un passage entre cellule1 et cellule2.

15
16
17
18
19
20
21
22
23
24
25
def creer_passage(self, c1_lig, c1_col, c2_lig, c2_col):
    cellule1 = self.grille[c1_lig][c1_col]
    cellule2 = self.grille[c2_lig][c2_col]
    # cellule2 au Nord de cellule1
    if c1_lig - c2_lig == 1 and c1_col == c2_col:
        cellule1.murs['N'] = False
        ...
    # cellule2 Ă  l'Ouest de cellule1
    elif ...
        ...
        ...

3. La ligne 20 permet de supprimer le mur Nord de cellule1. Un mur de cellule2 doit aussi ĂȘtre supprimĂ© pour libĂ©rer un passage entre cellule1 et cellule2.

Écrire l'instruction Python que l'on doit ajouter à la ligne 21.

RĂ©ponse 
21
cellule2.murs['S'] = False

4. Recopier et complĂ©ter sur la copie le code Python des lignes 23 Ă  25 qui permettent le traitement du cas oĂč cellule2 est Ă  l'Ouest de cellule1.

Deux cellules

RĂ©ponse 
15
16
17
18
19
20
21
22
23
24
25
def creer_passage(self, c1_lig, c1_col, c2_lig, c2_col):
    cellule1 = self.grille[c1_lig][c1_col]
    cellule2 = self.grille[c2_lig][c2_col]
    # cellule2 au Nord de cellule1
    if c1_lig - c2_lig == 1 and c1_col == c2_col:
        cellule1.murs['N'] = False
        cellule2.murs['S'] = False
    # cellule2 Ă  l'Ouest de cellule1
    elif c1_lig == c2_lig and c1_col - c2_col == 1:
        cellule1.murs['O'] = False
        cellule2.murs['E'] = False

Pour créer un labyrinthe, on utilise la méthode diviser pour régner en appliquant récursivement l'algorithme creer_labyrinthe sur des sous-grilles obtenues en coupant la grille en deux puis en reliant les deux sous-labyrinthes en créant un passage entre eux.

Création récursive

La mĂ©thode creer_labyrinthe permet, Ă  partir d’une grille, de crĂ©er un labyrinthe de hauteur haut et de longueur long dont la cellule en haut Ă  gauche est de coordonnĂ©es (ligne, colonne). Le cas de base correspond Ă  la situation oĂč la grille est de hauteur 1 ou de largeur 1. Il suffit alors de supprimer tous les murs intĂ©rieurs de la grille.

Cas de base

5. Recopier et compléter sur la copie les lignes 28 à 33 de la méthode creer_labyrinthe traitant le cas de base.

21
22
23
24
25
26
27
28
29
def creer_labyrinthe(self, ligne, colonne, haut, long):
        if haut == 1 : # Cas de base
            for k in range(...):
                self.creer_passage(ligne, colonne + k, ligne, colonne + k + 1)
        elif long == 1: # Cas de base
            for k in range(...):
                self.creer_passage(..., ..., ..., ...)
        else: # Appels récursifs
            # Code non étudié (Ne pas compléter)
RĂ©ponse
title
21
22
23
24
25
26
27
28
29
def creer_labyrinthe(self, ligne, colonne, haut, long):
        if haut == 1 : # Cas de base
            for k in range(long - 1):
                self.creer_passage(ligne, colonne + k, ligne, colonne + k + 1)
        elif long == 1: # Cas de base
            for k in range(haut - 1):
                self.creer_passage(haut + k, colonne, haut + k + 1, colonne)
        else: # Appels récursifs
            # Code non étudié (Ne pas compléter)

6. Dans cette question, on considĂšre une grille de hauteur haut = 4 et de longueur long = 8 dont chaque cellule possĂšde tous ses murs.

On fixe les deux contraintes supplémentaires suivantes sur la méthode creer_labyrinthe :

  • Si haut est supĂ©rieure ou Ă©gale Ă  long, on coupe horizontalement la grille en deux sous-labyrinthes de mĂȘme dimension ;
  • Si haut est strictement infĂ©rieur Ă  long, on coupe verticalement la grille en deux sous-labyrinthes de mĂȘme dimension.

L'ouverture du passage entre les deux sous-labyrinthes se fait le plus au Nord pour une coupe verticale et le plus Ă  l'Ouest pour une coupe horizontale.

Dessiner le labyrinthe obtenu suite à l'exécution complÚte de l'algorithme creer_labyrinthe sur cette grille.

RĂ©ponse

Avez-vous rĂ©ellement dessinĂ© votre rĂ©ponse ? Sinon, commencer par le faire avant de cliquer sur la solution ... 😉

RĂ©ponse

gif du labyrinthe

Crédits : Romain Janvier, Mireille Coilhac