06/09/14 18:25
sdbx
Ciao a tutti, ho una retta in cui sono collocati dei punti X1, X2... Xn fissi su di essa. A questo punto mi danno un numero N. Io devo inserire N nuovi punti sulla retta in modo che la somma totale di tutte le distanze fra ciascuna X e il più vicino nuovo punto inserito sia minima.
Con un esempio è più chiaro:
Dati i punti X1=1; X1=3 X2=20 X3=40; collocati su una retta:
-X0---X1-----------------X2--------------------X3------------>
Ora prendiamo a caso N = 3, devo collocare altri 3 punti in modo che la distanza tra i nuovi 3 punti e quello più lontano tra quelli vecchi sia minima, cioè inserisco 3 nuovi punti alle coordinate:
X4=2; X5=X2=20; X6=X3=40 così la distanza tra i nuovi punti e quelli vecchi è la minima.
Se N fosse stata = 1 allora avrei aggiunto un punto X4 = |X3 - X1|/2 = 19.5 così la distanza massima tra il nuovo punto e quello più lontano è 19.5 ed è il minimo che si possa avere.
Se N fosse stato = 2 allora avrei aggiunto due punti X4 = 10.5 e X5 = 30.5 così la distanza massima tra i nuovi punti e quelli più lontani è 10.5 ed è il minimo che si possa avere (credo XD).
Se N fosse stato = 3 (come scritto prima) allora avrei aggiunto 3 punti X4=2; X5=20; X6=40; così la distanza massima tra i nuovi punti e quelli più lontani è 1 ed è il minimo che si possa avere.
Se N fosse stato = 4 allora avrei aggiunto 4 nuovi nunti esattamente sui vecchi punti così la distanza è minima, quindi X4=X0; X5=X1; X6=X2; X7=X3;
Il mio problema è realizzare un algoritmo che mi inserisca i nuovi punti! Conoscete qualche algoritmo "famoso" che svolge questo compito? se no come lo risolvereste? Help!!!! Non ho idea di come fare!!!
Con un esempio è più chiaro:
Dati i punti X1=1; X1=3 X2=20 X3=40; collocati su una retta:
-X0---X1-----------------X2--------------------X3------------>
Ora prendiamo a caso N = 3, devo collocare altri 3 punti in modo che la distanza tra i nuovi 3 punti e quello più lontano tra quelli vecchi sia minima, cioè inserisco 3 nuovi punti alle coordinate:
X4=2; X5=X2=20; X6=X3=40 così la distanza tra i nuovi punti e quelli vecchi è la minima.
Se N fosse stata = 1 allora avrei aggiunto un punto X4 = |X3 - X1|/2 = 19.5 così la distanza massima tra il nuovo punto e quello più lontano è 19.5 ed è il minimo che si possa avere.
Se N fosse stato = 2 allora avrei aggiunto due punti X4 = 10.5 e X5 = 30.5 così la distanza massima tra i nuovi punti e quelli più lontani è 10.5 ed è il minimo che si possa avere (credo XD).
Se N fosse stato = 3 (come scritto prima) allora avrei aggiunto 3 punti X4=2; X5=20; X6=40; così la distanza massima tra i nuovi punti e quelli più lontani è 1 ed è il minimo che si possa avere.
Se N fosse stato = 4 allora avrei aggiunto 4 nuovi nunti esattamente sui vecchi punti così la distanza è minima, quindi X4=X0; X5=X1; X6=X2; X7=X3;
Il mio problema è realizzare un algoritmo che mi inserisca i nuovi punti! Conoscete qualche algoritmo "famoso" che svolge questo compito? se no come lo risolvereste? Help!!!! Non ho idea di come fare!!!
Ultima modifica effettuata da sdbx 06/09/14 18:28
aaa