De long en large

Rappels sur la

On rappelle ci-dessous les instructions utiles du module turtle.

Appel	Rôle
`hideturtle()`	Cache la tortue.
`speed(n)`	Définit la vitesse de l'animation. `n` est un entier entre `1` (lent) et `10` (rapide).
`animation(s)`	Autorise ou non les animations. `s` est soit `'on'` (avec animations, valeur par défaut) soit `'off'` (sans animations).
`penup()`	Lève le crayon : les déplacements de la tortue ne sont plus dessinés.
`pendown()`	Baisse le crayon : les déplacements de la tortue sont dessinés.
`heading()`	Renvoie la direction vers laquelle pointe la tortue sous la forme d'une mesure d'angle en degrés.
`setheading(d)`	Définit la direction vers laquelle pointe la tortue. `d` est une mesure d'angle en degrés.
`position()`	Renvoie la position de la tortue sous la forme d'un couple de nombres `(x, y)`.
`goto(x, y)`	La tortue se déplace à la position `(x, y)`. `x` et `y` sont des nombres.
`left(a)`	La tortue tourne sur elle-même vers la gauche de `a` degrés. `a` est un nombre.
`right(a)`	La tortue tourne sur elle-même vers la droite de `a` degrés. `a` est un nombre.
`forward(p)`	La tortue avance de `p` pixels. `p` est un nombre.

Dans CodEx, il est possible d'augmenter la vitesse jusqu'à speed(100) !

Nouvel arbre

Cet exercice est un prolongement de celui sur les dessins d'arbres.

On souhaite dessiner l'arbre ci-dessous en utilisant le module turtle.

On précise que la branche principale a une longueur de 200 pixels et que l'on a tracé 5 niveaux de profondeur. A chaque étape, la longueur est divisée par 2.

Cet arbre a une structure récursive : les sous-arbres de droite, du haut et de gauche ont, à un niveau de profondeur près, la même forme que l'arbre entier.

Il est donc possible de construire cet arbre en utilisant une fonction récursive. C'est ce qui est proposé dans cet exercice.

On propose ici de procéder différemment. Il est en effet possible de dessiner l'arbre en utilisant des parcours en profondeur ou en largeur :

dans le parcours en profondeur, on dessine l'arbre « branche » par « branche ». Ce parcours utilise une Pile ;
dans le parcours en largeur, on dessine l'arbre « niveau » par « niveau ». Ce parcours utilise une File ;

Dans les deux cas, l'algorithme est identique :

Algorithme commun

Soit s la Structure de données adaptée au parcours (Pile ou File)
Ajouter à s la position, la direction, la longueur et le nombre d'étapes initiaux
Tant que s n'est pas vide :
    Retirer de s la position, la direction, la longueur et le nombre d'étapes actuels
    Se déplacer à la position souhaitée
    S'orienter vers la direction souhaitée
    Tracer un segment de la longueur souhaitée
    Si le niveau est strictement positif :
        Ajouter à s la nouvelle position, la direction - 90°, la longueur * 0.5 et le niveau - 1
        Ajouter à s la nouvelle position, la direction inchangée, la longueur * 0.5 et le niveau - 1
        Ajouter à s la nouvelle position, la direction + 90°, la longueur * 0.5 et le niveau - 1

On fournit les classes Pile et File décrites ci-dessous :

La classe Pile

class Pile:
    def __init__(self):
        """Initialise une pile vide"""
        self.valeurs = []

    def est_vide(self):
        """Renvoie un booléen : la pile est-elle vide ?"""
        return len(self.valeurs) == 0

    def empile(self, element):
        """Empile un élément au sommet de la pile"""
        self.valeurs.append(element)

    def depile(self):
        """
        Dépile un élément au sommet et le renvoie.
        Provoque une erreur si la pile est vide.
        """
        if self.est_vide():
            raise ValueError("Erreur, pile vide")
        else:
            return self.valeurs.pop()

    def __repr__(self):
        """Affiche la pile, en indiquant le sommet"""
        return f"| {' | '.join([str(x) for x in self.valeurs])} | <- sommet"

La classe File

from collections import deque


