La communication des acacias⚓︎

Mécanisme de synchronicité

Une des observations les plus anciennes a été faite sur les girafes par Wouter Van Hoven. Il a étudié pendant 2 ans le comportement des girafes dans un parc national en Afrique du Sud. Les girafes ingurgitent environ 80 kg de feuilles par jour. Pourtant, lorsqu'elles arrivent sur un acacia, elles ne restent que quelques minutes, broutent que quelques feuilles puis vont vers un autre arbre. L'arbre a réagi à la présence de la girafe en secrétant des tanins. Ce sont des molécules amères et toxiques pour les girafes. Mais en même temps, l'acacia va émettre de l'éthylène, qui est un gaz qui va se déplacer dans l'air et informer les autres arbres qu'un prédateur est là. Que vont faire les autres arbres ? Ils vont augmenter de manière préventive leur teneur en tanin et se préparer à l'arrivée des girafes.

On vous donne une liste de quantités de feuilles que pourrait manger une girafe sur un arbre à un indice donné le long d'une ligne d'acacias. La seule contrainte, c'est que la girafe ne peut pas manger les feuilles sur deux arbres consécutifs, mais souhaite en manger le plus possible. Écrire une fonction qui indique quelle quantité totale la girafe peut ingurgiter.

Exemples

🐍 Console Python

>>> feuilles = [4, 25, 20, 8, 17]
>>> max_manger(feuilles)
42

La girafe peut manger \(25+17 = 42\) feuilles au maximum.

Prendre \(4+20+17\) n'en donne que \(41\).

🐍 Console Python

>>> feuilles = [4, 6, 5, 7, 4]
>>> max_manger(feuilles)
13

La girafe peut manger \(4+5+4=13\) ou bien \(6+7=13\) feuilles au maximum.

###

# testsbksl-nlbksl-nlfeuilles = [4, 25, 20, 8, 17]bksl-nlassert maxpy-undmanger(feuilles) == 42bksl-nlbksl-nlbksl-nlfeuilles = [4, 6, 5, 7, 4]bksl-nlassert maxpy-undmanger(feuilles) == 13bksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert maxpy-undmanger([9]) == 9bksl-nlassert maxpy-undmanger([]) == 0bksl-nlbksl-nlfeuilles = [0, 1] py-str 100bksl-nlassert maxpy-undmanger(feuilles) == 100bksl-nlfeuilles = [2, 1] py-str 100bksl-nlassert maxpy-undmanger(feuilles) == 200bksl-nlbksl-nlfeuilles = [1, 2, 1] py-str 20bksl-nlassert maxpy-undmanger(feuilles) == 40bksl-nlbksl-nlfeuilles = [1, 2, 3] py-str 20bksl-nlassert maxpy-undmanger(feuilles) == 61bksl-nlbksl-nlfeuilles = [4, 25, 20, 8, 17, 1, 30, 2]bksl-nlassert maxpy-undmanger(feuilles) == 72bksl-nlbksl-nlfeuilles = []bksl-nltotal = 0bksl-nlfor i in range(13):bksl-nl total += 2 py-str 10bksl-nl if pow(7, i, 17) % 3:bksl-nl feuilles.extend([0, 0, 10, 4, 5, 10, 3])bksl-nl else:bksl-nl feuilles.extend([0, 0, 10, 2, 7, 2, 3])bksl-nlassert maxpy-undmanger(feuilles) == totalbksl-nlbksl-nl ∞/∞

def maxpy-undmanger(feuilles):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlfeuilles = [4, 25, 20, 8, 17]bksl-nlassert maxpy-undmanger(feuilles) == 42bksl-nlbksl-nlbksl-nlfeuilles = [4, 6, 5, 7, 4]bksl-nlassert maxpy-undmanger(feuilles) == 13bksl-nlbksl-nldef maxpy-undmanger(feuilles):bksl-nl n = len(feuilles)bksl-nl if n == 0:bksl-nl return 0bksl-nl maxipy-undsanspy-undi, maxipy-undavecpy-undi = 0, feuilles[0]bksl-nl for i in range(1, n):bksl-nl maxipy-undsanspy-undi, maxipy-undavecpy-undi = (bksl-nl max(maxipy-undavecpy-undi, maxipy-undsanspy-undi),bksl-nl feuilles[i] + maxipy-undsanspy-undi,bksl-nl )bksl-nl return max(maxipy-undavecpy-undi, maxipy-undsanspy-undi)bksl-nlbksl-nl

A

Z

Indice 1

Se poser la question : « Combien peut-elle avoir mangé au maximum à la fin ? »

C'est aussi se poser la question : « A-t-elle mangé sur le dernier arbre ? »

En effet, si on veut envisager une récursion, la question se pose... et donc récursivement aussi...

Il faut donc envisager de savoir combien la girafe a pu manger au maximum en arrivant à un arbre i :

sans avoir mangé sur le précédent, auquel cas elle pourra manger ici, en i
en ayant mangé au précédent, auquel cas elle ne pourra manger ici, en i

Indice 2

On utilisera deux variables :

maxi_sans_i : la quantité maximale que la girafe peut manger sans pouvoir manger à la position i,
maxi_avec_i : : la quantité maximale que la girafe peut manger avec la position i dévorée.

Indice 3

On gèrera les cas avec peu d'arbres. Aucun arbre ; aucune feuille.
On initialisera correctement les variables.
On mettra en place avec prudence la récursion qui permet de progresser jusqu'au bout de la file d'arbres.