Aide Tours Animalières - Régionales 2019

Bonsoir,

En ces temps de confinement j'ai décidé de me pencher sur des annales de Prologin pour m'occuper. Et ça fait un petit moment que je bloque sur un des exos 5 des régionales de 2019, celui des Tours Animalières.

J'essaie de résoudre le problème de façon récursive, pour ça j'ai modélisé le problème sous forme d'arbre, en me disant que chaque sous arbre a des noeuds de valeur inférieure ou égale à celle de la racine de l'arbre. Et je considère que la racine de tous les arbres possibles est de valeur infinie.

Du coup, j'ai à chaque fois 2 types de choix possibles pour choisir le prochain noeud: Soit je choisis de ne pas prendre l'espèce la plus lourde, auquel cas je me ramène au problème "tours(n, m-1, k)", autrement dit je dénombre le nombre d'arbres qu'on peut former avec une espèce de moins. Soit je choisis de prendre l'espèce la plus lourde , et là j'ai un peu de mal à voir comment continuer proprement ma récursion... J'ai tenté plusieurs "intuition" mais sans succès.

Pour les cas de base, j'ai pris: - Quand m*k < n -> On peut faire 0 tours - Quand n = 1 - > On peut faire m tours - Quand m = 1 (et qu'on est pas dans le 1er cas) -> On peut faire 1 tour - Quand k = 1 (pareil) -> On peut faire m-n parmi m tours

Merci d'avance à la personne qui saura m'apporter une piste, de mémoire j'avais vu quelqu'un résoudre ce problème en 4 lignes, donc je pense que je me complique trop la tâche...

Salut !

Je suis aussi passé par de la récursion, mais je suis bien loin des tests de performances ....

https://pastebin.com/w5b36dvN

Au passage, il existe des balise pour afficher du code ? ^^"

Salut ! Merci beaucoup de ta réponse, effectivement en prenant le problème "en sens inverse" ça marche aussi... Je me suis obstiné à vouloir "déconstruire" les tours.

Pour passer les tests de performances, je me suis dit qu'il fallait "juste" détecter au plus vite les cas où il n'y aura pas de tours possibles pour ne pas faire de calculs inutiles (d'où le m*k < n en condition d'arrêt), mais je sais pas si c'est possible de le faire avec ton approche... Je vais continuer à chercher du coup, merci de m'avoir ouvert une nouvelle perspective ! ^^

Salut ! Il ne s'agit pas d'un exo 5 mais d'un 4 ^^" Du coup, pour ce qui est de la solution, je peux te donner un petit indice :p

Programmation dynamique

Si tu as d'autres questions n'hésite pas ! Yann

Salut, oui autant pour moi je me suis trompé de numéro x) Merci pour l'indice, ça m'a suffi pour trouver une façon d'optimiser le calcul ! Bonne soirée à toi !