Algorytm trybu obliczeniowego

Question

Próbuję opracować algorytm w postaci funkcji, która akceptuje dwa parametry, tablicę i rozmiar tablicy. Chcę, aby zwrócił tryb tablicy i jeśli istnieje wiele trybów, zwróć średnią. Moją strategią było wziąć tablicę i najpierw ją posortować. Następnie policz wszystkie wystąpienia liczby. podczas gdy liczba ta występuje, dodaj jedną do liczenia i zapisz ją w tablicy m. Więc m trzyma wszystkie liczby, a inna tablica q zatrzymuje ostatnią wartość, którą porównujemy.

Na przykład: moja lista jest {1, 1, 1, 1, 2, 2, 2} wtedy bym m[0] = 4 q[0] = 1 and then m[1] = 3 and q[1] = 2.

więc tryb q[0] = 1;

niestety nie miałem do tej pory sukces. mając nadzieję, że ktoś może pomóc.

float mode(int x[],int n) 
{ 
    //Copy array and sort it 
    int y[n], temp, k = 0, counter = 0, m[n], q[n]; 

    for(int i = 0; i < n; i++) 
     y[i] = x[i]; 

    for(int pass = 0; pass < n - 1; pass++) 
     for(int pos = 0; pos < n; pos++) 
      if(y[pass] > y[pos]) { 
       temp = y[pass]; 
       y[pass] = y[pos]; 
       y[pos] = temp; 
      } 

    for(int i = 0; i < n;){ 
     for(int j = 0; j < n; j++){ 
      while(y[i] == y[j]) { 
       counter++; 
       i++; 
      } 
     } 
     m[k] = counter; 
     q[k] = y[i]; 
     i--; //i should be 1 less since it is referring to an array subscript 
     k++; 
     counter = 0; 
    } 

} 

Answer 1

Nawet jeśli masz już kilka dobrych odpowiedzi, zdecydowałem się opublikować kolejny. Nie jestem pewien, czy to naprawdę dodaje wiele nowości, ale nie jestem wcale pewien, czy to też nie jest. Jeśli nic więcej, jestem pewien, że używa bardziej standardowych nagłówków niż jakakolwiek inna odpowiedź. :-)

#include <vector> 
#include <algorithm> 
#include <unordered_map> 
#include <map> 
#include <iostream> 
#include <utility> 
#include <functional> 
#include <numeric> 

int main() { 
    std::vector<int> inputs{ 1, 1, 1, 1, 2, 2, 2 }; 

    std::unordered_map<int, size_t> counts; 
    for (int i : inputs) 
     ++counts[i]; 

    std::multimap<size_t, int, std::greater<size_t> > inv; 
    for (auto p : counts) 
     inv.insert(std::make_pair(p.second, p.first)); 

    auto e = inv.upper_bound(inv.begin()->first); 

    double sum = std::accumulate(inv.begin(), 
     e, 
     0.0, 
     [](double a, std::pair<size_t, int> const &b) {return a + b.second; }); 

    std::cout << sum/std::distance(inv.begin(), e); 
} 

porównaniu do @ odpowiedź Dietmar, powinno to być szybciej, jeśli masz dużo powtórzeń w liczbach, ale jego prawdopodobnie będzie szybciej, jeśli numery są głównie wyjątkowy.

Answer 2

Oto działająca wersja Twojego kodu. m przechowuje wartości w tablicy, a q przechowuje ich wartości. Na koniec przechodzi przez wszystkie wartości, aby uzyskać maksymalną liczbę, sumę trybów i liczbę różnych trybów.

float mode(int x[],int n) 
{ 
    //Copy array and sort it 
    int y[n], temp, j = 0, k = 0, m[n], q[n]; 

    for(int i = 0; i < n; i++) 
     y[i] = x[i]; 

    for(int pass = 0; pass < n - 1; pass++) 
     for(int pos = 0; pos < n; pos++) 
      if(y[pass] > y[pos]) { 
       temp = y[pass]; 
       y[pass] = y[pos]; 
       y[pos] = temp; 
      } 

    for(int i = 0; i < n;){ 
     j = i; 
     while (y[j] == y[i]) { 
      j++; 
     } 
     m[k] = y[i]; 
     q[k] = j - i; 
     k++; 
     i = j; 
    } 

    int max = 0; 
    int modes_count = 0; 
    int modes_sum = 0; 
    for (int i=0; i < k; i++) { 
     if (q[i] > max) { 
      max = q[i]; 
      modes_count = 1; 
      modes_sum = m[i]; 
     } else if (q[i] == max) { 
      modes_count += 1; 
      modes_sum += m[i]; 
     } 
    } 

    return modes_sum/modes_count; 
} 

Answer 3

Jeśli po prostu chcesz policzyć liczbę wystąpień to proponuję użyć std::map lub std::unordered_map.

Jeśli odwzorowujesz licznik dla każdej odrębnej wartości, łatwo jest liczyć liczbę wystąpień przy użyciu std::map, ponieważ każdy klucz może zostać wstawiony tylko raz. Aby wyświetlić różne liczby na liście, należy po prostu powtórzyć mapę.

Oto przykład tego, jak można to zrobić:

#include <cstddef> 
#include <map> 
#include <algorithm> 
#include <iostream> 

std::map<int, int> getOccurences(const int arr[], const std::size_t len) { 
    std::map<int, int> m; 
    for (std::size_t i = 0; i != len; ++i) { 
     m[arr[i]]++; 
    } 
    return m; 
} 

int main() { 
    int list[7]{1, 1, 1, 1, 2, 2, 2}; 
    auto occurences = getOccurences(list, 7); 
    for (auto e : occurences) { 
     std::cout << "Number " << e.first << " occurs "; 
     std::cout << e.second << " times" << std::endl; 
    } 
    auto average = std::accumulate(std::begin(list), std::end(list), 0.0)/7; 
    std::cout << "Average is " << average << std::endl; 
} 

wyjściowa:

Number 1 occurs 4 times 
Number 2 occurs 3 times 
Average is 1.42857 

Answer 4

oparciu o komentarz, wydaje trzeba znaleźć wartości, które występują najczęściej i jeśli nie są wielokrotne wartości występujące tyle samo razy, musisz wytworzyć ich średnią. Wydaje się, można to łatwo zrobić std::sort() brzmienie stwierdzenia przemierzania gdzie zmiana wartości i utrzymanie kilku liczy bieżących:

template <int Size> 
double mode(int const (&x)[Size]) { 
    std::vector<int> tmp(x, x + Size); 
    std::sort(tmp.begin(), tmp.end()); 
    int size(0); // size of the largest set so far 
    int count(0); // number of largest sets 
    double sum(0); // sum of largest sets 
    for (auto it(tmp.begin()); it != tmp.end();) { 
     auto end(std::upper_bound(it, tmp.end(), *it)); 
     if (size == std::distance(it, end)) { 
      sum += *it; 
      ++count; 
     } 
     else if (size < std::distance(it, end)) { 
      size = std::distance(it, end); 
      sum = *it; 
      count = 1; 
     } 
     it = end; 
    } 
    return sum/count; 
}