Tous les problèmes sont identifiés par un niveau de difficulté :
Très facile
Facile
Moyen
Difficile
Très difficile
Variable
Â
Â
Â
Â
Â
Les figures et les graphes ont été réalisés grâce au logiciel Declic.
G2905. Deux tris au comparateur |
G2. Combinatoire - DĂ©nombrements |
On dispose d'une liste L de n = 2k (k ≥ 1) entiers naturels distincts que l’on cherche à classer dans l’ordre croissant avec deux programmes informatiques :
- le premier programme consiste à classer les deux premiers termes de L et à mettre le plus petit en tête, puis à comparer le troisième terme à ces deux termes en partant du plus petit pour obtenir une liste de trois termes classés dans l’ordre croissant. On poursuit en insérant à sa bonne place le i-ème terme après l’avoir comparé à tous les termes pris dans l’ordre croissant de la liste de i – 1 termes précédemment obtenue et ainsi de suite jusqu’au dernier terme. - le deuxième programme est fondé sur la partition d’une liste donnée en deux sous-listes si possible de même cardinal qui sont triées séparément avant d’être fusionnées. Comme par hypothèse n = 2k, on répète le processus de partition de L avec successivement des sous-listes de tailles 2k-1, 2k-2 ,2k-3..etc..,1 appelées ensuite à être fusionnées tout en étant triées, une par une, deux par deux, puis quatre par quatre etc...jusqu’à la reconstitution de la taille de la liste d’origine. On admet que le temps d’exécution des programmes est proportionnel au nombre maximum de comparaisons élémentaires effectuées dans chacun d’eux. Le premier programme demande 2 minutes 50 secondes pour trier L. Le deuxième programme requiert 3 secondes seulement. Donner la valeur de k en cochant la bonne case ci-après : A : 6 B : 8 C : 10 D : 12 E :16 |