Les exercices python à connaître

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 :
>>> 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.


>>> 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.

Votre solution doit pouvoir être efficace même avec de grands tableaux. Il est demandé d'utiliser une programmation dynamique.

Vous trouverez des indices pourvous aider sous la console Python

source : https://codex.forge.apps.education.fr

Indice 1 :
On peut 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 boucle qui permet de progresser jusqu'au bout de la file d'arbres.