class File:
    """Classe définissant une structure de file"""

    def __init__(self):
        self.valeurs = deque([])

    def est_vide(self):
        """Renvoie le booléen True si la file est vide, False sinon"""
        return len(self.valeurs) == 0

    def enfile(self, x):
        """Place x à la queue de la file"""
        self.valeurs.appendleft(x)

    def defile(self):
        """Retire et renvoie l'élément placé à la tête de la file.
        Provoque une erreur si la file est vide
        """
        if self.est_vide():
            raise ValueError("La file est vide")
        return self.valeurs.pop()

    def __repr__(self):
        """Convertit la file en une chaîne de caractères"""
        if self.est_vide():
            return "∅"
        return f"(queue) {' -> '.join(str(x) for x in self.valeurs)} (tête)"

On demande donc d'écrire les fonctions dessin_profondeur et dessin_largeur qui prennent l'une et l'autre en paramètres la longueur et le nombre de niveaux initial et dessinent l'arbre en effectuant respectivement un parcours en profondeur ou en largeur.

Évaluations restantes : 10/10

.128013,:CêLkn9DàSvFsuO8;y7e62-!0wr5_p»ag)R1Ii/é=m«hb.4x+*odt c(EP3qlf050#0v0$0H0N0.0o0%0(0.0H0o0o0Q010$0N0F010406050o0p0R0R0H0C0t040l0!0.0p130!0h0%020H0R0F0s0%0K0v1d0C0-0p0v0o050O1a1c1e1g180F041E1L051O0O1O1Q1L180#0N0m0{0}0 110T0N0I0T0.1(0T0$16050?0U0.0v1Z0~10011%1)1+1)0$1;1?1/0$0U0!0#1g1:0C1M0$0T0{1j0o0F0H0h110x011^1#010/0^0v0h1r0v1/2g2i2n1`2q1?2t0R2v040a0%0+0C0!0F0!0o0N1m1o0;2e0C0C0v0(2Q1E2x0h1M0O2c2$0$2a292b0#2z111+0h2s2N1/1W1Y0|1_2:0N2=0h261X1/0F2V1M2!2$37192h1o2{2o300C1d0.160%0L2Z3b173a2y3d1`3f3h3j0x3m2i3o2!2/013t0H3i040%0,3x2#183A3r113D3F0%0W3J3z3b3B3P3j0D3T3L3V3N3C0!3g3E3j0w3!3p3c1!3s3)3u3G0u3.3M3;3O3?3+3G0r3`3$3|3(3*3Q0i423q443X040L0A493:2|453@0L3l1F3n3#4a4i4c0L3w4n3y4p4h3e3~3F0L3I4v3K3/3W4A160L3S4E3U4q4z464J3Z4M4x4H4Q4d3-4T4G3%4s3_4Z3{4r4I4d414(434*4W0L484.4O3=4W0x4f4@4y4_3@0x4m374U4#4+0x4u534!4b564D594)4P504L5e4/5g3 0x4S5j4^3}4`4Y5p4~5r504%5u4V504-5z554`4?5D5b4W0,4|5H4:3@0,524o5a5N3 0,585R5f4 5U5d5X5k5Z3F0,5i5$5q4j5U5o5,5v5.5)5t5;5A5U5y5_5E5O5C5}5I5O5G615T3F0W5L655l675Q4w5S6b160W5W6e5Y5w3 0W5#6k5%6m675+6q5-4c0W5:6v5=6x5^6A5`675|6E5~6n606I626n646M66160D696Q6g040D6d4F6l5?6S6j6!6r6$6X6p6)6w4+0D6u6.6B6:6z6?6F6S6D6`6J3F0D6H6~6N706L736R6X6P776W0w6U2#1N351E2_2)0#2-3B0(262F0:1X1M340v363n3T057o0;7w5-0g0h160/2K0R7y6#0B3j7K6*0h7F040$0p0C0$1?7O5-7M3G7Y5=7E160N1s3)0$3T0%6f1`0!160Z3!54440(0L16031v0P0I0}0I1C0%2~2P0N0H0p0X4g3W162g0v0v0#7$3B15040)8j3%0R0N4J7e7C5=8l0J7.7/6#7{7}0%0m2P1C0o1@2S0.002i7*0H2Y4}8d040F2s0p0F8o448l0)8x4M0%8z6*8B047~1?0{0C0H0t1n0%1C0$0%1?0m0P8c4#160I0!0$0!8X4i8Z942o8q168t7:118l0b7.9c017=040y971`99044{9b6#8w8y9h8*7~2M2O2Q850h873E0v8}4b8e0=0T0v0H1W0h0I9m9d168n4M9h9o0i9r6*9t8$8(5-9w8_0H0%1W2V2X0N8=86139E9G4r168T0h0#0!0B0h9Q018Z8#378%9v7|8+8_1@0(8/8;1o8@0%0U0@0 8|4T067_4i0g160;0/a07!7/9U6#0h0/aq8G2~0E340!0/1n0;7Ua096aw7P160.1n0I1BaJaM5-9e9gax160=0H8TaK160J0c3!8%a5aY048baU8v169f8$9h7R0taX6*9j0Qa|6w9_2N871na%8ma34oa,9$6Baqb05=a~be8R9K9M2~9Pa;8k9Sb84wbaa_9_2rbh3%bga^a.0+bvbn3%a2a+a,bt8SbC396#9j0Va07R1x0FbK7x9s9S9TbLaNa/b6a@a4bIa{bD8Ya?bw9H048ib*95b,bzbZaP9OaS0Cb#b-9^04a!a$b;2o8wbq3Kbs6#ap040B1%7Xb@5-9}16307-cfbcbJcebYcg16bOc33saZ0o0$0E8E0;b68!a*4Tbac8bZa:cpa=04b$3nbb8Rb)cJbocLb~3ebdct9RcTcl8R0.b}c!8~c0cU7;16a c(b.bScobUa}crbPaAc;9FcXa1bpbGcFcOc)9`8VcBc617d1a-bZ9092cBc_b!c}aWc/b cQc?aVa(d0cFbI8H2c9L9NbmcRbE9Sdfb:dxb+04d706d9d2c:2s9|9~d6dpcGb104aG0C0B1edBdmcKbXdXc#b6dFdH9hca0NasdjcVc*d-c,04020I0$0sc+119o9Ydn04cD53dHdPcmcId!dycZb%a.dl3ydI4ibye9bZ9yb49 dhc cEe2dadQdWec9hefcNbIbjdvdNeneobIc{a0bNdfbRbT3y9h8ZdZeJa.e5eN9Zb?egdQeb7fbVe8eva.er2#ed2o9j9ld:d{8r049Xc%eTcmc$e+9i7?d`010Raz040A0V6_8ucScMesa.c|e;3Be)e`9o6Zf2e70Jd%eoe%cucnf7e644eFc}bQ1seIeWeR8meMfudQePfycKf4e$b(e:eZbZe#fedDfD7#a.e?f8bxe_e@e|9af0fGf5bZfmfYcq9kfbe-fdeKa(fheBa.eDc}fpdCb eHc=eQd~0)fxfKb fAf~c4eSfHeUfXfEe!e`9j0Yf(16e/eleYf#e=g9fSfQ44fUe~fWgffMfj3OaZgjf%fTf)d$dFamd)aAd,f?2oaubPe}0;0 aC0}0C83aTgF1`aLgRgt04b_aR0vgQfnb=ggg7fZ0?c2gUc~dEe0b9bHeOg6fNbZeVg@f$c.glb ei8Pg,bFeAgs3CcWg}e(c-e`7Rexbleze1g;bZ2Bf!g(g{ha160nftg1gSemhfepcmhieEc^fqaZayhpf+fwdfg0hDgrfFgqhmb/g?h47RgXb{hNbIc1hjhqcYfgdpgCcbcdhVh4ch04cjhLhwf;hyg,bQcwcy0NcAgfcCdOhgfzhSeah~fIi0dQfPg#g2g%g`cmh%eth9e@7Rh-g,f=i5fkarhCeX8!h{hu8Rd48Wh_f-dqa.dc93h_hFi2cmg_hDiue38Rdshc9OdehzhMgfiFh|cm9`dLekh1hsg:d1bIdSdU0CfJhDf}bIi4f`cKiPip3%d*gEg4i9gvd?d^gce~b6g/brfibIhGeXhIh e@eughiqb3h0iicYinh3d(g8j6ich7fkiJdwjcg-jehte2iZilc@04csh:hAifjoeLiAhKid16iDj3hLfJh(16e*jke,gdd}fChLi+hkbfgki?3Bgne f1hHhLiabMjMi{f*eXhYjfd9jtf_fBf9h/jobQhBj?hWjpi)g=jEjOh504jHfvj4i1k2jYc)jUi8j^047@fTe}j#iB8Rj)jvjNkbgmgyiOi.ivhhjuf$jxj`jzkxdYk0cHklc)k6d~k8eqgvgbgxjQkGb.kdjLkgfbkjgpiVi7hOgujigwk3fcgz7^and.gK2O0haD2KaG9{gZb|izc}9o9qkQ4i9oj$j.9@2o9(1w927U0%890%2M2~8^2S0#0P2h7Vl3fkirhe6afkixiLg,d|k~h8k%jok|0AjRcSdFdr9Jduhdk`lse-gekYlCf/dK9}iUjBiW6V1`9(0d0T2i832E0hleaa0!0p1?g!lTgV9`7oaPk_kYkE5-0o2l04012V0#01d$7^bIk.gM1egPl;lR8ma0lylAe7kK5=l0l 4Z0O7A7v7gmk0O7j1E0$7lmp2+2%25272)0H1=mm7j1Kj~2V0R0E0/0H0g0v0E0T0,161w1y1A84i~7f1R3o1L0d0!1c1@8=8T1la98D0!0N0C0ba90`aI0Xlb1e7o7U0`2*0H0(2s8^8-0R0e2El90C0U2V8?1o1a1X2i8^0p1o0S0{9K8q1o0G9+d+0/0P2Vl#cs1U1P040M0.8?cw9B0$np8Gnc9+1@cj0v0C0%mRm)lim^0C0`2slbk=aHk^lbgZ8^89gL0%0e2*l%lg0%0k8_8Lh@8I00ne1@k?9.8=0C0P0(m_1X1@cDnt2_3B1|1*1,1.j~hi2D2F0+m@l(nPn8nSaFnUl8n_n{nPd+7y7u8u387xmjj~caarat7NfqgJaBk:aEk?aIm6i,cSl?e4lufkkIjSjFb/m,2WjboHmcjTaQhRkaj8c)hUd$mTd8iQiq8Uisl=iubIlqlHkAdgkYmdcPmgjrlDdtbkiKo=oUb.9,oS9/lQp2g$o/lN9{lPlni i/b.i!dVlro?hQk^o{iXh4i;j(g*knf$i_d_kOi|gfo(dGj;k1o^hLg_kTg|kqg~jap6pec7pDfIoRn@p7jVkfpJo!b.jmpOo)iYfOoXpnk$0ZpXpV8pkWf1pCp%g)a#pujW9kp-ke8pksjriGc)m2oCnTk@l+j@e7oJ8Rj2k7pGoLgVp4pTgvkppYk lJmbfLoWb`p*pFoPo$iOiok!b/oBk;ohq6oGq8dDqac)qckJqeoZp.p3pSoTqFg$o_kcp)q7j~dik3bQptpopfkveqqAoDoiqEqXdziMqJoOqZjGqfk4qhqQp}fo16kNk(qnq^hPqVq-j%quq#qwmhotml2$mBnu0d0=0$1@a#aE0(9Kny8^051x8S2V0omR1Err850;l#0NnLn+m}0.8-1l0^0N0onEn;lb2r0V0%0*ae0/0/0=m.0N0(0Nm.1?067u8qnIl90F8Tnxokn|0/0%m{m}m)0ol(0o0y1en68I1@ng0#2K8F0%0GrP0q1or=1@2snarin,r|n70#0p0%nglXm(nl0=n82q3c0v1k0NnFsj0%0I89rm1@s51NmW040j2i0`8Krk2KsAl90m2W0%rMc{r!842~dS1d2Qm:n`0Cnbl#r@r_r{n5sgr 9+s2sdnlr^s%f^0P84nRr%0Nr)0c8?rF84s=le1n0(8?rToS0ps^nQ2RnI9CnI0Vtg0%0f9*7o0hcw0C0ppT0%8H0%mH2P7/rrn+8K2ssOnPrw0RcLsv0}sxszrntBsI9*s1m+sd0zsD18mna!0^0o04.

Vos arbres

Votre tracé sera ici