[Algorytmy] Najczęściej pojawiający się element

zuzka_kotek
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 23 lut 2016, o 20:45
Płeć: Kobieta
Lokalizacja: Gdańsk
Podziękował: 4 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: zuzka_kotek »

Dzień Dobry
Mam do zrobienia program, który działa na tablicy typu int z wartościami od -100 do 100 (losowymi), zaś ilość elementów mogę dowolnie wybierać. Jedna z funkcji, którą muszę napisać, ma za zadanie wyświetlić element najczęściej występujący oraz podać jej ilość. Tylko nie wiem jak mam się za to zabrać. Była bym wdzięczna za jakieś podpowiedzi.

Pozdrwiam
Ostatnio zmieniony 30 maja 2016, o 15:01 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: a4karo »

WYobraż sobie, że nie masz napisać funkcji, tylko ktoś Ci wysypał kupke owoców (jabłka, gruszki, pomarańcze i mandarynki) i kazał policzyć, których jest najwęcej. Jak się za to zabierzesz?
M Maciejewski
Użytkownik
Użytkownik
Posty: 318
Rejestracja: 14 maja 2016, o 16:25
Płeć: Mężczyzna
Lokalizacja: Toruń
Pomógł: 90 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: M Maciejewski »

Na początku mam 0 jabłek, 0 gruszek, 0 pomarańczy i 0 mandarynek (0,0,0,0).

Wyciągnąłem jabłko, zwiększam liczbę jabłek o 1 (1,0,0,0).
Wyciągnąłem mandarynkę, więc zwiększam liczbę mandarynek: (1,0,0,1).
Ooo, kolejna mandarynka, więc (1,0,0,2).

Na końcu: (5,4,9,7), a więc najwięcej mam pomarańczy (dziewięć).

To jest algorytm, który można zastosować w sytuacji, gdy liczba rodzajów elementów nie jest zbyt duża i jest a priori znana (tutaj mamy taką sytuację: od -100 do 100).
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: a4karo »

M Maciejewski pisze:Na początku mam 0 jabłek, 0 gruszek, 0 pomarańczy i 0 mandarynek (0,0,0,0).

Wyciągnąłem jabłko, zwiększam liczbę jabłek o 1 (1,0,0,0).
Wyciągnąłem mandarynkę, więc zwiększam liczbę mandarynek: (1,0,0,1).
Ooo, kolejna mandarynka, więc (1,0,0,2).

Na końcu: (5,4,9,7), a więc najwięcej mam pomarańczy (dziewięć).

To jest algorytm, który można zastosować w sytuacji, gdy liczba rodzajów elementów nie jest zbyt duża i jest a priori znana (tutaj mamy taką sytuację: od -100 do 100).

Brawo, ale to było zadanie dla autorki posta.
kalwi
Użytkownik
Użytkownik
Posty: 1931
Rejestracja: 29 maja 2009, o 11:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 320 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: kalwi »

Najwygodniej (ale niekoniecznie najszybciej) byłoby taką tablicę posortować (np. wbudowaną funkcją quicksqort - wiele języków ma ją w standardzie), i następnie zliczać wystąpienia i porównać. Proste w implementacji oraz dam głowę, że szybsze niż podejście M Maciejewski - gdyż w takim przypadku trzeba policzyć ile mamy unikalnych liczb, a następnie stworzyć tablicę o wielkości równej ich ilości.-- 30 maja 2016, o 18:21 --a tu gotowy i działający kod:

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int myComp(const void *, const void *);

