Aller au contenu

Créer une classe ABRI (ABR d'Intervalles)

La classe ABRI

On souhaite créer une classe qui ressemble à celle des arbres binaires de recherche, mais qui gère des intervalles comme objet de donnée. On propose ici une méthode simple.

Les bornes sont incluses dans les intervalles d'entiers, ainsi (7, 13) désignera la liste d'entiers 7, 8, 9, 10, 11, 12, 13.

Exemples d'application

Pour les besoins de cet exercice, on imagine que lorsqu'on envoie un satellite dans l'espace, celui-ci réclame une bande d'altitudes pour rester seul en sécurité.

On stocke les intervalles utilisés et on souhaite vérifier si le prochain envoi est compatible.

Dans le futur, on décide d'attribuer les fréquences (une bande d'un certain intervalle d'entiers) à des opérateurs par une méthode spéciale expérimentale due au hasard (et certainement très mauvaise). Chaque opérateur prépare une liste de 10 souhaits d'intervalle de fréquences entre \(0\) et \(10^6\) avec un total de largeur proposée égal à \(10^6\).

Tous les souhaits des opérateurs sont rangés dans l'ordre du plus fin au plus large. Ils sont proposés alors dans cet ordre-là. (Mélange en cas d'égalité).

Le premier est accepté, les suivants peut-être pas ! Les bandes ne doivent pas s'intersecter !

Chaque opérateur espère obtenir le total le plus élevé et voudrait tester des simulations de stratégie face à ses concurrents.

Envoyer votre idée à l'auteur, la plus plaisante sera insérée ici avec votre nom ou pseudo.

On vous demande d'écrire une classe ABRI pour aider à résoudre cette situation...

Description du test

🐍 Script Python
abri = ABRI()
assert abri.est_vide() is True
  • On crée abri de la classe ABRI.
  • On vérifie que abri est vide.
graph TB
    R("(7, 13)")
    R --> R0(" ")
    R --> R1(" ")
  • On tente l'insertion de (7, 13) ; c'est un succès. On obtient True.
graph TB
    R("(7, 13)")
    R --> R0(" ")
    R --> R1(" ")
  • On tente l'insertion de (10, 23) ; c'est un échec. On obtient False.
    • en effet, il y a intersection ; 10 est déjà dans l'intervalle (7, 13)
graph TB
    R("(7, 13)")
    R --> R0(" ")
    R --> R1(" ")
  • On tente l'insertion de (5, 10) ; c'est un échec. On obtient False.
    • en effet, il y a intersection ; 10 est déjà dans l'intervalle (7, 13)
graph TB
    R("(7, 13)")
    R --> R0("(2, 5)")
    R0 --> R00(" ")
    R0 --> R01(" ")
    R --> R1(" ")
  • On tente l'insertion de (2, 5) ; c'est un succès. On obtient True.
graph TB
    R("(7, 13)")
    R --> R0("(2, 5)")
    R0 --> R00(" ")
    R0 --> R01(" ")
    R --> R1("(15, 25)")
    R1 --> R10(" ")
    R1 --> R11(" ")
  • On tente l'insertion de (15, 25) ; c'est un succès. On obtient True.

Exercice

Coder une méthode insertion de la classe ABRI qui prend a et b en paramètres, deux entiers, et qui tente d'insérer l'intervalle (a, b) dans la structure.

  • Si a > b, l'intervalle n'existe pas et la méthode n'est pas censée gérer ce cas.
    • On garantit qu'elle sera toujours utilisée correctement !
    • 👍 Ainsi a <= b est garanti.
  • Si aucun autre intervalle ne contient déjà un entier de (a, b), l'intervalle est inséré dans la structure d'arbre binaire et la méthode renvoie True ; signe du succès.
  • Sinon, l'intervalle (a, b) n'est pas inséré et la méthode renvoie False ; signe de l'échec.

La classe ABRI minimaliste est déjà donnée, il suffit de la compléter.

abri à la fin du test

graph TB
    R("(7, 13)")
    R --> R0("(2, 5)")
    R0 --> R00(" ")
    R0 --> R01(" ")
    R --> R1("(15, 25)")
    R1 --> R10(" ")
    R1 --> R11(" ")
