Tính toán giá trị trung bình được lưu trữ trong Vector - C++?

Question

Tôi là một sinh viên lập trình và đối với một dự án tôi đang làm việc, về những điều tôi phải làm là tính toán giá trị trung bình của một vectơ các giá trị int. Tôi chỉ làm điều này bằng cách sử dụng chức năng sắp xếp từ các hàm thành viên STL và vector chẳng hạn như .begin(), .end() và .size().

Tôi cũng phải đảm bảo rằng tôi tìm thấy trung vị cho dù véc-tơ có số lượng giá trị lẻ hoặc số lượng giá trị chẵn.

Và tôi là Bị kẹt, bên dưới tôi đã bao gồm nỗ lực của mình. Vì vậy, tôi đang đi sai? Tôi sẽ đánh giá cao nếu bạn sẽ sẵn sàng để cho tôi một số gợi ý hoặc nguồn lực để có được đi đúng hướng.

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; 
} 

Cảm ơn !!

Answer 1

Bạn đang làm một bộ phận phụ và tổng thể làm cho nó phức tạp hơn một chút so với mức cần thiết. Ngoài ra, không cần phải tạo một DIVISOR khi 2 thực sự có ý nghĩa hơn trong ngữ cảnh.

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; 

Đừng làm điều này. Nó chỉ làm cho mã của bạn phức tạp hơn. Bạn đã có thể đọc hướng dẫn về việc không sử dụng số ma thuật, nhưng tính đồng đều so với kỳ quặc của số là tài sản cơ bản, vì vậy việc trừu tượng hóa điều này không mang lại lợi ích nào nhưng có thể dễ đọc.

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

Bạn đang dùng trình vòng lặp đến cuối vectơ, lấy một trình lặp khác trỏ một điểm đến cuối vectơ, thêm các trình vòng lặp lại với nhau (không phải là thao tác có ý nghĩa) và sau đó chia bộ lặp kết quả (cũng không có ý nghĩa). Đây là trường hợp phức tạp hơn; Tôi sẽ giải thích việc cần làm cho vectơ có kích thước lẻ trước và để trường hợp có kích thước bằng nhau làm bài tập cho bạn.

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

Một lần nữa, bạn đang chia một trình lặp. Những gì bạn thay vì muốn làm là để tăng một iterator đến đầu của vector bởi hWScores.size()/2 yếu tố:

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

Và lưu ý rằng bạn phải dereference lặp để có được giá trị ra khỏi chúng. Nó muốn được đơn giản hơn nếu bạn sử dụng các chỉ số:

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

Answer 3

Tôi không chắc chắn chính xác những gì giới hạn của bạn về người sử dụng các chức năng thành viên của vector là, nhưng truy cập chỉ mục với [] hoặc at() sẽ làm cho việc tiếp cận các yếu tố đơn giản hơn:

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

bạn cũng có thể làm việc với lặp như begin() + offset như bạn đang làm, nhưng sau đó bạn cần phải đầu tiên tính toán chính xác bù đắp với size()/2 và thêm rằng để begin(), không phải là cách khác xung quanh.Ngoài ra, bạn cần phải dereference iterator kết quả để truy cập vào giá trị thực tế tại thời điểm đó:

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

Answer 4

Tôi đưa ra một chương trình mẫu tương tự như chương trình trong phản hồi của Max S. Để giúp OP nâng cao kiến ​​thức và hiểu biết của mình, tôi đã thực hiện một số thay đổi. Tôi có:

a) thay đổi cuộc gọi bằng tham chiếu const thành gọi theo giá trị, vì sắp xếp sẽ muốn thay đổi thứ tự của các phần tử trong vectơ của bạn, (EDIT: Tôi vừa thấy Rob Kennedy cũng nói điều này trong khi tôi đang chuẩn bị bài của tôi)

b) thay thế size_t với vector thích hợp hơn <int> :: size_type (trên thực tế, một từ đồng nghĩa thuận tiện sau này),

c) lưu kích thước/2 đến một biến trung gian,

d) đã ném ngoại lệ nếu véc tơ trống và

e) Tôi cũng đã giới thiệu toán tử điều kiện (? :).

Thực ra, tất cả các sửa đổi này đều nằm ngay trong Chương 4 của "Tăng tốc C++" của Koenig và 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

Không cần phải sắp xếp hoàn toàn véc tơ: std::nth_element có thể làm đủ công việc để đặt vị trí trung bình vào đúng vị trí. Xem câu trả lời của tôi cho this question để biết ví dụ.

Tất nhiên, điều đó không có tác dụng nếu giáo viên của bạn cấm sử dụng đúng công cụ cho công việc.

Answer 6

Sau đây là một hàm đơn giản sẽ trả về giá trị trung bình của một tập hợp các giá trị bằng cách sử dụng trình lặp đầu vào. Nó sẽ không sửa đổi tập dữ liệu gốc, với chi phí cấp phát bộ nhớ.

// 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]; 
} 

Nếu bạn muốn tránh chi phí phân bổ một bản sao của dữ liệu và sẵn sàng để thay đổi dữ liệu cơ bản, bạn có thể sử dụng thay vì:

// 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); 
}