Une idée de sujet !

Bonjour à tous !

Je m'adresse ici aux organisateurs du concours. En lisant les questions d'algorithmique, je me suis dit que vous deviez vraiment vous creusez pour trouver des idées différentes tout les ans. C'est pourquoi j'ai voulu vous donner un mini coup de pouce. En effet, j'ai eu une idée d'exercice qui peut être intéressante, mais après, c'est à vous de voir. Le but ici serait que les participants arrivent à programmer une fonction qui utilise la recherche dichotomique ! => c'est vraiment pas difficile (qui n'a jamais fait ça sur sa TI ?! :p), mais ça oblige à réfléchir un minimum.

Pour le sujet, je n'ai pas vraiment une immense imagination, mais voici à quoi est-ce que j'aurais pensé:

Rémi veut épater ses copains et pour cela, ils leurs lance un défi ! Il pari 20€ à celui qui arrive à battre le robot qu'il a programmé au jeu du nombre mystère. Dans ce jeu très simple, le but est de trouver un nombre aléatoire appelé "nombre mystère" dans un intervalle donné (dans l'exercice, on prendra l'intervalle [0;n] avec n un entier naturel supérieur ou égal à 1000). Seuls les indices "plus" (indiquant que le nombre mystère est plus grand que celui que vous avez entré) et "moins" (indiquant que le nombre mystère est plus petit que celui que vous avez entré) sont donnés dans ce jeu. Ce que ses amis ne savent pas, c'est que Rémi est malin et qu'il a fait en sorte que son robot trouve le nombre mystère en le moins de coup possible (sans triche ni chance). Pour cela, il l'a programmé de façon à ce que qu'il divise par deux l'intervalle de recherche. Prenons l'exemple d'un nombre entre 0 et 100. Le robot va d'abord chercher au milieu de cet intervalle, soit 50. Ensuite, le robot indiquera soit "plus", soit "moins" en fonction de la valeur du nombre mystère. Si c'est "plus", le robot dira 75 dans le cas contraire, si c'est moins, il dira 25. Le but de cet exercice est de créer une fonction qui renvoie le nombre de coup qu'a fait le robot pour trouver un nombre mystère quelconque.

Paramètres en entrée:

n: la valeur maximal que peut prendre le nombre mystère, c'est une des borne de l'intervalle de recherche (n'oublions pas que n>=1000)
m: la valeur du nombre mystère

Sortie:

c: le nombre de coups

Exemple 1:

Entrées
1000
750

Sortie
2

Exemple 2:

Entrées
5000
142

Sortie
12

Exemple 3:

Entrée
165789
3215

Sortie
17

Bon, excusez-moi pour mon manque d'imagination et par ma maigre participation... En espérant que ça vous aide un jour !

Longue vie au Prologin !

Salut,

Déjà, cet exercice ne sera pas repris cette année pour des raisons évidentes (les sujets sont déjà faits, et surtout ils sont tenus secrets). Ensuite, la dichotomie a déjà été utilisée dans plusieurs sujets (aussi bien les épreuves écrites que sur la partie entraînement). Mais en général, elle est un peu masquée : on donne un problème, c'est au candidat de réfléchir et de trouver la méthode par lui-même. Ton sujet donne directement l'algorithme, il y a donc juste à implémenter et c'est un peu dommage.