Somme fixée de deux valeurs d'un tableau trié
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
- Avec le tableau \(3, 4, 6, 9, 13, 18, 19\), il est impossible d'obtenir \(20\) comme somme de deux éléments distincts.
- 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 classe Tableau qui dispose :
- d'une méthode
taillequi renvoie la taille du tableau trié considéré ; - d'une méthode 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.
Écrire une fonction est_somme qui prend en paramètres une instance de la classe Tableau et un entier et qui renvoie True cet entier peut être la somme de deux éléments distincts du tableau, et False sinon.
Exemples
Avec l'exemple 1 précédent :
>>> t = Tableau([3, 4, 6, 9, 13, 18, 19])
>>> taille()
7
>>> somme(0, 2)
9
>>> est_somme(t, 20)
False
Avec l'exemple 2 précédent :
>>> t = Tableau([3, 5, 7, 8, 9, 12, 16, 19])
>>> t.taille()
8
>>> t.somme(0, 2)
10
>>> est_somme(t, 21)
True
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)