Mamy dane n liczb. Mamy znaleźć taką liczbę, że suma |s0-x|+|s1-x|+|s2-x|+...+|sn-x| była jak najmniejsza. Np. Dla liczb 2,4,6 ta liczb to 4, a suma to 4 (|2-4|+|4-4|+|6-4|=0). Nie mam pojęcia jak się za to zabrać, a robienie pętli w pętli będzie trwało zbyt długo.
0
0
A nie wystarczy policzyć średniej arytmetycznej z danych wejściowych?
0
A dlaczego to liczba to akurat 4? przy 6 wyszło by ci -6, czyli jeszcze mniej.
1
piotrpo napisał(a):
A nie wystarczy policzyć średniej arytmetycznej z danych wejściowych?
Niestety nie. Dla danych wejściowych 8, 0, 0, 0 średnią artytmetyczną jest 2, ale najlepszym x-em jest 0.
3
Dla nieparzystej liczby próbek rozwiązaniem jest mediana.
Dla parzystej liczby próbek rozwiązań jest wiele, w okolicy mediany.
0
MarekR22 napisał(a):
Dla nieparzystej liczby próbek rozwiązaniem jest mediana.
Dla parzystej liczby próbek rozwiązań jest wiele, w okolicy mediany.
Zakładając, że funkcja jest monotoniczna to tak będzie, kod w Pythonie liczący sumy dla liczb na lewo i na prawo od mediany; zatrzymuje sie gdy suma zacznie rosnąć:
https://gist.github.com/lion137/7263b9c2fe0e12137be8c0104e12b2b1