Forum de mathématiques - Bibm@th.net

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Entretien d'embauche (bis) ...

Bonsoir,

on vient de me communiquer une question posée à un candidat (jeune ingénieur ENSIMAG) lors d'un entretien d'embauche à Paris pour une SSII.

On présente un tableau contenant les n premiers nombres entiers de 1 à n.

Dans le tableau, on a modifié un (et un seul) nombre. La modification consiste à remplacer un nombre par un autre de la liste (par exemple, p à la place de q).

QUESTION

On demande la procédure de lecture du tableau qui permet de trouver le plus rapidement possible les nombres p et q.

Sauriez vous faire ?

goz

Membre

Inscription : 22-02-2010

Messages : 10

Re : Entretien d'embauche (bis) ...

J'ai bien une idée, mais c'est si tordu que je crains bien que si je l'expose lors d'un entretien d'embauche je me fasse éjecter sur le champ...

Donc si je comprends bien on a une liste [tex](a_1,a_2,\ldots a_n)[/tex] dans laquelle on trouve tous les entiers consécutifs de 1 à [tex]n[/tex], si ce n'est que l'entier [tex]q[/tex] n'apparaît pas et que l'entier [tex]p[/tex] apparaît deux fois, et on cherche le moyen le plus rapide de trouver [tex]p[/tex] et [tex]q[/tex].
Je ne sais pas ce qu'on entend par plus rapide et encore moins si ce que je propose est le plus rapide possible, mais j'imagine au moins qu'il faut faire moins d'opérations que la méthode consistant à comparer tous les [tex]a_i[/tex] deux à deux (soit [tex]\frac{n(n-1)}{2}[/tex] comparaisons).

Calculons d'abord [tex]S=\sum_{i=1}^{n}a_i[/tex], alors [tex]S=\left(\sum_{i=1}^{n}i\right)+p-q[/tex], donc [tex]p-q=S-\frac{n(n+1)}{2}[/tex]. En [tex]n[/tex] calculs environ dont essentiellement des additions, on connaît donc [tex]p-q[/tex].

Calculons ensuite [tex]R=\sum_{i=1}^{n}(a_i)^2[/tex] et [tex]R_n=\sum_{i=1}^{n}i^2[/tex]. Il est bien connu que [tex]R_n=\frac{n(n+1)(2n+1)}{6}[/tex]. Et [tex]R=R_n+p^2-q^2[/tex]. Ainsi on connaît [tex]p^2-q^2[/tex] et connaissant déjà [tex]p-q[/tex] on en déduit [tex]p+q[/tex]. Le tout en faisant [tex]n[/tex] multiplications, [tex]2n[/tex] additions et encore quelques autres opérations.

Remarque : le calcul de [tex]R[/tex] est relativement lourd. Voici une idée qui permet de faire moins de calculs, mais seulement quand [tex]p[/tex] et [tex]q[/tex] ont des parités différentes. Peut-être quelqu'un aura-t-il une idée pour des parités identiques ? A moins bien sûr qu'un lecteur ait une idée plus simple et plus efficace que le présent fatras !
Observons évidemment que si on connaît [tex]p-q[/tex], on sait si [tex]p[/tex] et [tex]q[/tex] sont de même parité ou pas.

S'ils sont de parités différentes, on calcule plutôt [tex]T=\sum_{i=1}^{n}p(a_i)a_i[/tex], où [tex]p(m)[/tex] est la parité de [tex]m[/tex], soit 0 ou 1 selon que [tex]m[/tex] soit pair ou non. Soit [tex]T_n=\sum_{i=1}^{n}p(i)i[/tex] : on calcule facilement [tex]T_n[/tex], c'est [tex]\frac{n^2}{4}[/tex] si [tex]n[/tex] est pair et [tex]\frac{(n+1)^2}{4}[/tex] si [tex]n[/tex] est impair.
Et :
- si [tex]p[/tex] est impair et [tex]q[/tex] est pair, alors [tex]T=T_n+p[/tex]
- si [tex]p[/tex] est pair et [tex]q[/tex] est impair, alors [tex]T=T_n-q[/tex]
Il est donc possible de déterminer dans lequel des deux cas on est, et selon le cas on calcule [tex]p[/tex] ou [tex]q[/tex]. Tout cela nécessite les [tex]n[/tex] opérations déjà rencontrées pour déterminer [tex]p-q[/tex], [tex]n[/tex] vérifications (pour voir la parité des [tex]a_i[/tex]) et de l'ordre de [tex]\frac{n}{2}[/tex] additions. De là on trouve [tex]p[/tex] et [tex]q[/tex].

S'ils sont de mêmes parités, cette méthode ne marche pas (le lecteur peut le vérifier).

Dernière modification par goz (24-02-2010 01:28:12)

goz

Membre

Inscription : 22-02-2010

Messages : 10

Re : Entretien d'embauche (bis) ...

