Calcolo mediano dei valori memorizzati in Vector - C++?

Question

Sono uno studente di programmazione e per un progetto su cui sto lavorando, le cose che devo fare è calcolare il valore mediano di un vettore di valori int. Devo farlo utilizzando solo la funzione di ordinamento da STL e funzioni membro vettoriali come , .end() e .size().

Inoltre, dovrei assicurarmi di trovare la mediana se il vettore ha un numero dispari di valori o un numero pari di valori.

E io sono bloccato, di seguito ho incluso il mio tentativo. Quindi dove sto andando male? Apprezzerei se saresti disposto a darmi alcuni suggerimenti o risorse per andare nella giusta direzione.

Codice:

int CalcMHWScore(const vector<int>& hWScores) 
{ 
    const int DIVISOR = 2; 
    double median; 
    sort(hWScores.begin(), hWScores.end()); 
    if ((hWScores.size() % DIVISOR) == 0) 
    { 
     median = ((hWScores.begin() + hWScores.size()) + (hWScores.begin() + (hWScores.size() + 1)))/DIVISOR); 
    } 
    else 
    { 
     median = ((hWScores.begin() + hWScores.size())/DIVISOR) 
    } 

    return median; 
} 

Grazie !!

Answer 1

Stai facendo una divisione in più e nel complesso rendendola un po 'più complessa di quanto dovrebbe essere. Inoltre, non è necessario creare un DIVISOR quando 2 è effettivamente più significativo nel contesto.

double CalcMHWScore(vector<int> scores) 
{ 
    size_t size = scores.size(); 

    if (size == 0) 
    { 
    return 0; // Undefined, really. 
    } 
    else if (size == 1) 
    { 
    return scores[0]; 
    } 
    else 
    { 
    sort(scores.begin(), scores.end()); 
    if (size % 2 == 0) 
    { 
     return (scores[size/2 - 1] + scores[size/2])/2; 
    } 
    else 
    { 
     return scores[size/2]; 
    } 
    } 
} 

Answer 2

const int DIVISOR = 2; 

non fare questo. Rende solo il tuo codice più complicato. Probabilmente hai letto le linee guida sul non uso dei numeri magici, ma l'uniformità rispetto alla stranezza dei numeri è una proprietà fondamentale, quindi l'astrazione non offre alcun vantaggio, ma ostacola la leggibilità.

if ((hWScores.size() % DIVISOR) == 0) 
{ 
    median = ((hWScores.begin() + hWScores.size()) + (hWScores.begin() + (hWScores.size() + 1)))/DIVISOR); 

Stai prendendo un iteratore fino alla fine del vettore, prendendo un altro iteratore che punta uno oltre la fine del vettore, aggiungendo i iteratori insieme (che non è un'operazione che ha un senso), e quindi dividendo l'iteratore risultante (che inoltre non ha senso). Questo è il caso più complicato; Spiegherò prima cosa fare per il vettore di dimensioni ridotte e lascerò il caso uniforme come un esercizio per te.

} 
else 
{ 
    median = ((hWScores.begin() + hWScores.size())/DIVISOR) 

Ancora una volta, si sta dividendo un iteratore. Quello che invece vuole fare è quello di incrementare un iteratore all'inizio del vettore per hWScores.size()/2 elementi:

median = *(hWScores.begin() + hWScores.size()/2); 

E notare che si deve dereferenziare iteratori per ottenere valori di fuori di essi. Sarebbe più semplice se si è utilizzato indici:

median = hWScores[hWScores.size()/2]; 

Answer 3

io non sono esattamente sicuro che cosa il vostro restrizioni alla all'utente di funzioni membro di vettore sono, ma l'accesso indice con [] o at() vorrei fare accedere agli elementi più semplici:

median = hWScores.at(hWScores.size()/2); 

si può anche lavorare con iteratori come begin() + offset come si sta facendo, ma poi è necessario calcolare prima l'offset corretto con size()/2 e aggiungere che a begin(), non il contrario.Inoltre è necessario dereference l'iteratore risultante per accedere al valore effettivo a quel punto:

median = *(hWScores.begin() + hWScores.size()/2) 

Answer 4

mi danno seguito un programma di esempio che è in qualche modo simile a quello in risposta di Max S.. Per aiutare l'OP a far progredire la sua conoscenza e comprensione, ho apportato una serie di cambiamenti. Ho:

a) ha cambiato la chiamata con riferimento const a chiamata per valore, poiché l'ordinamento sta per voler cambiare l'ordine degli elementi nel vettore, (EDIT: Ho appena visto che anche Rob Kennedy ha detto questo stavo preparando il mio post)

b) sostituito size_t con il più appropriato vettore <int> :: size_type (in realtà, un comodo sinonimo di quest'ultimo),

c) salvato dimensioni/2 ad una variabile intermedia,

d) generata un'eccezione se il vettore è vuoto e

e) Ho anche introdotto l'operatore condizionale (? :).

In realtà, tutte queste correzioni sono direttamente dal capitolo 4 di "Accelerated C++" di Koenig e Moo.

double median(vector<int> vec) 
{ 
     typedef vector<int>::size_type vec_sz; 

     vec_sz size = vec.size(); 
     if (size == 0) 
       throw domain_error("median of an empty vector"); 

     sort(vec.begin(), vec.end()); 

     vec_sz mid = size/2; 

     return size % 2 == 0 ? (vec[mid] + vec[mid-1])/2 : vec[mid]; 
} 

Answer 5

Non c'è bisogno di ordinare completamente il vettore: std::nth_element può fare abbastanza lavoro per mettere la mediana nella posizione corretta. Vedere la mia risposta a this question per un esempio.

Ovviamente, questo non aiuta se il tuo insegnante vieta di usare lo strumento giusto per il lavoro.

Answer 6

Quanto segue è una semplice funzione che restituirà la mediana di un insieme di valori utilizzando gli iteratori di input. Non modificherà il set di dati originale, a costo di allocare memoria.

// Get the median of an unordered set of numbers of arbitrary 
// type without modifying the underlying dataset. 
template <typename It> 
auto Median(It begin, It end) 
{ 
    using T = typename std::iterator_traits<It>::value_type; 
    std::vector<T> data(begin, end); 
    std::nth_element(data.begin(), data.begin() + data.size()/2, data.end()); 
    return data[data.size()/2]; 
} 

Se si vuole evitare il costo di destinare una copia del set di dati e sono disposti a modificare il set di dati di base, è possibile utilizzare questo invece:

// Get the median of an unordered set of numbers of arbitrary 
// type (this will modify the underlying dataset). 
template <typename It> 
auto Median(It begin, It end) 
{ 
    const auto size = std::distance(begin, end) 
    std::nth_element(begin, begin + size/2, end); 
    return *std::next(begin, size/2); 
}