Calculer la médiane des valeurs stockées dans Vector-c++?
je suis étudiant en programmation, et pour un projet sur lequel je travaille, sur les choses que je dois faire est de calculer la valeur médiane d'un vecteur de valeurs int. Je dois faire ceci en utilisant seulement la fonction de tri des fonctions de membre STL et vectoriel telles que .begin() , .end() , et .size() .
je suis aussi censé assurez-je trouver la médiane si le vecteur a un nombre impair de valeurs ou d'un même nombre de valeurs.
et je suis Coincé , ci-dessous, j'ai inclus ma tentative. Alors où est-ce que je vais mal? J'apprécierais que vous me donniez quelques conseils ou ressources pour aller dans la bonne direction.
Code:
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;
}
Merci!!
6 réponses
vous faites une division supplémentaire et dans l'ensemble ce qui rend un peu plus complexe qu'il n'a besoin d'être. De plus, il n'est pas nécessaire de créer un diviseur lorsque 2 est en fait plus significatif dans le contexte.
double CalcMHWScore(vector<int> scores)
{
size_t size = scores.size();
if (size == 0)
{
return 0; // Undefined, really.
}
else
{
sort(scores.begin(), scores.end());
if (size % 2 == 0)
{
return (scores[size / 2 - 1] + scores[size / 2]) / 2;
}
else
{
return scores[size / 2];
}
}
}
il n'est pas nécessaire de trier complètement le vecteur: std::nth_element peut faire assez de travail pour mettre la médiane dans la bonne position. Voir ma réponse à cette question pour un exemple.
bien sûr, cela n'aide pas si votre professeur interdit d'utiliser le bon outil pour le travail.
ce qui suit est une fonction simple qui retournera la médiane d'un ensemble de valeurs en utilisant des itérateurs d'entrée. Il ne modifiera pas l'ensemble de données original, au prix d'une allocation de mémoire.
// 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];
}
si vous voulez éviter le coût d'allocation d'une copie de l'ensemble de données et que vous êtes prêt à modifier l'ensemble de données sous-jacent, vous pouvez utiliser ceci à la place:
// 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);
}
const int DIVISOR = 2;
ne faites pas ça. Ça rend votre code plus compliqué. Vous avez probablement lu des lignes directrices sur le fait de ne pas utiliser des nombres magiques, mais l'équitabilité vs. l'étrangeté des nombres est une propriété fondamentale, donc l'abstraction de ceci ne fournit aucun avantage mais entrave la lisibilité.
if ((hWScores.size() % DIVISOR) == 0)
{
median = ((hWScores.begin() + hWScores.size()) + (hWScores.begin() + (hWScores.size() + 1))) / DIVISOR);
vous prenez un itérateur à la fin du vecteur, prendre un autre itérateur qui pointe un après la fin du vecteur, en ajoutant les itérateurs ensemble (qui n'est pas un opération logique), puis en divisant l'itérateur résultant (ce qui n'a pas non plus de sens). C'est le cas le plus compliqué; je vais d'abord vous expliquer ce qu'il faut faire pour le vecteur de taille impaire et vous laisser le cas de taille égale comme un exercice.
}
else
{
median = ((hWScores.begin() + hWScores.size()) / DIVISOR)
encore une fois, vous divisez un itérateur. Ce que vous voulez faire est d'incrémenter un itérateur sur le début du vecteur par hWScores.size() / 2 éléments:
median = *(hWScores.begin() + hWScores.size() / 2);
et noter que vous avez à déréférencer itérateurs pour obtenir les valeurs. Ce serait plus simple si vous utilisiez les indices:
median = hWScores[hWScores.size() / 2];
je donne ci-dessous un exemple de programme qui est quelque peu similaire à celui de la réponse de Max S. Pour aider L'OP à faire progresser ses connaissances et sa compréhension, j'ai apporté un certain nombre de changements. J'ai:
a) j'ai changé l'appel par référence const en appel par valeur, puisque sort va vouloir changer l'ordre des éléments dans votre vecteur, (EDIT: je viens de voir que Rob Kennedy a aussi dit cela pendant que je préparais mon post)
b) a remplacé size_t par vecteur plus approprié <int >:: size_type (en fait, un synonyme commode de ce dernier),
c) enregistrées taille/2 pour une variable intermédiaire,
d) jeté une exception si le vecteur est vide, et
e) j'ai également introduit l'opérateur conditionnel (? :).
en fait, toutes ces corrections sont directement issues du Chapitre 4 de "Accelerated C++" par Koenig et 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];
}
Je ne sais pas exactement quelles sont vos restrictions sur l'Utilisateur des fonctions de membre de vector, mais l'accès index avec [] ou at() simplifierait l'accès aux éléments:
median = hWScores.at(hWScores.size() / 2);
vous pouvez aussi travailler avec des itérateurs comme begin() + offset comme vous le faites actuellement, mais vous devez d'abord calculer le déport correct avec size()/2 et ajouter cela à begin() , pas l'inverse. Aussi vous devez déréférencer le résultat itérateur pour accéder à la valeur réelle à ce point:
median = *(hWScores.begin() + hWScores.size()/2)