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

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : 5/5

.128013w]itkc[v8o-)Oyl0bqpx_P3(a;j+g=/mà4r*se97Sf,d 612:é5nuh050S0M0e0z0d0p0L0T0g0p0z0L0L0E010e0d0t010406050L0#0G0G0z0J0o040P0k0p0#0`0k0!050F111315170 0t04051n1g1q0F1n0 0S0d0i0/0;0?0^0;0!0D0#0z0D0M0l0t0o0e0$1e0T0$0d0D0$0p1S0$0e0}050*0r0p0M1z0=0@011R1T1V1T0e1#1%1Z0e0J1o1N0/1a0L0t0z0!0^0W011)1B010Q0,0M0!0z0G0M1Z1~20251+281%2b2d0}0a0T0w0J0k0t0k0L0d1d0!0T0(1|0J0J0M0g2y1g2g0!1o0F1N2L1^1`1_1!0S2i1C0d0!2a2v1Z1w1y0:1*2V2X0!0k2#1Z0t2E1o2J2L2=101 2z2%262+0J140p1Z0z1Q2E0Q0^030v0v0g2,0M1V2*0k0l0q0l0V0}0T0V1g0z2?2_0~2^2h2{1+2}2 31330M350137393b3d2Y3g0l23040T0W3n3p203r2J2U013w0z301o320$3436383a0(3G2+3I0x3k0x3O2I3q0 3S3u0^3V3X053Z3#3C3%3F2W3H3h0I3k0I3:1h3=3s2`1A3v0k2~3W3y3!3A3$3E3)423+3h0Z3k0Z482=3?2_3T3`4i3~3D3(3c4o3f3h0U3k0U4u4a3@4d3_4f3x3Y3z3B4C413e3I0O3k0O4L3Q4w3t4O3U4Q4h4S4j4U404n4X3h0j3k0j4$2K4(4c2(4+4g3{3}4k3 4m4E4?0l0N3k0N4{3R4x3^504R3|4T4l4D3*4G3i0q0}0V0q5d4}4y4,525k555m4F3I0V3j045E5u4b5w514A544V4=433i3K0V3N0F3o3;4%5J5g4z4.4B4;575Q0V3-5G3/5V3P4|5Z4*5#5j4/5l4W5*455G475/5X5;4N4 5@534:565n5D4r5G4t60495Y632|5x5M675B580V4I5G4K6e4v5=646j5$5N5(693h0V4Z5G4#6s4M5f5?6w5^5%685C6B4^5G4`6G6g6I6v5L6x6l5{4p3i5a5G5c6T626V6i6X6L6y6N580W5q046?5I6h4e6.665`5P6#0W5F726`6,6|5i6~5A6!5o0W3K7d754)6W785z5O5)715,0W5.5W6f6+7h6-7j5_7a707c5}0W5 7r6t6{4P6}7k6z6O3J6b0W6d7E6H7u774-6/6Z7z3I0W6p7Z7g4~7v7U797l6A3J6D0W6F7Q6U7S7H7w6M6m5Q0W6Q7|7$5K7^6:7`716%0W6)7;7t7%7T5y7x7+7L0x6@8g7 5!6K7*7K580x5F8p8j6J7I8d8n5Q0x3K8y8s7i7)7J6;8x5,0x7q5:5e7?5h8D8v8F6#0x5}8S8B7(8c7_7b3,6b0x7P8K5v8k8u8Y7X3h0x6p8/5d1r2:1g2#2O0S1`2T5g4D2!1x1o2/0M2;3q611o4D952h0d0S0^382J5D3y9c9e8Q5o3j0T2m0M9k839m1Z607G010f0}0(0Q976u260b3k9C9w0!0Q0}0Q0#2w1e9H760^0|040y9Q8M0!0}1#3m7s9a8a9S0}0R970T9D3v9Z0z0r5U2@9w9T0m0X970 9$5J9j019f2_7Y9i9da19la49o2c9qa79sa42L3o0Tai9-9I0r0}2/2W0e9W9(019T9V9~9w0L3K020s0#0k0e0A1P9M9O0!2XaAaCaEar3T9T9+9$ak9R3U9:0r9#9@aUaQ9,9.0^ay0}aLaD0A0)a+aNawa!9*a$9IaW9?969^0}0m9|aOa0a2203,a59r8Z8.249pb68-0l5,3OajaT9X0}0!aY3qbhas0k0}0Ea@aU0!am042laO5gauby5?aWbl3Qa%ata}a a;9ba6b20!3I5}5jb1a844b9abbb7m5obQ5/bgbG9Y040!a`3Qbn3Tbp04braSb%bvbxbKasbAb_4ya_bB4 9_bJaZbL9k9g4qb5adb70l4raa2dbX7,6bbfajb%aWbs8Mb/b;2=b-bz0}0hb 260G0d0}5tb|cs040ccmbo0}0KcFaP0}avc3asb(bkcv1+b/0CcR3_bjb+2KbGc19$9}cN0TbSc60l6pbRbMbTc,bVcec9bcc-b#cja^040dbE2Kcr4*cocJ5gcxczc2a{4xc*a33h6Dc.cf7L4Zcdac8w6#dec`aickc}cY3LbGd3b=9wd604cA6tb|dbb34@c8dl5o4^djdg586Qcidp9w0g5F030T0n2`1e0`0!0#1(0B9NaB02030x0N0A0H0T0z0i0k0d0J0T280!0d0T0#2z0(0.1=0M0z0#0ud8bF3SdDbO3h6%dfc@bY3I5adKee7,ecdod14 9y040b1R1%d4bCc}c dt9wb/020pa:cqdqcQdwaU0k9F04200Seu640}0ddsen26eAeC0AeO2|cXcVbH049{c$b0c/c+5sdGc:e-eidH5D6@dObgeT1+ep0d9BeHbi049!e#9TcucBevc~f30}cEe cG04eBeDbmdq1#dsc!cte#b(eRf9cDe(dBc(e95D5Fede=6B9nbaej7L5E9uahe_fIfi9;fqf5c(5!eQexdu0}cUf6ePdrfqfbeEezbqeY9/f19;fRa|04fNd9f0f8fV269TfZ4adCe+dc5Re.ae6B23e;e/3Ke^fIdPbtfQf%0^cTcpfhdxcy5Ge6cZe8f{dE3ibe32bSf gnc=dke/beemb$9wep3c0L0Mfqfsf_fuglea3ibQgpc/gr0V45g2gOb!fHg6c{g8f)0rfMfng9f=cSfTg#fXg%9)cDga01dvf!gXfjg!g,aVg+fO4*f@gi9%c)gI6af~ca0VccfCfz3ichgxg6dqfpfcb.fTgdb,bGdyexc%f/2zfv6Bc-gMdL5*4IgRh5c_gUe`0^dR0}dTdV1|0t0d1(1%0T2E0L0e1(2B9!0T2w9o0Y0g0M0?0+2Eg 9 h26BdehufD6ndih8e/dnhBbGeper29g/foexhCg:a*eWh{bjf+a=e%h%gkc5f|0VdNh,h9ibgthv6#ifag3Lhdc|1#g^g|fWf;iqeUg)g_fofkf,f^hkf#b:i2gYi48Mf4g*ishpcKg.e)f`i9gm0Vecide/ehh:gOelhBgygXiKiBeIhig/hmi7dah)3Je@iUgr6?igh-7{e@embGhE04hGdWhJhL1(hOhQ2A1(fjhUd{0!hXhZ0Lh#gDiOgHiQgJ72h4bcjmhyjofxi|gz0}h_ethgfPg{gei)fei1jyevb*gEi-c4a7c+7djnef3hjNjqjP3Jg4hcg7f0iog_iIiwg$itg(04fUj(cWjAe7i5iAd0fSiDjFfWg@j!fmj$j.gjj:jJhqi/7pjO7,k4jSk6gwi!gWf:eSj?0Chjj=gf5rk1h1jk7YgLkmi_71gQiXca7CfGiljXasep2E0e0#0J1fj^eZgYklhr7Mk57L7Oi^h9kPikhoj/jKbN7YhtkqkRhxkujohAh05gep9Ae#eK9-iw9Kf10J0d0vaH0d9Pj{9Ug*jZj,e$9`kKk3h+k!c:7/kQl8h=kyh~buank@0!aqk}cMiL5ga)feaBa,1P1^hKa/eXk}aRg=jYfLk}a~jiiLkL7|kN6=dJk%jTlHiki#f0kGlzfdkheybtb@2afqllkVcOcllCl4knjQiTl7i?iWbWkr7ciZldh@eQe~lSb}b)g/eA0Dfgi(8Mi,k}gF5YiPjLf|8glI8x5qk88fi{kbkz3Ti~j0hIhK0T1%e09;1%e3e5lEl#l7c+8pmc8RfBl:h9mAlOimg?f*l~f$kH1+j#l1b(l0lmg}j|mQeQfYg/ep0Q4fiE0dl~eK2Wh{bv0J201IlZe#dydAmTc0a?mNj-lRm^iu040F0Fm=ggiyi50mj;3rm8kX8.g4i=ca8ylagrngmHfJin9;keiClUh~mPm~f(mSmxcCf.nwf7mYm{9x9Lm$nCfom)eQm}m2cOm-m/jhl1b{mWl}g_b/n1n30}n5iHm`l{jznKj n!04n7l)m9gm8ImB5on:mf8okaldlPasmldU2zk`1e2XmphZj7e40Te1muo7k@0Y0Ln-nbbdkpgqnfktmEc:8SkxgVl^04kCkEn(lVf0o0ouflk~j}ltk_9Nk{oyf,l!n)l$iFfq0mlyjBjYk@oDaIm;oBnnoMlDftlFi/8$n;8!nhnfhbh?ju04gBnPntg-m65;na0vmzkZoibc8/o)o}k)opo-oskFiEnvo@2@0F998?948^911g0e8{pg2R2Mmspd0F8_9}0(0*0,0L04.

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

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.

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

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.

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

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.

Réponse

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.

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.

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

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

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

Crédits : Romain Janvier, Mireille Coilhac