Plus sérieusement, il faudrait savoir si ce qu'on cherche c'est une méthode telle que le maximum de comparaisons à faire soit le plus petit possible, ou telle que l'espérance du nombre de comparaisons soit la plus petite possible (le tableau étant supposé aléatoire, [tex]n[/tex] étant fixé).
Par exemple, la méthode suivante me semble assez efficace, surtout si l'ordre des nombres dans le tableau est très aléatoire.
On prend le 1er nombre [tex]a_1[/tex], on le compare à tous les autres et on compte combien de ces autres sont strictement inférieurs à [tex]a_1[/tex].
Si on ne retrouve jamais le même nombre et qu'on retrouve [tex]a_1-1[/tex] nombres qui lui sont inférieurs, c'est soit que [tex]p[/tex] et [tex]q[/tex] sont tous deux strictement inférieurs à [tex]a_1[/tex], soit qu'ils lui sont tous deux strictement supérieurs. Si on en retrouve [tex]a_1-2[/tex] c'est que [tex]q[/tex] est strictement inférieur à [tex]a_1[/tex] et [tex]p[/tex] lui est strictement supérieur. Si on en retrouve [tex]a_1[/tex], c'est le contraire. Aucun autre cas n'est possible. Et si jamais je retrouve une deuxième fois la valeur [tex]a_1[/tex], alors c'est que cette valeur est [tex]p[/tex], quant à [tex]q[/tex] il est strictement inférieur si on trouve [tex]a_1-2[/tex] nombres inférieurs à [tex]a_1[/tex] et il lui est strictement supérieur si on en trouve [tex]a_1-1[/tex]. En continuant le même processus avec [tex]a_2[/tex] puis [tex]a_3[/tex] on a des chances de délimiter assez vite des intervalles possibles et de cerner les deux nombres par une sorte de dichotomie. Je serais incapable de déterminer si cette méthode est d'un point de vue probabiliste plus efficace que de comparer tous les nombres deux à deux, intuitivement je pense tout de même que oui. Mais si par malheur les nombres sont bêtement placés dans l'ordre croissant et que [tex]p=n[/tex] et [tex]q=n-1[/tex], cette méthode nécessitera bien de comparer deux à deux tous les nombres.

Dernière modification par goz (24-02-2010 01:59:42)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Entretien d'embauche (bis) ...

Bonjour,

les nombres sont placés bêtement dans un ordre croissant, et la question est de trouver le nombre minimal de lecture à faire pour trouver p et q.

Au pire, je trouve en  [tex]q\leq n[/tex] lectures ... Peut on faire plus court ?

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Entretien d'embauche (bis) ...

Hello,

je pense que la réponse est [tex]q-1[/tex] opérations.

En effet,  je fais q-1 soustractions consécutives de la forme :

[tex]a_{i+1}-a_i[/tex] qui donnent [tex]p-2[/tex] fois le nombre + 1

et une fois le nombre [tex]r=p-a_{i}[/tex] différent de + 1.

J'en déduis [tex]q=a_i+1\;et\; p=a_{q}[/tex].

C'est bon ?

gatha de La Ciotat

Invité

Re : Entretien d'embauche (bis) ...

Bonjour à tous,
les nombres constituant la série sont-ils aléatoires, ou consécutifs, façon n, n+1, n+2 ...
auquel cas il suffit d'appliquer la formule de Freddy, S= n(n+1)/2

goz

Membre

Inscription : 22-02-2010

Messages : 10

Re : Entretien d'embauche (bis) ...

En fait j'ai bien peur qu'on ne sache pas trop quelle est la question...
Si les nombres sont dans l'ordre et qu'on dispose des numéros des cases dans lesquels il se trouve, il suffit en effet de lire les nombres l'un après l'autre et quand un nombre ne correspond pas au numéro de sa case c'est que le numéro de la case est q est le nombre qui est répété est le contenu de la case.
Effectivement la deuxième réponse de freddy permet d'éviter de devoir disposer des numéros des cases : dès qu'on repère un [tex]a_{i+1}-a_i[/tex], on sait que [tex]q=a_i + 1\; (=i+1[/tex])et que [tex]p=a_q=a_{i+1}[/tex]. Mais il faut quand même lire [tex]q[/tex] nombres.
Mais ce qui me gêne surtout c'est que le nombre maximal de lectures dépend de [tex]q[/tex]. Parce que si la personne qui fait l'opération choisit [tex]q=100[/tex], la méthode de Freddy conduit à lire tous les nombres ! Donc je ne vois pas ce qu'on gagne. Et en plus dans ce cas, la méthode qui consiste à prendre les nombres à partir du centième sera beaucoup plus efficace !!! Une lecture suffira ! Donc en quoi être certain de trouver [tex]q<[/tex] lectures est-il le plus intéressant ? De manière générale si la méthode consiste à lire les nombres et à les comparer au numéro de leur case, alors quel que soit l'ordre dans lequel on lit les nombres il sera toujours possible que par malchance on ne trouve [tex]p[/tex] et [tex]q[/tex]  qu'à la fin, tout comme il est possible qu'on les trouve au début. D'où cette question que je posais, est-ce qu'on cherche à minimiser le maximum de lectures que requiert la méthode, ou à prendre un point de vue probabiliste ? Dans le premier cas, je ne vois pas comment s'en sortir à coup sûr en étant certain de ne pas devoir lire tous les nombres. Et si on prend le point de vue probabiliste et qu'on considère que les nombres [tex]p[/tex] et [tex]q[/tex]  sont choisis aléatoirement, alors j'ai l'impression que toutes les méthodes consistant à lire les nombres et à les comparer au numéro de la case prennent en moyenne le même nombre de lectures, à savoir 50.
C'est pour cela que j'avais considéré comme sous-entendu d'une part que les nombres étaient dans un ordre arbitraire et que d'autre part on ne pouvait pas garder mémoire de la liste des nombres déjà lus.