Aller au contenu

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

  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.

Écrire une fonction telle que est_somme(x) 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

###
bksl-nl# testsbksl-nlbksl-nl# test 1bksl-nltableaupy-und1 = [3, 4, 6, 9, 13, 18, 19]bksl-nlbksl-nldef taille():bksl-nl return len(tableaupy-und1)bksl-nlbksl-nlnbpy-undtests = 0bksl-nldef somme(i, j):bksl-nl global nbpy-undtestsbksl-nl assert 0 <= i < j < taille(), "Mauvais indices"bksl-nl nbpy-undtests += 1bksl-nl correct = nbpy-undtests <= taille()bksl-nl assert correct, "Il faut utiliser `somme` moins souvent"bksl-nl return tableaupy-und1[i] + tableaupy-und1[j]bksl-nlbksl-nlassert estpy-undsomme(20) == Falsebksl-nlbksl-nl# test 2bksl-nltabpy-und2 = [3, 5, 7, 8, 9, 12, 16, 19]bksl-nlbksl-nldef taille():bksl-nl return len(tabpy-und2)bksl-nlbksl-nlnbpy-unds = 0bksl-nldef somme(i, j):bksl-nl global nbpy-undsbksl-nl assert 0 <= i < j < taille(), "Mauvais indices"bksl-nl nbpy-unds += 1bksl-nl correct = nbpy-unds <= taille()bksl-nl assert correct, "Il faut utiliser `somme` moins souvent"bksl-nl return tabpy-und2[i] + tabpy-und2[j]bksl-nlbksl-nlassert estpy-undsomme(21) == Truebksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nldef secretpy-undestpy-undsomme(x):bksl-nl i = 0bksl-nl j = taille() - 1bksl-nl while i < j:bksl-nl y = somme(i, j)bksl-nl if y < x:bksl-nl i += 1bksl-nl elif y > x:bksl-nl j -= 1bksl-nl else:bksl-nl return Truebksl-nl return Falsebksl-nlbksl-nlbksl-nl# test 1bksl-nlbksl-nltpy-undsecret = [1, 2, 3, 5, 8, 13, 21]bksl-nlbksl-nldef taille():bksl-nl return len(tpy-undsecret)bksl-nlbksl-nldef somme(i, j):bksl-nl mouchard.append(None)bksl-nl correct = len(mouchard) <= taille()bksl-nl assert correct, "Il faut utiliser `somme` moins souvent"bksl-nl assert 0 <= i < j < taille()bksl-nl return tpy-undsecret[i] + tpy-undsecret[j]bksl-nlbksl-nlfor x in range(tpy-undsecret[0], 2py-strtpy-undsecret[-1] + 2):bksl-nl mouchard = []bksl-nl attendu = estpy-undsomme(x)bksl-nl mouchard = []bksl-nl juste = attendu == secretpy-undestpy-undsomme(x)bksl-nl assert juste == True, "Erreur sur un test secret"bksl-nlbksl-nl# test 2bksl-nlbksl-nltpy-undsecret = [11, 12, 13, 15, 18, 23, 31, 44]bksl-nlbksl-nldef taille():bksl-nl return len(tpy-undsecret)bksl-nlbksl-nldef somme(i, j):bksl-nl mouchard.append(None)bksl-nl correct = len(mouchard) <= taille()bksl-nl assert correct, "Il faut utiliser `somme` moins souvent"bksl-nl assert 0 <= i < j < taille()bksl-nl return tpy-undsecret[i] + tpy-undsecret[j]bksl-nlbksl-nlfor x in range(tpy-undsecret[0], 2py-strtpy-undsecret[-1] + 2):bksl-nl mouchard = []bksl-nl attendu = estpy-undsomme(x)bksl-nl mouchard = []bksl-nl juste = attendu == secretpy-undestpy-undsomme(x)bksl-nl assert juste == True, "Erreur sur un test secret"bksl-nlbksl-nldel sommebksl-nlbksl-nl ∞/∞

def estpy-undsomme(x):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl# test 1bksl-nltableaupy-und1 = [3, 4, 6, 9, 13, 18, 19]bksl-nlbksl-nldef taille():bksl-nl return len(tableaupy-und1)bksl-nlbksl-nlnbpy-undtests = 0bksl-nldef somme(i, j):bksl-nl global nbpy-undtestsbksl-nl assert 0 <= i < j < taille(), "Mauvais indices"bksl-nl nbpy-undtests += 1bksl-nl correct = nbpy-undtests <= taille()bksl-nl assert correct, "Il faut utiliser somme moins souvent"bksl-nl return tableaupy-und1[i] + tableaupy-und1[j]bksl-nlbksl-nlassert estpy-undsomme(20) == Falsebksl-nlbksl-nl# test 2bksl-nltabpy-und2 = [3, 5, 7, 8, 9, 12, 16, 19]bksl-nlbksl-nldef taille():bksl-nl return len(tabpy-und2)bksl-nlbksl-nlnbpy-unds = 0bksl-nldef somme(i, j):bksl-nl global nbpy-undsbksl-nl assert 0 <= i < j < taille(), "Mauvais indices"bksl-nl nbpy-unds += 1bksl-nl correct = nbpy-unds <= taille()bksl-nl assert correct, "Il faut utiliser somme moins souvent"bksl-nl return tabpy-und2[i] + tabpy-und2[j]bksl-nlbksl-nlassert estpy-undsomme(21) == Truebksl-nlbksl-nlbksl-nldef estpy-undsomme(x):bksl-nl i = 0bksl-nl j = taille() - 1bksl-nl while i < j:bksl-nl y = somme(i, j)bksl-nl if y < x:bksl-nl i += 1bksl-nl elif y > x:bksl-nl j -= 1bksl-nl else:bksl-nl return Truebksl-nl return Falsebksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl# test 1bksl-nltableaupy-und1 = [3, 4, 6, 9, 13, 18, 19]bksl-nlbksl-nldef taille():bksl-nl return len(tableaupy-und1)bksl-nlbksl-nlnbpy-undtests = 0bksl-nldef somme(i, j):bksl-nl global nbpy-undtestsbksl-nl assert 0 <= i < j < taille(), "Mauvais indices"bksl-nl nbpy-undtests += 1bksl-nl correct = nbpy-undtests <= taille()bksl-nl assert correct, "Il faut utiliser somme moins souvent"bksl-nl return tableaupy-und1[i] + tableaupy-und1[j]bksl-nlbksl-nlassert estpy-undsomme(20) == Falsebksl-nlbksl-nl# test 2bksl-nltabpy-und2 = [3, 5, 7, 8, 9, 12, 16, 19]bksl-nlbksl-nldef taille():bksl-nl return len(tabpy-und2)bksl-nlbksl-nlnbpy-unds = 0bksl-nldef somme(i, j):bksl-nl global nbpy-undsbksl-nl assert 0 <= i < j < taille(), "Mauvais indices"bksl-nl nbpy-unds += 1bksl-nl correct = nbpy-unds <= taille()bksl-nl assert correct, "Il faut utiliser somme moins souvent"bksl-nl return tabpy-und2[i] + tabpy-und2[j]bksl-nlbksl-nlassert estpy-undsomme(21) == Truebksl-nlbksl-nlbksl-nl

A

Z