int main()
{
    srand(time(NULL));
    int i, tab_size;
    printf("Ile elementow ma byc w tablicy: ");
    scanf("%d", &tab_size);
    int tab[tab_size];
    for(i = 0; i < tab_size; ++i)
        tab[i] = rand() % 200 - 100;
    qsort(tab, tab_size, sizeof(int), myComp);
    for(i = 0; i < tab_size; ++i)
        printf("%d ", tab[i]);
    int counter_cur = 0, counter_prev = 0;
    int prev_num, cur_num;
    int max_num = tab[0], amount_max = 0;
    prev_num = tab[0];
    
    for(i = 0; i < tab_size - 1; ++i)
    {
        if(tab[i] != tab[i + 1])
        {
            cur_num = tab[i + 1];
            if(counter_cur > counter_prev)
            {
                max_num = tab[i];
                amount_max = counter_cur;
            }
            counter_prev = counter_cur;
            counter_cur = 0;
        }
        else
            ++counter_cur;
    }
    printf("

Najwiecej razy (%d) wystapila liczba: %d

", amount_max + 1, max_num);
    return 0;
}

int myComp (const void *a, const void *b)
{
    int _a = *(int*)a;
    int _b = *(int*)b;
    if(_a < _b) return -1;
    else if(_a == _b) return 0;
    else return 1;
}
M Maciejewski
Użytkownik
Użytkownik
Posty: 318
Rejestracja: 14 maja 2016, o 16:25
Płeć: Mężczyzna
Lokalizacja: Toruń
Pomógł: 90 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: M Maciejewski »

a4karo pisze:Brawo, ale to było zadanie dla autorki posta.
Chyba za dużo podpowiedziałem, przepraszam.
kalwi pisze: Proste w implementacji oraz dam głowę, że szybsze niż podejście M Maciejewski - gdyż w takim przypadku trzeba policzyć ile mamy unikalnych liczb, a następnie stworzyć tablicę o wielkości równej ich ilości.
Jak napisałem, algorytm, który zaproponowałem jest efektywny wtedy, gdy liczba rodzajów elementów \(\displaystyle{ k}\) jest nieduża, wyraźnie mniejsza niż liczba elementów \(\displaystyle{ n}\) w tablicy (i te elementy są znane a priori, jak np. tutaj: liczby całkowite z przedziału [-100,100]). W tym przypadku jest z pewnością szybszy niż sortowanie o złożoności \(\displaystyle{ n\cdot \log n}\), ponieważ wystarczy raz przelecieć tablicę długości \(\displaystyle{ n}\), a potem raz przelecieć tablicę długości \(\displaystyle{ k}\). Jest to podobne do algorytmu sortowania przez zliczanie.

Tak więc ktoś traci głowę .

Jeśli jednak możliwych wartości jest bardzo dużo, są to np. wartości rzeczywiste, to ten algorytm z pewnością się nie sprawdzi.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: a4karo »

kalwi napisał ładny program, ale nie do tego zadania. A priori nie musimy z góry wiedzieć ile mamy elementów na wyjściu. Jedyne co wiemy, to że są to liczby całkowite z zakresu podanego.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: Afish »

Podpowiem, że da się to rozwiązać w oczekiwanym czasie liniowym od długości tablicy, niezależnie od zakresu czy rodzaju elementów.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: a4karo »

Koledzy, trochę opamiętania.
Koleżanka ma problem z napisaniem prostego algorytmu, a wy tu dyskutujecie o sortowaniu i optymalizacji.

Nie ten poziom... Jeszcze nie.
kalwi
Użytkownik
Użytkownik
Posty: 1931
Rejestracja: 29 maja 2009, o 11:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 320 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: kalwi »

To jeśli chcemy mieć rozwiązanie naiwne:
- masz tablicę tab o rozmiarze n z liczbami z zakresu od <-k;k>
- tworzysz tablicę array[2k+1] (+1, ponieważ jeszcze jest zero po środku), inicjalizujesz zerami (tutaj wygodnie byłoby użyć calloca)
- robisz pętle od i=0 do i<n i następnie co iterację zwiększasz ilość wystąpień danej liczby: ++array[tab[i]+k]

Następnie wyszukanie najczęściej powtarzającego się numeru:

Kod: Zaznacz cały

int counter = array[0]
int max = -k;
for(i = 0; i < 2k + 1; ++i)
     if(array[i] > counter)
     {
           counter = array[i];
           max = i-k;
     }
Złożoność czasowa: \(\displaystyle{ O(2n)}\) = \(\displaystyle{ O(n)}\) - jak mniemam właśnie ten algorytm miał na myśli Afish
Ostatnio zmieniony 2 cze 2016, o 10:19 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
M Maciejewski
Użytkownik
Użytkownik
Posty: 318
Rejestracja: 14 maja 2016, o 16:25
Płeć: Mężczyzna
Lokalizacja: Toruń
Pomógł: 90 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: M Maciejewski »

Kalwi, to jest dokładnie algorytm, który podałem.
kalwi pisze: Złożoność czasowa: O(2n) = O(n) - jak mniemam właśnie ten algorytm miał na myśli Afish
No właśnie wg mnie złożoność czasowa to \(\displaystyle{ O(n)+O(k)}\), więc jeśli \(\displaystyle{ k}\) jest duże (np maxlongint), to jest bieda. Ten algorytm jest super, gdy \(\displaystyle{ k}\) nie jest wielkie (stałe lub ograniczone przez \(\displaystyle{ n}\) i wtedy mamy faktycznie złożoność liniową. Afish pisze jednak:
Afish pisze: niezależnie od zakresu czy rodzaju elementów.
Jeśli chodzi o algorytm o złożoności liniowej, wyszukujący najczęściej pojawiający się element, ale bez żadnych ograniczeń, to ja znam jedynie wyszukujący element, który pojawia się więcej niż \(\displaystyle{ \frac{n}{2}}\) razy:

Kod: Zaznacz cały

kandydat=Tablica[0];
moc=1;
for k=1 to n:
{
jeśli Tablica[k]==kandydat, to moc++
w przeciwnym wypadku moc--
jeśli moc==0, to kandydat=Tablica[k]
}
return kandydat //wynik poprawny, jeśli faktycznie jest taki element, który pojawia się więcej, niż n/2 razy. W przeciwnym wypadku algorytm nie musi zwrócić najczęściej pojawiającego się elementu.
Ostatnio zmieniony 2 cze 2016, o 10:20 przez Afish, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: Afish »

kalwi pisze:Złożoność czasowa: \(\displaystyle{ O(2n)}\) = \(\displaystyle{ O(n)}\)
Jak już M Maciejewski podał, złożoność to \(\displaystyle{ O(n)+O(k)}\). Wyzerowanie tablicy wymaga przeiterowania po \(\displaystyle{ k}\) elementach.
kalwi pisze:jak mniemam właśnie ten algorytm miał na myśli Afish
Nie, nie o ten algorytm mi chodzi. Algorytm wspomniany przeze mnie wykorzystuje hashmapę do przechowywania liczników, stąd jego niska oczekiwana złożoność.
M Maciejewski
Użytkownik
Użytkownik
Posty: 318
Rejestracja: 14 maja 2016, o 16:25
Płeć: Mężczyzna
Lokalizacja: Toruń
Pomógł: 90 razy

[Algorytmy] Najczęściej pojawiający się element

Post autor: M Maciejewski »

Afish pisze:Algorytm wspomniany przeze mnie wykorzystuje hashmapę do przechowywania liczników, stąd jego niska oczekiwana złożoność.
Aaaacha. To ma sens.
ODPOWIEDZ