Discussion :

[neoncyber]

Bonjour,
Il y a quelque temps j'ai fais un entretient pour un poste de developpeur C#.
J'ai complètement loupé l'entretient, je voudrai savoir quel est la solution du problème qu'on ma posé, et comment j'aurai pu réussir cet entretient, j'ai cherché sur internet et sur tous les algo je n'ai toujours pas trouvé la solution, sachant que j'ai une experience en developpement Web, je trouve que cet question étais vraiment abusé.

Exercice:
Nous voulons relier toute les maison d'un quartier à un cable internet.
Le but est de trouver sur une grille avec axe x/y l'emplacement du cable horizontal (est/ouest), qui permettra d'utiliser le moins de cable possible suivant une liste de maison position sur cette grille. Donc il faut trouver le y optimal (vu que le x sera toujours une ligne droite d'est/ouest)
Par exemple, trois maison,
x: 1 y: 4
x: 10 y: 1
x: 15: y: 7

Les maison seront relié sur le cable horizontal par des cable verticale (il faut donc calculer leur disance par rapport au cable horizontal pour calculer la longueur total necessaire et donc optimal recherché)

[anapurna]

salut

sans trop réfléchir j'aurais dis la moyenne de tes 3 valeur en Y
ce qui nous donne ... a toi de calculer mais tu vas t’apercevoir que l'une des maisons est sur le même axe

[neoncyber]

C'est ce que j'ai dis pendant l'entretien le mec semblait pas convaincu... donc je ne sais pas si c'étais ca la bonne réponse.
Quand j'ai commencé a implémenté l'algo, j'ai commencé a m'enbrouiller avec un int[][], alors qu'en faite les x on en a pas besoin...
Le mec ma dis tu sais pas manipuler un clavier byebye....
Abusé...

[anapurna]

salut

il y a une différence entre manipuler un clavier et déterminer un algo
il chercher surement une secrétaire sachant taper 300 mots a la minute

[Flodelarab]

Bonjour

Le mot adéquat n'est pas "moyenne" mais "médiane".

La médiane est la valeur qui coupe un ensemble en deux ensembles de cardinaux égaux.
Évidemment, dans une gaussienne, la moyenne est la médiane. Du coup, tout le monde confond.

Si tu prends 2 points, alors le y idéal est entre les deux.
Et tu notes que tous les y (qui séparent les points) donnent la même longueur. (Les y ne séparant pas les points ne minimisent pas la distance)
Donc peu importe la position du y.

Si tu prends 1 seul point, le y idéal est forcément le y de ton point.

En supprimant les extrémités, 2 points par 2 points, tu arriveras à la valeur gagnante.

Et on appelle celle-ci la médiane.

[neoncyber]

Et tu notes que tous les y (qui séparent les points) donnent la même longueur. (Les y ne séparant pas les points ne minimisent pas la distance)
Donc peu importe la position du y.

Si tu prends 1 seul point, le y idéal est forcément le y de ton point.

En supprimant les extrémités, 2 points par 2 points, tu arriveras à la valeur gagnante.

Je ne suis pas sur de comprendre, tu prend les deux point les plus éloigné et tu calcule leur millieu (ce milieu devient un nouveau point) et tu fait ca jusqu'a qu'il reste un seul point ?

[Flodelarab]

Le milieu, c'est la moyenne. N'est-ce pas ?
La moyenne n'est pas la solution de ce problème classique.
Donc oublie le milieu.

Prenons ton exemple.
Les x sont sans importance. La distance du plus à gauche au plus à droite est une valeur fixe.
On trie les y.
On obtient 1;4;7.
Entre 1 et 7, ton câble peut avoir les y suivants:

• 1 distance 0+6=6
• 2 distance 1+5=6
• 3 distance 2+4=6
• 4 distance 3+3=6
• 5 distance 4+2=6
• 6 distance 5+1=6
• 7 distance 6+0=6

Quelque soit le y, la longueur de câble nécessaire est la même.
Dans ta liste de y, tu peux donc supprimer les extrémités. N'est-ce pas ?
Si tu tombes sur 0 points, tu peux prendre n'importe quel valeur du dernier intervalle considéré.
Si tu tombes sur 1 point, le y est la valeur du y de ton point.

Ici, la médiane est 4.

Solution : 4

[wiwaxia]

Bonjour,

La solution correspond au minimum de la somme:
S(y) = Abs(y - 1) + Abs(y - 4) + Abs(y - 7) .

Le procédé d'élimination des extrêmes s'impose dès que les points deviennent nombreux.

... Le mec m'a dit tu sais pas manipuler un clavier byebye ...

Un entretien délibérément stressant en dit moins sur les capacités du candidat que sur la psychologie de l'examinateur (on devrait plutôt dire dans ce cas: du petit chef ...) .

[tbc92]

On va commencer par un exemple, pour se faire une idée de la réponse.

Si les y valent 2, 3, 4 et 19, la moyenne vaut 7. Si on place la box à y=7, on obtient une certaine distance , mais on voit très vite qu'en déplaçant un peu la box vers 6.5 ou 6, on améliore la note. Donc effectivement, la moyenne n'est pas la bonne position. Et en continuant avec cet exemple, on voit qu'en déplaçant notre box jusqu'au point y=4, on améliore la note. Quand on déplace la box quelque part entre 3 et 4 , on a 2 câbles qu'il faut allonger un peu, et on a 2 câbles qu'on peut un peu raccourcir. Et en fait , on peut mettre notre box n'importe où entre le point 3 et 4, la somme des 4 distances ne bouge pas.

Et on retombe sur cette médiane : Si on a un nombre impair de maisons, il faut placer la box au niveau de la maison du milieu.
Et si on a un nombre pair de maisons, on peut choisir n'importe quel y entre les 2 maisons du milieu.

Si on regarde le problème sous l'aspect mathématique, on va dire que le minimum est un point où la dérivée est nulle ... A partir d'un point donné C, s'il y a n maisons à droite de C, et p maisons à gauche de C, la dérivée vaut p-n. Et donc A partir d'un point donné, si p est différent de n, on va forcément pouvoir améliorer le résultat en déplaçant la box, soit vers la droite si n est plus grand que p, soit vers la gauche dans le cas contraire. Les points où on ne gagne rien en déplaçant la boite vers la droite ou vers la gauche, ce sont les points où p=n. ( notre médiane)

[wiwaxia]

... Si on regarde le problème sous l'aspect mathématique, on va dire que le minimum est un point où la dérivée est nulle ...

En chacun des (N) points (x₀, y_k) la fonction
S(y) = S_k=1^k=NAbs(y - y_k)
n'est pas dérivable, parce que son graphe y présente une discontinuité de pente; on a en effet pour chaque terme
T_k = Abs(y - y_k) = y - y_k pour y > y_k
T_k = Abs(y - y_k) = y_k - y pour y < y_k
de sorte que sa dérivée T'_k vaut (+1) ou (-1) sur le domaine correspondant.

C'est justement cette propriété qui permet l'élimination progressive des termes extrêmes (le plus grand et le plus petit) pour parvenir à Med(y₁, y₂ ... y_N).