Aller au contenu

Exercices Diviser pour Régner

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

.128013vt4=8fw2pmuP(j751,:cSsr]ék[63;0 dg)/+n9qiyelh_bà*oaOx-050H0R0c0Z0P0S0w0G0u0S0Z0w0w0e010c0P0j010406050w0l0k0k0Z0x0Q040v0Y0S0l0`0Y0M050K111315170 0j04051n1g1q0K1n0 0H0P0b0/0;0?0^0;0M0I0l0Z0I0R0$0j0Q0c0T1e0G0T0P0I0T0S1S0T0c0}050*0V0S0R1z0=0@011R1T1V1T0c1#1%1Z0c0x1o1N0/1a0w0j0Z0M0^0i011)1B010g0,0R0M0Z0k0R1Z1~20251+281%2b2d0}0a0G0m0x0Y0j0Y0w0P1d0M0G0(1|0x0x0R0u2y1g2g0M1o0K1N2L1^1`1_1!0H2i1C0P0M2a2v1Z1w1y0:1*2V2X0M0Y2#1Z0j2E1o2J2L2=101 2z2%262+0x140S1Z0Z1Q2E0g0^030U0U0u2,0R1V2*0Y0$0F0$0r0}0G0r1g0Z2?2_0~2^2h2{1+2}2 31330R350137393b3d2Y3g0$23040G0i3n3p203r2J2U013w0Z301o320T3436383a0(3G2+3I0D3k0D3O2I3q0 3S3u0^3V3X053Z3#3C3%3F2W3H3h0d3k0d3:1h3=3s2`1A3v0Y2~3W3y3!3A3$3E3)423+3h0q3k0q482=3?2_3T3`4i3~3D3(3c4o3f3h0C3k0C4u4a3@4d3_4f3x3Y3z3B4C413e3I0p3k0p4L3Q4w3t4O3U4Q4h4S4j4U404n4X3h0f3k0f4$2K4(4c2(4+4g3{3}4k3 4m4E4?0$0N3k0N4{3R4x3^504R3|4T4l4D3*4G3i0F0}0r0F5d4}4y4,525k555m4F3I0r3j045E5u4b5w514A544V4=433i3K0r3N0K3o3;4%5J5g4z4.4B4;575Q0r3-5G3/5V3P4|5Z4*5#5j4/5l4W5*455G475/5X5;4N4 5@534:565n5D4r5G4t60495Y632|5x5M675B580r4I5G4K6e4v5=646j5$5N5(693h0r4Z5G4#6s4M5f5?6w5^5%685C6B4^5G4`6G6g6I6v5L6x6l5{4p3i5a5G5c6T626V6i6X6L6y6N580i5q046?5I6h4e6.665`5P6#0i5F726`6,6|5i6~5A6!5o0i3K7d754)6W785z5O5)715,0i5.5W6f6+7h6-7j5_7a707c5}0i5 7r6t6{4P6}7k6z6O3J6b0i6d7E6H7u774-6/6Z7z3I0i6p7Z7g4~7v7U797l6A3J6D0i6F7Q6U7S7H7w6M6m5Q0i6Q7|7$5K7^6:7`716%0i6)7;7t7%7T5y7x7+7L0D6@8g7 5!6K7*7K580D5F8p8j6J7I8d8n5Q0D3K8y8s7i7)7J6;8x5,0D7q5:5e7?5h8D8v8F6#0D5}8S8B7(8c7_7b3,6b0D7P8K5v8k8u8Y7X3h0D6p8/5d1r2:1g2#2O0H1`2T5g4D2!1x1o2/0R2;3q611o4D952h0P0H0^382J5D3y9c9e8Q5o3j0G2m0R9k839m1Z607G010A0}0(0g976u260h3k9C9w0M0g0}0g0l2w1e9H760^0|040n9Q8M0M0}1#3m7s9a8a9S0}0s970G9D3v9Z0Z0V5U2@9w9T0J0t970 9$5J9j019f2_7Y9i9da19la49o2c9qa79sa42L3o0Gai9-9I0V0}2/2W0c9W9(019T9V9~9w0w3K020O0l0Y0c0E1P9M9O0M2XaAaCaEar3T9T9+9$ak9R3U9:0V9#9@aUaQ9,9.0^ay0}aLaD0E0)a+aNawa!9*a$9IaW9?969^0}0J9|aOa0a2203,a59r8Z8.249pb68-0$5,3OajaT9X0}0MaY3qbhas0Y0}0ea@aU0Mam042laO5gauby5?aWbl3Qa%ata}a a;9ba6b20M3I5}5jb1a844b9abbb7m5obQ5/bgbG9Y040Ma`3Qbn3Tbp04braSb%bvbxbKasbAb_4ya_bB4 9_bJaZbL9k9g4qb5adb70$4raa2dbX7,6bbfajb%aWbs8Mb/b;2=b-bz0}0Bb 260k0P0}5tb|cs040ycmbo0}0XcFaP0}avc3asb(bkcJ5gb/0LcRbCb)b+2KbGc19$9}cN0GbSc60$6pbRbMbTc,bVcec9bcc-b#cja^040PbE2Kcr4*cocV4 cxczc2a{4xc*a33h6Dc.cf7L4Zcdac8w6#dec`aickc}cY3LbGd3b=9wd604cA6tb|dbb34@c8dl5o4^djdg586Qcidp9w0u5F030G0!2`1e0`0M0l1(0o9NaB02030D0N0E0W0G0Z0b0Y0P0x0G280M0P0G0l2z0(0.1=0R0Z0l0#d8bF3SdDbO3h6%dfc@bY3I5adKee7,ecdod14 9y040h1R1%d42|0}c~eu1+b/020Sa:cqdqcQdwaU0Y9F04200Hey3_ewdsen26eAeC0EeOaVcXcv1+9T9{c$b0c/c+5sdGc:e,eidH5D6@dObgeS1+ep0P9BeHbi049!e!9)04cucBcWexf6c00}cEe~cG04eBeDbmdq1#dsc!ctf2eY0Pfla|cDe%dBc(e95D5Fede;6B9nbaej7L5E9uahe^fKfj9;fo9Tf5c(5!ewc dt9wcTeXb(fqfOfbeXdveEc|f1f926fPfofZfUfmcDe6cZe8e*dc5Re-ae6B23e:e.3Ke@fKdPbtfTf%0}0Lcpfidxcy5Gf@9%c)f`dE3ibe32bSf~gmc=dke.beemb$9wep3c0w0Rf#04fu4adCgkea3ibQgoc/gq0r45g1gOb!fJg5c{g7f0fNf,e#fng!ePc}fUe_0^fXfdb}drgDfcf)eIbqfYb~g%bHf4f/eQg;gh9 gI6af}ca0rccfEfB3ichgwg5dqf!g.cSgagcb,bGdyfUc%d9c4a7e+c-gMdL5*4IgRh6c_gUg+01dR0}dTdV1|0j0P1(1%0G2E0w0c1(2B9!0G2w9o0z0u0R0?0+2Eh1f_c5f{6Ch5bch,hzh.dnhCbGeper29g_g)g9ffeVh{eGfR4*e$h(dah36Ph-efi8h:ia3idNhdg6e 1#gDfQhqcOg8hhd2gah{hgi2faf?ip4 f(gdgXf+iuf-g$iD9/h|g{9Tg=gGfwi76$i97,0rehh9e.elhCgxgXf8g?cnhjeXhni5hrbN7Ye?hvfF6=5qic7,6?fI3LgW8MhF04hHdWhKhM1(hPhR2A1(fkhVd{0MhYh!0wh$gCe(gHh*gl72iQ7Ljli?jnfzemh@0}h_etixevg:jxeza*h jAg(b*gDgF5Yjihsf{7djm6=g0iUgqjNagi`fLf*gZiGf3ile7iZg*duirjEfpfra=iwi#fehkd0fM9=ikg~jzjZg|iLjJiNjjgJ7pjO7{3-jp6=gviXi{inj{iAi$04gbi(gfhoe)k17YgLgjhw71gQjRca7Ci_iY8Mep2E0c0l0x1fj+b(ijjhk0jLjkchi/ha7Ogskq7chc3ohpj$i+0Uc+7Zk471hyktbck!jUjt049AfoeK9-g{9J9Z0x0P0UaH0P9PiJcLj`kHj|9_jI5;jKi,3h7/k#7cdik(idl9jUkxcObvao0Maqk~9Ufoa)ffaBa,1P1^hLa/eWlnaRj:g/l1imcK04a~kIlEfxl8dNkNc:7|kQi:7{ifh?c|kElBhib:fYb@2agDcMlEfSgY0VgDlHfvlJiO86la7YiTbWlR84kwkb3Te{e}lXcWlWkefe020Ifhhlge5rjHi*2zlKbdi.kpl`5o8glQhamllghedQdSdUj0hL0G1%e09;1%e3e5lIkWmeiO8pl?8.fDl_mnjrkaihkciCm4b.g^j+f.k=cllnj#f^iZh0j+ep0g4fisf%eK2Wl!0}0x201Il%fodydAl)i3a?kFbjfob/0K0Km_gfj-8M9_j~l5kJl7bdg3lNgq8ymmc:nimpjWiB9;eRj)lZmViFm|64mYl2numEg/0Pm%m1eo9Lm+m c}m-ewm3m9btbvm=1EjgnylomXb)n10}n3n50}n7b`m~nEjynMm#n8a}na3rl6kYf{8ImIbdk6ld7,n@nme^bGi}i d^9Nk|aJj20.0(e40Ge1mBobk^0z0wmdmind8Sn^olk78xgTjVn gym;0)kCn+fVgXk{k}nTl(nAl*lvk`o4oBnviEnUj|kG9;f;fs0JlAmSoFk^oHaIm^nVfkl-l.iMl:km8.kMojnkh8mLo.l|mPl~0}gAnSoKg#gEoimf8/omk%o:nhhBorlho@04kAowh{lDj 960K998?948^911g0c8{pm2R2Mmzpj0K8_9}0(0*0,0w04.

2. Bien comprendre les affichages en console.

II. 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 à 34 de la méthode creer_labyrinthe traitant le cas de base.

28
29
30
31
32
33
34
35
36
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
28
29
30
31
32
33
34
35
36
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

III. Exercices CodEx⚓︎

Exercice 1⚓︎

Sommet d'un tableau unimodal

Exercice 2⚓︎

Carré parfait

Exercice 3⚓︎

Minimum et maximum

Exercice 4⚓︎

Tri rapide

Exercice 5⚓︎

Indice d'une panne