Bonjour,
J'ai lu le corrigé de l'exercice 5, et je me demandais s'il était possible que quelqu'un qui ait utilisé les méthodes alternatives mentionées mais non détaillées (FFT et/ou (je ne suis pas sûr duquel ?) arbre binaire) pourrait expliquer à peu près comment il/elle a fait ? Je suis curieux de savoir car je ne vois pas du tout comment cela s'applique à ce problème.
Merci !
J'avais utilisé des arbres AVL pour cet exercice pour construire les tableaux g et h dans l'ordre. Il s'agit d'arbres binaires de recherches améliorés qui permettent de trouver l'élément qui est juste au dessous ou juste au dessus d'un autre en temps logarithmique avec un ajout en temps logarithmique.
Je sais que c'est possible de ne pas faire le prétraitement avec g et h en stockant pour chaque étape les résultats dans un arbre binaire (mais je n'ai pas codé cette solution).
Prologin
2025