Aller au contenu

Somme fixée de deux valeurs d'un tableau trié

Le cadre

On dispose d'un tableau d'entiers triés dans l'ordre croissant, mais on ne dispose pas d'accès à la valeur d'un élément, on dispose de la somme de deux éléments d'indices distincts donnés.

L'objectif est de savoir si on peut obtenir une somme donnée avec deux indices distincts.

Deux exemples

  1. Avec le tableau \(3, 4, 6, 9, 13, 18, 19\), il est impossible d'obtenir \(20\) comme somme de deux éléments distincts.
  2. Avec le tableau \(3, 5, 7, 8, 9, 12, 16, 19\), il est possible d'obtenir \(21\) comme somme de deux éléments distincts.

Vous disposez :

  • d'une fonction taille() qui renvoie la taille du tableau trié considéré ;
  • d'une fonction telle que somme(i, j) renvoie la somme de deux éléments distincts d'un tableau. Attention, on veillera à ce que 0 <= i < j < taille() sinon une erreur se produira. D'autre part, il ne sera autorisé d'utiliser la fonction somme qu'au maximum taille() fois, et vous ne connaissez pas la structure cachée derrière somme, ni taille.

Exercice

Coder une fonction est_somme qui prend en paramètre un entier x et qui renvoie un booléen qui détermine si x peut être la somme de deux éléments distincts du tableau.

Exemples

Avec l'exemple 1 précédent :

🐍 Console Python
>>> taille()
7
>>> somme(0, 2)
9
>>> est_somme(20)
False

Avec l'exemple 2 précédent :

🐍 Console Python
>>> taille()
8
>>> somme(0, 2)
10
>>> est_somme(21)
True
###(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 : ∞/∞
.128013x,59/fT78r;nb _o=ylaepcwgu)vd46F13kmhtsP(S0+2j-i:050D0v0M0u0W0t0N0o0x0t0u0N0N0r010M0W0w010406050N0A0K0K0u0k0s040Q0q0t0A0=0q0m050f0|0~10120`0w04051i1b1l0f1i0`0D0W0C0*0,0.0:0L0W0z0L0t1z0L0M0^050#0n0t0v1u0-0/011y1A1C1A0M1I1K1G0M0k1j0M0L1M1w010g0%0v0m0u0K0v010*150N0w0u0m0:0T1G1@1_1%1O1*1K1-1/0^0a0o0O0k0q0w0q0N0W180m0o0Z1=0k0k0v0x2g1b1~0m1j0f1#2t1Y1!1Z1H0D200:1C0m1,2d1G1r1t0+1N2D0W2F0m0q2J1G0w2m1j2r2t2X0{1^2h2L1(2Q0k0 0t0^0o0H2q2#0_2!1 2%1O2)2+2-0T2:1_2=2r2C012`0u2,040o0I2~2s0`312^0:34360o0E3a302#323g2-0d3k3c3m3e330q2*352-0F3r2?2$1v2_3w2{370i3B3d3E3f3G3y370j3K3t3M3v3x3h0e3S2@3U3o040H0R3Z3D2M3V3H0H2/1c2;3s3!3,3$0H2}3;2 1m2V1b2J2w0D1!2B3u0x2R1:1j411k3 2Z3|2s05470Z2W3T3,0J0^0Z0g3k3C320y2-4r3L3^0g0^0v0N0M0p0N0q0~0v4w4l1(0@040P4J3@2(0^0b4P3+4L0^0B0X3r0o4#0o4s3u0m0^0W3k4%4x1(0q0^0r4-4(3U0K0W0^3)4f0_4$4.4K2_0^0U4@4/1O4;044?4~514Q53040#0%1K4U324M0P0B56520:590V5p5e0:4`0^3:2X06504^4m0^0y1y5j5c5D4R044,5J575r0^020t0M0l5u4V5f554~5K1O4M4Z4~5B504$5#3f0^0s5W32595b2X5d5X5.044F4H5k3u5m5 3#4+623,4M0c5;4)54654W045o5)5+5,5P014n5M4q5O5q335/693U595S5U6s3^4S6c5$0^5(5A6h6h5-6q5M6x4:0^0S5@2;5_325x3%4!6F6H6l0v1C6n5^6H4*045:6o5v016u0z6w6*5`6I4T5!6j5%6U6F6i6p6%5Z6#6j5s6O2 6Q3u6S5z3=6{6W4A0(4I6@6p6_6g6{6|6+6l2m0M0A0k1a6:320J0x0^0h0k0A7e6E7k6;7m0!7p7r706p7u0^0G350N7A3=1b4i0v2t2U7T401s422w2z2u0u1J7W0f410`7*0!0$0(04.