###(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 : ∞/∞
.339.128013x/.ùTr;nbOylaeu)dM6ç3HAm(P02è-U],59fq!7B8 N_o=pcwgvF41kRIéhtsàSC[ji:050s0p0-0o0@0n0.0R0X0n0o0.0.0V010-0@0W010406050.0q0z0z0o0h0m040:0U0n0q190U0j0R020o0z0W0i0R0)0p1j0h0M0q0p0.050d1g1i1k1m1e0W04051R1K1U0d1R1e0s0@0!111315170,0@0Z0,0n1,0,0-1c050|0k0n0p1%1416011+1-1/1-0-1^1`1?0-0h1S0-0,1|1)010L0~0p0j1x0p01111p0.0W0o0j170D1?2p2r2d1~2g1`2j0z2l040b0R0B0h0U0W0U0.0@1s1u0`2n0h0h0p0X2P1K2w0j1S0d2b2#282a291@0s2y171/0j2i2M1?1!1$121}2/0@2;0j0U2^1?0W2U1S2Z2#361f2q1u2`2e2 0h1j0n1c0R0%2Y3a1d392x3c1~3e3g3i0D3l2r3n2Z2.013s0o3h040R0w3w2!1e3z3q173C3E0R0$3I3y3a3A3O3i0J3S3K3U3M3B0U3f3D3i0u3Z3o3b1(3r3(3t3F0O3-3L3:3N3=3*3F0Q3_3#3{3%3)3P0K413p433W040%0C483/2{443?0%3k1L3m3!494h4b0%3v4m3x4o4g3d3}3E0%3H4u3J3.3V4z1c0%3R4D3T4p4y454I3Y4L4w4G4P4c3,4S4F3$4r3^4Y3`4q4H4c404%424)4V0%474-4N3;4V0D4e4?4x4^3?0D4l364T4!4*0D4t524Z4a554C584(4O4 4K5d4.5f3~0D4R5i4@3|4_4X381X341K2^2(0s2a2-3$0X302E0_1#1S330p353m3S055D0`5L5p010(1c3q5N5e1~0Y3i5X5j3r0X1c0y0P0)0*5$5S1b040^3Z0R5^0R594h5U040`0L5/4}175!3F613A0L0z1c0T0T2}2O6b663$5;0A6g430k5;0.0p0n604L5{2e5;0r3S5`5Y170U1c0F020Z0-0i6x6t1~0(5)040S1t0p6k4h5;5?4S5_6W6y5%176m1c6o6q6R2e6B040e6)3r1c0z6d6I6z016+0V6?6Z5T6M6O2;5@6X5^6J6!6n6p6r386@6+6-6s6@0j6:0o0c0@6{5S6_7k626}1c6 6Q4S066W745T1c5 6.635#7d6|0j0L1c1I0-0T0!0@0`7A016i7O6#046%785M6@6v7n3A6+6D6F6H4L6Y5S0j0k1c0k0U1p7O6T71727w5}2U0-0q0h0j7Z6h1c6j7D5S7S7U7O7b7O7f046;0j7j7)7w0U640@1J8g6@6L7q6P7=1c6w8m6|8i1c2r0s80437Q847o8677881c7c797E7g7i8A4h8w048k8O2e8o6N8q8D3A7Y7t7v8n7y0p7V3x7w645`8Y4!7G8R0j6o0h2X8/8B827R766(8`6S1c0I8T6/040o8r04938u7+7.988t367*7o7#6E6G943N7-047/7;906u1c6U5o7o8-728.8K5S0.0s1c019G0g2i0-1{0s002}0.0+2U0h0R0=0o0I0R0k0H4f3A9D3i9z6W0F0R2U0j0!0U0@1{0g0h1H0R2i11140R2R1g0X0X0E102R0n9N8?0p8^0@1t9a9w9#9E3F9(5_9*9,9.9:0R0#3D6o0R2N2 0j8J4n7w9$af729G017@6X7_1c0@8*2!9h3A8F8 9B9i8I8a7H0.7J7L7N9s1~6i0r9v4nag5_7waLaH5RaO6,aQ8c6=9ba,6`a;3V8xaC9(a(8~a*8haPaW3N8M8f9ga 04a?b57e9d6Va$aJ3$a)8Ha-b13B1c0Z0o0q0X0,7sb98v1cb83mbe4a5*5,5.bjaYa`9za|6$8Gbj89bj8b0s2J2Obrbwb6bv3xbx4qbz5-980A9fa#bdaE047{7}7 a@3$8V9=1H3Z7ubF8%8Ra*bV3dbbbs7l1c020n9lb-6la}bhau8+baa/8e98a!4vbdb{6K1cb*7~9m01bgbJb0aNa^04bmbobqc7a.9Oa78_cr810483cCby9698abbRca0k9ebE73b^6paGcm8b97c48Pc07%cmcocGcYbic%b|8c7hb47W6|7?bca$b(ckb,b~8Ec6cpc)c/9c5~bO9KcxbLaFa6a81tbZa.cWc*aX92cUb}c 7o8!52a{cR0 bQc9c:9ucPaDb^c^cm8Vando3-0d5P5K1V5v0d5x1K0-5zdJ2+2$0o1_dEdH5H1Qa+3A2U0z0T0L0o0(0p0T0,0w1c1C1E1G1I0Rce2!1V3n2^3A0o0s0z1t2Oa91u2}0L6+1Qd_d{d}2P0F190-26040y1r2U0Rd!0v1t9|1{d!0@2Ud?dU0G2;eh0oej1u0k9:1u0W1q100.0U0qeB9Lem0}eg7Iel110h0+a70R0qet3q1{5O5E040*0j9K0h0!3D1`1KdD3F0o0!2VeSet0z0+2b5EeN5D1y1k0}eE1u1G0@0R0Wa72D0-eNeP2L0jbN1{0/e;9X7:0neQ1ufeeX5Qe!e$e(0n1`0A9V9X0r1vc21Afoa7fqfs0X9W0s8te,0e0R0leA0p1reOeQ9S3D3(101`10e?e^0`eD0W0+0X0@3D1Ieq050q0n3n1/1Se,6bc26fdCeY0R6j1D35281t0Z040n2Yf 0jg11I8@6yg5g10-g42Jg6040,2r1Kf}0R1AeB0q10f4ea0Rd.0r7cf:1ef:fm5K6b6Ff^e,f{05f}1fgbctgeg0b)0p0oe$gagfgcgMgggib,glgneC0R0Z0h8ygt1Hgv1Kgx1Kf-3n1R0y9O0@9Wekf4fO1r0~8keR1!2U2W1D9J0R132yeWe,5+0)e+f`0.2rgq2U0.d.9+ez11gX0Za79Wfe2q8^h6eJ2Of82i9.0meReTfg1pfj7c1Y1T040;00eMg}1`aqf2ek0oe;1{eV5`ha5,hd5Q9|0+0?fe0h0@bp1{0{g*00ekeE0qgibPg$1k0`9S9Mbn28d/fX0,5EeDhghv10ePf$h*eg8ei62n0W9:9S2L7}hXeYhbbBgF0Nf+d^3$201.1:1=dV3$2A2i2k1c2G0:0Xh*0Wf70B0me^c_5M5Ja+375Me,b(5Wbj8-8a6MfAe%e)dpd=7Xdsc=ch175}7ziV7Cdd17686a6c8e7J0Tdabjc$di8ZdfcXc+dci cDcKbU7w8bcNbC8scm9jc!j26K6~8Xi;7Pi)dlb@6|i~dqb c~js7o8b8dc.j87abudgcIi*8$jqc|jlbKjljxc-jejCjhb29pb=jG5Si-8)7OiWbji?04gCi`i|jljri%dr99jDh~epjc04b#jAbt047$c3c`3V9o9qg3j=d;1ddm6|0.2u04010te@i22Ra3h:f#g(9Kij9k1A9Jeg2}fpi#0.aBjFa%dv0{b+c#jIj543jKkBbWcbjzaIb6klj/efi$ixkCcqkEc+1j8N8#kv6|jWa~6@jZjlj#f?j(j=cFkR1~j+kO91j.jQbk96kMcOk=jfj|cL7Ej fhcddtawk8kakce_kf2K9QgQfN9Sc16G9^e#koe#fBkrktjo7^kw7|clk=k.b6c8j,d0kTkH65jB04le7(j}4!8xk^c}lvk/kSa:5253435}iUjlk#k,3N6Mhbl14|3A9y73bjaxaA0;3:1{hb0R0U0ff3eF9Sbp0ohk0j0a0q8zl!3$ax9)h600e@0@d.241{0jhMaSf39{7rf{mf0s0+2N0ZethDl.aU0p9W0~0RmahT2qa2m9l|fG9!m0aem2fV0R0+fi2De#10fecuh,aq1tf7lD0Rfe0X6p0qf20s0qmtmzmB43m1ahidmH0+mJ0-mL9|d21{e mR7%mT11mWmYm!l{l}b=awmD5_0B9{keeF1_d9l m(n35^aAaCb(i.lTi:lV2f69j$i^6ei{k*8}bHaMnldkk}jtj{lEny7o8V7rlZlndujHnukZj_lKj91c130k6pjOb7dxjj70kucQnJ7TbIjJkQjvcsmNcwk`jPlFlQnWkNb?lon!87lJa.bN9/d3n-nUk=nEjk4nn?i+7x5~jXi/65bL8;7I7K7MkN7w8Cj*kAn)cDj@kIlBnAcUk 9rjlc;nHjUnDcjkxlrn/4hltlBnNcanQnSk`8j8loD8Un;jTkWjV8(nL5SlUom4a8;czd8iMoYk:k+o(2eoFj-j7op8L040ck_oO1~k{nBj^7+otk1ovjnb$n@9Cl4fL0R9Klj9|a59P9R0R0c9Wh.ekaj9/1{hDk0fj0Rb:h-3bn6m?boa00.9Wdzapar1tlmp2nIoTb_kznKd4jLaRaTogbZaZdtoyaKollwa,oHo;oJo nC7!n.p#lGo=pRoSc{pJn`d5ctbnh,nTbTo:d0lYk*ook4b%6@o-jtpXd0n|bPp@jDp{p0cEp}o5k5pGdwo16Mpql2dncTk=8bo?n lDpIn#nvo+o_n(pVcspZnGbwo60X0%1c03f{0%0ripnYpFozgOlqo%p_p-qtoVpWa.n+ohoGcyd7cBnw8|p:qpqaqcqeqOcSb`nOp*qqjgo^75p.n%juqyp)qAk26xqDqF04qH0A0DqKp+nZqfoBqRlAn^n$nlkDqvjRq5n~q|q3jwd68@q%rkjmcEa.q+q(j?qkkX7HdAr1qMpS5Cr4qH0;9{2pf$f(0n9Wmwpao#rt3Jcgc@rdnV1cpzn=h!dRiO5wdT051pf/0@hKmbf7h+f2hkgAnof@nrgFhN191/9P1{qLg.f:hLeMr@g*h9eYj%gEf`r g~s20Rs4r:1e0dr.1Z0{0}0 3A0s2rhp0h1c3K1h1E1m0xfTf32Jg%1x2Dd:0R0,9Q2O0ohp2YsA1Og;04p6ii2T0}f7bn15f2hOg 9S8)2g0X0omVm.m3sMh*0|hplg2H0l0l0Re.2Viq1#3Ait221;2v6|iz2C2EiDiF1aiIiKi2re1T5v5t38iSb^lSnloXq~4alXhZrFnH7wqEqG0Ree0XeT1{d|1!s,gQd m`9.h h8tA5,0R6d19f)ngi(040=c70erpj0049Z7tiT3:jYnkru0jiYlji!frqZj-k3o5txrJ0R0;ePtIg`l?m30U9 14d tUj-tXlJtZ98t%lOt)1}t+objLttbYnsp:q9rzpQi*t`tzp60o0?eF9KaqfN1`s:fZ0Ri1i3aqf#f%2gd.oNpEnho9njuinl7FrrcAu6umokq{rzo/rfd0ryru6vt^q.t#u9roubj=udavf_5QdFdR5xsm0`0|0~0.3ndS0!v1u}srv0.