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